Сэвидж, Сложность вычислений // М.: «Факториал», 1998. Тема 4. NP-полнота различных задач, сводимость к задачам из NP NP-полнота различных задач: 3-КНФ, 3-Раскраска, Клика, Вершинное покрытие

Правительство Российской Федерации

Государственное образовательное бюджетное учреждение высшего профессионального образования
Государственный университет –
Высшая школа экономики

Факультет БИЗНЕС-ИНФОРМАТИКИ


Программа дисциплины

Сложность вычислений

для направления 010500.68 «Прикладная математика и информатика» подготовки магистров


Автор: Воронцов К.В.
([email protected])


Рекомендована секцией УМС
«Прикладная математика
и информатика»

Председатель
__________________ Кузнецов С.О.
«_____» __________________ 20___ г.
Одобрена на заседании кафедры
Анализа данных
и искусственного интеллекта

Зав. кафедрой
__________________ Кузнецов С.О.
«_____» __________________ 20___ г.


Утверждена УС факультета
бизнес-информатики

Ученый секретарь
__________________ Фомичев В.А.
« ____» ___________________20___ г.





Москва

Пояснительная записка
Автор программы
доктор технических наук К.В. Воронцов
Требования к студентам
Предполагается базовое знание теории вероятностей, умение вычислять сложность операций для задач из области программирования.
Аннотация
Курс «Сложность вычислений» предназначен для углубления знаний магистров 1-го года обучения в области программирования и сложности. В рамках курса студенты познакомятся с основными вычислительными моделями, такими как машина Тьюринга, равнодоступные адресные машины, схемы из функциональных элементов. Далее они познакомятся с различными классами трудностей, научатся оценивать время и память, требуемые алгоритму для решения задачи.
Теоретическая часть курса подкреплена многочисленными задачами и примерами. Так же студентам будут предоставлены задачи для самостоятельного решения.
Учебные задачи курса
Основные задачи курса:
Познакомить с основными вычислительными моделями, используемыми в оценках сложности;
Научить быстро оценивать время и память, требуемые данному алгоритму при его реализации на данной вычислительной модели;
Научить различать различные виды трудности задач (трудность для наихудшего входа и трудность для случайно взятого входа);
Изучить известные методы установления вычислительной трудности задач различного типа (задач вычисления функции, поиска, оптимизации, аппроксимации, подсчета, обращения функции): дать представление о том, как устанавливается "эталонных задач", и научить сводить данную задачу к одной из эталонных трудных задач.

Тематический план курса «Сложность вычислений»

Название темы
Всего часов по дисциплине
Аудиторные часы
Самосто-ятельная работа




Лекции
Сем. и практика занятия


1
Вычислительные модели
18
6
2
10

2
Сводимость и полнота задач
24
4
4
16

3
Класс NP
48
10
8
30

4
NP-полнота различных задач, сводимость к задачам из NP
34
6
8
20

5
Схемы из функциональных элементов. Класс BPP
18
4
6
8

6
Класс PSPACE
12
4
4
4

7
Вероятностно-проверяемые доказательства
8
2
2
4


Итого
162
36
34
92


