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

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

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

Расписание лекций:
понедельник 12:10 – 13:30, ауд. R304
пятница 10:30 – 11:50, ауд. R401

Консультации:
понедельник 18:00 – 20:00, к. T915
четверг 16:30 – 18:00, к. T915

Ассистенты:

Группы 182 и 184 — Александра Латышева.

Группы 185 и 186 — Мария Полякова.

Группы 187 и 188 — Агзамходжа Турсунходжаев.


Лекции

  1. 2 сентября. Класс P: определение, примеры задач.
  2. 6 сентября. Класс NP: определение, примеры задач. Класс coNP. Возможное соотношение классов. Полиномиальные сведения.
  3. 9 сентября. NP-полные задачи.
  4. 13 сентября. Точные алгоритмы решения NP-трудных задач.
  5. 16 сентября. Полиномиально разрешимые частные случаи NP-трудных задач: минимальное вершинное покрытие для дерева (без весов и с весами на вершинах) и двудольного графа, 2SAT. Метод ветвей и границ: задачи коммивояжера и о рюкзаке.
  6. 20 сентября. Приближенные алгоритмы.
  7. 27 сентября. Локальный поиск. Приближенное решение задачи о максимальном разрезе. Эвристика Кернигана – Лина для определения соседних решений при поиске максимального разреза.
  8. 30 сентября. Сегментация изображений на передний/задний план с помощью минимального разреза. Приближенный алгоритм сегментации изображений на несколько классов.
  9. 4 октября. Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние. NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние. Приближенный алгоритм кластеризации, минимизирующий максимальное внутрикластерное расстояние. Невозможность лучшего приближения для этой задачи (если P ≠ NP).
  10. 5 октября. Теорема Кука – Левина.
  11. 7 октября. Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный алгоритм для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ, его дерандомизация.
  12. 11 октября. Потоковые алгоритмы. Алгоритмы SpaceSaving и Count-Min Sketch для поиска частых элементов в потоке.

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

Первое домашнее задание: 13 – 29 сентября.

Второе домашнее задание: 27 сентября — 15 октября. Третья задача будет добавлена позже.

Аудиторная работа

Оценка за аудиторную работу складывается из следующих частей: 3 балла за письменный тест (примерно такой), по 1 баллу за каждый из трех наборов задач, по 1 или 2 балла за каждое из трех заданий на программирование. Дробные оценки не предусмотрены. Если в сумме получается более десяти баллов, оценка за аудиторную работу равна десяти баллам.

Наборы задач

До указанного срока можно сдавать задачи устно (каждый студент сдает все задачи). Срок сдачи может быть продлен по согласованию с преподавателем. Те, кто не успевает, сдают письменно в течение следующей недели и в течение еще одной недели рассказывают решения некоторых задач преподавателю или (по согласованию с преподавателем) учебному ассистенту. Чтобы получить балл за набор задач, нужно решить все задачи. Дробные оценки не предусмотрены.

  1. P и NP Срок сдачи — 16 сентября.
  2. Полиномиальные сведения и NP-полные задачи Срок сдачи — 27 сентября.
  3. Алгоритмы решения трудных задач Эти задачи нужно решить письменно. Срок письменной сдачи — 16 октября.

Задания на программирование

Первое

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

Второе

В задании необходимо реализовать сегментацию изображений: на два класса в первой части (один балл) и на несколько — во втором (еще один балл). Изображения и заготовка кода с визуализацией — здесь. Срок сдачи — 11 октября.

Цвета классов являются параметрами алгоритмов (определяются с помощью алгоритма kmeans в заготовке; можно использовать тот же код, другой, или подбирать цвета вручную).

Штраф за сегментацию состоит из двух компонент, с весами alpha и beta соответственно:

  • штраф за непохожесть на класс: если пиксель с компонентами (r1, g1, b1) отнесен к классу с цветом (r, g, b), штраф этого пикселя составляет sqrt((r1 - r)^2 + (g1 - g)^2 + (b1 - b)^2))
  • штраф за отнесение соседних пикселей похожих цветов к разным классам: если два соседних пикселя с компонентами (r1, g1, b1) и (r2, g2, b2) отнесены к разным классам, штраф этой пары составляет 1 / (1 + sqrt((r1 - r2)^2 + (g1 - g2)^2 + (b1 - b2)^2)) / 255)
  • суммарный штраф сегментации равен сумме штрафов за каждый пиксель, умноженной на alpha, к которой прибавлена сумма штрафов за все пары пикселей, умноженная на beta

Убедитесь, что ваш алгоритм дает меньшую величину штрафа чем простое отнесение каждого пикселя к ближайшему классу.

Как меняется штраф в зависимости от соотношения параметров alpha и beta?

Видны ли отличия в качестве кластеризации визуально? Соответствует ли меньшее значение штрафа интуитивно лучшей кластеризации?

Письменный тест

Письменный тест состоится 1 октября в 9:00 – 10:30. Группы 185-1, 186 и 187 пишут тест в ауд. R404, прочие группы — в аудиториях, указанных в расписании.

Оценки

Итоговая оценка: 0,15 · оценка за первое домашнее задание + 0,15 · оценка за второе домашнее задание + 0,3 · оценка за аудиторную работу + 0,4 · оценка за письменный экзамен.

Необходимым условием получения итоговой оценки автоматом является наличие трех баллов (из трех возможных) за решение наборов задач и по крайней мере двух баллов (из трех возможных) — за письменный тест.

Таблицы с оценками