- Артикул:00-01057088
- Автор: М. Гери, Д. Джонсон
- Тираж: 8000 экз.
- Обложка: Твердая обложка
- Издательство: МИР (все книги издательства)
- Город: Москва
- Страниц: 416
- Формат: 60 90/16
- Год: 1982
- Вес: 653 г
Развернуть ▼
Монография американских ученых, посвященная вопросам сложности решения комбинаторных задач, возникающих в дискретной оптимизации, математическом программировании, алгебре, теории чисел, теории автоматов, математической логике, теории множеств, теории графов и т.п. Книга отличается строгим и систематическим изложением теории, в приложении содержится более 300 труднорешаемых задач из различных разделов математики. Для математиков-прикладников, аспирантов и студентов университетов
Оглавление
От редактора перевода
Предисловие
1. Вычислительные машины, сложность и труднорешаемые задачи
1.1. Введение
1.2. Задачи, алгоритмы и сложность
1.3. Полиномиальные алгоритмы и труднорешаемые задачи
1.4. Задачи, труднорешаемость которых доказуема
1.5. NP-полные задачи
1.6. О содержании книги
2. Теория NP-полных задач
2.1. Задачи распознавания, языки и кодирование
2.2. Детерминированные машины Тьюринга и класс Р
2.3. Недетерминированное вычисление и класс NP
2.4. Взаимоотношения между классами Р и NP
2.5. Полиномиальная сводимость и NP-полные задачи
2.6. Теорема Кука
3. Доказательство результатов об NP-полноте
3.1. Шесть основных NP-полных задач
3.2. Некоторые методы доказательства NP-полноты
3.3. Упражнения
4. Применение теории NP-полноты для анализа задач
4.1. Анализ подзадач
4.2. Задачи с числовыми параметрами и сильная NP-полнота
4.3. Временная сложность как функция натуральных параметров
5. NP-трудные задачи
5.1. Сводимость по Тьюрингу и NP-трудные задачи
5.2. Историческая справка
6. Подходы к решению NP-полных задач
6.1. Оценки погрешности приближенных алгоритмов
6.2. Применение теории NP-полноты к отысканию приближенных решений
6.3 Оценки погрешности и поведение алгоритмов «на практике»
7. За пределами класса NP-полных задач
7.1. Структура класса NP
7.2. Полиномиальная иерархия
7.3. Сложность задач перечисления
7.4. Полнота с полиномиально ограниченной памятью
7.5. Логарифмическая память
7.6. Доказательства труднорешаемости и взаимоотношения между Р и NP
Литература
Предметный указатель
Рекомендуем
