Tags: математика

wall

(no subject)

Очень простую штуку объяснили, как-то мимо проходила.

В книжках про ассемблер и прочее такое пишут про "представление отрицательных чисел в дополнительном коде", и потом там у них особые правила сложения-умножения, обоснования, почему это работает и всё такое.

Так вот, это всё от математической безграмотности. Этот самый дополнительный код это в точности представление по модулю 2n.

Ну, -1 == 255 mod 256 -- и оно ровно так и получается двоично.

И остальные отрицательные тоже так же.

То есть мы просто всю дорогу оперируем с остатками, складываем их, вычитаем и умножаем по общим правилам (с делением хуже), а кто там из них представляет собой отрицательное число, а кто положительное, нам надо помнить
- при сравнении
- при делении
- если расширяем число, т.е. приводим к остатку по другому модулю, большему, чем исходный
- может ещё есть пара случаев, которые я забыл
wall

(no subject)

Наконец вроде осознал, когда и зачем аксиома выбора нужна, а когда она не нужна.

Если у нас есть одно непустое множество X и нам нужно взять какой-то элемент из него, мы можем формально написать ∀x∈X(...) и в скобках использовать этот x -- типа, "выбрали элемент".

Если у нас конечное заранее известное количество непустых множеств, можем проделать этот фокус нужное количество раз, и выбрать из каждого по элементу.

А вот если бесконечное, то увы (кажется, если заранее неизвестное, то тоже). Если у нас есть бесконечное семейство непустых множеств X и из каждого его элемента нужно выбрать по элементику (это не вполне конвенциальная терминология, но нужно же как-то разделять), нам нужна "функция выбора", сопоставляющая каждому элементу Х его элементик.

Тут нужно вспомнить, что такое "функция" в теории множеств. В теории множеств функция отождествляется со своим графиком, то есть это специальное множество пар. В данном случае

f := {(x,y)∈X×∪X| y∈x ∧ ... тут какое-то условие ...}

осталось написать "какое-то условие", чтобы это получилась именно функция, то есть чтобы каждому элементу X соответствовал ровно один элементик (это основное свойство функции: для каждого x f(x) должно быть определено однозначно).

Если наши множества какие-то хорошие, например, если каждое из них это множество натуральных чисел, это можно обеспечить. На натуральных есть порядок и есть теорема, что в любом множестве натуральных есть минимальный элемент, значит его всегда можно выбрать, вот и готова функция. Это будет выглядеть как-то так

f := {(x,y)∈X×∪X| y∈x ∧ ∀z∈x(y ≤ z)}

и никакая аксиома выбора не понадобилась, справились без неё.

Но если у нас какие-то произвольные множества, про которые мы может ничего не знаем, нам никакое такое условие в общем виде не записать. То есть явным образом предъявить функцию не получается.

Казалось бы, ну ёжику же понятно, что ну конечно такая функция должна быть, ну ничего же не мешает же! Но ёжика к делу не пришьешь, и тогда в отчаянии мы кастуем аксиому выбора: существует!

То есть, формально можно записать

∃f(f:X --> ∪X ∧ ∀u∈X(f(u) ∈ u))

И дальше её использовать.
wall

CRC-3: как его обойти

CRC не криптографически-стойкий алгоритм, он предназначен для обнаружения ошибок, вызванных неразумными обстоятельствами, а не разумным противником. В некоторых частных случаях оказывается ну очень просто изменить сообщение, сохранив значение CRC.

Collapse )

Collapse )

Collapse )

Collapse )

Всё! И на этом тему CRC закрываем.
wall

CRC-2: немного алгебры

Благодаря разговору с kodt_rsdn в прошлом посте, удалось переформулировать происходящее, добавив туда немного математического смысла.

Потому что сначала он там есть и очень явный -- просто вычисляем остаток от деления по несколько необычным правилам, а вот потом куда-то полностью пропадает.

... итак, допустим мы разобрались с арифметикой полиномов по модулю 2, и договорились, что значение CRC это остаток от деления дополненного нулями полинома-сообщения на порождающий полином конкретного алгоритма CRC.

Collapse )

Collapse )

