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

Э.Н.Гордеев

ВВЕДЕНИЕ В ТЕОРИЮ СЛОЖНОСТИ АЛГОРИТМОВ.

Электронное учебное издание

Учебное пособие

по дисциплине «Математическая логика и теория алгоритмов».

Москва

(С) 2012 МГТУ им. Н.Э. БАУМАНА

УДК 519.7

Рецензенты: проф., д.ф.-м.н., Кузюрин Н.Н.

проф., д.ф.-м.н.,.

Гордеев Э.Н.

Введение в теорию сложности алгоритмов. Электронное учебное издание. - М.: МГТУ имени Н.Э. Баумана, 2012. 84 с.

Издание содержит конспект лекций по курсу «Математическая логика и теория алгоритмов», предусмотренного учебным планом МГТУ им. Н.Э.Баумана. Представлены формальные модели алгоритмов, рассмотрены различные подходы к понятию сложность задачи. Описаны наиболее известные классы сложности задач. Приведены примеры исследования сложности известных задач.

Для студентов факультета «Информатики и систем управления» МГТУ имени Н.Э. Баумана.

Рекомендовано учебно-методической комиссией НУК «Информатики и систем управления» МГТУ им. Н.Э. Баумана

Электронное учебное издание

Гордеев Эдуард Николаевич

ВВЕДЕНИЕ В ТЕОРИЮ СЛОЖНОСТИ АЛГОРИТМОВ.

© 2012 МГТУ имени Н.Э. Баумана

Оглавление

1. Введение. 6

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

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

2.1. Задача. 8

2.2. Алгоритм.. 13

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10.2. Классы P-SPACE и NP-SPACE. 61

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

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

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

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

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

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

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

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

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

13. Вопросы для самопроверки по курсу «Математическая логика и теория алгоритмов». 82

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

Введение

Дата добавления: 2015-07-11