Версия 12:52, 11 октября 2016

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

Расписание лекций:
вторник 10:30 – 11:50, ауд. 509
пятница 15:10 – 16:30, ауд. 509

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

Программа дисциплины

Лекции

• 2 сентября. Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоклеточной машины с временем работы t(n) > n на одноленточной машине за время O(t(n)²). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов.

• 6 сентября. Полиномиальные сведения. NP-трудные и NP-полные задачи. Формулировка теоремы Кука – Левина. Сведение задачи 3SAT к задаче Not-All-Equal-3SAT.

• 9 сентября. Доказательство теоремы Кука – Левина. NP-полнота задачи 3SAT.

• 13 сентября. NP-полнота задач о сумме подмножества и о рюкзаке. Сведение Not-All-Equal-3SAT к задаче о максимальном разрезе.

• 16 сентября. Соотношение классов NP и EXPTIME. Теорема об иерархии задач по времени. Полиномиальная иерархия: классы Σ_kP и Π_kP.

• 20 сентября. Три подхода к решению NP-трудных задач: эффективные алгоритмы для частных случаев, эвристические алгоритмы, экспоненциальные алгоритмы, отличные от полного перебора. Точный алгоритм для поиска вершинного покрытия размера k в графе с m ребрами с временем работы O(2^km). Локальный поиск: градиентный спуск и алгоритма Метрополиса, применение к задаче о вершинном покрытии. Имитация отжига.

• 30 сентября. Приближенное решение задачи о максимальном разрезе. Эвристика Кернигана – Лина для определения соседних решений при поиске максимального разреза.

• 4 октября. Сегментация изображений на несколько классов. NP-трудность задачи сегментации изображений на три класса.

• 7 октября. Сегментация изображений на передний/задний план с помощью минимального разреза. Приближенный алгоритм сегментации изображений на несколько классов (без доказательства качества аппроксимации).

• 11 октября. Анализ приближенного алгоритма сегментации изображений на несколько классов. Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние.

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

Первое домашнее задание

Первое домашнее задание стоит из нескольких частей.

(1) Из первой части нужно решить все задачи. Если иное не сказано преподавателем, ведущим семинары, решение нужно прислать ему по электронной почте до вечера 14 сентября.

(2) Из второй части нужно решить одну задачу (какую именно, определяет преподаватель, ведущий семинары). Если иное не сказано преподавателем, ведущим семинары, решение нужно загрузить в anytask до вечера 23 сентября.

(3) Третью (и последнюю) часть первого домашнего задания нужно выполнить до вечера 11 октября.

Дано: неориентированный граф G = (V, E) без весов.

Найти: самый длинный простой путь в графе G.

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

Запрограммируйте на языке C++ алгоритм градиентного спуска, алгоритм Метрополиса без отжига и алгоритм Метрополиса с отжигом в применении к этой задаче. Проведите экспериментальное сравнение запрограммированных алгоритмов (с различными значениями параметров) по скорости и качеству найденного решения на случайных графах (и, при желании, на некоторых специальных графах или графах, возникающих из реальных данных). По результатам сравнения подготовьте небольшой отчет.

Разрешается использовать код из vertex_cover_lab.cpp. У преподавателей, ведущих практические занятия, могут быть особые требования к структуре кода и к отчету, которые будут объявлены на ближайшем практическом занятии.

Страницы семинаров

152-2

154-2

156-2

Учебные ассистенты

Антон Лебедев — группы 151 и 153

Юрий Мокрий — группа 152

Лев Пролеев — группы 154 и 156-2

Максим Ушаков — группы 155 и 156-1