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

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

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

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

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

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

Лекции

  • 2 сентября. Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоленточной машины с временем работы t(n) > n на одноленточной машине за время O(t(n)2). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс 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(2km). Локальный поиск: градиентный спуск и алгоритм Метрополиса, применение к задаче о вершинном покрытии. Имитация отжига.
  • 30 сентября. Приближенное решение задачи о максимальном разрезе. Эвристика Кернигана – Лина для определения соседних решений при поиске максимального разреза.
  • 4 октября. Сегментация изображений на несколько классов. NP-трудность задачи сегментации изображений на три класса.
  • 7 октября. Сегментация изображений на передний/задний план с помощью минимального разреза. Приближенный алгоритм сегментации изображений на несколько классов (без доказательства качества аппроксимации).
  • 11 октября. Анализ приближенного алгоритма сегментации изображений на несколько классов. Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние.
  • 14 октября. NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние. Приближенный алгоритм кластеризации, минимизирующий максимальное внутрикластерное расстояние. Приближенное решение задачи коммивояжера.
  • 15 октября. Корректность 2-приближенного алгоритма кластеризации, минимизирующего максимальное внутрикластерное расстояние. Невозможность лучшего приближения для этой задачи. Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ.
  • 18 октября. Рандомизированный и детерминированный алгоритмы для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ. Потоковые алгоритмы. Алгоритм SpaceSaving для поиска частых элементов в потоке.
  • 21 октября. Алгоритм Count-Min Sketch для поиска частых элементов в потоке. Переборные алгоритмы. Полиномиальная задержка, инкрементальная (кумулятивная) полиномиальная задержка, оценка времени работы алгоритма относительно комбинированного размера входа и выхода. Перечисление всех путей между двумя заданными вершинами в графе. Перечисление всех максимальных клик графа.

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

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

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

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

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

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

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

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

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

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

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


Второе домашнее задание

  1. Предложите и реализуйте линейный алгоритм, вычисляющий паросочетание в произвольном неориентированном графе без весов, отличающееся по размеру от наибольшего (по размеру) паросочетания в этом графе не более, чем вдвое. Напомним, что паросочетанием называется подмножество ребер графа, в котором ни у каких двух ребер нет одинаковых вершин. Докажите корректность алгоритма. Формат входного файла: на первой строке — разделенные пробелом число вершин n и число ребер m, на каждой следующей из m строк — разделенные пробелом номера вершин очередного ребра (от 1 до n).
  2. Будем считать расстояние между двумя битовыми строками равным числу позиций, в которых значения битов у этих строк различаются. Например, расстояние между строками 10001 и 11011 равно двум, а между строками 10001 и 01010 — четырем. Требуется разбить заданный массив строк на максимально возможное число кластеров так, чтобы расстояние между строками из разных кластеров было не меньше трех. Например, для массива из файла b7x5.txt такое число равно двум. Ориентируйтесь на следующие параметры входных данных: в массиве 200 тыс. 32-битовых строк (пример). Предложите и реализуйте эффективный алгоритм, решающий эту задачу, докажите его корректность и оцените время работы. Формат входного файла: на первой строке — разделенные пробелом число битовых строк n и число бит в строке m; на каждой следующей из n строк — битовая строка, заданная последовательностью из m нулей и единиц (см. примеры по ссылкам выше). Алгоритм должен вычислять число кластеров, сами кластеры возвращать не нужно.


За теоретическое решение каждой задачи можно получить до четырех баллов. При наличии теоретического решения задачи за ее практическую реализацию можно получить еще до четырех баллов. Во второй задаче теоретическое решение без практической реализации засчитывается только, если предложенный алгоритм применим на практике к данным указанных размеров. Разумеется, оценка за все домашнее задание — не более десяти баллов.

Срок выполнения — вечер 22 октября.

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

152-2

154-2

156-2

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

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

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

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

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

Источник — «http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных_2_2016/2017&oldid=21408»