Collapse )

Мне кажется, стало гораздо понятнее. Математика рулит!
wall

CRC

Очень вольный пересказ классического текста Ross N. Williams A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS, с лакунами, добавлениями, изменениями, попытками изложить лучше сложные места и пропустить простые. Вообще текст рекомендую, он очень милый и прекрасно написан, но некоторые места мне всё же было сложно понять, поэтому я подошел к ним иначе.

CRC это семейство алгоритмов для вычисления контрольной суммы, объединенных общей идеей, но отличающихся набором параметров.
Подробности того, как оно внутри устроены -- абсолютно бесполезное знание почти для всех почти всегда.
А мне просто было интересно.

Collapse )

Collapse )

Collapse )

Collapse )

Collapse )

Collapse )
wall

Код Хэмминга

Есть 10 типов людей: те, кто понимают двоичную систему счисления и те, кто нет.


Я несколько раз про него читал и вроде бы даже один раз делал. Но каждый раз это было как-то непросто. То есть воспринималось как некоторая (хотя и не слишком сложная) магия, которую надо в правильном порядке сделать и тогда -- крэкс-пэкс-фэкс -- получаем в синдроме номер ошибочного бита. Откуда он там? Ну как же, мы же вместе вычисляли, по формулам. Вот формулы, вот матрица преобразования -- там всё получается, можете проверить. Доктор, а откуда у вас такие формулы? А их придумал великий Хэмминг.

Richard Wesley Hamming, кстати, если и не великий, то выдающийся без дураков. Мало того, что он сам получил премию Тьюринга и проч., так ещё и имени его учреждена медаль. Вручается с 1988 за достижения в теории информации.

В общем, поскольку там всё действительно несложно, то продраться и на некоторое время усилием удержать в голове это было можно, но потом оно каждый раз ускользало. И только сегодня я случайно понял, что формулы и матрицы не просто так, а там есть мысль, простая как полено (но от этого не менее, а более красивая), отчего-то не осознанная мною ранее. Оказывается, достаточно правильно поставить задачу, пять минут подумать, как её решать, и сразу всё становится очевидно.

А обычно почему-то сразу кидаются рассказывать про матрицы, и в целом даже получается вроде бы ясно -- вот только не понятно.

Пришедшая мне в голову мысль структурировала изложение, но собственно изложена она ближе к концу, после введения в проблему. Введение совершенно общее, так или иначе написано везде, если когда-то про Хэмминга читали, можно смело пропускать.

Это правда просто, совсем просто, и даже формул почти не будет. Но вот двоичная система счисления понадобится, не без этого.

Collapse )
Collapse )

Тут можно пять минут подумать.

[Код Хэмминга: решение]Код Хэмминга: решение
Постановка, высказанная в такой форме оставляет на самом деле очень мало свободы для решения. Если заранее знать, что решение есть, то нужно просто идти вперед по единственному очевидному пути.

Давайте посмотрим на пример:

c0c11c2001c30110100

приемник это получил и вычислил свои контрольные биты

c'0c'1c'2c'3

Теперь, если в синдроме должен быть номер ошибочного бита, а сравнение c3 и c'3 отвечает за третий (считаем от 0) бит синдрома, то это сравнение должно сообщать о наличие/отсутствие ошибки в битах с номерами 8, 9, 10, .. 15. Просто потому, что если значение синдрома от 8 до 15, то в двоичной системе это от 10002 до 11112 и его третий (старший в данном случае) бит установлен в 1. Отсюда получаем:

c3 = d9 + d10 + d11 + d12 + d13 + d14 + d15

Если при передаче изменится значение бита 8 (это как раз сам c3), 9, 10 .. 15 (а эти участвуют в вычислении c3), то вычисленное на приёмнике таким же образом c'3 не совпадет и -- ура -- третий бит синдрома равен 1.

Аналогично можно выделить область ответственности остальных контрольных битов.

c2 = d5 + d6 + d7 + d12 + d13 + d14 + d15

Потому что это синдромы из диапазонов 01002 -- 01112 и 11002 -- 11112 -- и второй бит у них установлен в 1.

