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