4

Московский Государственный Университет им. Н.Э.Баумана

Гордеев Э.Н.

Лекции

Введение в теорию сложности алгоритмов

Москва 2011

УДК 519.9

Гордеев Э.Н.

ЭЛЕМЕНТЫ ТЕОРИИ СЛОЖНОСТИ АЛГОРИТМОВ (ЧАСТЬ I)/ Москва, МГТУ им. Н.Э.Баумана, 2011, 49 с.

Данный текст – это семестровый курс лекций для студентов третьего курса МГТУ им. Н.Э.Баумана, обучающихся по инженерной специальности на кафедре Информационной безопасности. В этом курсе проведено изложение и сравнение основных базовых формальных схем алгоритмов: алгорифм Маркова, детерминированная и недетерминированная машина Тьюринга, оракульная машина Тьюринга и др. Введены и рассмотрены основные классы сложности: P, NP, NPC, Co-NP, PSPACE, NPSPACE, EXPTIME и др. Описаны соотношения этих классов. Рассмотрены подходы к решению NP- полных задач. Цель курса – дать представление и базовые знания в теории сложности студентам и аспирантам инженерных специальностей: информационная безопасность, математическое моделирование, построение СУБД и пр. Изложение максимально упрощено и базируется на многолетнем опыте чтения такого курса в МГТУ им. Н.Э.Баумана. Пособие может быть использовано в учебном процессе для подготовки семинарских занятий, экзаменационного материала и как источник проблемных задач. Данное пособие является переработанным вариантом предыдущего, выпущенного в 2002 году.

Рецензент: д.ф.-м.н., проф. Леонтьев В.К.

Оглавление

1. Введение 5

1.1. Предмет и цель курса лекций. 5

1.2. Некоторые необходимые определения и понятия. 5

2. Задачи, алгоритмы 7

2.1. Задача 7

2.2. Алгоритм 12

3. Нормальные алгорифмы Маркова (НАМ). 15

4. Машины Тьюринга 18

4.1. Одноленточная МТ 18

4.2. Многоленточная МТ 20

4.3. Недетерминированная МТ 21

4.4. Оракульная МТ 22

5. Равнодоступная адресная машина (РАМ) и некоторые другие подходы. 23

6. Сравнение различных формальных схем. 27

6.1. Кодировки входных данных. 27

6.2. О мерах сложности 28

6.3. Теоремы сравнения 31

6.4. Полиномиальные и неполиномиальные оценки сложности 33

7. Сложность алгоритмов некоторых задач. 35

7.1. Задача нахождения максимального числа. 35

7.2. Задача сортировки. 35

7.3. Задача о камнях. 37

7.4. Простота числа. 37

7.5. Задача о кратчайшем (минимальном) остове (остовном дереве). 38

7.6. Задача коммивояжера. 40

7.7. Задача о кратчайшем пути. 40

7.8. Задача о выполнимости КНФ (КНФ-выполнимость) 42

8. Схемы из функциональных элементов. Схемная сложность. 42

8.1. Схемы из функциональных элементов 42

8.2. Оценки сложности СФЭ. 45

9. Теория NP-полноты 49

9.1. Классы P и NP. 50

9.2. Сводимость задач 51

9.2.1. Смысл сводимости 51

9.2.2. Полиномиальная сводимость 52

9.2.3. Сводимость по Тьюрингу 54

9.3. Теорема Кука 57

9.4. Структура класса NP и некоторые выводы 63

10. Иерархия сложности 65

10.1. Классы NP и co-NP 65

10.2. Классы P-SPACE и NP-SPACE. Элементы исчисления предикатов. 67

10.2.1. Классы сложности P-SPACE и NP-SPACE 67

10.2.2. Логика предикатов и PSPACE –полные задачи. 73

10.3. Классы P и P/poly. 82

10.4. Некоторые результаты 84

11. Подходы к решению NP-полных задач 84

11.1. NP-полнота в сильном смысле. Псевдополиномиальные алгоритмы 85

11.2. Приближенные алгоритмы 86

11.3. Полиномиально-разрешимые частные случаи NP-полных задач 88

11.4. Методы направленного перебора 88

12. Параллельные вычисления 91

12.1. Классификация моделей параллельных вычислений. 91

12.2. Примеры способов параллельной обработки данных 93

12.3. Вопросы производительности параллельных вычислений 96

12.3.1. Основной вопрос сложности параллельных вычислений 96

12.3.2. Асимптотическая производительность 98

12.3.3. Гипотеза Минского. 102

12.4. Пример параллельного вычисления. 104

13. Коммуникационная сложность 107

14. Рекомендованная литература 111