c1 = d3 + d6 + d7 + d10 + d11 + d14 + d15

Это синдромы 00102, 00112, 01102, 01112, 10102, 10112, 11102, 11112.

И наконец

c0 = d3 + d5 + d7 + d9 + d11 + d13 + d15

А это просто младший бит, т.е. все нечетные синдромы.
Обобщить этот пример и получить классический код Хэмминга довольно несложно.

Если по честному, то к ci относятся номера из диапазона [2i, 2i+1) и далее от такого же диапазона, смещенного на 2i+1, потом ещё на 2i+1 и т.п.
Если по хардкору, то можно даже как-то так: c[i] = sum(d[j] for j in range(i+1, n) if j & (1 << i)) % 2

Вот собственно и всё.


Теперь вы знаете, как работает код Хэмминга. Если же ещё хочется понять, какого черта о нём написано в википедии, читайте дальше.

[приложения: то же, но без сравнений; пример; матрицы; обобщение; несколько ошибок]
Appendix A: Отказываемся от сравнений
Мне кажется, со сравнениями понятнее, но в других местах это описывают без них, и определенный смысл в этом есть, так что надо как-то объяснить...

Выше была предложена следующая модель вычисления синдрома:
- по полученным данным приемник вычисляет свои контрольные биты c'0..c'k
- сравнивает их с полученными контрольными битами c0..ck
- если c'i != ci, то i-й бит синдрома si устанавливается в 1.

Первое, что тут можно упростить это собственно сравнение. Так как сложение по модулю 2 одинаковых значений дает 0, а разных -- 1, вместо сравнения можно написать

si = c'i + ci

Дальше, поскольку c'i вычисляется на приёмнике по формуле вида c'i = dk + dr + ... + dp, это выражение можно подставить и получить

si = ci + dk + dr + ... + dp

То есть, поскольку ci должен дополнять до четности биты dk, dr, ..., dp, бит si будет равен 1, если контроль четности не проходит, то есть, если некорректно передан либо один из битов dk, dr, ..., dp, либо сам бит ci. Это в точности то, что нам надо.

Appendix B: Пример
Ну, куда же без примера.

10010110100 -- исходные данные
сс1с001с0110100 -- напихали контрольных битов

c0c113c2050617c309110111012113014015 -- и все пронумеровали для ясности

Теперь вычисляем контрольные биты:
с3 = 09 + 110 + 111 + 012 + 113 + 014 + 015 = 3 = 1
с2 = 05 + 06 + 17 + 012 + 113 + 014 + 015 = 2 = 0
с1 = 13 + 06 + 17 + 110 + 111 + 014 + 015 = 4 = 0
с0 = 13 + 05 + 17 + 09 + 111 + 113 + 015 = 4 = 0

001000110110100 -- итого
001001110110100 -- изменим шестой бит

Заново вычисляем контрольные биты

с'3 = 09 + 110 + 111 + 012 + 113 + 014 + 015 = 3 = 1
с'2 = 05 + 16 + 17 + 012 + 113 + 014 + 015 = 3 = 1
с'1 = 13 + 16 + 17 + 110 + 111 + 014 + 015 = 5 = 1
с'0 = 13 + 05 + 17 + 09 + 111 + 113 + 015 = 4 = 0

В результате c'1 != c1 и c'2 != c2, то есть синдром равен 01102 = 6. Магия!

Appendix C: причем тут матрицы
Посмотрим на преобразование "туда", т.е. кодирование. На входе битовый вектор длины n, на выходе битовый вектор длины m, m > n (добавились контрольные биты). Каждый бит выходного вектора либо просто равен соответствующему биту входного, либо получается как линейная комбинация нескольких входных битов. Это выглядит как работа для матрицы!

Конечно, это можно так записать, взять матрицу m*n, умножить её на вектор длины n и получить закодированный вектор. Строки матрицы, соответствующие информационным битам содержат только одну 1, строки матрицы, соответствующие контрольным -- несколько единиц, те, которые нужны по формуле.

Теперь вычисление синдрома. На входе битовый вектор длины m, на выходе вектор длины m-n, и, как понятно после Приложения A, все биты выходного вектора и тут получаются как линейные комбинации входного. То есть это тоже работа для матрицы. И вот это будет как раз та матрица, которую везде рисуют.

