Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Гэри М., Джонсон Д. — Вычислительные машины и труднорешаемые задачи
Гэри М., Джонсон Д. — Вычислительные машины и труднорешаемые задачи



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Вычислительные машины и труднорешаемые задачи

Авторы: Гэри М., Джонсон Д.

Аннотация:

Монография американских ученых, посвященная вопросам сложности решения комбинаторных задач, возникающих в дискретной оптимизации, математическом программировании, алгебре, теории чисел, теории автоматов, математической логике, теории множеств, теории графов и т.п. Книга отличается строгим и систематическим изложением теории, в приложении содержится более 300 труднорешаемых задач из различных разделов математики.
Для математиков-прикладников, аспирантов и студентов университетов.


Язык: ru

Рубрика: Computer science/Вычислимость/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1982

Количество страниц: 416

Добавлена в каталог: 16.11.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
3-выполнимость (3-ВЫП)      65 67
3-разбиение      124
4-разбиение      125
DLB-автомат детерминированный линейно ограниченный      220
GA-алгоритм      171
K-е по порядку подмножество (K-th largest set subset)      145
KP-полная задача (#P-complete)      210
Length [I]      35 119
Max [I]      119—120
MM-алгоритм      167—168
MST-алгоритм      166
NLB-автомат (недетерминированный линейно ограниченный)      220
NN-алгоритм      163—164
NP-легкая задача (easy)      149
NP-полная задача      27 45 48 51
NP-полная задача в сильном смысле      123
NP-трудная задача (hard)      145
NP-эквивалентная задача      149
P-space-полная задача      213
Алгоритм      17
Алгоритм недетерминированный      44
Алгоритм полиномиальный      19
Алгоритм приближенный      156
Алгоритм псевдополиномиальный (pseudo polynomial time algorithm)      121
Алгоритм эвристический      155
Алгоритм экспоненциальный      19
Алгоритм «в наилучший из подходящих» (best fit)      159
Алгоритм «в первый подходящий» (first fit)      157
Алгоритм «в первый подходящий» в порядке убывания      160
Алгоритм «жадный» (greedy)      171
Алфавит      18 33
Асимптотическая погрешность алгоритма (asymptotic performance ratio)      162
Бандерснечи      13
Булевские формулы с кванторами (БФК)      213
Быстродействие ЭВМ      19
Величина решения (solution value)      156
Вершинное покрытие (ВП) (vertex cover)      65 74
Вполне полиномиальная приближенная схема      173
Временная сложность алгоритма (time complexity function)      18 137
Временная сложность НДМТ-программы      48
Входная длина задачи (input length)      18
Выигрыш форсированный (forced win)      215
Выполнимость (ВЫП)      56—57
Вычисление семейства (ensemble computation)      88
Гамильтонов путь (Path)      81
Гамильтонов цикл (ГЦ) (circuit)      53 66 77
Граф ориентированный (directed)      81
Граф пленарный      113
Делимость на четыре      41
Дерево      135
Дерево Штейнера      100
Детерминированная одноленточная машина Тьюринга, или ДМТ      38
Дизъюнкция (clause)      56
Длина решения задачи (solution length)      25
ДМТ программа      38—40
ДМТ программа линейно ограниченная (linear bounded)      218
ДМТ программа полиномиальная      42
Доминирующее множество      100
Достройка маршрута коммивояжера (ДМК) (extension)      147
Единичная резолюция (unit resolution)      223
Задача (problem)      16
Задача выполнимости (satisfiability)      27
Задача индивидуальная (instance)      16
Задача комбинаторная оптимизационная      156
Задача массовая      16
Задача перечисления (enumeration)      209
Задача распознавания свойств (decision problem)      27 31—32
Задача с числовыми параметрами (number problem)      122
Задача труднорешаемая (intractable)      21
Игры комбинаторные (combinatorial games)      215
Иерархия полиномиальная      203
Изоморфизм графов      194
Изоморфизм подграфу      32 43 86
Изоморфизм подлесу (subforest)      135
Изоморфность языков полиномиальная      200
Индивидуальная задача (instance)      16 139
Класс DLOG-SPACE      220
Класс EXP-SPACE      228
Класс EXP-TIME      228
Класс KP      210
Класс KP-полных задач (P-complete)      210
Класс NEXP-SPACE      229
Класс NEXP-TIME      228
Класс NLOG-SPACE      225
Класс NP      27 28 45 48
Класс NP-SPACE      219
Класс NP-полных задач (NPC)      45
Класс NPI      193
Класс P      42
Класс P-SPACE      213
Класс P-SPACE-полных задач      23
Клика      65 242
Клика максимального размера (maximum size clique)      205
Коммивояжер (КМ)      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
Набор значений истинности (truth assignment)      56
Наибольший общий подграф      99
НДМТ-программа      46
Недетерминированная машина      26
Недетерминированная одноленточная машина Тьюринга, или НДМТ      46
Недетерминированная оракульная машина Тьюринга, или НОМТ      202
Независимое множество      74
Неразрешимая задача (undecidable)      25
Неуниверсальность регулярного выражения      217
Неэквивалентность регулярного выражения, не содержащего звездочек      100
Неэквивалентность целочисленных выражений      207
Нумерация графа по Грунди      101
Обобщенный гекс (generalized Hex)      216
ОМТ-программа      144
Оптимальное решение задачи      156
Оракульная машина Тьюринга, или ОМТ (oracle)      141
Остовное дерево (spanning tree)      86 165 258
Остовное дерево ограниченной степени      86
Отношение $R_M$ (relation)      198
Параметр      16
Параметр числовой      122
Паросочетание (matching)      167 169
Паросочетание максимальное      169
Переборная задача (search problem)      139
Погрешность алгоритма (performance ratio)      162
Подзадача (subproblem)      105
Покрытие множества (cover)      86
Полиномиальная ДМТ-программа      42
Полиномиальная ОМТ-программа      144
Полиномиальная память (space)      212
Полиномиальная сводимость (polynomial transformation)      51—52
Полиномиальная схема      173
Полиномиально эквивалентны (polynomial related)      35
Построение компоненты (component design)      84 96
Правильно построенное слово (structured string)      36
Принимаемое программой слово (accepted)      39
Принятие с линейной памятью      218
Программа ДМТ (DTM)      38
Программа НДМТ (NDTM)      46
Псевдополиномиальная сводимость (pseudo-polynomial transformation)      130
Псевдополиномиальный алгоритм      121
Разбиение (partition)      66 81
Разбиение на гамильтоновы подграфы      99
Разбиение на пути длины 2      10
Разбиение на треугольники      90—91
Размер задачи (size)      17—18
Размер минимального эквивалентного выражения      205
Раскрашиваемость графа в 3 цвета (3-colorability)      101 110 182
Расписание для мультипроцессорной системы      87
Расписание для обратного дерева заданий      112
Расписание для прямого дерева заданий      112
Расписание с отношением предшествования (precedence constrained scheduling)      107
Распознавание языка (recognition)      47
Расщепление множества (splitting)      100
Реберное покрытие (edge cover)      112
Регулярное выражение      217
Релятивизация      230
Решение задачи алгоритмом (solution)      17
Рюкзак (knapsack)      87 171
Самый длинный путь      99 112
Сводимость $\gamma$ ($\gamma$-reducibility)      198
Сводимость log-space      222
Сводимость консервативная (parsimonious transformation)      210
Сводимость по Куку      150
Сводимость по Тьюрингу      141
Сводимость полиномиальная      51—52
Сводимость псевдополиномиальная      130
Словарное отношение (string relation)      140
Слово алфавита (string)      33
Слово алфавита, правильно построенное (structured)      36
Сложность алгоритма временная (time complexity function)      18 137
Составные числа (composite numbers)      194
Степень вершины графа (degree)      110
Сужение задачи (restriction)      85
Схема кодирования (encoding scheme)      18
Схема приближенная      173
Схема приближенная «разумная»      24 34 36
Теория графов      110
Точное покрытие 3-множествами (ТП-3)      73
Точное покрытие 4-множествами      100
Транзитивная редукция      112
Трехмерное сочетание (3-С)      65 70
Угадывающее устройство (guessing device)      47
Упаковка в контейнеры      157
Упаковка множеств      99
Упорядочение внутри интервалов (sequencing within intervals)      93
Упорядочение с минимальным запаздыванием (tardiness)      97
Управляющее устройство ДМТ (finite state control)      38
Функция, конструируемая по времени (time constructible)      227
Функция, конструируемая по памяти (space constructible)      227
Цепочка символов (string)      18 (см. также «Слово алфавита»)
Цикл простой в графе (simple circuit)      53
Числовой параметр (number)      122
Читающая/пишущая головка ДМТ      38
Эвристический алгоритм      155
Эйлеров граф      166
Эйлеров маршрут (tour)      166
Эквивалентность полиномиальная      35
Язык $\gamma$-полный      199
Язык log-space-полный      223
Язык NP-полный      55
Язык в алфавите      33—34
Язык контекстно-зависимый (context-sensitive)      220
Язык рекурсивный      193
Язык, распознаваемый программой      39 47
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте