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

Материал из eSyr's wiki.

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

[править] Сокращения

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

[править] Математические обозначения

$Π$ -- массовая задача (стр. 4)
$I \in \Pi$ -- индивидуальная задача (стр. 4)
$Σ$ -- алфавит кодирования (стр. 7)
$e$ -- кодировка задачи $Π$ (стр. 7)
$L (Π, e)$ -- язык задачи (стр. 7)
$T A (n)$ -- временная сложность алгоритма $A$ (стр. 8)
$\overline{\Pi}$ -- дополнительная задача к массовой задача $Π$ (стр. 12)
$\Pi' \propto \Pi$ --массовой задача $Π'$ полиномиально сводится к задаче $Π$ (стр. 13)
$num(I)$ -- максимальное по модулю число, фигурирующее в условии в задачи или 0, если числовых параметров нет. (стр. 21)
$p(\cdot); p(\cdot, \cdot)$ -- полином от одной, двух переменных (стр. ??)
$Δ(D) = max | det(D 1) |$ , где $D 1$ -- квадратная подматрица $D$ (стр. 28)
$\left[A | b \right]$ -- матрица, составленная из матрицы $A$ , и дописанного справа столбца $b$ (стр. 28)
$\langle x,y \rangle$ -- скалярное произведение векторов $x, y$ : $\langle x,y \rangle = x_1 y_1 + x_2 y_2 + \dots x_n y_n$ (стр. ??)
$\varepsilon_1$ -- минимальное приближение, при котором система линейных неравенств имеет решение (стр. 29)

[править] Классы сложности задач

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