Если изобразить зоны ответственности контрольных битов в виде таблички, она окажется примерно такой (такой, с точностью до перестановок строк):

c0c13c2567c39101112131415
ответственность с0++++++++
ответственность с1++++++++
ответственность с2++++++++
ответственность с3++++++++


теперь осталось заменить + на 1, а в пустые места поставить 0, и это будет в точности матрица, на которую нужно умножить полученный вектор, чтобы вычислить синдром.

Appendix D: обобщаем
На эту матрицу можно посмотреть с другой стороны. Каждый столбец соответствует одному биту вектора. При изменении этого бита окажутся затронуты -- то есть, равны 1 -- те биты синдрома, которые за него "отвечают". То есть, фактически, в столбце под битом номер i записан синдром, который мы получим при изменении этого бита.

И теперь можно раскрутить всё в обратную сторону!

a) Взять матрицу правильного размера, выбрать, где там будут контрольные биты, написать под каждым битом симпатичный синдром -- готово, это будет матрица получения синдрома.
b) По ней понять, что за формулы соответствуют контрольным битам. Этот пункт накладывает ограничения на предыдущий. Формулы для одних контрольных битов не должны включать другие контрольные биты, т.к. их нет в исходном векторе. Это значит, что соответствующий контрольному биту синдром должен состоять из одной единички -- его самого.
с) По ним уже, если хочется, можно сделать матрицу преобразования, тоже поставив в ней контрольные биты на выбранные места.

Ура, получили код с выбранными синдромами для каждого бита и выбранным же расположением контрольных. А если синдромы ещё и уникальны (для произвольной матрицы это не обязательное условие, что хотим, то и рисуем), то с помощью такого кода можно даже ошибки исправлять!

В общем, это не рокет сайнс, конечно, и вроде бы можно эту идею и сразу понять. Но почему-то у меня до сих пор "сразу" не получалось. А сейчас получилось :)

Appendix E: если ошибок больше
Понятно, что происходит, если ошибка не одна. Каждый изменившийся бит меняет те биты синдрома, которые отмечены в его столбце. Если битов изменилось несколько, в результате получится побитовая сумма соответствующих им синдромов. Если все синдромы в матрице уникальны, то никакие два при побитовой сумме не дадут 0, а значит двойную ошибку можно обнаружить, хотя и не исправить. Тройную уже не обязательно, как повезёт.

Обычно говорят, что код Хэмминга позволяет исправить одинарную и обнаружить двойную. Мне кажется, точнее было бы сказать "или". Потому что он не позволяет отличить двойную от одинарной, по синдрому не понятно, можем ли мы это исправить, или нет, это решение, которое нужно принять заранее: либо всё исправляем (и возможно попытаемся исправить лишнее), либо всё замечаем (и не исправляем даже то, что могли бы).

И, кстати, интересный нетривиальный результат: из соображений расстояния Хэмминга (я про это не писал тут, почитайте сами, там просто) возможен код, который умеет замечать одну и две ошибки, но не умеет исправлять, и он должен быть экономнее, чем код Хэмминга. Но при выбранном подходе не получается сэкономить и замечать две ошибки. Потому что если у нас в матрице есть два одинаковых столбца, то ошибка в этих двух битах даст нулевой синдром и мы её не обнаружим. А если все столбцы уникальные, то это аналог Хэмминга, мы уже можем и исправлять... То есть такой код должен строиться по каким-то другим принципам, он уже не может укладываться в линейные комбинации битов и матрицы.
wall

Периодические дроби

Это которые 0.33333...333.. -- и так всё время 3. Записывается обычно как 0.(3)

Мне про них рассказывали когда-то очень давно, классе в третьем-втором, и, по понятным причинам, рассказали не всё. А между тем, там есть один неожиданный момент.

То, что любая дробь вида q/p представляется в виде периодической, понять довольно просто. Надо делить в столбик и смотреть, что получается. Остается остаток от деления q на p,

[если хочется, в этом месте можно подумать самостоятельно]q = целая_часть * p + r1