Источники информации
Основная литература
А. А. Разборов, О сложности вычислений // Математическое просвещение. МЦНМО, 1999.
Т. Кормен, Ч. Лейзерсон, Р. Ривест, Кл. Штайн, Алгоритмы: построение и анализ // М.: «Вильямс», 2005.
А. А. Зыков Основы теории графов. 3-е изд. М.: «Вузовская книга», 2004.
Гери М. , Джонсон Д. Вычислительные машины и труднорешаемые задачи // М.: «Мир», 1982.
Х. Пападимитриу, К. Стайглиц, Комбинаторная оптимизация. Алгоритмы и сложность. // М.: «Мир», 1985.
А. Схрейвер, Теория целочисленного и линейного программирования // М.: «Мир», 1991.
Дополнительная литература
А. Ахо, Дж. Хопкрофт , Дж. Ульман, Построение и анализ вычислительных алгоритмов // М.: «Мир», 1979.
А. Китяев, А. Шень, М. Вялый, Классические и квантовые вычисления // М.: МЦНМО, 1999.
Дж. Сэвидж, Сложность вычислений // М.: «Факториал», 1998.
Дж. Хартманис, Дж. Хопкрофт, «Кибернетический сборник» // М.: «Мир», 1974
P. Gacs, L. Lovasz, Complexity of algorithms // Cambridge MA: MIT Press, 1999.
J. van Leeuwen, Algorithms and complexity // Cambridge MA: MIT Press, 1990.
M. Sipser, Introduction to the theory of computation // Boston: PWS publishing company, 1997.
Формы контроля и структура итоговой оценки
Текущий контроль: письменная контрольная работа (80 мин.) в конце 3-го модуля,
домашнее задание в 4-ом модуле.
Итоговый контроль – зачет в конце 4-го модуля.
Итоговая оценка зачета складывается из следующих элементов:
- письменный зачет – 30%;
- письменная контрольная работа – 40%;
- домашнее задание – 30%;
Таблица соответствия оценок по десятибалльной и системе зачет/незачет
Оценка по 10-балльной шкале
Оценка по 5-балльной шкале

1
Незачет

2


3


4
Зачет

5


6


7


8


9


10



Таблица соответствия оценок по десятибалльной и пятибалльной системе
По десятибалльной шкале
По пятибалльной системе

1 – неудовлетворительно
2 – очень плохо
3 – плохо
неудовлетворительно – 2

4 – удовлетворительно
5 – весьма удовлетворительно
удовлетворительно – 3

6 – хорошо
7 – очень хорошо
хорошо – 4

8 – почти отлично
9 – отлично
10 – блестяще
отлично – 5


