Вычислительные машины и труднорешаемые задачи. М.Гери, Д.Джонсон (1982) (Вычислительные машины и труднорешаемые задачи. М.Гери, Д.Джонсон (1982).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.

Формальные языки343A11. Оптимизация программ349А11.1 Генерация кода программы349А11.2. Программы и схемы364А12. Разное369А13. Открытые задачи367Литература374Предметный указатель411Предметный указательВполне полиномиальнаяАлгоритм 17приближенная схема 173- «в наилучший из подходящих» (bestВременная сложность алгоритмаfit) 159(time complexity function) 18,- «в первый подходящий» (first fit)137157- - НДМТ-программы 48- - - - в порядке убывания 160Входная длина задачи (input length)- «жадный» (greedy) 17118- недетерминированный 44Выигрыш форсированный (forced- полиномиальный 19win) 215- приближенный 156ВЫПОЛНИМОСТЬ (ВЫП) 56—57- псевдополиномиальный (pseudoвыполнимость, вып, 3, 3, 65, 67polynomial time algorithm) 121ВЫЧИСЛЕНИЕ СЕМЕЙСТВА- эвристический 155(ensemble computation) 88- экспоненциальный 19ГАМИЛЬТОНОВ ПУТЬ (Path) 81Алфавит 18, 33- ЦИКЛ (ГЦ) (circuit) 53, 66, 77Асимптотическая погрешностьГраф ориентированный (directed) 81алгоритма (asymptotic- планарный 113performance ratio) 162ДЕЛИМОСТЬ НА ЧЕТЫРЕ 41Бандерснечи 13Дерево 135БУЛЕВСКИЕ ФОРМУЛЫ СДЕРЕВО ШТЕЙНЕРА 100КВАНТОРАМИ (БФК) 213Детерминированная одноленточнаяБыстродействие ЭВМ 19машина Тьюринга, или ДМТ 38Величина решения (solution value)Дизъюнкция (clause) 56156Длина решения задачи (solutionВЕРШИННОЕ ПОКРЫТИЕlength) 25(ВП)(vertex cover) 65, 74ДОМИНИРУЮЩЕЕ МНОЖЕСТВО100ДМТ [см.

Детерминированнаяодноленточная машинаТьюринга] 38- программа 38—40- - линейно ограниченная (linearbounded) 218- - полиномиальная 42ДОСТРОЙКА МАРШРУТАКОММИВОЯЖЕРА (ДМК)(extension) 147ЕДИНИЧНАЯ РЕЗОЛЮЦИЯ (unitresolution) 223Задача (problem) 16- выполнимости (satisfiability) 27- индивидуальная (instance) 16- комбинаторная оптимизационная156- массовая 16- перечисления (enumeration) 209- распознавания свойств (decisionproblem) 27, 31—32- с числовыми параметрами (numberproblem) 122- труднорешаемая (intractable) 21Игры комбинаторные (combinatorialgames) 215Иерархия полиномиальная 203ИЗОМОРФИЗМ ГРАФОВ 194- ПОДГРАФУ 32, 43, 86- ПОДЛЕСУ (subforest) 135Изоморфность языковполиномиальная 200Индивидуальная задача (instance) 16,139Класс 220DLOG-SPACE 220EXP-SPACE 228EXP-TIME 228KP 210КР-полных задач (Р-complete) 210NEXP-SPACE 229NEXP-T 1me, 228NLOQ-SPACE 225NP 27, 28, 45, 48NP-полных задач (NPC) 45NPI 193NP-SPACE 219Р 42P-SPACE 213P-SPACE — полных задач 23КЛИКА 65, 242- МАКСИМАЛЬНОГО РАЗМЕРА(maximum size clique) 205КОММИВОЯЖЕР (KM) 32, 43—44Композиция графов 181КРАТЧАЙШИЙ ПУТЬ МЕЖДУДВУМЯ ВЕРШИНАМИ 112Кука теорема 57Лес (forest) 134ЛИНЕЙНАЯ ДЕЛИМОСТЬ 200ЛИНЕЙНОЕПРОГРАММИРОВАНИЕ 194Логарифмическая память 220Локальная замена (local replacement)88Максимальная полиномиальноразрешимая подзадача 108МАКСИМАЛЬНЫЙ РАЗРЕЗ(maximum cut) 113Машина недетерминированная 26, 46- Тьюринга 24, 46Минимальная NP-полная подзадача108Минимальное остовное дерево(spanning tree) 165МИНИМАЛЬНОЕ ПОКРЫТИЕ 86- ЭКВИВАЛЕНТНОЕ ВЫРАЖЕНИЕ201МИНИМАЛЬНЫЙ НАБОР ТЕСТОВ95- ЭКВИВАЛЕНТНЫЙОРИЕНТИРОВАННЫЙ ГРАФ87, 112МИНИМУМ СУММЫ КВАДРАТОВ99МНОЖЕСТВО ВЕРШИН,РАЗРЕЗАЮЩИХ КОНТУРЫ(feedback vertex set) 100- ПРЕДСТАВИТЕЛЕЙ (hitting set) 86Мультираскраска графа 182Набор значений истинности (truthassignment) 56НАИБОЛЬШИЙ ОБЩИЙ ПОДГРАФ99НДМТ-программа 46Недетерминированная машина 26- одноленточная машина Тьюринга,или НДМТ 46- оракульная машина Тьюринга, илиНОМТ 202НЕЗАВИСИМОЕ МНОЖЕСТВО 74Неразрешимая задача (undecidable)25НЕУНИВЕРСАЛЬНОСТЬРЕГУЛЯРНОГО ВЫРАЖЕНИЯ217НЕЭКВИВАЛЕНТНОСТЬРЕГУЛЯРНОГОВЫРАЖЕНИЯ, НЕСОДЕРЖАЩЕГО ЗВЕЗДОЧЕК100- ЦЕЛОЧИСЛЕННЫХВЫРАЖЕНИЙ 207НУМЕРАЦИЯ ГРАФА ПО ГРУНДИ101ОБОБЩЕННЫЙ ГЕКС (generalizedHex) 216ОМТ-программа 144Оптимальное решение задачи 156Оракульная машина Тьюринга, илиОМТ (oracle) 141Остовное дерево (spanning tree) 86,165, 258ОСТОВНОЕ ДЕРЕВООГРАНИЧЕННОЙ СТЕПЕНИ86Отношение Rм (relation) 198Параметр 16- числовой 122Паросочетание (matching) 167, 169- максимальное 169Переборная задача (search problem)139Погрешность алгоритма (performanceratio) 162Подзадача (subproblem) 105Покрытие множества (cover) 86Полиномиальная ДМТ-программа 42- ОМТ-программа 144- память (space) 212- схема 173- сводимость (polynomialtransformation) 51—52Полиномиально эквивалентны(polynomialy related) 35Построение компоненты (componentdesign) 84, 96Правильно построенное слово(structured string) 36Принимаемое программой слово(accepted) 39ПРИНЯТИЕ С ЛИНЕЙНОЙПАМЯТЬЮ 218Программа ДМТ (DTM) 38- НДМТ (NDTM) 46Псевдополиномиальная сводимость(pseudo-polynomialtransformation) 130Псевдополиномиальный алгоритм121РАЗБИЕНИЕ (partition) 66, 81- НА ГАМИЛЬТОНОВЫПОДГРАФЫ 99- - ПУТИ ДЛИНЫ 2, 100- - ТРЕУГОЛЬНИКИ 90—91разбиение, 3, 124разбиение, 4, 125Размер задачи (size) 17—18РАЗМЕР МИНИМАЛЬНОГОЭКВИВАЛЕНТНОГОВЫРАЖЕНИЯ 205РАСКРАШИВАЕМОСТЬ ГРАФА Вcolorability, цвета, 3, 3, 101, 110,182РАСПИСАНИЕ ДЛЯМУЛЬТИПРОЦЕССОРНОЙСИСТЕМЫ 87- - ОБРАТНОГО ДЕРЕВАЗАДАНИЙ 112- - ПРЯМОГО ДЕРЕВА ЗАДАНИЙ112- С ОТНОШЕНИЕМПРЕДШЕСТВОВАНИЯ(precedence constrainedscheduling) 107Распознавание языка (recognition)РАСЩЕПЛЕНИЕ МНОЖЕСТВА(splitting) 100РЕБЕРНОЕ ПОКРЫТИЕ (edge cover)112Регулярное выражение 217Релятивизация 230Решение задачи алгоритмом(solution) 17РЮКЗАК (knapsack) 87, 171САМЫЙ ДЛИННЫЙ ПУТЬ 99, 112Сводимость консервативная(parsimonious transformation)210- по Куку 150- полиномиальная 51—52- по Тьюрингу 141- псевдополиномиальная 130- log-space 222- Y(v-reducibility) 198Словарное отношение (string relation)140Слово алфавита (string) 33- - — правильно построенное(structured) 36Сложность алгоритма временная(time complexity function) 18,137СОСТАВНЫЕ ЧИСЛА (compositenumbers) 194Степень вершины графа (degree) 110Сужение задачи (restriction) 85Схема кодирования (encodingscheme) 18- приближенная 173- - «разумная» 24, 34, 36Теория графов 110ТОЧНОЕ ПОКРЫТИЕ множествами,тп, 3, 3, 73- - множествами, 4, 100ТРАНЗИТИВНАЯ РЕДУКЦИЯ 112ТРЕХМЕРНОЕ СОЧЕТАНИЕ ( с, 3,65, 70Угадывающее устройство (guessinedevice) 47Упаковка в контейнеры 157УПАКОВКА МНОЖЕСТВ 99УПОРЯДОЧЕНИЕ ВНУТРИИНТЕРВАЛОВ (sequencingwithin intervals) 93- С МИНИМАЛЬНЫМЗАПАЗДЫВАНИЕМ (tardiness)97Управляющее устройство ДМТ (finitestate control) 38Функция, конструируемая повремени (time constructible) 227- - по памяти (space constructible) 227Цепочка символов (string) 18Цикл простой в графе (simple circuit)53Числовой параметр (number) 122Читающая/пишущая головка ДМТ 38Эвристический алгоритм 155Эйлеров граф 166- маршрут (tour) 166Эквивалентность полиномиальная 35Язык в алфавите 33—34- контекстно-зависимый (contextsensitive) 220- распознаваемый программой 39, 47- рекурсивный 193- log-space-полный 223- NP-полный 55- \gamma-полный 199DLB-автомат детерминированныйлинейно ограниченный 220GA-алгоритм 171К-е ПО ПОРЯДКУПОДМНОЖЕСТВО (K-thlargest set subset) 145КР-полная задача (#Р-complete) 210Length [I] 35, 119Max [I] 119—120ММ-алгоритм 167—168MST-алгоритм 166NLB-автомат (недетерминированныйлинейно ограниченный) 220NN-алгоритм 163—164NP-легкая задача (easy) 149NP-полная задача 27, 45, 48, 51- - в сильном смысле 123NP-трудная задача (hard) 145NP-эквивалентная задача 149P-space-полная задача 213.