Продолжаем деление, следующий шаг это

10*r1 = цифра * p + r2

Здесь можно считать, что "10" это "основание системы счисления", утверждение верно для двоичной, десятичной и т.п., лишь бы целым было.

Потом

10*r2 = цифра * p + r3
10*r3 = цифра * p + r4
10*r4 = цифра * p + r5

и так далее. ri это остатки от деления на p, их бывает всего p штук разных: 0, 1, 2, .. p-1. Если где-нибудь встретится 0, процесс на этом заканчивается, поделили. Значит, если у нас периодическая дробь, остатков всего p-1. Значит, не позднее чем через p-1 шагов они начнут повторяться. Поскольку значение остатка полностью определяет следующий остаток, повторяться будет целый цикл. Вот и периодическая дробь.


Но есть ещё и обратное утверждение: любая периодическая дробь это рациональное число. Интересно, какое. Вот например 0.(714285) это что за дробь? Понять это можно так:

0.(1) это 1/9 -- ну это все знают
0.(01) это 1/99 -- это несложно проверить
0.(0...01) это 1/9...99 -- а это несложно доказать

[доказательство]Ну правда, деля 1 на 9...99 мы будем получать 0 умножать остаток на 10, пока он не станет больше делителя. Тогда мы наконец сможем вычесть делитель, получим 1, остаток 1, и всё с начала.

Можно предположить, чему будет равна 0.(0...02) -- правильно, это будет 2/9...99. Эти дроби прекрасно можно складывать и умножать на целые, ну и в общем 0.(714285) это конечно 714285/999999. Ответ понятный, хотя и немного разочаровывающий.

Если период начинается не сразу, надо поделить на 10. Например 0.0(01) = 0.(01) / 10 = 1/990. Т.е. количество девяток задает длину повторяющейся части, не повторяющийся префикс нужно учитывать отдельно. Если в этом префиксе не 0, например 0.2(01) это будет 2/10 + 1/990 = 2*99/990 + 1/990 = 199/990. В общем, дроби-с-префиксом тоже представляются в таком виде.

Но чуть выше мы доказали, что как периодическую можно представить любую дробь, не обязательно только с девятками в знаменателе. Вместе эти два утверждения означают, что любую дробь вида q/p можно представить в виде x/99..990..00. Это значит, что для любого натурального p найдется нужное количество девяток и нулей, такое, что 99..990..0 делится на p нацело.

Дальше я пошел по сложному пути, см. в комментах более простое объяснение этого факта от avsmal, спасибо ему.

Утверждение нетривиальное, проще всего разобраться с нулями. Их нужно столько, сколько в разложении p на простые встречается двоек или пятерок -- максимальное из двух. Это понятно, нули больше ничего не добавляют. Тогда получаем такое утверждение: для любого p, которое не делится на 5 и 2, найдется такое число 9...99, что оно делится на p.

Всё ещё не понятно, с чего бы это вдруг. Чтобы разобраться, надо посмотреть немного с более общей точки зрения. Вместо "9...99 делится на p" можно рассмотреть равносильное "10..00 при делении на p дает остаток 1". В доказательстве не было ничего специфичного для десятичной системы счисления, так что утверждение более общее. То есть, примерно так: если у p и g нет общих делителей, то существует такое n, что gn = 1 mod p. А вот это уже понятно почему, это по теореме Эйлера, и даже можно назвать, чему равно n.

Кстати, 0.(714285) это 5/7.
wall

Где спрятать лист

Писал когда-то про диагональную конструкцию Кантора, там от простого примера к более абстрактному один и тот же прием прослеживается. Внезапно ещё одна теорема из теории множеств проясняется похожим методом -- теорема Кантора-Бернштейна-Шредера.

Мощность
Мощность множества это обобщение понятия "количество элементов". Когда элементов становится бесконечно много, говорить о "количестве" уже не очень получается и нужно что-то придумывать. Вот, в частности придумали, как сказать, что у двух бесконечных множеств "равное количество" элементов:

Два множества называются равномощными, если существует взаимно однозначное отображение (биекция) между ними.

