https://www.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_2019%2F2020Алгоритмы и структуры данных 2 2019/2020 - История изменений2026-06-06T12:35:23ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://www.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_2019/2020&diff=932&oldid=previmported>.obj: Migrated current public revision from wiki.cs.hse.ru2019-10-20T15:55:55Z<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, ауд. R304<br /><br />
пятница 10:30 – 11:50, ауд. R401<br /><br />
<br />
'''Консультации:'''<br/><br />
понедельник 18:00 – 20:00, к. T915<br /><br />
четверг 16:30 – 18:00, к. T915<br />
<br />
'''Ассистенты:'''<br />
<br />
Группы 182 и 184 — [mailto:alatysheva@edu.hse.ru Александра Латышева].<br />
<br />
Группы 185 и 186 — [mailto:polyakovam1708@gmail.com Мария Полякова].<br />
<br />
Группы 187 и 188 — [mailto:Amtursunkhodzhaev@edu.hse.ru Агзамходжа Турсунходжаев].<br />
<br />
<br />
= Лекции =<br />
# [https://www.dropbox.com/s/1jwy67gb6g0by8e/algo2-1-p.pdf?dl=0 2 сентября.] Класс P: определение, примеры задач.<br />
# [https://www.dropbox.com/s/j7cbbdez08bwnn2/algo2-2-np.pdf?dl=0 6 сентября.] Класс NP: определение, примеры задач. Класс coNP. Возможное соотношение классов. Полиномиальные сведения.<br />
# [https://www.dropbox.com/s/bkdp3xtfpxt3j21/algo2-3-npc.pdf?dl=0 9 сентября.] NP-полные задачи.<br />
# [https://www.dropbox.com/s/gsesd7hw978wn0w/algo2-4-nph.pdf?dl=0 13 сентября.] Точные алгоритмы решения NP-трудных задач.<br />
# '''16 сентября.''' Полиномиально разрешимые частные случаи NP-трудных задач: минимальное вершинное покрытие для дерева (без весов и с весами на вершинах) и двудольного графа, 2SAT. Метод ветвей и границ: задачи коммивояжера и о рюкзаке.<br />
# [https://www.dropbox.com/s/fypj77z7a248fp3/algo2-6-approximation.pdf?dl=0 20 сентября.] Приближенные алгоритмы.<br />
# '''27 сентября.''' Локальный поиск. Приближенное решение задачи о максимальном разрезе. Эвристика Кернигана – Лина для определения соседних решений при поиске максимального разреза.<br />
# [https://www.dropbox.com/s/waysdhvex1nnu13/algo2-8-segmentation.pdf?dl=0 30 сентября.] Сегментация изображений на передний/задний план с помощью минимального разреза. Приближенный алгоритм сегментации изображений на несколько классов.<br />
# '''4 октября.''' Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние. NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние. Приближенный алгоритм кластеризации, минимизирующий максимальное внутрикластерное расстояние. Невозможность лучшего приближения для этой задачи (если P ≠ NP).<br />
# [https://www.dropbox.com/s/w6kfnslk78sw49d/algo2-10-sat.pdf?dl=0 5 октября.] Теорема Кука – Левина.<br />
# '''7 октября.''' Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный алгоритм для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ, его дерандомизация.<br />
# '''11 октября.''' Потоковые алгоритмы. Алгоритмы SpaceSaving и Count-Min Sketch для поиска частых элементов в потоке.<br />
# '''14 октября.''' Эффективное перечисление решений. Полиномиальная задержка, инкрементальная (кумулятивная) полиномиальная задержка, оценка времени работы алгоритма относительно комбинированного размера входа и выхода. [https://www.dropbox.com/s/mfebtpkl1dfuvvf/algo2-13-enumeration.pdf?dl=0 Перечисление всех путей между двумя заданными вершинами в графе.] Перечисление всех максимальных (по вложению) клик графа.<br />
# [https://www.dropbox.com/s/8uuueyzonjo7jya/algo2-14-problems.pdf?dl=0 18 октября.] Задачи для подготовки к экзамену.<br />
<br />
= Домашние задания =<br />
[https://official.contest.yandex.ru/contest/13942 Первое домашнее задание]: 13 – 29 сентября.<br />
<br />
[https://official.contest.yandex.ru/contest/14358 Второе домашнее задание]: 27 сентября — 15 октября. (Третья задача уже добавлена.)<br />
<br />
= Аудиторная работа =<br />
<br />
Оценка за аудиторную работу складывается из следующих частей: 3 балла за письменный тест (примерно [https://www.dropbox.com/s/fd0j31udiag7x8x/algo2-test.pdf?dl=0 такой]), по 1 баллу за каждый из трех наборов задач, по 1 или 2 балла за каждое из трех заданий на программирование. Дробные оценки не предусмотрены. Если в сумме получается более десяти баллов, оценка за аудиторную работу равна десяти баллам.<br />
<br />
==Наборы задач==<br />
До указанного срока можно сдавать задачи устно (каждый студент сдает все задачи). Срок сдачи может быть продлен по согласованию с преподавателем. Те, кто не успевает, сдают письменно в течение следующей недели и в течение еще одной недели рассказывают решения некоторых задач преподавателю или (по согласованию с преподавателем) учебному ассистенту. Чтобы получить балл за набор задач, нужно решить все задачи. Дробные оценки не предусмотрены.<br />
# [https://www.dropbox.com/s/nkys3fgn5071tia/algo2-problems1.pdf?dl=0 P и NP] Срок сдачи — 16 сентября.<br />
# [https://www.dropbox.com/s/79l5xud1x5escdu/algo2-problems2.pdf?dl=0 Полиномиальные сведения и NP-полные задачи] Срок сдачи — 27 сентября.<br />
# [https://www.dropbox.com/s/irj176fpigvousb/algo2-problems3.pdf?dl=0 Алгоритмы решения трудных задач] Эти задачи нужно решить письменно. Срок письменной сдачи — 16 октября.<br />
<br />
==Задания на программирование==<br />
<br />
===Первое===<br />
[https://www.dropbox.com/s/6u8sflhq3w1ilxh/statement.pdf?dl=0 Описание задания] и [https://www.dropbox.com/s/ty7ouwnx86g2sdq/tests.zip?dl=0 тесты] к нему. Срок сдачи — 20 сентября. Срок сдачи может быть продлен по согласованию с преподавателем. Задание состоит из двух частей. За выполнение первой части моно получить один балл, за выполнение обеих частей — два балла. Дробные оценки не предусмотрены. При выполнении задания может оказаться полезным следующий [https://colab.research.google.com/drive/1dJ-l7ESm0oCjdADRvcJwz5JWUIkms3x7 ноутбук].<br />
<br />
===Второе===<br />
В задании необходимо реализовать сегментацию изображений: на два класса в первой части (один балл) и на несколько — во втором (еще один балл). Изображения и заготовка кода с визуализацией — [https://drive.google.com/open?id=1pijeYwhchSrFdQKzmTXJiWXzNiPPD49S здесь]. Срок сдачи — 11 октября.<br />
<br />
Цвета классов являются параметрами алгоритмов (определяются с помощью алгоритма kmeans в заготовке; можно использовать тот же код, другой, или подбирать цвета вручную).<br />
<br />
Штраф за сегментацию состоит из двух компонент, с весами alpha и beta соответственно:<br />
<br />
* штраф за непохожесть на класс: если пиксель с компонентами (r1, g1, b1) отнесен к классу с цветом (r, g, b), штраф этого пикселя составляет sqrt((r1 - r)^2 + (g1 - g)^2 + (b1 - b)^2))<br />
* штраф за отнесение соседних пикселей похожих цветов к разным классам: если два соседних пикселя с компонентами (r1, g1, b1) и (r2, g2, b2) отнесены к разным классам, штраф этой пары составляет 1 / (1 + sqrt((r1 - r2)^2 + (g1 - g2)^2 + (b1 - b2)^2)) / 255)<br />
* суммарный штраф сегментации равен сумме штрафов за каждый пиксель, умноженной на alpha, к которой прибавлена сумма штрафов за все пары пикселей, умноженная на beta<br />
<br />
Убедитесь, что ваш алгоритм дает меньшую величину штрафа чем простое отнесение каждого пикселя к ближайшему классу.<br />
<br />
Как меняется штраф в зависимости от соотношения параметров alpha и beta?<br />
<br />
Видны ли отличия в качестве кластеризации визуально? Соответствует ли меньшее значение штрафа интуитивно лучшей кластеризации?<br />
<br />
===Третье===<br />
[https://www.dropbox.com/s/wfgjj00yycvkiyf/algo2-clustering.pdf?dl=0 Описание задания], [https://www.dropbox.com/s/h2f2e6gukzyxxz7/task.zip?dl=0 заготовка кода и тестовые данные] к нему. Срок сдачи — 18 октября, 9:00.<br />
<br />
== Письменный тест ==<br />
Письменный тест состоится 1 октября в 9:00 – 10:30. Группы 185-1, 186 и 187 пишут тест в ауд. R404, прочие группы — в аудиториях, указанных в расписании.<br />
<br />
=Экзамен=<br />
Экзамен пройдет 21 октября в 9:00 – 11:50 в ауд. R204 (группы 182, 184 и 185) и ауд. R205 (группы 186, 187 и 188). Экзамен — письменный. С собой на экзамен можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается.<br />
<br />
Показ работ — 23 октября в 9:00 – 9:50 в ауд. R407.<br />
<br />
= Оценки =<br />
Итоговая оценка: 0,15 · оценка за первое домашнее задание + 0,15 · оценка за второе домашнее задание + 0,3 · оценка за аудиторную работу + 0,4 · оценка за письменный экзамен.<br />
<br />
Необходимым условием получения итоговой оценки автоматом является наличие трех баллов (из трех возможных) за решение наборов задач и по крайней мере двух баллов (из трех возможных) — за письменный тест.<br />
<br />
[https://docs.google.com/spreadsheets/d/1OGOfQ7Wyjc0eCBc6GciEf8kXr0epBD0joAwoEsgOFeM/edit?usp=sharing Таблицы с оценками]</div>imported>.obj