Содержание курса «Сложность вычислений»
Тема 1. Вычислительные модели
Вычислительные модели: многоленточные машины Тьюринга, равнодоступные адресные машины. Оценка времени и памяти, необходимых для реализации основных арифметических алгоритмов. Полиномиальная эквивалентность по времени и памяти разумных вычислительных моделей. Класс P функций, вычислимых за полиномиальное время.
Основная литература
А. А. Разборов, О сложности вычислений // Математическое просвещение. МЦНМО, 1999.
Т. Кормен, Ч. Лейзерсон, Р. Ривест, Кл. Штайн, Алгоритмы: построение и анализ // М.: «Вильямс», 2005.
А. Схрейвер, Теория целочисленного и линейного программирования // М.: «Мир», 1991.
Дополнительная литература
Дж. Сэвидж, Сложность вычислений // М.: «Факториал», 1998.
Дж. Хартманис, Дж. Хопкрофт, «Кибернетический сборник» // М.: «Мир», 1974
P. Gacs, L. Lovasz, Complexity of algorithms // Cambridge MA: MIT Press, 1999.
J. van Leeuwen, Algorithms and complexity // Cambridge MA: MIT Press, 1990.
M. Sipser, Introduction to the theory of computation // Boston: PWS publishing company, 1997.
Тема 2. Сводимость и полнота задач
Сводимость одной задачи к другой. Полные в данном классе задачи. Теорема о иерархии для временной сложности, как метод доказательства вычислительной трудности задач. Доказуемо трудные алгоритмические проблемы: проверка эквивалентности расширенных регулярных выражений, выяснение истинности формул языка первого порядка в аддитивной группе действительных числах.
Основная литература
Т. Кормен, Ч. Лейзерсон, Р. Ривест, Кл. Штайн, Алгоритмы: построение и анализ // М.: «Вильямс», 2005.
Гери М. , Джонсон Д. Вычислительные машины и труднорешаемые задачи // М.: «Мир», 1982.
Х. Пападимитриу, К. Стайглиц, Комбинаторная оптимизация. Алгоритмы и сложность. // М.: «Мир», 1985.
Дополнительная литература
А. Ахо, Дж. Хопкрофт , Дж. Ульман, Построение и анализ вычислительных алгоритмов // М.: «Мир», 1979.
P. Gacs, L. Lovasz, Complexity of algorithms // Cambridge MA: MIT Press, 1999.
J. van Leeuwen, Algorithms and complexity // Cambridge MA: MIT Press, 1990.
M. Sipser, Introduction to the theory of computation // Boston: PWS publishing company, 1997.
Тема 3. Класс NP
Класс NP. Задачи поиска и класс SearchP. Сведение задач поиска к задачам разрешения из класса NP. Задачи подсчета и класс #P. NP-трудные и NP-полные задачи. Проблема перебора и предположительная трудность NP-трудных задач. Вопрос о совпадении и вложенности классов P и NP.
Основная литература
А. А. Разборов, О сложности вычислений // Математическое просвещение. МЦНМО, 1999.
А. А. Зыков Основы теории графов. 3-е изд. М.: «Вузовская книга», 2004.
Гери М. , Джонсон Д. Вычислительные машины и труднорешаемые задачи // М.: «Мир», 1982.
Х. Пападимитриу, К. Стайглиц, Комбинаторная оптимизация. Алгоритмы и сложность. // М.: «Мир», 1985.
Дополнительная литература
А. Ахо, Дж. Хопкрофт , Дж. Ульман, Построение и анализ вычислительных алгоритмов // М.: «Мир», 1979.
А. Китяев, А. Шень, М. Вялый, Классические и квантовые вычисления // М.: МЦНМО, 1999.
Дж. Сэвидж, Сложность вычислений // М.: «Факториал», 1998.
Тема 4. NP-полнота различных задач, сводимость к задачам из NP
NP-полнота различных задач: 3-КНФ, 3-Раскраска, Клика, Вершинное покрытие, Гамильтонов цикл, Рюкзак, Коммивояжер, Целочисленное линейное программирование. Задачи оптимизации и их сводимость к задачам из NP. Приближенное решение оптимизационных задач. Трудность задачи аппроксимации хроматического числа данного графа.
Основная литература
А. А. Разборов, О сложности вычислений // Математическое просвещение. МЦНМО, 1999.
А. А. Зыков Основы теории графов. 3-е изд. М.: «Вузовская книга», 2004.
Гери М. , Джонсон Д. Вычислительные машины и труднорешаемые задачи // М.: «Мир», 1982.
Х. Пападимитриу, К. Стайглиц, Комбинаторная оптимизация. Алгоритмы и сложность. // М.: «Мир», 1985.
А. Схрейвер, Теория целочисленного и линейного программирования // М.: «Мир», 1991.
Дополнительная литература
А. Ахо, Дж. Хопкрофт , Дж. Ульман, Построение и анализ вычислительных алгоритмов // М.: «Мир», 1979.
А. Китяев, А. Шень, М. Вялый, Классические и квантовые вычисления // М.: МЦНМО, 1999.
Дж. Сэвидж, Сложность вычислений // М.: «Факториал», 1998.
Дж. Хартманис, Дж. Хопкрофт, «Кибернетический сборник» // М.: «Мир», 1974
Тема 5. Схемы из функциональных элементов. Класс BPP
Схемы их функциональных элементов. Теорема Кука-Левина об NP-полноте проблемы выполнимости схем из функциональных элементов. Класс nuP задач разрешения, решаемых схемами полиномального от длины входа размера. Вероятностные полиномиальные алгоритмы и класс BPP задач разрешения, решаемых полиномиальными вероятностными алгоритмами с небольшой вероятностью ошибки. Примеры. Уменьшение вероятности ошибки. Вложение классов P и BPP в класс nuP.
Основная литература
А. А. Разборов, О сложности вычислений // Математическое просвещение. МЦНМО, 1999.
Х. Пападимитриу, К. Стайглиц, Комбинаторная оптимизация. Алгоритмы и сложность. // М.: «Мир», 1985.
А. Схрейвер, Теория целочисленного и линейного программирования // М.: «Мир», 1991.
Дополнительная литература
А. Ахо, Дж. Хопкрофт , Дж. Ульман, Построение и анализ вычислительных алгоритмов // М.: «Мир», 1979.
А. Китяев, А. Шень, М. Вялый, Классические и квантовые вычисления // М.: МЦНМО, 1999.
Дж. Сэвидж, Сложность вычислений // М.: «Факториал», 1998.
Дж. Хартманис, Дж. Хопкрофт, «Кибернетический сборник» // М.: «Мир», 1974

