Алгоритмы и структуры данных 2 2018/2019 — различия между версиями
.obj (обсуждение | вклад) (→Лекции) |
.obj (обсуждение | вклад) |
||
(не показаны 23 промежуточные версии этого же участника) | |||
Строка 16: | Строка 16: | ||
# '''14 сентября.''' NP-полные задачи: 3SAT, Not-All-Equal-3SAT, о максимальном разрезе. | # '''14 сентября.''' NP-полные задачи: 3SAT, Not-All-Equal-3SAT, о максимальном разрезе. | ||
# '''17 сентября.''' Три подхода к решению NP-трудных задач (на примере задачи о вершинном покрытии): экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы, эффективные алгоритмы для частных случаев. Локальный поиск. | # '''17 сентября.''' Три подхода к решению NP-трудных задач (на примере задачи о вершинном покрытии): экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы, эффективные алгоритмы для частных случаев. Локальный поиск. | ||
+ | # '''21 сентября.''' Алгоритм Метрополиса и имитация отжига. Приближенное решение задачи о максимальном разрезе. Эвристика Кернигана – Лина для определения соседних решений при поиске максимального разреза. | ||
+ | # '''24 сентября.''' Сегментация изображений на передний/задний план с помощью минимального разреза. Сегментация изображений на несколько классов: приближенный алгоритм. | ||
+ | # '''28 сентября.''' Кластеризация. NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние; приближенный алгоритм и невозможность лучшего приближения для этой задачи (если P ≠ NP). Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние. | ||
+ | # '''5 октября.''' Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный и детерминированный алгоритмы для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ. Рандомизированный алгоритм для проверки выполнимости 2-КНФ. | ||
+ | # '''8 октября.''' Вероятностная машина Тьюринга. Класс сложности BPP. Рандомизированный алгоритм проверки числа на простоту. | ||
+ | # '''12 октября.''' Потоковые алгоритмы. Алгоритмы Count-Min Sketch и SpaceSaving для поиска частых элементов в потоке. | ||
+ | # '''19 октября.''' Разбор [https://www.dropbox.com/s/f32cvbtds48fy2k/algo2exam2017.pdf?dl=0 экзаменационных задач прошлого года]. | ||
= Оценки = | = Оценки = | ||
Накопленная оценка: 0,25 · оценка за первое домашнее задание + 0,25 · оценка за второе домашнее задание + 0,5 · оценка за аудиторную работу. | Накопленная оценка: 0,25 · оценка за первое домашнее задание + 0,25 · оценка за второе домашнее задание + 0,5 · оценка за аудиторную работу. | ||
− | Результирующая оценка: 0,6 · накопленная оценка + 0,4 · оценка за письменный экзамен | + | Результирующая оценка: 0,6 · накопленная оценка + 0,4 · оценка за письменный экзамен |
+ | |||
+ | [https://docs.google.com/spreadsheets/d/1drGcL0VO9tXgcQGI5S0k_Mw7B-wMrX-k9ukoDdbt9mo/edit?usp=sharing Таблицы с оценками] | ||
= Аудиторная работа = | = Аудиторная работа = | ||
− | Оценка за аудиторную работу складывается из следующих частей: 3 балла за | + | Оценка за аудиторную работу складывается из следующих частей: 3 балла за письменный тест 28 сентября, по 1 баллу за каждый из трех наборов задач, по 1 баллу за каждое из четырех заданий на программирование. За каждый набор задач и каждое задание на программирование можно получить 1 балл. Дробные оценки не предусмотрены. |
+ | |||
+ | == Письменный тест == | ||
+ | Письменный тест состоится 28 сентября в 9:00 – 10:30. Группы 174-2, 175-1 и 176 пишут тест в ауд. 622, прочие группы — в аудиториях, указанных в расписании. | ||
==Задания на программирование== | ==Задания на программирование== | ||
# Конечные автоматы: [https://official.contest.yandex.ru/contest/8915 контест] до 30 сентября. | # Конечные автоматы: [https://official.contest.yandex.ru/contest/8915 контест] до 30 сентября. | ||
+ | # [[Алгоритмы_и_структуры_данных_2_2018/2019/segmentation | Сегментация изображений]]. | ||
+ | # [https://www.dropbox.com/s/ndv7ogo0rzmzxdp/task.zip?dl=0 Кластеризация]. | ||
+ | # Можно сделать задание на [[Алгоритмы_и_структуры_данных_2_2018/2019/communities | поиск сообществ]] (на основе алгоритма поиска максимальных клик) или же получить дополнительный балл за активную работу на семинарах, задачу по сегментации или кластеризации (по согласованию с преподавателем, ведущим семинары). | ||
==Наборы задач== | ==Наборы задач== | ||
Нужно подготовить письменные решения всех задач и устно рассказать преподавателю решения некоторых задач в течение двух недель после выдачи набора задач. | Нужно подготовить письменные решения всех задач и устно рассказать преподавателю решения некоторых задач в течение двух недель после выдачи набора задач. | ||
# [https://www.dropbox.com/s/fczhk8fwgkrwn1d/algo2-problems1.pdf?dl=0 P и NP] | # [https://www.dropbox.com/s/fczhk8fwgkrwn1d/algo2-problems1.pdf?dl=0 P и NP] | ||
+ | # [https://www.dropbox.com/s/cxtoxnu1mj9hkow/algo2-problems2.pdf?dl=0 Полиномиальные сведения и NP-полные задачи] | ||
+ | # [https://www.dropbox.com/s/nzv7xc14gtml5d3/algo2-problems3.pdf?dl=0 Алгоритмы решения трудных задач] | ||
= Домашние задания = | = Домашние задания = | ||
+ | Первое домашнее задание: [https://official.contest.yandex.ru/contest/9145 контест] до 23:59 30 сентября. | ||
+ | |||
+ | Второе домашнее задание: [https://official.contest.yandex.ru/contest/9407 контест] до 23:59 18 октября. | ||
+ | |||
+ | =Экзамен= | ||
+ | Экзамен пройдет 22 октября в 9:00 – 11:50 в ауд. 205 (группа 172), ауд. 317 (группы 174 и 175) и ауд. 402 (группа 176). Экзамен — письменный. С собой на экзамен можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. | ||
+ | |||
+ | Показ работ — 24 октября в 10:30 – 11:50 в ауд. 509. |
Текущая версия на 12:41, 21 октября 2018
Лектор: С. Объедков
Расписание лекций:
понедельник 12:10 – 13:30, ауд. 622
пятница 10:30 – 11:50, ауд. 622
Консультации:
понедельник 18:00 – 20:00, к. 324
четверг 16:30 – 18:00, к. 324
Ассистент: Игорь Минеев
Содержание
Лекции
- 7 сентября. Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоленточной машины с временем работы t(n) > n на одноленточной машине за время O(t(n)2). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов.
- 10 сентября. Полиномиальные сведения. NP-трудные и NP-полные задачи. Теорема Кука – Левина.
- 14 сентября. NP-полные задачи: 3SAT, Not-All-Equal-3SAT, о максимальном разрезе.
- 17 сентября. Три подхода к решению NP-трудных задач (на примере задачи о вершинном покрытии): экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы, эффективные алгоритмы для частных случаев. Локальный поиск.
- 21 сентября. Алгоритм Метрополиса и имитация отжига. Приближенное решение задачи о максимальном разрезе. Эвристика Кернигана – Лина для определения соседних решений при поиске максимального разреза.
- 24 сентября. Сегментация изображений на передний/задний план с помощью минимального разреза. Сегментация изображений на несколько классов: приближенный алгоритм.
- 28 сентября. Кластеризация. NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние; приближенный алгоритм и невозможность лучшего приближения для этой задачи (если P ≠ NP). Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние.
- 5 октября. Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный и детерминированный алгоритмы для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ. Рандомизированный алгоритм для проверки выполнимости 2-КНФ.
- 8 октября. Вероятностная машина Тьюринга. Класс сложности BPP. Рандомизированный алгоритм проверки числа на простоту.
- 12 октября. Потоковые алгоритмы. Алгоритмы Count-Min Sketch и SpaceSaving для поиска частых элементов в потоке.
- 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, прочие группы — в аудиториях, указанных в расписании.
Задания на программирование
- Конечные автоматы: контест до 30 сентября.
- Сегментация изображений.
- Кластеризация.
- Можно сделать задание на поиск сообществ (на основе алгоритма поиска максимальных клик) или же получить дополнительный балл за активную работу на семинарах, задачу по сегментации или кластеризации (по согласованию с преподавателем, ведущим семинары).
Наборы задач
Нужно подготовить письменные решения всех задач и устно рассказать преподавателю решения некоторых задач в течение двух недель после выдачи набора задач.
Домашние задания
Первое домашнее задание: контест до 23:59 30 сентября.
Второе домашнее задание: контест до 23:59 18 октября.
Экзамен
Экзамен пройдет 22 октября в 9:00 – 11:50 в ауд. 205 (группа 172), ауд. 317 (группы 174 и 175) и ауд. 402 (группа 176). Экзамен — письменный. С собой на экзамен можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается.
Показ работ — 24 октября в 10:30 – 11:50 в ауд. 509.