Курс поддерживается группой

Комментарии для потенциальных слушателей

Мое личное мнение: курс с таким названием и соответствующим ему содержанием должен быть естественным окончанием¹⁾ программы обучения по Computer Science. Собственно, объяснение теоретических основ алгоритмов обработки информации. Не всем этот уровень знаний нужен — большинство программистов преспокойно обходятся самими алгоритмами («дайте нам спецификации, а уж мы вам их запрограммируем!»). $ \mathfrak{Jedem} $ $ \mathfrak{das} $ $ \mathfrak{ Seine} $: выбирайте по себе — «шпагу для дуэли, меч для битвы».

Материала много и он в некоторых местах сложный, даже очень сложный. Много математики — главным образом, алгебры; но и теорию вероятностей тоже приходится подтаскивать. Я стараюсь подстраиваться под уровень слушателей, но иногда могу лишь слегка облегчить перенапряжение их мозгов.

Уже выложенные материалы дадут представление чего ожидать. Но много чего еще не выложено, или выложено в полупереработанном мною (черновом) варианте. Приходится доделывать «на ходу». Не обессудьте!

Июнь 2012.

Теория информации. Энтропия, информация, избыточность. Сжатие данных, префиксные коды: Хаффмана и Шеннона-Фано. Код LZW. Теоремы Шеннона. Коды, исправляющие ошибки. Шифрование.

Начала теории целых чисел. Наибольший общий делитель ($ \operatorname{HOD} $). Алгоритм Евклида, теорема Ламе. Линейное представление $ \operatorname{HOD} $, континуанта. Делимость целых чисел, взаимно-простые числа, простые числа. Факторизация, метод Ферма. Функция Эйлера.

Модулярная арифметика. Сравнения. Вычисление $ A^B \pmod{M} $ — алгоритм квадрирования-умножения. Теоремы Ферма и Эйлера. Решение линейных сравнений. Китайская теорема об остатках.

Индекс (дискретный логарифм). Первообразный (примитивный) корень по модулю. Решение сравнений вида $ x^n \equiv B \pmod{M} $.

Комплексные числа. Корни из единицы, первообразные корни из единицы.

Полином одной переменной. Схема Хорнера. Умножение полиномов — классические и быстрые алгоритмы. Приводимость и неприводимость полиномов над $ \mathbb Q_{} $. Уравнения деления круга.

Интерполяция. Матрица Вандермонда. Интерполяционный полином в форме Лагранжа. Тригонометрическая интерполяция. Интерполяция при наличии систематических ошибок в таблице.

Результант. Представление в детерминантной форме по методу Сильвестра и по методу Безу. Связь с $ \operatorname{HOD} $ полиномов, тождество Безу. Преобразование Чирнгауза.

История криптографии. Шифры Цезаря, Кардано, Виженера и скиталы.

Криптография открытых ключей. Односторонняя функция (с секретом). Алгоритмы RSA и ЭльГамаля построения ключей.

Алгоритмы проверки числа на простоту. Вероятностно простые числа. Алгоритм Рабина-Миллера.

Криптоанализ. Факторизация — алгоритмы Полларда. Атака малых показателей.

Аутентификация. Функции хэширования. Атака парадокса дней рождения. Цифровая подпись.

Схема Шамира разделения секрета. Децентрализованный протокол голосования.

Основы теории конечных полей. Бесконечные поля. Конечные поля, представление элемента в векторном, полиномиальном и матричном видах.

Умножение и обращение. Обобщенная теорема Ферма. Порядок элемента, примитивный элемент поля. Проблема обращения элемента в поле Галуа.

Полиномы над $ \mathbf{GF}(2) $. Разложение $ x^{2^{n}} - x $. Неприводимые и примитивные полиномы. Полиномы над $ \mathbf{GF}(2^n) $.

Коды, исправляющие ошибки. Расстояние Хэмминга. Коды Адамара. Линейный код, порождающая и проверочная матрицы. Коды Хэмминга.

Циклические коды. Систематическое и несистематическое кодирование. Свёртка.

Коды Боуза-Чоудхури-Хоквингема. Коды Рида-Соломона. Математика RAID-6.

Дискретное преобразование Фурье. Интерполяция алгебраическая и тригонометрическая.

Быстрое преобразование Фурье.

преобразование Ферма. Алгоритм Шенхаге-Штрассена.

Применения быстрого преобразования Фурье и числового преобразования Ферма. Умножение полиномов и целых чисел. Циклическая свертка.

1. Коды Хаффмана и Шеннона-Фано.
2. $ \operatorname{HOD}(A,B) $ и линейное представление.
3. $ \phi(A) $
4. $ A^B \pmod{M} $ (со всевозможными упрощающими соображениями)
5. $ Ax\equiv B \pmod{M} $
6. $ A_1x\equiv B_1 \pmod{M_1},\dots,A_kx\equiv B_k \pmod{M_k} $
7. Индекс. $ x^n \equiv B \pmod{p} $
8. RSA схема выбора ключей; алгоритмы шифрования и цифровой подписи
9. Вероятностный алгоритм проверки простоты числа.
10. Код Хемминга.

☞ ЗДЕСЬ

☞ ЗДЕСЬ

Берлекэмп Э. Алгебраическая теория кодирования. М.Мир. 1971

Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М. Мир. 1989

Лидл Р., Нидеррайтер Г. Конечные поля. Том 1, том 2. М.Мир. 1988.

Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.Мир. 1976.

Сэломон Д. Сжатие данных, изображений и звука. М.Техносфера. 2006.

Утешев А.Ю., Черкасов Т.М., Шапошников А.А. Цифры и шифры.СПб. СПбГУ. 2001.

Menezes A. J., van Oorschot P.C., Vanstone S.A. Handbook of Applied Cryptography. (5th ed.) 2001. CRC Press

.

bc