Алгоритмы и структуры данных 2 2016/2017
Материал из Wiki - Факультет компьютерных наук
Версия от 17:37, 14 сентября 2016; .obj (обсуждение | вклад)
Лектор: С. Объедков
Расписание лекций:
вторник 10:30 – 11:50, ауд. 509
пятница 15:10 – 16:30, ауд. 509
Консультации:
понедельник 18:00 – 20:00, к. 324
четверг 16:30 – 18:00, к. 324 (по предварительной договоренности)
Лекции
- 2 сентября. Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоклеточной машины с временем работы t(n) > n на одноленточной машине за время O(t(n)2). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов.
- 6 сентября. Полиномиальные сведения. NP-трудные и NP-полные задачи. Формулировка теоремы Кука – Левина. Сведение задачи 3SAT к задаче Not-All-Equal-3SAT.
- 9 сентября. Доказательство теоремы Кука – Левина. NP-полнота задачи 3SAT.
- 13 сентября. NP-полнота задач о сумме подмножества и о рюкзаке. Сведение Not-All-Equal-3SAT к задаче о максимальном разрезе.
Домашние задания
Первое домашнее задание
Первое домашнее задание стоит из нескольких частей. Из первой части нужно решить все задачи. Если иное не сказано преподавателем, ведущим семинары, решение нужно прислать ему по электронной почте до вечера 14 сентября.
Студенты группы 155-2, загрузите, пожалуйста, решение домашнего задания в anytask.
