Алгоритмы и структуры данных 2 2017/2018

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

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

Расписание лекций:
вторник 15:10 – 16:30, ауд. 622
пятница 10:30 – 11:50, ауд. 509
Дополнительная лекция — суббота 23 сентября 12:10 – 13:30, ауд. 622.

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

Ассистент: Максим Рябинин

Консультации:
суббота 16:40 – 18:00, ауд. 509.
Просьба информировать о необходимости проведения консультации заранее по почте.

Лекции

  • 5 сентября. Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоленточной машины с временем работы t(n) > n на одноленточной машине за время O(t(n)2). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов.
  • 8 сентября. Полиномиальные сведения. NP-трудные и NP-полные задачи. Формулировка теоремы Кука – Левина. Сведение задачи 3SAT к задаче Not-All-Equal-3SAT и задачи Not-All-Equal-3-SAT к задаче о максимальном разрезе.
  • 12 сентября. Доказательство теоремы Кука – Левина. NP-полнота задач 3SAT и MINESWEEPER.
  • 15 сентября. NP-полнота задач о сумме подмножества, рюкзаке, раскраске графа. Соотношение классов NP и EXPTIME.
  • 19 сентября. Теорема об иерархии задач по времени. Три подхода к решению NP-трудных задач: эффективные алгоритмы для частных случаев (пример — минимальное вершинное покрытие для дерева), эвристические алгоритмы (пример — 2-приближенный алгоритм поиска минимального вершинного покрытия), экспоненциальные алгоритмы, отличные от полного перебора (пример — алгоритм для поиска вершинного покрытия размера k в графе с m ребрами с временем работы O(2km).
  • 22 сентября. Локальный поиск: градиентный спуск, применение к задаче о вершинном покрытии. Приближенное решение задачи о максимальном разрезе. Эвристика Кернигана – Лина для определения соседних решений при поиске максимального разреза.
  • 26 сентября. Сегментация изображений на передний/задний план с помощью минимального разреза. Приближенный алгоритм сегментации изображений на несколько классов (без доказательства качества аппроксимации).
  • 29 сентября. Анализ приближенного алгоритма сегментации изображений на несколько классов. Алгоритм Метрополиса и имитация отжига.
  • 3 октября. Приближенный алгоритм кластеризации, минимизирующий максимальное расстояние до центра кластера. Невозможность лучшего приближения для этой задачи (если P ≠ NP). Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние. Приближенное решение задачи коммивояжера.
  • 6 октября. Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный и детерминированный алгоритмы для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ.

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

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


Страницы групп

группа 165-1