https://wikicshse.ru/index.php?action=history&feed=atom&title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_2_2018%2F2019Алгоритмы и структуры данных 2 2018/2019 - История изменений2026-06-06T16:01:22ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://wikicshse.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B8_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_2_2018/2019&diff=929&oldid=previmported>.obj: Migrated current public revision from wiki.cs.hse.ru2018-10-21T09:41:42Z<p>Migrated current public revision from wiki.cs.hse.ru</p>
<p><b>Новая страница</b></p><div>'''Лектор:''' [http://www.hse.ru/staff/obiedkov С. Объедков]<br />
<br />
'''Расписание лекций:'''<br/><br />
понедельник 12:10 – 13:30, ауд. 622<br /><br />
пятница 10:30 – 11:50, ауд. 622<br /><br />
<br />
'''Консультации:'''<br/><br />
понедельник 18:00 – 20:00, к. 324<br /><br />
четверг 16:30 – 18:00, к. 324<br />
<br />
'''Ассистент:''' [mailto:iemineev@edu.hse.ru Игорь Минеев]<br />
<br />
= Лекции =<br />
# '''7 сентября.''' Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоленточной машины с временем работы ''t''(''n'') > ''n'' на одноленточной машине за время ''O''(''t''(''n'')<sup>2</sup>). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов.<br />
# '''10 сентября.''' Полиномиальные сведения. NP-трудные и NP-полные задачи. Теорема Кука – Левина.<br />
# '''14 сентября.''' NP-полные задачи: 3SAT, Not-All-Equal-3SAT, о максимальном разрезе.<br />
# '''17 сентября.''' Три подхода к решению NP-трудных задач (на примере задачи о вершинном покрытии): экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы, эффективные алгоритмы для частных случаев. Локальный поиск.<br />
# '''21 сентября.''' Алгоритм Метрополиса и имитация отжига. Приближенное решение задачи о максимальном разрезе. Эвристика Кернигана – Лина для определения соседних решений при поиске максимального разреза.<br />
# '''24 сентября.''' Сегментация изображений на передний/задний план с помощью минимального разреза. Сегментация изображений на несколько классов: приближенный алгоритм.<br />
# '''28 сентября.''' Кластеризация. NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние; приближенный алгоритм и невозможность лучшего приближения для этой задачи (если P ≠ NP). Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние.<br />
# '''5 октября.''' Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный и детерминированный алгоритмы для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ. Рандомизированный алгоритм для проверки выполнимости 2-КНФ.<br />
# '''8 октября.''' Вероятностная машина Тьюринга. Класс сложности BPP. Рандомизированный алгоритм проверки числа на простоту.<br />
# '''12 октября.''' Потоковые алгоритмы. Алгоритмы Count-Min Sketch и SpaceSaving для поиска частых элементов в потоке.<br />
# '''19 октября.''' Разбор [https://www.dropbox.com/s/f32cvbtds48fy2k/algo2exam2017.pdf?dl=0 экзаменационных задач прошлого года].<br />
<br />
= Оценки =<br />
Накопленная оценка: 0,25 · оценка за первое домашнее задание + 0,25 · оценка за второе домашнее задание + 0,5 · оценка за аудиторную работу. <br />
Результирующая оценка: 0,6 · накопленная оценка + 0,4 · оценка за письменный экзамен<br />
<br />
[https://docs.google.com/spreadsheets/d/1drGcL0VO9tXgcQGI5S0k_Mw7B-wMrX-k9ukoDdbt9mo/edit?usp=sharing Таблицы с оценками]<br />
<br />
= Аудиторная работа =<br />
<br />
Оценка за аудиторную работу складывается из следующих частей: 3 балла за письменный тест 28 сентября, по 1 баллу за каждый из трех наборов задач, по 1 баллу за каждое из четырех заданий на программирование. За каждый набор задач и каждое задание на программирование можно получить 1 балл. Дробные оценки не предусмотрены.<br />
<br />
== Письменный тест ==<br />
Письменный тест состоится 28 сентября в 9:00 – 10:30. Группы 174-2, 175-1 и 176 пишут тест в ауд. 622, прочие группы — в аудиториях, указанных в расписании.<br />
<br />
==Задания на программирование==<br />
# Конечные автоматы: [https://official.contest.yandex.ru/contest/8915 контест] до 30 сентября.<br />
# [[Алгоритмы_и_структуры_данных_2_2018/2019/segmentation | Сегментация изображений]].<br />
# [https://www.dropbox.com/s/ndv7ogo0rzmzxdp/task.zip?dl=0 Кластеризация].<br />
# Можно сделать задание на [[Алгоритмы_и_структуры_данных_2_2018/2019/communities | поиск сообществ]] (на основе алгоритма поиска максимальных клик) или же получить дополнительный балл за активную работу на семинарах, задачу по сегментации или кластеризации (по согласованию с преподавателем, ведущим семинары).<br />
<br />
==Наборы задач==<br />
Нужно подготовить письменные решения всех задач и устно рассказать преподавателю решения некоторых задач в течение двух недель после выдачи набора задач.<br />
# [https://www.dropbox.com/s/fczhk8fwgkrwn1d/algo2-problems1.pdf?dl=0 P и NP]<br />
# [https://www.dropbox.com/s/cxtoxnu1mj9hkow/algo2-problems2.pdf?dl=0 Полиномиальные сведения и NP-полные задачи]<br />
# [https://www.dropbox.com/s/nzv7xc14gtml5d3/algo2-problems3.pdf?dl=0 Алгоритмы решения трудных задач]<br />
<br />
= Домашние задания =<br />
Первое домашнее задание: [https://official.contest.yandex.ru/contest/9145 контест] до 23:59 30 сентября.<br />
<br />
Второе домашнее задание: [https://official.contest.yandex.ru/contest/9407 контест] до 23:59 18 октября.<br />
<br />
=Экзамен=<br />
Экзамен пройдет 22 октября в 9:00 – 11:50 в ауд. 205 (группа 172), ауд. 317 (группы 174 и 175) и ауд. 402 (группа 176). Экзамен — письменный. С собой на экзамен можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается.<br />
<br />
Показ работ — 24 октября в 10:30 – 11:50 в ауд. 509.</div>imported>.obj