Базовый курс лекций для введения студентов в теоретическую информатику. Был проведен для студентов 1 курса МатМеха СПбГУ в 2002/03 учебном году.
| № |
Название лекции |
Конспект |
Тематика лекции |
| 1 |
Введение в предмет. Литература. |
- |
Примечание: лекция 1 отсутствует на сайте автора курса. |
| 2 |
Представление данных I |
 |
Очередь. Стек. Рекурсия. |
| 3 |
Представление данных II |
|
Heap Sort. Quick Sort. Поиск k-го элемента в массиве. |
| 4 |
Представление данных III |
|
Файлы. Сортировка на четырех лентах. Списки. Хеш-таблицы. Деревья. |
| 5 |
Алгоритмы на графах I |
|
Граф и его представление в машине. Поиск в глубину. Минимальное остовное дерево. |
| 6 |
Алгоритмы на графах II |
|
Нахождение кратчайших путей. Лексикографическая сортировка. Изоморфизм деревьев. Максимальный поток. |
| 7 |
Рисование планарного графа. Нахождение пары ближайших точек на плоскости |
|
Рисование планарного графа. Сложность рекурсивных алгоритмов. Умножение матриц (над кольцом и булевых). Нахождение пары ближайших точек на плоскости. |
| 8 |
Нахождение пары пересекающихся отрезков. Построение выпуклой оболочки |
|
Нахождение пары пересекающихся отрезков. Построение выпуклой оболочки. |
| 9 |
Теория формальных языков I |
|
Теория формальных языков (I): языки, регулярные выражения и грамматики; недетерминированные конечные автоматы. |
| 10 |
Теория формальных языков II |
|
Теория формальных языков (II): праволинейные грамматики, их эквивалентность регулярным выражениям, детерминированным и недетерминированным конечным автоматам; лемма о разрастании для них; свойства регулярных языков. |
| 11 |
Теория формальных языков III |
|
Теория формальных языков (III): бесконтекстные языки, лемма о разрастании для них, магазинные автоматы, проверка принадлежности бесконтектному языку. |
| 12 |
Теория формальных языков IV |
|
Теория формальных языков (IV): рекурсивно-перечислимые языки, алгоритмическая неразрешимость. |
| 13 |
Элементы теории сложности |
|
Элементы теории сложности: классы P, NP, RP; NP-полные задачи; вероятностная проверка простоты числа. |
| 14 |
Приближенные алгоритмы I |
|
Приближенные алгоритмы для задач о рюкзаке и коммивояжере. |
| 15 |
Приближенные алгоритмы II |
|
Приближенные алгоритмы для задач о покрытии множествами и о кратчайшей общей надпоследовательности. Поиск подстроки. |
| 16 |
Алгоритм Шенхаге-Штрассена I |
|
Алгоритм Шенхаге-Штрассена (часть I: сам алгоритм). |
| 17 |
Алгоритм Шенхаге-Штрассена II |
|
Алгоритм Шенхаге-Штрассена (часть II: вычисление ДПФ и оценка времени работы всего алгоритма). |
| 18 |
Параллельные алгоритмы |
|
Параллельные алгоритмы. |