Версия 01:16, 17 октября 2018

Лектор: С. Объедков

Расписание лекций:
понедельник 12:10 – 13:30, ауд. 622
пятница 10:30 – 11:50, ауд. 622

Консультации:
понедельник 18:00 – 20:00, к. 324
четверг 16:30 – 18:00, к. 324

Ассистент: Игорь Минеев

Лекции

1. 7 сентября. Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоленточной машины с временем работы t(n) > n на одноленточной машине за время O(t(n)²). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов.
2. 10 сентября. Полиномиальные сведения. NP-трудные и NP-полные задачи. Теорема Кука – Левина.
3. 14 сентября. NP-полные задачи: 3SAT, Not-All-Equal-3SAT, о максимальном разрезе.
4. 17 сентября. Три подхода к решению NP-трудных задач (на примере задачи о вершинном покрытии): экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы, эффективные алгоритмы для частных случаев. Локальный поиск.
5. 21 сентября. Алгоритм Метрополиса и имитация отжига. Приближенное решение задачи о максимальном разрезе. Эвристика Кернигана – Лина для определения соседних решений при поиске максимального разреза.
6. 24 сентября. Сегментация изображений на передний/задний план с помощью минимального разреза. Сегментация изображений на несколько классов: приближенный алгоритм.
7. 28 сентября. Кластеризация. NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние; приближенный алгоритм и невозможность лучшего приближения для этой задачи (если P ≠ NP). Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние.
8. 5 октября. Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный и детерминированный алгоритмы для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ. Рандомизированный алгоритм для проверки выполнимости 2-КНФ.
9. 8 октября. Вероятностная машина Тьюринга. Класс сложности BPP. Рандомизированный алгоритм проверки числа на простоту.
10. 12 октября. Потоковые алгоритмы. Алгоритмы Count-Min Sketch и SpaceSaving для поиска частых элементов в потоке.
11. 19 октября. Разбор экзаменационных задач прошлого года.

Оценки

Накопленная оценка: 0,25 · оценка за первое домашнее задание + 0,25 · оценка за второе домашнее задание + 0,5 · оценка за аудиторную работу. Результирующая оценка: 0,6 · накопленная оценка + 0,4 · оценка за письменный экзамен

Таблицы с оценками

Аудиторная работа

Оценка за аудиторную работу складывается из следующих частей: 3 балла за письменный тест 28 сентября, по 1 баллу за каждый из трех наборов задач, по 1 баллу за каждое из четырех заданий на программирование. За каждый набор задач и каждое задание на программирование можно получить 1 балл. Дробные оценки не предусмотрены.

Письменный тест

Письменный тест состоится 28 сентября в 9:00 – 10:30. Группы 174-2, 175-1 и 176 пишут тест в ауд. 622, прочие группы — в аудиториях, указанных в расписании.

Задания на программирование

1. Конечные автоматы: контест до 30 сентября.
2. Сегментация изображений.
3. Кластеризация.
4. Можно сделать задание на поиск сообществ (на основе алгоритма поиска максимальных клик) или же получить дополнительный балл за активную работу на семинарах, задачу по сегментации или кластеризации (по согласованию с преподавателем, ведущим семинары).

Наборы задач

Нужно подготовить письменные решения всех задач и устно рассказать преподавателю решения некоторых задач в течение двух недель после выдачи набора задач.

1. P и NP
2. Полиномиальные сведения и NP-полные задачи
3. Алгоритмы решения трудных задач

Домашние задания

Первое домашнее задание: контест до 23:59 30 сентября.

Второе домашнее задание: контест до 23:59 18 октября.