Теоретическая информатика 2 (алгоритмы)

Продолжение курса алгоритмов для студентов 1-го курса СПбГУ, обучающиxся по программе «математика», было прочитано А. Охотиным весной 2017 года. Вслед за курсом алгоритмов, Ф. В. Петров прочитал курс по комбинаторике; в расписании эти два курса в совокупности носят имя «теоретическая информатика-2».

Лекции по алгоритмам

  1. (13 февраля) Удаление в красно-чёрных деревьях (добавлено в конспект последней лекции осеннего семестра). Хэш-таблицы. Префиксное дерево. Поиск в строке: алгоритм Рабина–Карпа.
  2. (20 февраля) Алгоритм Кнута–Морриса–Пратта. Конечные автоматы, реализация алгоритма Кнута–Морриса–Пратта, алгоритм Ахо–Корасик. Суффиксные деревья.
  3. (27 февраля) Суффиксные деревья (окончание). Нахождение наибольшей общей подпоследовательности, алгоритм Хиршберга. Сжатие данных: RLE, Хаффман, арифметическое кодирование. (11 апреля: добавлена оценка времени работы алгоритма Хиршберга и существенно исправлена целочисленная реализация арифметического кодирования)
  4. (6 марта) Сжатие данных: LZ77, LZ78, LZW, BWT. Лес непересекающихся множеств, компоненты связности в неориентированном графе. Остовное дерево: алгоритм Крускала, алгоритм Прима. Поиск в глубину. (3 июня: исправлен LZ78, добавлены ссылки)
  5. (13 марта) Топологическая сортировка. Алгоритм Косараджу–Шарира для нахождения сильно связных компонентов. Вычислительная геометрия: нахождение ближайшей пары точек, нахождение выпуклой оболочки, нахождение самой отдалённой пары точек. Целочисленные алгоритмы: алгоритм Евклида, возведение в степень по модулю.
  6. (20 марта) Вероятностная проверка простоты числа: алгоритм Миллера–Рабина. Быстрое преобразование Фурье, его итеративная реализация. Последовательная свёртка. Понятие о сжатии звука и изображения с потерями. (3 июня: исправлена опечатка в теореме об алгоритме Миллера–Рабина)

Коллоквиум и экзамен

Коллоквиум прошёл в субботу, 15-го апреля. Перед коллоквиумом была консультация. Экзамен пройдёт 5-го и 6-го июня, с утра и до позднего вечера.

Литература по алгоритмам

E-mail: christian_name.family_name@spbu.ru.