РЕШАЕМ МАТЕМАТИКУ ВМЕСТЕ!
 
СТУДЕНТАМ:    Учебники     Решебники    Шпаргалки    Контрольные работы   Видео уроки

ШКОЛЬНИКАМ:  ГДЗ - 1 класс  2 класс  3 класс  4 класс  5 класс  6 класс  7 класс  8 класс  9 класс  10 класс  11 класс

Главная » Файлы » Учебные материалы » Математическая логика и теория алгоритмов
Босс В. Лекции по математике. Т. 10: Перебор и эффективные алгоритмы: Учебное пособие.

12.12.2011, 23:40
Книга посвящена теории сложности алгоритмов в той ее части, где речь идет о противостоянии Р- и NP-задач. В резонанс с проблемой «Р против NP» входит обширная тематика: комбинаторные задачи на графах, неразрешимые проблемы теории алгоритмов, криптография, целочисленное программирование, вероятностные методы, квантовые вычисления, алгоритмы Хачияна и Кармаркара для линейного программирования, а также полиномиальный алгоритм AKS для выяснения простоты числа. Особое внимание уделяется геометрическому взгляду на проблему, который в привычном уже пейзаже обнаруживает свежие ракурсы.
Изложение отличается краткостью и прозрачностью.
Для студентов, преподавателей, инженеров и научных работников.

Оглавление

Предисловие к «Лекциям».....................................................................................7
Предисловие к десятому тому................................................................................9

Глава 1. Комбинаторные задачи..............................................................................................................10

1.1. Экспоненциальный кошмар...............................................................................10

1.2. Р- и NP-задачи..................................................................................................11

1.3. Центральный вопрос и окружение.....................................................................17

1.4. Задачи на графах.............................................................................................18

1.5. Целочисленное программирование.....................................................................25

1.6. Логические задачи............................................................................................27

1.7. (0, 1)-матрицы...................................................................................................30

1.8. Простые и составные числа................................................................................32

1.9. Комбинаторные механизмы.................................................................................33

Глава 2. Инструменты и декорации......................................................................................................35

2.1. Вычислимые функции........................................................................................35

2.2. Перечислимые множества..................................................................................37

2.3. Неразрешимые проблемы...................................................................................39

2.4. Машины Тьюринга.............................................................................................40

2.5. Полиномиальные алгоритмы...............................................................................45

2.6. Вычислительная сложность...............................................................................47

2.7. Задачи верхнего уровня...................................................................................49

Глава 3. Проблема Р = NP...................................................................52

3.1. Класс Р............................................................................................................52

3.2. Класс NP..........................................................................................................54

3.3. Сводимость и NP-полнота.................................................................................56

3.4. Универсальная переборная задача..................................................................58

3.5. Теорема Кука..................................................................................................59

3.6. Класс NPC.......................................................................................................62

3.7. Подход Левина...............................................................................................64

3.8. Полиномиальное раздутие...............................................................................66

3.9. Будет ли решена проблема Р = NP....................................................................67

Глава 4. Анатомия переборных задач.......................................69

4.1. Проблема co-NP=NP..........................................................................................69

4.2. Сильная NP-полнота.........................................................................................70

4.3. Кратчайший путь..............................................................................................72

4.4. Максимальный поток и минимальный разрез.....................................................75

4.5. Теория матроидов и жадный алгоритм..............................................................76

4.6. Вариации МОД.................................................................................................80

4.7. PSPACE-задачи................................................................................................80

4.8. Схемная сложность..........................................................................................83

4.9. Интерактивные протоколы................................................................................83

4.10. Релятивизация и оракулы...............................................................................86

4.11. Рамсеевские задачи.......................................................................................88

Глава 5. Линейное программирование......................................91

5.1. Постановка задачи..........................................................................................91

5.2. Предыстория комбинаторного варианта............................................................95

5.3. Эффекты ограниченной точности.....................................................................97

5.4. Алгоритм эллипсоидов..................................................................................100

5.5. Природа алгоритма.......................................................................................102

5.6. Методы внутренней точки.............................................................................103

5.7. Феномен целочисленных вершин...................................................................104

Глава 6. Арифметика и криптография.....................................107

6.1. О причинах исключительности......................................................................107

