Теоретическая информатика 1

Курс «теоретическая информатика-3», посвящённый началам дискретной математики и алгоритмов, был прочитан А. Охотиным осенью 2016 года студентам 1-го курса СПбГУ, обучающимся по программе «математика».

Лекции

  1. (5 сентября) Введение в ТИ. Машины Тьюринга. Множество, не распознаваемое никакой машиной Тьюринга.
  2. (12 сентября) Булевы функции, замкнутые классы, классы T0, T1, S, M, L, критерий функциональной полноты семейства функций.
  3. (19 сентября) Введение в графы. Эйлеровы пути и циклы.
  4. (26 сентября) Деревья. Перестановки, сочетания, числа Каталана. Формулы для числа сочетаний. Две формулы для чисел Каталана.
  5. (3 октября) Подсчёт числа деревьев. Планарные графы: формула Эйлера, графы K5 и K3,3, теорема о 5 красках, теорема о художественной галерее, теорема Фари (14 января: добавлена картинка про граф Петерсена)
  6. (10 октября) Паросочетания: Теорема Холла, доказательства индукцией по числу вершин и через увеличивающие пути. Паросочетания с предпочтениями. Теорема Татта, вывод теоремы Холла из неё.
  7. (17 октября) Теорема Петерсена, формула Татта–Бержа, теорема Кёнига, теорема Менгера, теорема Форда–Фалкерсона о наибольшем потоке и наименьшем сечении.
  8. (24 октября) Гамильтоновы циклы, теорема Брукса, раскраска рёбер, теорема Визинга.
  9. (31 октября) Числа Рамсея, верхняя оценка, нижняя оценка. Понятие о многоцветных числах Рамсея.
  10. (7 ноября) Машина с произвольным доступом к памяти, сортировка вставкой, сортировка слиянием, быстрое умножение.
  11. (14 ноября) Быстрое умножение матриц, умножение булевых матриц, оценка времени работы рекурсивных алгоритмов, нахождение всех кратчайших путей в графе.
  12. (21 ноября) Пути в графе: алгоритм Беллмана--Форда, алгоритм Дейкстры. Очередь с приоритетами. Куча. Сортировка кучей. "Быстрая сортировка".
  13. (28 ноября) Нижняя оценка числа сравнений при сортировке. Сортировка подсчётом, поразрядная сортировка. Динамическое программирование: задача о разделении стержня, задача о порядке умножения матриц. Двоичные деревья поиска: обход дерева..
  14. (5 декабря) Двоичные деревья поиска, операции над ними. АВЛ-деревья. Высота АВЛ-деревьев и числа Фибоначчи. Операции над АВЛ-деревьями. 2-3 деревья, операция вставки. (15 января: добавлены подробности про вращение в АВЛ-деревьях, исправлена ошибка в лемме о высоте АВЛ-дерева)
  15. (12 декабря) Операция удаления в 2-3 деревьях. 2-3-4-деревья. B-деревья. Красно-чёрные деревья, операция вставки.

Практические занятия

  1. Задачи к 14-му сентября.
  2. Задачи к 21-му сентября.
  3. Задачи к 28-му сентября.
  4. Задачи к 5-му октября.
  5. Задачи к 12-му октября.
  6. Задачи к 19-му октября.
  7. Задачи к 26-му октября.
  8. В среду, 2-го ноября, на 2-й и 4-й парах состоится проверочное собеседование по содержанию курса со всеми желающими студентами. По результатам будут начислены некоторые баллы, которые будут переданы начальству. Кроме того, студенты с хорошей суммой баллов будут освобождены от билета по дискретной математике на экзамене в январе. Список вопросов.

Дополнительная литература по дискретной математике

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

E-mail: