Алгоритмы и структуры данных 2 2017/2018 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
.obj (обсуждение | вклад) |
.obj (обсуждение | вклад) |
||
| (не показано 26 промежуточных версии 2 участников) | |||
| Строка 9: | Строка 9: | ||
понедельник 18:00 – 20:00, к. 324<br /> | понедельник 18:00 – 20:00, к. 324<br /> | ||
четверг 16:30 – 18:00, к. 324 | четверг 16:30 – 18:00, к. 324 | ||
| + | |||
| + | '''Ассистент:''' [mailto:mkryabinin@edu.hse.ru Максим Рябинин] | ||
| + | |||
| + | '''Консультации:'''<br /> | ||
| + | суббота 16:40 – 18:00, ауд. 509.<br /> | ||
| + | Просьба информировать о необходимости проведения консультации заранее по почте. | ||
| + | |||
| + | Консультация перед экзаменом: 21 октября, 10:30 – 11:50, ауд. 402. На консультации будет разобран [https://www.dropbox.com/s/jkn3r2v0yk588p7/algo2practice.pdf?dl=0 ряд задач]. | ||
= Лекции = | = Лекции = | ||
* '''5 сентября.''' Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоленточной машины с временем работы ''t''(''n'') > ''n'' на одноленточной машине за время ''O''(''t''(''n'')<sup>2</sup>). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов. | * '''5 сентября.''' Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоленточной машины с временем работы ''t''(''n'') > ''n'' на одноленточной машине за время ''O''(''t''(''n'')<sup>2</sup>). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс 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''(2<sup>''k''</sup>''m''). | ||
| + | * '''22 сентября.''' Локальный поиск: градиентный спуск, применение к задаче о вершинном покрытии. Приближенное решение задачи о максимальном разрезе. Эвристика Кернигана – Лина для определения соседних решений при поиске максимального разреза. | ||
| + | * '''26 сентября.''' Сегментация изображений на передний/задний план с помощью минимального разреза. Приближенный алгоритм сегментации изображений на несколько классов (без доказательства качества аппроксимации). | ||
| + | * '''29 сентября.''' Анализ приближенного алгоритма сегментации изображений на несколько классов. Алгоритм Метрополиса и имитация отжига. | ||
| + | * '''3 октября.''' Приближенный алгоритм кластеризации, минимизирующий максимальное расстояние до центра кластера. Невозможность лучшего приближения для этой задачи (если P ≠ NP). Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние. Приближенное решение задачи коммивояжера. | ||
| + | * '''6 октября.''' Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный и детерминированный алгоритмы для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ. | ||
| + | * '''10 октября.''' Рандомизированный алгоритм для проверки выполнимости 2-КНФ. Вероятностные структуры данных: фильтр Блума. | ||
| + | * '''13 октября.''' Потоковые алгоритмы. Алгоритмы Count-Min Sketch и SpaceSaving для [https://www.dropbox.com/s/phd3ngtj1vnp7kl/ch-p97-cormode.pdf?dl=0 поиска частых элементов в потоке]. | ||
| + | * '''20 октября.''' Переборные алгоритмы. Полиномиальная задержка, инкрементная полиномиальная задержка, оценка времени работы алгоритма относительно комбинированного размера входа и выхода. Перечисление всех путей между двумя заданными вершинами в графе. Перечисление всех максимальных клик графа. | ||
| − | == Страницы групп | + | = Домашние задания = |
| + | Первое домашнее задание: [https://official.contest.yandex.ru/contest/5166 контест] до 23:59 9 октября. | ||
| + | |||
| + | Второе домашнее задание: [https://official.contest.yandex.ru/contest/5422 контест] до '''10:00 22 октября.''' | ||
| + | |||
| + | = Страницы групп = | ||
[[Алгоритмы_и_структуры_данных_2_2016/2017/165-1 | группа 165-1]] | [[Алгоритмы_и_структуры_данных_2_2016/2017/165-1 | группа 165-1]] | ||
| + | |||
| + | = [https://docs.google.com/spreadsheets/d/1iSJH6Z2yQtioZK2XsjvQ-UlNOFPPjZ-eGETB8I-2iQ0/edit?usp=sharing Оценки] = | ||
Текущая версия на 15:34, 29 октября 2017
Лектор: С. Объедков
Расписание лекций:
вторник 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.
Просьба информировать о необходимости проведения консультации заранее по почте.
Консультация перед экзаменом: 21 октября, 10:30 – 11:50, ауд. 402. На консультации будет разобран ряд задач.
Содержание
Лекции
- 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-КНФ.
- 10 октября. Рандомизированный алгоритм для проверки выполнимости 2-КНФ. Вероятностные структуры данных: фильтр Блума.
- 13 октября. Потоковые алгоритмы. Алгоритмы Count-Min Sketch и SpaceSaving для поиска частых элементов в потоке.
- 20 октября. Переборные алгоритмы. Полиномиальная задержка, инкрементная полиномиальная задержка, оценка времени работы алгоритма относительно комбинированного размера входа и выхода. Перечисление всех путей между двумя заданными вершинами в графе. Перечисление всех максимальных клик графа.
Домашние задания
Первое домашнее задание: контест до 23:59 9 октября.
Второе домашнее задание: контест до 10:00 22 октября.
