СПб.: Санкт-Петербургский государственный университет;
Санкт-Петербургский государственный университет;
Санкт-Петербургское отделение Математического института им.
В.А.Стеклова (ПОМИ) РАН, Гирш Э.А., 2003 г.
Курс лекций прочитан для студентов-математиков во втором семестре
первого года обучения в Санкт-Петербургском государственном
университете в 2003 г.
Теория формальных языков (I): языки, регулярные выражения и
грамматики; недетерминированные конечные автоматы.
Теория формальных языков (II): праволинейные грамматики, их эквивалентность регулярным выражениям, детерминированным и недетерминированным конечным автоматам; лемма о разрастании для них; свойства регулярных языков.
Теория формальных языков (III): бесконтекстные языки, лемма о разрастании для них, магазинные автоматы, проверка принадлежности бесконтектному языку.
Теория формальных языков (IV): рекурсивно-перечислимые языки, алгоритмическая неразрешимость.
Элементы теории сложности: классы P, NP, RP; NP-полные задачи; вероятностная проверка простоты числа.
Приближенные алгоритмы для задач о рюкзаке и коммивояжере.
Приближенные алгоритмы для задач о покрытии множествами и о кратчайшей общей надпоследовательности. Задача о подстроке. Поиск подстроки.
Алгоритм Шенхаге-Штрассена (часть I: сам алгоритм).
Алгоритм Шенхаге-Штрассена (часть II: вычисление дискретного преобразования Фурье (ДПФ) и оценка времени работы всего алгоритма).
Параллельные алгоритмы.
Предварительный список вопросов к зачету (по лекциям второго семестра).
Теория формальных языков (II): праволинейные грамматики, их эквивалентность регулярным выражениям, детерминированным и недетерминированным конечным автоматам; лемма о разрастании для них; свойства регулярных языков.
Теория формальных языков (III): бесконтекстные языки, лемма о разрастании для них, магазинные автоматы, проверка принадлежности бесконтектному языку.
Теория формальных языков (IV): рекурсивно-перечислимые языки, алгоритмическая неразрешимость.
Элементы теории сложности: классы P, NP, RP; NP-полные задачи; вероятностная проверка простоты числа.
Приближенные алгоритмы для задач о рюкзаке и коммивояжере.
Приближенные алгоритмы для задач о покрытии множествами и о кратчайшей общей надпоследовательности. Задача о подстроке. Поиск подстроки.
Алгоритм Шенхаге-Штрассена (часть I: сам алгоритм).
Алгоритм Шенхаге-Штрассена (часть II: вычисление дискретного преобразования Фурье (ДПФ) и оценка времени работы всего алгоритма).
Параллельные алгоритмы.
Предварительный список вопросов к зачету (по лекциям второго семестра).