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

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

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

10.12.2011, 14:55

Босс В. Лекции по математике. Т. 10: Перебор и эффективные алгоритмы: Учебное пособие. — М.: Издательство ЛКИ, 2008. — 216 с. 

Книга посвящена теории сложности алгоритмов в той ее части, где речь идет о противостоянии Р- и 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 ПО

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)

Категория: Лекции | Добавил: Andrey
Просмотров: 1600 | Загрузок: 308 | Рейтинг: 0.0/0


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



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

Алгебра [10]
Аналитическая геометрия [3]
Лекции [5]



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


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