[Кафедра дискретной математики]

Суффиксные деревья, алгоритмы построения и применение в словарных алгоритмах.
Суффиксные массивы, алгоритмы построения и применение в словарных алгоритмах.
Суффиксные автоматы, алгоритмы построения и применение в словарных алгоритмах.
Поиск палиндромов и периодичностей в словах с использованием суффиксных деревьев и массивов.

Коды, исправляющие ошибки: аддитивные, стирания, пакеты. Оценки мощности и скорости максимального кода, исправляющего независимые аддитивные ошибки. Теорема Шеннона о кодировании в двоичном симметричном канале.
Линейные коды. Проверочная и порождающая матрицы. Неравенство
Варшамова--Гилберта. Оценки размерности, скорости и минимального расстояния
линейных кодов, исправляющих независимые аддитивные ошибки.
Коды Хемминга. Коды Рида--Маллера. Алгоритм исправления ошибок кода Рида--Маллера.
Конечные поля. Кольцо многочленов. Разложение на неприводимые над $GF(q)$ множители двучлена $x^{q^m}-x$.
Минимальные многочлены. Структура конечного поля.
Циклические коды. Полиномиальные коды. Порождающий и проверочный многочлены. Неравенство Варшамова--Гилберта для полиномиальных кодов.
Коды Боуза--Чоудхури--Хоквингема. Алгоритм Питерсона--Горенстейна--Цирлера исправления ошибок в БЧХ-кодах.
Оценки размерности, скорости и минимального расстояния двоичных примитивных БЧХ-кодов. Коды Голея. Циклические коды Рида--Маллера.
Коды Рида-Соломона. Два определения кодов Рида-Соломона и их эквивалентность.
Алгоритм Гао исправления независимых аддитивных ошибок. Алгоритм исправления аддитивных ошибок и ошибок стирания.
Исправление аддитивных ошибок и ошибок стирания БЧХ-кодами.
Каскадные коды. Оценки размерности, скорости и минимального расстояния
каскадных кодов. Теорема Форни.

Оценки сложности схем ограниченной глубины. Лемма о переключении.
Оценки сложности схем в монотонном базисе. Лемма о подсолнухах.
Метод приближений.

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

Реализация булевых функций формулами, схемами, автоматами и машинами Тьюринга. Сложность функции.
Сложность систем линейных булевых функций.
Оценки сложности и глубины вычисления префиксных сумм.
Оценки сложности и глубины арифметических операций над целыми числами.
Оценки сложности быстрого преобразования Фурье и умножения многочленов. Асимптотические методы реализации булевых функций схемами и формулами.
Оценки сложности вычисления монотонных булевых функций.
Вычисления с ограниченной памятью.
Схемы на плоскости и их сложность (площадь).
Схемы в 3-х мерном пространстве и их сложность (объем).
Самокорректирующиеся схемы.
Моделирование схем автоматами и машинами Тьюринга.
Теорема Кука. NP-полные задачи.

Теорема Поста о конечной порожденности всех замкнутых классов булевых функций.
Описание решетки всех замкнутых классов булевых функций.
Предикатное описание замкнутых классов. Соответствие Галуа.
Классы частичных функций в P_2. Критерий полноты.