Версия 11:57, 15 сентября 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-трудных задач.

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

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

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

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

Наборы задач

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

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

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

Оценки

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

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