Тема 6. Класс PSPACE
Полиномиальные игры и класс PSPACE задач, разрешимых с полиномиальной памятью. Вложение класса NP в класс PSPACE. PSPACE-полные задачи.
Основная литература
А. А. Разборов, О сложности вычислений // Математическое просвещение. МЦНМО, 1999.
А. А. Зыков Основы теории графов. 3-е изд. М.: «Вузовская книга», 2004.
Дополнительная литература
А. Китяев, А. Шень, М. Вялый, Классические и квантовые вычисления // М.: МЦНМО, 1999.
Тема 7. Вероятностно-проверяемые доказательства
Вероятностно проверяемые доказательства и теорема о существовании вероятностно проверяемых доказательств для любого языка из NP. Применение вероятностно проверяемых доказательств для доказательства трудности приблизительного вычисления оптимизационных задач. Сложность в среднем. Теорема об NP-трудности в среднем задачи о замощении.
Основная литература
Т. Кормен, Ч. Лейзерсон, Р. Ривест, Кл. Штайн, Алгоритмы: построение и анализ // М.: «Вильямс», 2005.
Гери М. , Джонсон Д. Вычислительные машины и труднорешаемые задачи // М.: «Мир», 1982.
Х. Пападимитриу, К. Стайглиц, Комбинаторная оптимизация. Алгоритмы и сложность. // М.: «Мир», 1985.
Дополнительная литература
А. Ахо, Дж. Хопкрофт , Дж. Ульман, Построение и анализ вычислительных алгоритмов // М.: «Мир», 1979.
P. Gacs, L. Lovasz, Complexity of algorithms // Cambridge MA: MIT Press, 1999.
J. van Leeuwen, Algorithms and complexity // Cambridge MA: MIT Press, 1990.
M. Sipser, Introduction to the theory of computation // Boston: PWS publishing company, 1997.

Вопросы для оценки качества освоения дисциплины
Определение МТ.
Пример задачи, решаемой с помощью МТ.
Оценка времени и памяти, необходимых для реализации основных арифметических алгоритмов.
Определение принадлежности классу Р.
Примеры функций, вычислимых за полиномиальное время.
Полные задачи, примеры.
Теорема о иерархии для временной сложности.
Определение принадлежности классу NP.
Соотношение классов P и NP.
Задача коммивояжера, ее NP-трудность, теоремы о приближенных алгоритмах для нее.
Задача о максимальной клике, ее NP-трудность, теорема о приближенных алгоритмах для нее.
NP-полнота задачи о рюкзаке.
NP-полнота задачи о гамильтоновом цикле.
Сводимость задач оптимизации к задачам из NP.
Схемы их функциональных элементов.
Теорема Кука-Левина.
Определение принадлежности классу BPP.
Определение принадлежности классу PSPACE.
Соотношение между классами NP и PSPACE. Теорема о PSPACE-полноте задачи о квантифицированных булевских формулах.
Пример PSPACE-полной задачи.
Теорема об NP-трудности в среднем задачи о замощении.
Автор программы: _____________________________/ Воронцов К.В. /











13 PAGE \* MERGEFORMAT 14215




†ђ Заголовок 113ђ Заголовок 2 ђ Заголовок 3‘ђ Заголовок 4*ђ Заголовок 5*ђ Заголовок 615

Приложенные файлы

  • doc 26501904
    Размер файла: 132 kB Загрузок: 0

Добавить комментарий