Глубоко в Джунглях
Oct. 31st, 2009
03:24 am - Двухбуквенный шифр Фрэнсиса Бэкона
В 160х-м году Фрэнсис Бэкон (Francis Bacon, 1561 - 1626) разработал "двухбуквенный шифр". Очень простой: каждой букве латинского алфавита ставится в соответствие строчка из пяти букв a и b.
Вот так вот:
a AAAAA g AABBA n ABBAA t BAABA b AAAAB h AABBB o ABBAB u-v BAABB c AAABA i-j ABAAA p ABBBA w BABAA d AAABB k ABAAB q ABBBB x BABAB e AABAA l ABABA r BAAAA y BABBA f AABAB m ABABB s BAAAB z BABBBНесложно распознать здесь последовательные числа в двоичной системе счисления. Ну и понятно, что "буквы a и b" это просто обозначение для двух различимых сигналов. Мы бы сейчас написали 0 и 1, Морзе использовал точку и тире (Морзе смухлевал, у него ещё паузы разной длины, но это к делу не относится). Бэкону, конечно, это тоже было понятно.
Но это только половина идеи.
Вторая половина -- как передавать эти два различимых сигнала. Бэкон предложил передавать их при помощи различного шрифта.
Например, берём фразу:
Ребята, надо верить в чудеса. Когда-нибудь весенним утром ранним.Удаляем пробелы и знаки препинания, разбиваем на группы по пять букв:
Ребят анадо верит ьвчуд есаКо гдани будьв есенн имутр омран нимБуквам, набранным курсивом, ставим в соответствие b, обычным шрифтом - a.
Курсив слишком заметно отличается от обычного шрифта. У Бэкона было два довольно похожих шрифта, случайный читатель не заметил бы подвоха.
aabab baaaa aabaa aabaa aaaab baaab aaabb bbbbb bbbbb bbbbb bbbОтбрасываем хвост, состоящий из отсутствующих в таблице комбинаций, расшифровываем остальные:
freebsdА вы что думали -- Ассоль? :)
Чтобы прочитать сообщение, нужно смотреть не на то, что бросается в глаза, а на мелкие детали, и закономерности их появления. Смысл же "явного" сообщения не важен вообще (интересно, коррелирует ли это как-то с философскими взглядами Фрэнсиса Бэкона). Сейчас это называется стеганография. Причём, в отличии от "классических" средневеково-античных способов с невидимыми чернилами и бритыми рабами, Бэкон (ну, с некоторой натяжкой) применил очень современный: передачу значения в младших битах.
К сожалению, нигде не нашёл упоминаний об использовании этой системы на практике.
Зато вспомнил представителя этого самого взгляда на мир. Фрейд со своими оговорками явно думал в том же духе.
Ещё несколько ссылок:
Машинка для кодирования по Бэкону (генерирует последовательности из a-b, умеет расшифровывать их обратно).
Поиски шифра в текстах Шекспира. Очень забавная история, косвенно связанная с этим кодом. О том, что не все "закономерности в мелких деталях" одинаково полезны.
Кусочки из Бэкона с картинками. На картинках есть те самые шрифты.
Ещё пара мыслей о том, как можно закодировать два значения в тексте
Пока статью про Грея писал, случайно наткнулся, очередной раз поразился красоте идеи.
Oct. 29th, 2009
03:53 am - Код Грея
Обещанная умная статья по математике. Начинается она так:
Я еду к жене. Она еще не жена мне, но будет ею. Мне нужны алые паруса, чтобы
еще издали, как условлено с нею, она заметила нас. Вот и все. Как видите,
здесь нет ничего таинственного. И довольно об этом.
Александр Грин, «Алые паруса»
Представьте себе, что вы – молодой капитан Грей (не путать с Грэем! Та история уже рассказана, вы – другой капитан), уже знающий, что Ассоль сидит на берегу и смотрит вдаль и ждёт. Ушибленный на голову волшебник обещал ей принца, использующего такое двоичное представление чисел, что коды соседних чисел отличаются ровно на один бит.
Чего не сделаешь ради счастья любимой женщины – приходится придумывать.
Наложим несколько ограничений:
- Было бы здорово, если бы, имея n битов, мы могли бы закодировать все числа от 0 до 2n-1. Т.е. если у нас 8 бит, а код числа 5 ну ни как не влезает, это плохо. Даже если ни одна комбинация не пропадает, и какой-то 8-и битной соответствует число 1567 – всё равно плохо. Очень неудобно с практической точки зрения.
- При этом код числа не должен зависеть от того, сколько битов у нас есть. Ситуации, когда при 8-и доступных битах код числа 5 требует 6 битов, а при 32-х – 17 – хотелось бы избежать. Чтобы не приходилась каждый раз оговаривать, сколько битов есть. Пусть 5 всегда будет 5.
Кодировку, удовлетворяющую этим ограничениям, назовём вменяемой (это же математика! тут нельзя без строгой терминологии). Очевидный признак вменяемости:
- Код числа, меньшего 2n должен занимать не более чем n битов.
ПРИМЕЧАНИЕ
Т.е. для любого x и любого n, если x < 2n, код x не длиннее n. Длина кода – позиция старшего единичного разряда.
Отсюда сразу получаем:
- код 0 – 0000 (для него должно хватать 0 бит, ага)
- код 1 – 0001
- код 2 – 0011 (а как ещё изменить только 1 бит, остаться в пределах 2-х битов, и не повториться?)
- код 3 – 0010
- код 4 – 0110
А вот дальше могут быть варианты. А жаль, а то бы сразу раз – и всё построили.
продолжение
Тема, конечно, довольно известная, но вроде бы я залез в неё необычно глубоко.
Да, конечно, это абсолютно бессмысленно и бесполезно, но местами забавно; как обычно.
Комментарии и замечания приветствуются.
Jun. 28th, 2009
04:10 am - А теперь про школьное образование
Интереснейшая дискуссия очередной флейм со мной в главной роли (по количеству комментов) только что тихо умер.
( Список участников и краткое содержание )
Итак, собственно, что же говорит Маша.
Самое главное: ничего не изменится, пока в министерстве не начнут думать зачем нужно изучать тот или иной предмет. Они этого не делают совершенно.
В яблочко! Абсолютно очевидная постановка вопроса, и никаких даже следов обсуждения! О чем-то это говорит... Ну, т.е. это коррелирует с моими предыдущими двумя постами (три подряд про образование! Пора завязывать :)), но так явно [даже :)] я это не формулировал.
Нет цели. Хоть как-то очерченной. На первый взгляд это может показаться несущественным -- мол, физика и есть физика, какая разница, в чём цель, физика-то остаётся одна и та же? Учим физике чтобы был образованным!
Во-первых, ссылка на "чтобы был образованным" это ссылка в никуда. Непонятно ни что такое "образованный", ни зачем им быть.
Во-вторых, про физику не скажу, но математик много разных точно. И много способов её преподавать. Эта тема живо обсуждалась в помянутой дискуссии :) Там как минимум два варианта. Ещё есть смешной вариант. Ну и много чего ещё можно придумать.
Пример подобной переориентации, произошедшей на наших глазах: информатика эволюционировала от программирования до MS офиса. Изменилась цель -- изменилось направление.
Думаю, с физикой, биологией, географией, историей и т.п. та же фигня. В том смысле, что есть разные варианты и подходы. И текущий вариант не является само собой разумеющимся.
Нужно понимание чего хотим, куда стремимся. Зачем мучаем детей, кого хотим воспитать. Что такое человек, каким он должен быть :) Сложные вопросы, проще не отвечать и продолжать пихать в детей ту же программу потому что "так делали наши предки" и "советское образование было лучшим в мире". Но, дело в том, что его мы уже почти разрушили (об этом наглядно говорят результаты ЕГЭ) и надо в любом случае что-то новое создавать. И, мне кажется, даже приблизительные и не полные ответы могли бы сделать обучение гораздо более эффективным.
Upd: Немного о собственном опыте. Я иногда студентами балуюсь... :) На тему ассемблера x86.
Важнейшее, что я пытаюсь объяснить -- факт наличия внутренней логики. Мы изучаем систему, разработанную инженерами, у которых были задачи и ограничения. Исходя из задач и ограничений они поступили так-то и так-то. Т.е. это не совсем произвольные, не случайные решения. Помогает вопрос "как бы решили эту задачу Вы?" Но это когда времени много.
Я не знаю, насколько успешно я объясняю. Обычно я объясняю что-то студенту при сдаче отчёта по лабораторной, т.е. это как раз тот момент, когда надо было бы проверять :) И после моего объяснения проверять уже особо некогда. Но зато в такие моменты они очень внимательно слушают :) И у меня складывается ощущение, что что-то понимают.
Да, и важны здесь не знания конкретного процессора, а подход к изучению системы. Через цели, задачи и ресурсы-ограничения.
Jan. 26th, 2009
12:47 pm - Граждане умные,
.. подскажите, алгорифмы Маркова и неограниченные грамматики Хомского -- это одного и то же, с точностью до терминов? Или я проглядел что-то важное?
Upd: Вопрос, по видимому, закрыт. Пришли умные и меня переубедили :) Спасибо!
Jan. 20th, 2009
04:23 am
Наконец начал статью про КС-грамматики и парсеры.
Я в курсе, что про это не писал только ленивый. Но:
-- мне процесс важнее "практической полезности результата"
-- я думаю, у меня получится лучше :)
И как-то это непросто, так что, видимо, по мере продвижения будет несколько постов на эту тему. С надеждой, что умные люди подскажут.
Рассматриваем любимый всеми калькулятор. Грамматику на сложение-умножение можно записать так:
E --> T + E | T T --> I * T | I I --> (E) | number | name
Замечательная LL(1) грамматика, разбирается на ура, строит адекватное дерево, всё работает.
Дальше, понятно, почему вот такое:
E --> T + E | Т - E | T T --> I * T | I / T | I I --> (E) | number | name
работает плохо. Операции "бинарный минус" и "разделить" левоассоциативны, грамматика этого не учитывает, для выражения
2 - 1 + 1
она построит дерево
-
/ \
2 +
/ \
1 1А это не то, что нам нужно. Стандартный подход заключается в том, что грамматика переписывается в духе
E --> E + T | E - T | T T --> T * I | T / I | I I --> (E) | number | name
Получается совсем не LL(1) грамматика, и вроде даже вообще не LL. Разбирать её плохо. При написании парсера ручками, методом рекурсивного спуска, функции для разбора E и T пишут не "по грамматике", а "по пониманию".
Мне в голову пришёл несложный трюк, позволяющий сохранить LL(1). Для этого мы меняем язык, вводя две дополнительные унарные операции: минус и инверсию.
E --> T + E | Т - E | T T --> I * T | I / T | I I --> (E) | number | name | -I | %I
А встречая бинарный минус парсер преобразует его в бинарный плюс и унарный минус. Т.е.
2 - 1 + 1 = 2 + -1 + 1
и тут любое дерево нас устраивает, т.к. остались только ассоциативные операции. Аналогично с делением.
Внимание вопросы:
-- кто-то это придумал до меня? :), может даже есть специальное название? Или просто где-то описано? (я уверен, что тут я не первый, но интересны подробности..)
-- насколько это вообще нормально, что парсер в процессе работы меняет входной поток? Хотя в данном случае можно было это поручить отдельному препроцессору, т.к. замены на уровне регулярных выражений.
-- может какие-то комментарии? Что так не всё можно преобразовать я уже знаю...
Nov. 17th, 2008
07:52 pm - Это МатанализЪ
Ржал.
Для тех, кто ещё помнит...
Послушать проще всего вконтакте
Есть видео, но оно менее удачно, имхо
Текст
А вот и авторы
Да, там в конце одно матерное слово... раз 10 повторяется. Но оно очень уместно, надо сказать.
via ![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
sweater_judah
Nov. 2nd, 2008
05:36 am - Остаточные классы
Продолжаем выковыривать изюм из лекций. Самое красивое, интересное, бесполезное :) В этот раз речь про очень простой, очень красивый и неожиданный способ представления чисел, подававший большие надежды где-то в 60-х, но благополучно померший впоследствии: не смогли преодолеть критический недостаток. Но сама идея!
А идея такая:
- берём несколько взаимно простых чисел, для конкретности пусть их будет 3: p, q, g
- для любого числа x можно вычислить тройку остатков от деления: [x mod p], [x mod q], [x mod g]
- так как числа взаимно простые, остатки независимы, т.е. любому остатку от деления на p может соответствовать любой остаток от деления на q. Значит таких троек ровно pqg штук
- так как иксов от 0 до pqg (включая 0, исключая pqg) столько же, то более-менее понятно, что разным x в этом диапазоне соответствуют разные тройки. Т.е. можно установить взаимно-однозначное соответствие, а значит можно использовать тройку остатков для представления числа x.
Например, возьмём числа 5, 7, 9
5 * 7 * 9 = 315
42 --> 42 mod 5 / 42 mod 7 / 42 mod 9 = 2 / 0 / 6
126 --> 128 mod 5 / 128 mod 7 / 128 mod 9 = 3 / 2 / 2
На виндовом калькуляторе в "инженерном" режиме есть кнопка Mod, это оно.
Теперь вспоминаем свойства остатков:
(a + b) mod c = ([a mod c] + [b mod c]) mod c
(a * b) mod c = ([a mod c] * [b mod c]) mod c
то есть, сложение, вычитание, умножение можно производить по частям.
2 / 0 / 6 + 3 / 2 / 2 = 0 / 2 / 8
128 + 42 = 170 --> 170 mod 5 / 170 mod 7 / 170 mod 9 = 0 / 2 / 8 -- всё правильно
Для того, чтобы понять, почему это круто, нужно немного понимать как работают железки и немного знать, как устроены сумматоры и умножители. Именно для этого был написан предыдущий пост :)
Про умножители там ничего нет, но с ними всё так же, только гораздо хуже, в подробности вдаваться не будем.
Какие из него можно сделать выводы:
- Железо по своей природе работает параллельно, независимые части выполняются одновременно. Применительно к нашему случаю: все три остатка можно складывать/умножать одновременно.
- Чем меньше разрядов, тем быстрее сложение и умножение. Так как каждый остаток примерно в три раза короче "нормального" числа, сложение/умножение займёт примерно в три раза меньше времени.
Это прорыв!!
Но... К сожалению, операция деления за разумное время не реализуется, никак. И перевести число из вида a/b/c в какой-нибудь "обычный" -- очень сложно. А без этого использовать такие числа вряд ли кто-нибудь когда-нибудь будет. Вот так вот.
Upd: В обсуждении всплыло. Так же непонятно, как делать сравнение больше-меньше и проверку на переполнение при сложении/умножении.
Oct. 31st, 2008
08:13 pm - Числа
Здравствуйте, дети! Скажите, кто знает, что такое натуральные числа? Все! Ой как хорошо. А, скажите, кто может объяснить? Ты, Васенька? Ну давай. Гм, гм, "положительные целые числа", нет, не пойдёт. Тебе придётся объяснить, что такое "целые числа", а это сложнее. Ещё у кого есть версии? Количество яблок? Мне кажется, вы не понимаете, зачем нужно объяснять.
Натуральные числа это некоторые математические объекты, чтобы делать о них какие-то утверждения, вводить на них операции (сложение, умножение), нам нужно какое-то формальное определение. Иначе операция сложения останется такой же неформальной, на уровне "было две кучки яблок, сложили их в одну". И доказывать теоремы, в которых используется сложение, станет невозможно, это печально.
Да-да, вы совершенно верно вспомнили, что точки и прямые это неопределимые понятия. Но у нас есть аксиомы, задающие свойства, на которые можно опираться в доказательствах. Например, "через любые две точки на плоскости можно провести прямую и притом только одну". И т.п. Вот чего-нибудь такого хотелось бы.
Натуральные числа
О том, что такое натуральные числа нам всем рассказал Джузеппе Пеано (говорят, ударение на "а", ПеАно), книжка вышла в 1889 году. С тех пор его объяснение широко известно как аксиомы Пеано или "арифметика Пеано". В исходном варианте это выглядело так:( Про Пеаоно и его числа )
Дважды два -- четыре. Всё верно!
Изображения
Что же такое тогда: "0", "1", "2", ... "41", "42", "43", ...?( ? )
Операции над изображениями
Что такое сложение в столбик? Это алгоритм, получающий на вход две строки символов и выдающий на выход одну строку. Алгоритм работает в терминах изображений, символов, он ничего не знает об "истинных натуральных числах".Но в чём его суть: если есть числа n1 и n2, и изображающие их строки s1 и s2, то (s1 + s2) является изображением (n1 + n2). Это называется изоморфизм (если мне не изменяет память). Аналогично для других операторов.
Если это условие выполняется, то алгоритм сложения "правильный". Для разных видов изображений такие алгоритмы будут иметь разную сложность, с этой точки зрения изображения могут быть более или менее удобными для тех или иных применений.
Например, умножать римские числа ужасно. А русские числительные сложно даже складывать: надо сначала конвертировать в десятичные, потом складывать и конвертировать обратно.
Могут быть какие-то параметры для предпочтений: по используемым символам, по быстродействию... Что важно: это всё –- строки и алгоритмы над строками. Они все равнозначны и являются числами примерно в одинаковой степени.
Немного глубже всё немного хитрее. Функция S произвольна, она может принимать и возвращать в том числе и строки символов. Любые. Может -- десятичные числа. И это будет корректная функция и корректные числа. Вопрос в том, чтобы не останавливаться на одном варианте, и не приписывать числам свойства строк. Например, признак деления на 3 -- типичное свойство представления. Он не работает ни с шестнадцатеричными, ни с двоичными числами, не определён для русских числительных. А вот коммутативность сложения -- свойство общее.
Примерно так могла бы начинаться моя сегодняшняя лекция, если бы половину я не забыл, половину бы не сократил, не заменил бы 0 на 1... Ну и начало, которое курсивом, конечно, откуда-то из детского сада :) Никаких "детей" и "ой как хорошо" :) И даже фамилию "Пеано" вспомнили и как правильно произносится сказали. Дальше, правда, не вспомнили, ну должен же и я что-то рассказать. А вообще мне очень понравилось. Интересно, как студентам.
Sep. 18th, 2008
04:57 am - Наука vs. жизнь
Начнём с малого.
В эти выходные я в CSClub-е слушал лекции Александра Шеня по алгоритмической теории информации. Шень, конечно, страшный человек. Очень много знает, ужасно умный, потрясающе читает лекции, не пользуется дурацкими слайдами.. И физиономия у него -- довольная-довольная. В общем -- мечта, а не преподаватель.
Я честно пытался найти его отчество, пока безуспешно. Спрошу в субботу, если не постесняюсь. А вот ещё одна фотка.
В одном из перерывов, пребывая в лёгком шоке от рассказанного, я спросил его: "А это вообще как-то применяется на практике? А мы до этого дойдём?" Он сказал, что ответит на это всем сразу, и после перерыва действительно ответил (от первого лица, по памяти, как будет видео -- сверю):Есть такая теория, что математика применяется следующим образом: математик придумывает теорему, рассказывает её инженеру, инженер строит мост, если теорема правильная -- мост не падает. Если мост всё-таки падает... то инженер неправильно понял теорему, или не учёл условия применимости, или ещё что-то такое. Так вот, я считаю, что это в корне неверно. На мой взгляд, студент изучает, изучает свою математику... А потом бросает это дело и начинает зарабатывать деньги. А то, что он изучал математику помогает ему как-то лучше соображать, и именно в этом её основное практическое применение и польза.
И вот где-то тут я понял, что математиком я не являюсь и быть не хочу. А хочу быть инженером, но не простым, а умным, строить мосты которые не падают. И это серьёзный и неожиданный поворот в моих отношениях с математикой. Первый раз за последние пять лет я усомнился в собственном желании всё-таки поступить на матмех.
Я даже не буду спорить и пытаться что-то обосновать. Я обобщу и перейду к большому.
Совпадения это наше всё. Я бы не допёр до правильного обобщения, если бы заранее не подвернулись:
* дискуссия с Маусом и его сестрой
* гениальный пост А.Б.Покоя и мой ответ
А вопрос-то простой.
Икс чтобы жить или жить чтобы икс? При каких икс второй выбор -- допустим?
И где проходит грань между (1) и (2)? В диалоге с Маусом я противопоставлял понятия "жизнь" и "побег от жизни". Но эти понятия мягко говоря недоопределены. Что вообще такое жизнь, что -- побег от неё, на что стоит разменивать своё время, на что -- нет? На что-то же по-любому приходится, его не накопить. Свобода как вызов это очень круто, и я горжусь формулировкой (она чуть ниже, ссылка -- на контекст, без которого не понятно, что к чему). Но на практике это же будут какие-то обычные действия, которые с тем же успехом можно объявить побегом, пользуясь тем, что формальных отличий не существует.
Я -- не знаю. И единственное, на что могу полагаться -- на своё чувство баланса. И (возвращаясь к Шеню) в данном случае оно подсказывает мне, что уход в теорию-ради-теории это не наш выбор. Ну там, можно какие-нибудь причины придумать, типа того, что такая теория принципиально неопровержима, понятия "реальный мир" и "проверка на практике" просто не приложимы... Но это вторично, первично чувство. Ну и в остальных случаях оно тоже что-то там подсказывает.
Но оно, конечно, правильно работает только для меня.
Чувствуйте сами :)
Upd: а в эти выходные я, конечно, снова на него пойду :) Не пропускать же такого мужика только потому, что он читает не совсем то, что я хотел бы услышать :)
Upd2: В общем, не пошёл. Впрочем, наполовину случайно... Тем временем, А.Б.Покой продолжает жечь в созвучном направлении.
Sep. 15th, 2008
11:46 pm - Теория вычислений, программа, beta-1
Чему я буду учить детей весной, если дело выгорит (громко не ржать!):
( Вступительное слово )
Программа
| Лекций | Самостоятельно | |
| Конечные автоматы | ||
| 1. Детерминированные конечные автоматы. | ||
| 2. Недетерминированные конечные автоматы. | 2 | |
| 3. Преобразование НКА в ДКА | ||
| 4. Алгоритм минимизации ДКА. | 2 | 4 |
| Регулярные выражения | ||
| 5. Определение, основные свойства. | ||
| 6. Преобразование регулярного выражения в НКА | 2 | |
| 7. Стандартные расширения языка регулярных выражений. Утилиты grep, flex, регулярные выражения в Python. | 2 | |
| 8. Реализация лексического анализатора | ||
| 9. Лемма о накачке. | 2 | 4 |
| Контекстно-свободные грамматики | ||
| 10. Определение, основные свойства. | ||
| 11. Атрибутные грамматики | 2 | |
| 12. Алгоритм разбора рекурсивным спуском. | 2 | |
| 13. LL- и LR-грамматики, алгоритмы разбора. | 4 | |
| 14. Инструменты antlr и bison | 4 | |
| 15. Лемма о накачке для КС-грамматик | 4 | |
| Машины Тьюринга | ||
| 16. Определение, основные свойства, теоретическое значение. | ||
| 17. Варианты машин Тьюринга, преобразования между ними | 2 | |
| 18. Разрешимые, перечислимые, неперечислимые множества. Проблема останова. | 2 | |
| 19. Классы сложности P, NP, PSPACE. | 2 | 4 |
| Курсовой проект | 4 | 16 |
( Немного подробнее, тем же весёлым языком )
На данный момент половину программы я представляю себе довольно ясно, а половину - довольно смутно... К счастью, впереди ещё вся осень и почти вся зима. "Самостоятельно" - это домашние задания, пока планирую по штуке на раздел. Ну и курсовик, конечно. 4 часа лекций на курсовик - устроим публичную защиту.
Более подробного плана пока в природе не существует.
Мысли-предложения?
Aug. 22nd, 2008
04:53 am - Пирамиды
Когда-нибудь это будет маленькая но гордая статья, пока - так.
Пирамида это дерево. Не обязательно двоичное - любое. Листья и узлы это некие "элементы", на которых определены операции сравнения (<>=). И единственное условие на пирамиду - узел должен быть меньше-или-равен каждого из своих детей.
Очевидно, что минимальный элемент находится в корне дерева.
Очевидно, что вверх/вниз по любой из веток происходит уменьшение/увеличение элементов.
По английски такая структура данных называется heap, ну и сортировка - heapsort. Всем известно, что heap это куча. Но, в данном контектсте перевод "пирамида" неплохо подходит и более-менее устоялся.
( ..ну и что у них внутри?.. )
Aug. 6th, 2008
06:43 am - Криптографические хеш-функции -II
Коллизии это здорово, но обращать функции - гораздо круче. Особенно если в истинную веру. Как это эффективно сделать, в 1980 году придумал человек с говорящей фамилией Хеллман.
Мартин Хеллман, да, это тот самый Хеллман, который вместе с Диффи. Кстати, недавно смотрел забавный фильм про его молодость. Мужик зажигал! Но, став отцом, видимо, пересмотрел взгляды на жизнь и двинул в науку.
Компромисс время-память (Time-Memory trade-off)
Оригинальная статья: A Cryptanalytic Time - Memory Trade-OffЗадача
Мы заранее знаем функцию h. Мощность её множества значений обозначим N.Дано z: h(x) = z
x = ?
Решение "в лоб" требует O(N) попыток, это слишком много. Но, раз функция известна заранее, мы можем как-то подготовиться, что-нибудь такое вычислить и запомнить, а потом использовать... И опять, простое решение требует O(N) памяти и тоже не подходит.
( Трепещите, неверные )
В следующей серии - про то, чем настоящие функции отличаются от оракулов. Сорвём же покровы.
Есть подозрение, что следующая серия подзадержится эдак на месяц. Сорри, дела.
Jul. 27th, 2008
08:05 am - Криптографические хеш-функции -I
Конспективное изложение курса, прочитанного Ильёй Мироновым в CSClub-е 17-18-24-го мая 2008.
Что такое хеш-функции я знал довольно давно... И именно поэтому Илья произвёл на меня огромное впечатление: оказалось, что там внутри куча интересных деталей, о которых я как-то никогда не задумывался. Давно хотел написать, но всё недосуг было. Исправляюсь. Предупреждаю: сначала всё очень просто, а потом всё очень интересно :)
Вообще-то тут лежат видеозаписи лекций Ильи. Так что большого смысла в моём конспекте нет. Но, во-первых, я кое-чего от себя добавил :) Во-вторых, по печатному тексту понимать проще. Ну и, в-третьих, я всё равно в основном для себя писал :)
( Всё, что вы не хотели узнать про хеш-функции потому что не догадывались спросить. )
В следующем выпуске - чудеса обращения. Оставайтесь с нами!
Jul. 18th, 2007
04:21 am - Огрызки методички по ЦОС
Весной 2006, вместо честного зачёта-экзамена по ЦОС (цифровая обработка сигналов; digital signal processing), преподаватель (А.В.Лупин) предложил мне поучаствовать в написании методички (там всё запутано было, я возвращался из академки и этот курс вообще не слушал, но сдать был должен). Я и согласился :) Правда, довольно быстро выяснилось, что он от методички ждёт соовсем другого. Ему нужен был пересказ его же лекций, которые меня не очень устраивали... А я, как обычно, полез разбираться с основами.
В итоге, мы сошлись на тупой работе по перерисовыванию рисунков из конспекта с моей стороны (в Visio, с тех пор я его не очень люблю) и четвёрке с его, на чём и разошлись, не слишком довольные друг другом. А то, что я начал писать - осталось.
Что там есть полезного - внятное описание преобразования Фурье и быстрого преобразования Фурье. Внятное в том смысле, что широко известная формула не приводится, а выводится и обосновывается. Почему-то в доступных источниках мне ничего подобного не попадалось. Только в книжках по мат-анализу, но это же ещё догадаться надо распространить доказательство на дискретный случай... В общем, я как раз догадался :) Параллельно значительно вырос в собственных глазах - оказалось, что даже через столько лет умственного застоя способен воспринимать формулы с интегралами :))
Помимо этого, вроде бы, мне удалось достаточно строго и понятно ввести основные понятия ЦОС, что также не может не радовать.
Итак:
dsp.zip -- 122 Кб архив, внутри вордовский документ и несколько картинок.
ch01.pdf -- 344 Кб pdf-ник, за конвертацию спасибо oziro
Вряд ли я когда-нибудь закончу или продолжу, но, возможно, оно и так будет кому-то полезно.
Apr. 25th, 2006
03:11 pm - Духовно вырос
Теперь я знаю, что такое Быстрое Преобразование Фурье.
( Upd: Для тех, кому тоже интересно )