Методы оптимизации, обозначения

Версия от 17:04, 8 июня 2009; StepLg (Обсуждение | вклад)

К каждому определению в скобочках указывается номер страницы в методичке, на которой впервые данное определение встречается

Сокращения

КМ (ЗК) -- коммивояжёр (задача о коммивояжёре) (стр. 6)
ПЧ -- задача распознавания простоты числа (стр. 8)
ДМТ -- детерминированная машина Тьюринга (стр. 9)
НДМТ -- недетерминированная машина Тьюринга (стр. 9)
ВЫП -- проверить на выполнимость конечной КНФ (стр. 14)
ЦЛН -- задача о целочисленном решении сислемы линейных неравенств (стр. 15)
БЛН -- задача о булевом решении сислемы линейных неравенств (стр. 16)
3-ВЫП -- проверить на выполнимость конечной КНФ от ровно трёх переменных (стр. 17)
ЗР -- задача о рюкзаке (стр. 19)
ЛП -- линейное программирование (стр. 25)
озЛП -- основная задача линейного программирования (стр. 25)
ЗМП -- задача математического программирования (стр. 39)
ЦЛП -- целочисленное линейное программирование (стр. 55)
БЛП -- булево линейное программирование (стр. ??)

$Π$ -- массовая задача (стр. 4)
$I \in \Pi$ -- индивидуальная задача (стр. 4)
$Σ$ -- алфавит кодирования (стр. 7)
$e$ -- кодировка задачи $Π$ (стр. 7)
$L (Π, e)$ -- язык задачи (стр. 7)
$T A (n)$ -- временная сложность алгоритма $A$ (стр. 8)
$\overline{\Pi}$ -- дополнительная задача к массовой задача $Π$ (стр. 12)
$\Pi' \propto \Pi$ --массовой задача $Π'$ полиномиально сводится к задаче $Π$ (стр. 13)

P -- класс полиномиальных разрешимых задач (стр. 8)
NP -- класс недетерминированно полиномиальных разрешимых задач (стр. 9, 10)
co-P -- класс задач, дополнительных к полиномиально разрешимым задачам (стр. 12)
co-NP -- класс задач, дополнительных к недетерменированно полиномиально разрешимым задачам (стр. 12)
NPC -- класс NP-полных задач (стр. 14)
PSPACE -- класс задач, требующих для решения не более чем полиномиальной памяти (стр. 19)