Оглавление книги М.Гэри, Д.Джонсон Вычислительные машины и трудно решаемые задачи
№	Название	стр.
1	Вычислительные машины, сложность и труднорешаемые задачи	11
1.1	Введение	11
1.2	Задачи, алгоритмы и сложность	14
1.3	Полиномиальные алгоритмы и труднорешаемые задачи	16
1.4	Задачи, труднорешаемость которых доказуема	21
1.5	NP-полные задачи	23
1.6	О содержании книги	25
2	Теория NP-полных задач	27
2.1	Задачи распознавания, языки и кодирование	27
2.2	Детерминированные машины Тьюринга и класс P	33
2.3	Недетерминированное вычисление и класс NP	37
2.4	Взаимоотношения между классами P и NP	43
2.5	Полиномиальная сводимость и NP-полные задачи	45
2.6	Теорема Кука	49
3	Доказательство результатов об NP-полноте	57
3.1	Шесть основных NP-полных задач	58
3.1.1	3-выполнимость	60
3.1.2	Трёхмерное сочетание	62
3.1.3	Вершинное покрытие и Клика	66
3.1.4	Гамильтонов цикл	69
3.1.5	Разбиение	73
3.2	Некоторые методы доказательства NP-полноты	75
3.2.1	Сужение задачи	76
3.2.2	Локальная замена	79
3.2.3	Построение компонент	86
3.3	Упражнения	89
4	Применение теории NP-полноты для анализа задач	92
4.1	Анализ подзадач	95
4.2	Задачи с числовыми параметрами и сильная NP-полнота	106
4.2.1	Некоторые дополнительные определения	108
4.2.2	Доказательство результатов о сильной NP-полноте	112
4.3	Временнaя сложность как функция натуральных параметров	124
5	NP-трудные задачи	126
5.1	Сводимость по Тьюрингу и NP-трудные задачи	126
5.2	Историческая справка	136
6	Подходы к решению NP-полных задач	139
6.1	Оценки погрешности приближённых алгоритмов	141
6.2	Применение теории NP-полноты к отысканию приближённых решений	158
6.3	Оценки погрешности и поведение алгоритмов на практике	170
7	За пределами класса NP-полных задач	173
7.1	Структура класса NP	174
7.2	Полиномиальная иерархия	181
7.3	Сложность задач перечисления	188
7.4	Полнота c полиномиально ограниченной памятью	191
7.5	Логарифмическая память	198
7.6	Доказательства труднорешаемости и взаимоотношения между P и NP	202
A	Список NP-полных задач	208
A1	ТЕОРИЯ ГРАФОВ	211
A1.1	Покрытие и разбиение	211
A1.2	Подграфы и надграфы	216
A1.3	Упорядочение вершин	222
A1.4	Морфизмы и изоморфизмы	225
A1.5	Разное	227
A2	ПОСТРОЕНИЕ СЕТЕЙ	229
A2.1	Остовные деревья	229
A2.2	Разрезы и связность	233
A2.3	Задачи о маршрутах	236
A2.4	Потоковые задачи	239
A2.5	Разное	244
A3	МНОЖЕСТВА И РАЗБИЕНИЯ	246
A3.1	Покрытие, представители и расщепление	246
A3.2	Задачи о множествах с взвешенными элементами	249
A4	ХРАНЕНИЕ И ПОИСК ДАННЫХ	252
A4.1	Хранение данных	252
A4.2	Сжатие и представление информации	255
A4.3	Задачи о базах данных	260
A5	ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ	264
A5.1	Задачи составления расписания в случае одного процессора	264
A5.2	Многопроцессорные расписания для параллельных процессоров	267
A5.3	Многопроцессорные расписания конвейерного типа	271
A5.4	Разные задачи	273
A6	МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ	275
A7	АЛГЕБРА И ТЕОРИЯ ЧИСЕЛ	279
A7.1	Задачи о делимости	279
A7.2	Разрешимость уравнений	281
A7.3	Разное	283
A8	ИГРЫ И ГОЛОВОЛОМКИ	285
A9	ЛОГИКА	290
A9.1	Пропозициональная логика	290
A9.2	Разное	294
A10	ТЕОРИЯ АВТОМАТОВ И ЯЗЫКОВ	297
A10.1	Теория автоматов	297
A10.2	Формальные языки	300
A11	ОПТИМИЗАЦИЯ ПРОГРАММ	305
A11.1	Генерация кода программы	305
A11.2	Программы и схемы	309
A12	РАЗНОЕ	313
A13	ОТКРЫТЫЕ ЗАДАЧИ	320
B	ЛИТЕРАТУРА	326
B1	Книги, указанные авторами	326
B2	Работы, переведённые на русский язык или первоначально изданные в СССР	368
B3	Литература, дополненная авторами при переиздании	369
B4	Литература, дополненная при переводе на русский язык	370
B5	Литература, дополненная при изготовлении элькопии	371
Полный текст (.ps) (илл. 126 p/inch.) – архив 1.76 Мб Полный текст (.ps) без уплотнения. Полный текст (.pdf)