Методы оптимизации, обозначения
Материал из eSyr's wiki.
(Различия между версиями)
Строка 16: | Строка 16: | ||
* '''озЛП''' -- основная задача линейного программирования (стр. 25) | * '''озЛП''' -- основная задача линейного программирования (стр. 25) | ||
* '''ЗМП''' -- задача математического программирования (стр. 39) | * '''ЗМП''' -- задача математического программирования (стр. 39) | ||
+ | * '''МВГ''' -- метод ветвей и границ (стр. 54) | ||
* '''ЦЛП''' -- целочисленное линейное программирование (стр. 55) | * '''ЦЛП''' -- целочисленное линейное программирование (стр. 55) | ||
* '''БЛП''' -- булево линейное программирование (стр. ??) | * '''БЛП''' -- булево линейное программирование (стр. ??) | ||
- | * ''' | + | * '''ДП''' -- динамическое программирование (стр. 59) |
== Математические обозначения == | == Математические обозначения == |
Версия 18:23, 8 июня 2009
К каждому определению в скобочках указывается номер страницы в методичке, на которой впервые данное определение встречается
Сокращения
- КМ (ЗК) -- коммивояжёр (задача о коммивояжёре) (стр. 6)
- ПЧ -- задача распознавания простоты числа (стр. 8)
- ДМТ -- детерминированная машина Тьюринга (стр. 9)
- НДМТ -- недетерминированная машина Тьюринга (стр. 9)
- ВЫП -- проверить на выполнимость конечной КНФ (стр. 14)
- ЦЛН -- задача о целочисленном решении сислемы линейных неравенств (стр. 15)
- БЛН -- задача о булевом решении сислемы линейных неравенств (стр. 16)
- 3-ВЫП -- проверить на выполнимость конечной КНФ от ровно трёх переменных (стр. 17)
- ЗР -- задача о рюкзаке (стр. 19)
- ПППС -- полностью полиномиальная приближенная схема (стр. 24)
- ЛП -- линейное программирование (стр. 25)
- озЛП -- основная задача линейного программирования (стр. 25)
- ЗМП -- задача математического программирования (стр. 39)
- МВГ -- метод ветвей и границ (стр. 54)
- ЦЛП -- целочисленное линейное программирование (стр. 55)
- БЛП -- булево линейное программирование (стр. ??)
- ДП -- динамическое программирование (стр. 59)
Математические обозначения
- Π -- массовая задача (стр. 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)
- -- матрица, составленная из матрицы A, и дописанного справа столбца b (стр. 28)
- -- скалярное произведение векторов x,y : (стр. ??)
- -- минимальное приближение, при котором система линейных неравенств имеет решение (стр. 29)
Классы сложности задач
- P -- класс полиномиальных разрешимых задач (стр. 8)
- NP -- класс недетерминированно полиномиальных разрешимых задач (стр. 9, 10)
- co-P -- класс задач, дополнительных к полиномиально разрешимым задачам (стр. 12)
- co-NP -- класс задач, дополнительных к недетерменированно полиномиально разрешимым задачам (стр. 12)
- NPC -- класс NP-полных задач (стр. 14)
- PSPACE -- класс задач, требующих для решения не более чем полиномиальной памяти (стр. 19)