Версия 19:23, 17 сентября 2019

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

Расписание лекций:
понедельник 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. Метод ветвей и границ: задачи коммивояжера и о рюкзаке.

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

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

Второе домашнее задание: 27 сентября — 15 октября.

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

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

Наборы задач

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

1. P и NP Срок сдачи — 16 сентября.
2. Полиномиальные сведения и NP-полные задачи Срок сдачи — 27 сентября.

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

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

Оценки

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

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

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