Методы оптимизации, обозначения
Материал из eSyr's wiki.
(Различия между версиями)
| Строка 12: | Строка 12: | ||
* ''' 3-ВЫП ''' -- проверить на выполнимость конечной КНФ от ровно трёх переменных (стр. 17) | * ''' 3-ВЫП ''' -- проверить на выполнимость конечной КНФ от ровно трёх переменных (стр. 17) | ||
* ''' ЗР ''' -- задача о рюкзаке (стр. 19) | * ''' ЗР ''' -- задача о рюкзаке (стр. 19) | ||
| + | * ''' ПППС ''' -- полностью полиномиальная приближенная схема (стр. 24) | ||
* ''' ЛП ''' -- линейное программирование (стр. 25) | * ''' ЛП ''' -- линейное программирование (стр. 25) | ||
* '''озЛП''' -- основная задача линейного программирования (стр. 25) | * '''озЛП''' -- основная задача линейного программирования (стр. 25) | ||
| Строка 17: | Строка 18: | ||
* '''ЦЛП''' -- целочисленное линейное программирование (стр. 55) | * '''ЦЛП''' -- целочисленное линейное программирование (стр. 55) | ||
* '''БЛП''' -- булево линейное программирование (стр. ??) | * '''БЛП''' -- булево линейное программирование (стр. ??) | ||
| + | * '''ЗМП''' -- задачи математического программирования (стр. 39) | ||
== Математические обозначения == | == Математические обозначения == | ||
| Строка 28: | Строка 30: | ||
* <math>\overline{\Pi}</math> -- дополнительная задача к массовой задача <math>\Pi</math> (стр. 12) | * <math>\overline{\Pi}</math> -- дополнительная задача к массовой задача <math>\Pi</math> (стр. 12) | ||
* <math>\Pi' \propto \Pi</math> --массовой задача <math>\Pi'</math> полиномиально сводится к задаче <math>\Pi</math> (стр. 13) | * <math>\Pi' \propto \Pi</math> --массовой задача <math>\Pi'</math> полиномиально сводится к задаче <math>\Pi</math> (стр. 13) | ||
| + | * <math>\mathrm{num}(I)</math> -- максимальное по модулю число, фигурирующее в условии в задачи или 0, если числовых параметров нет. (стр. 21) | ||
| + | * <math>p(\cdot); p(\cdot, \cdot)</math> -- полином от одной, двух переменных (стр. ??) | ||
| + | * <math>\Delta(D) = \max | \det(D_1) | </math>, где <math>D_1</math> -- квадратная подматрица <math>D</math> (стр. 28) | ||
| + | * <math>\left[A | b \right]</math> -- матрица, составленная из матрицы <math>A</math>, и дописанного справа столбца <math>b</math> (стр. 28) | ||
| + | * <math>\langle x,y \rangle</math> -- скалярное произведение векторов <math>x,y</math> : <math>\langle x,y \rangle = x_1 y_1 + x_2 y_2 + \dots x_n y_n</math> (стр. ??) | ||
| + | * <math>\varepsilon_1</math> -- минимальное приближение, при котором система линейных неравенств имеет решение (стр. 29) | ||
| + | |||
Версия 17:26, 8 июня 2009
К каждому определению в скобочках указывается номер страницы в методичке, на которой впервые данное определение встречается
Сокращения
- КМ (ЗК) -- коммивояжёр (задача о коммивояжёре) (стр. 6)
- ПЧ -- задача распознавания простоты числа (стр. 8)
- ДМТ -- детерминированная машина Тьюринга (стр. 9)
- НДМТ -- недетерминированная машина Тьюринга (стр. 9)
- ВЫП -- проверить на выполнимость конечной КНФ (стр. 14)
- ЦЛН -- задача о целочисленном решении сислемы линейных неравенств (стр. 15)
- БЛН -- задача о булевом решении сислемы линейных неравенств (стр. 16)
- 3-ВЫП -- проверить на выполнимость конечной КНФ от ровно трёх переменных (стр. 17)
- ЗР -- задача о рюкзаке (стр. 19)
- ПППС -- полностью полиномиальная приближенная схема (стр. 24)
- ЛП -- линейное программирование (стр. 25)
- озЛП -- основная задача линейного программирования (стр. 25)
- ЗМП -- задача математического программирования (стр. 39)
- ЦЛП -- целочисленное линейное программирование (стр. 55)
- БЛП -- булево линейное программирование (стр. ??)
- ЗМП -- задачи математического программирования (стр. 39)
Математические обозначения
- Π -- массовая задача (стр. 4)
-
-- индивидуальная задача (стр. 4)
- Σ -- алфавит кодирования (стр. 7)
- e -- кодировка задачи Π (стр. 7)
- L(Π,e) -- язык задачи (стр. 7)
- TA(n) -- временная сложность алгоритма A (стр. 8)
-
-- дополнительная задача к массовой задача Π (стр. 12)
-
--массовой задача Π' полиномиально сводится к задаче Π (стр. 13)
- num(I) -- максимальное по модулю число, фигурирующее в условии в задачи или 0, если числовых параметров нет. (стр. 21)
-
-- полином от одной, двух переменных (стр. ??)
- Δ(D) = max | det(D1) | , где D1 -- квадратная подматрица D (стр. 28)
-
![\left[A | b \right]](/w/images/math/2/2/7/227b535df59409b2795cb581ca6fe43b.png)
-- матрица, составленная из матрицы A, и дописанного справа столбца b (стр. 28)
-
-- скалярное произведение векторов x,y : 
(стр. ??)
-
-- минимальное приближение, при котором система линейных неравенств имеет решение (стр. 29)
Классы сложности задач
- P -- класс полиномиальных разрешимых задач (стр. 8)
- NP -- класс недетерминированно полиномиальных разрешимых задач (стр. 9, 10)
- co-P -- класс задач, дополнительных к полиномиально разрешимым задачам (стр. 12)
- co-NP -- класс задач, дополнительных к недетерменированно полиномиально разрешимым задачам (стр. 12)
- NPC -- класс NP-полных задач (стр. 14)
- PSPACE -- класс задач, требующих для решения не более чем полиномиальной памяти (стр. 19)
