Вычислительные машины и труднорешаемые задачи. М.Гери, Д.Джонсон (1982) (Вычислительные машины и труднорешаемые задачи. М.Гери, Д.Джонсон (1982).pdf)
Описание файла
Просмотр PDF-файла онлайн
Текст из PDF
М.Гэри, Д.ДжонсонВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ И ТРУДНОРЕШАЕМЫЕ ЗАДАЧИМ.: Мир, 1982Монография американских ученых, посвященная вопросам сложностирешения комбинаторных задач, возникающих в дискретной оптимизации,математическом программировании, алгебре, теории чисел, теории автоматов,математической логике, теории множеств, теории графов и т.п. Книга отличаетсястрогим и систематическим изложением теории, в приложении содержится более300 труднорешаемых задач из различных разделов математики.Для математиков-прикладников, аспирантов и студентов университетов.СодержаниеОт редактора перевода5Предисловие101. Вычислительные машины, сложность и труднорешаемые задачи131.1. Введение131.2.
Задачи, алгоритмы и сложность161.3. Полиномиальные алгоритмы и труднорешаемые задачи191.4. Задачи, труднорешаемость которых доказуема251.5. NP-полные задачи261.6. О содержании книги282. Теория NP-полных задач312.1. Задачи распознавания, языки и кодирование312.2. Детерминированные машины Тьюринга и класс Р382.3. Недетерминированное вычисление и класс NP432.4. Взаимоотношения между классами Р и NP492.5.
Полиномиальная сводимость и NP-полные задачи512.6. Теорема Кука563. Доказательство результатов об NP-полноте643.1. Шесть основных NP-полных задач643.1.1. 3-выполнимость673.1.2. Трехмерное сочетание693.1.3. Вершинное покрытие и Клика733.1.4. Гамильтонов цикл773.1.5. Разбиение813.2. Некоторые методы доказательства NP-полноты843.2.1. Сужение задачи853.2.2.
Локальная замена883.2.3. Построение компонент963.3. Упражнения994. Применение теории NP-полноты для анализа задач1024.1. Анализ подзадач1054.2. Задачи с числовыми параметрами и сильная NP-полнота1174.2.1. Некоторые дополнительные определения1194.2.2. Доказательство результатов о сильной NP-полноте1234.3. Временная сложность как функция натуральных параметров5. NP-трудные задачи5.1. Сводимость по Тьюрингу и NP-трудные задачи5.2. Историческая справка6. Подходы к решению NP-полных задач6.1.
Оценки погрешности приближенных алгоритмов6.2. Применение теории NP-полноты к отысканию приближенныхрешений6.3 Оценки погрешности и поведение алгоритмов «на практике»7. За пределами класса NP-полных задач7.1. Структура класса NP7.2. Полиномиальная иерархия7.3. Сложность задач перечисления7.4. Полнота с полиномиально ограниченной памятью7.5. Логарифмическая память7.6. Доказательства труднорешаемости и взаимоотношения между Р и NPА. Приложение. Список NP-полных задачА1.
Теория графовА1.1. Покрытие и разбиениеА1.2. Подграфы и надграфыА1.3. Упорядочение вершинА1.4 Морфизмы и изоморфизмыА1.5. РазноеА2. Построение сетейА2.1. Остовные деревьяА2.2. Разрезы и связностьА2.3. Задачи о маршрутахА2.4. Потоковые задачиА2.5. РазноеA3. Множества и разбиенияА3.1.
Покрытие, представители к расщеплениеА3.2. Задачи о множествах с взвешенными элементамиА4. Хранение и поиск данныхА4.1. Хранение данныхА4.2. Сжатие и представление информацииА4.3. Задачи о базах данныхА5. Задачи теории расписанийА5.1. Задачи составления расписания в случае одногоА5.2. Многопроцессорные расписания для параллельных процессоровА5.3.
Многопроцессорные расписания конвейерного типаА5.4. Разные задачиА6. Математическое программированиеА7. Алгебра и теория чиселА7.1. Задачи о делимости136139139150154156174189192192201208212220225232235235242249252254258258263266270275279279282286286289295300300304308311313318318А7.2. Разрешимость уравнений321А7.3. Разное323А8. Игры и головоломки325А9. Логика332А9.1. Пропозициональная логика332А9.2. Разное336А10. Теория автоматов и языков339А10.1. Теория автоматов339А10.2.