6.2. Тесты на простоту........................................................................................108

6.3. Полиномиальный тест AKS............................................................................11О

6.4. Алгоритмы факторизации..............................................................................112

6.5. Система RSA................................................................................................113

6.6. Вариант распознавания................................................................................116

6.7. Дискретный логарифм..................................................................................117

6.8. Системы с нулевым разглашением.................................................................119

6.9. Другие задачи..............................................................................................120

6.10. Технические дополнения............................................................................123

Глава 7. Геометрический подход................................................126

7.1. Общая картина..............................................................................................126

7.2. Выпуклые многогранники...............................................................................130

7.3. Циклические многогранники...........................................................................134

7.4. Линейные разделяющие деревья...................................................................136

7.5. Алгоритмы прямого типа.................................................................................139

7.6. Релаксационные многогранники.....................................................................142

7.7. Аффинная сводимость....................................................................................144

7.8. Комментарии и дополнения............................................................................146

Глава 8. Вероятностные алгоритмы...................................................................................................148

8.1. Напоминание о смешанных стратегиях............................................................149

8.2. Интерактивные доказательства......................................................................150

8.3. РСР-проблематика.........................................................................................153

8.4. Рутинная колея.............................................................................................155

8.5. Простые числа...............................................................................................157

Глава 9. Прагматика и эвристика.................................................158

9.1. Сетевое программирование как обобщение динамического.............................158

9.2. Ареал жадного алгоритма...............................................................................160

9.3. Приближенные алгоритмы...............................................................................161

9.4. Метод ветвей и границ....................................................................................163

9.5. О задаче ЦЛП.................................................................................................164

Глава 10. Квантовые вычисления................................................166

10.1. В чем идея и каковы препятствия..................................................................166

10.2. Основные понятия.........................................................................................168

10.3. Вычисление и феномен измерения..................................................................174

10.4. Квантовые вентили........................................................................................175

10.5. Алгоритм ускоренного поиска.........................................................................176

10.6. Квантовое преобразование Фурье..................................................................177

10.7. Алгоритм факторизации Шора.........................................................................179

10.8. Антипод здравого смысла...............................................................................180

10.9. ЭПР-парадокс и скрытые параметры...............................................................183

10.10. О перетягивании каната................................................................................185

10.11. Комментарии и дополнения............................................................................186

Глава 11. Сводка основных определений и результатов...................................................................................................188

11.1. Список NP-полных задач.................................................................................188

11.2. Алгоритмы и вычислимость...............................................................................191

11.3. Проблема Р = NP...............................................................................................192

11.4. Вокруг «Р или NP»...........................................................................................193

11.5. Линейное программирование............................................................................194

11.6. Арифметика и криптография.............................................................................195

11.7. Геометрический подход....................................................................................197

11.8. Вероятностные алгоритмы................................................................................200

11.9. Квантовые вычисления.....................................................................................201

Сокращения и обозначения......................................................................................203
Литература................................................................................................................205
Предметный указатель..............................................................................................207





Размер файла: (3.51Mb)

Категория: Математическая логика и теория алгоритмов | Добавил: nikka
Просмотров: 1194 | Загрузок: 260 | Рейтинг: 0.0/0


Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]



ВЫБОР ПО КАТЕГОРИЯМ:

Аналитическая геометрия и алгебра [0]
Высшая алгебра [52]
История математики [55]
Математика для технарей [21]
Математика для экономистов, юристов и т.д.. [5]
Математическая логика и теория алгоритмов [40]
Теория вероятностей и мат. статистика [28]
Теория чисел [33]
Учебники по математике [46]



При полном или частичном использовании материалов
активная ссылка на портал VMATE.RU обязательна


Высшая математика онлайн - всё бесплатно, наш портал создан специально для студентов кому интересна высшая математика. У нас на портале возможно скачать бесплатно учебники по высшей математике, книги по математике или сделать заказ учебных пособий, скачать контрольные по высшей математике, заказать, задачники по высшей математики и решебники. Оставить запрос по предмету - аналитическая геометрия или задать вопрос - справочная по математике Заказать решение и т.д. Высшая математика онлайн - математический портал и здесь собраны шпаргалки по высшей математике и видео уроки. Добро пожаловать! Вход