zhChinese    enEnglish
  ПМ-ПУ  » Образование  » Программы курсов  » Факультативные » Конструктивная алгебра: алгоритмические основы обработки информации

Конструктивная алгебра: алгоритмические основы обработки информации

Факультативный курс для студентов 4 курса
При поддержке компании Digital Design

Лектор: д.ф.-м.н., проф. Утешев А.Ю.

Задачи учебной дисциплины. Изложить алгоритмические основы современных методов хранения информации (архивирование), контроля ее целостности при передаче по каналам связи и записи (помехоустойчивое кодирование, шифрование), а также ее распознавания (кластеризации). Проиллюстрировать применение современных пакетов аналитических вычислений для решения теоретических и практических задач вычислительной алгебры.

Актуальность курса: комментарий генерального директора Digital Design АНДРЕЯ ФЕДОРОВА

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

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

Программа курса

Введение
Теория информации. Избыточность, энтропия; сжатие данных, префиксные коды, коды Хаффмана; коды, исправляющие ошибки; шифрование.
Алгебраические основы
Начала теории целых чисел. Наибольший общий делитель (НОД). Алгоритм Евклида, теорема Ламе. Линейное представление НОД, континуанта. Делимость целых чисел, взаимно-простые числа, простые числа. Факторизация, метод Ферма. Функция Эйлера.
Модулярная арифметика. Сравнения. Вычисление $A^B (\mod M )$ — алгоритм квадрирования-умножения. Теоремы Ферма и Эйлера. Решение линейных сравнений. Китайская теорема об остатках.
Индекс (дискретный логарифм. Первообразный (примитивный) корень по модулю. Решение сравнений вида $x^n \equiv B ( \mod M )$.
Комплексные числа. Корни из единицы, первообразные корни из единицы.
Полином одной переменной. Схема Хорнера. Умножение полиномов — классические и быстрые алгоритмы. Приводимость и неприводимость полиномов над $Q$. Уравнения деления круга. Интерполяция. Матрица Вандермонда. Интерполяционный полином в форме Лагранжа. Тригонометрическая интерполяция.
Результант. Представление в детерминантной форме по методу Сильвестра и по методу Безу. Связь с НОД полиномов, тождество Безу. Преобразование Чирнгауза.
Криптография
История криптографии. Шифры Цезаря, Кардано, Виженера и скиталы.
Криптография открытых ключей. Односторонняя функция (с секретом). Алгоритмы RSA и ЭльГамаля построения ключей.
Алгоритмы проверки числа на простоту. Вероятностно-простые числа, псевдопростые числа, числа Кармайкла. Алгоритм Миллера-Рабина.
Криптоанализ. Факторизация — алгоритмы Полларда. Атака малых показателей.
Аутентификация. Функции хэширования. Атака парадокса дней рождения. Цифровая подпись.
Поля Галуа
Основы теории конечных полей. Бесконечные поля. Конечные поля, представление элемента в векторном, полиномиальном и матричном видах.
Умножение и обращение. Обобщенная теорема Ферма. Порядок элемента, примитивный элемент поля. Проблема обращения элемента в поле Галуа.
Полиномы над $GF(2)$. Разложение $x^{2^n} - x$. Неприводимые и примитивные полиномы. Полиномы над $GF(2^n)$.
Кодирование
Коды, исправляющие ошибки. Расстояние Хэмминга. Коды Адамара. Линейный код, порождающая и проверочная матрицы. Коды Хэмминга.
Циклические коды. Систематическое и несистематическое кодирование. Свёртка.
Коды Боуза-Чоудхури-Хоквингема. Коды Рида-Соломона. Математика RAID-6.
Быстрое преобразование Фурье
Дискретное преобразование Фурье. Интерполяция алгебраическая и тригонометрическая.
Быстрое преобразование Фурье.
Числовое преобразование Ферма. Алгоритм Шенхаге-Штрассена.
Применения быстрого преобразования Фурье и числового преобразования Ферма. Умножение полиномов и целых чисел. Циклическая свертка.

Материалы к курсу

Материалы к курсу находятся здесь

Литература

  1. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М. Мир. 1989
  2. Лидл Р., Нидеррайтер Г. Конечные поля. Том 1, том 2. М.Мир. 1988.
  3. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.Мир. 1976.
  4. Сэломон Д. Сжатие данных, зображений и звука. М.Техносфера. 2006.
  5. Утешев А.Ю., Черкасов Т.М., Шапошников А.А. Цифры и шифры.СПб. СПбГУ. 2001.
  6. Menezes A. J., van Oorschot P.C., Vanstone S.A. Handbook of Applied Cryptography. (5th ed.) 2001. CRC Press