То есть, если их элементы можно разбить на парочки, так чтобы при этом никто не остался обиженным. Это сравнение через обобщение принципа Дирихле, про голубей и клетки, и для конечных множеств это будет в точности он. Но с конечными множествами слишком просто, с ними, если сажать по одному голубю в клетку, как ни сажай, результат не изменится: либо количество равное, либо нет.

С бесконечными множествами все гораздо интереснее, там становится важным слово существует. Потому что одновременно для одних и тех же двух множеств могут существовать как отображения, в которых не хватает голубей, так и те, которым не хватает клеток, и это ничему не мешает и к делу не относится. Вопрос только в том, существует ли такое, где всем всего хватает.

Например, понятно, что множество натуральных чисел {1,2,3,4,5,...} равномощно множеству квадратов натуральных чисел {1,4,9,16,25,...} . Биекция очевидная: число однозначно соответствует своему квадрату. Всё честно, определению удовлетворяет.

Но при этом же понятно, что квадратов "меньше" чем просто чисел, так как вон сколько мы пропустили: 2, 3, 5, 6 -- бесконечно много чисел пропустили, как же так. Осталось много голубей. С другой стороны, можно сделать так, что останется много клеток: сопоставить число и его квадрат, умноженный на 4. Все числа рассадим по клеткам и при этом ещё и половина клеток пустая окажется.

То есть, вроде бы результаты противоречивые, но на самом деле это совсем не важно. Важно, есть ли биекция. То, что есть много не устраивающих нас способов рассадить к делу не относится. Как выяснится немного дальше, если бы биекции не было, всегда не хватало бы только чего-то одного.


Простой пример
Множество N = {1,2,3,4, ...} и множество N' = {2,3,4,5, ...}. В множестве N одна лишняя точка, но это не проблема, биекцию можно сразу же предъявить: f: n --> n+1.

Тривиально, не стоило даже и писать, правда?

Пример посложнее
Полуинтервал (0, 1] и интервал (0, 1). Множества почти идентичны, вроде бы и делать ничего не надо, но в полуинтервале одна лишняя точка. Предыдущий пример подсказывает, как с ней можно поступить Collapse )

Теорема Кантора-Бернштейна-Шредера - 2
Ну и последний шаг, раз уж начали: почему из доказанного собственно следует искомая теорема.

X равномощно некоторому X' ⊂ Y, значит есть биекция f: X --> X'
Y равномощно некоторому Y' ⊂ X, значит есть биекция g: Y --> Y'

g(X') = X'' ⊂ Y' ⊂ X
И композиция f и g функция gf: X --> X'' это биекция

То есть пришли к начальным условиям доказанной выше теоремы: X'' ⊂ Y' ⊂ X и X равномощно X''. Отсюда, по доказанному, X равномощно Y', а значит и Y тоже. Что и требовалось доказать.

Теперь можно посмотреть доказательство в википедии и плакать, плакать от того, что всё равно ничерта не понятно может быть, зная суть, удастся что-то разобрать в этой последовательности значков.
wall

(no subject)

Шеннон (в той самой статье) описывает, как он построил примеры случайных последовательностей в 1948-м году без компьютера. Последовательности такие:

(1) равномерно распределённых английских букв с пробелом
(2) букв с правильными индивидуальными частотами (т.е. как в обычном английском тексте)
(3) с правильными частотами биграмм
(4) правильными частотами триграмм
(5) слов с правильными индивидуальными частотами
(6) слова с правильными вероятностями пар слов

Это просто примеры, так что они не очень длинные: 50-100 букв, 30-45 слов. Помимо того что есть всегда, доступны таблицы частот и книги случайных чисел (занимательные должно быть!).

В чём трудность. Чтобы строить биграммы тривиальным способом по буквам, нужно 27 таблиц условных вероятностей (27 == алфавит + пробел). Вроде обозримо, особенно если таблицы уже есть. Но чтобы строить триграммы, таких таблиц нужно уже 729. Для того чтобы привести пример в статье это кажется несколько избыточно. Со словами всё ещё хуже, таблицу условных вероятностей для слов даже представить страшно. Да даже просто частот слов.

Collapse )