Методы оптимизации, обозначения
Материал из eSyr's wiki.
(Различия между версиями)
(→Сокращения) |
(→Сокращения) |
||
| Строка 3: | Строка 3: | ||
== Сокращения == | == Сокращения == | ||
| + | * ''' КМ (ЗК) ''' -- коммивояжёр (задача о коммивояжёре) (стр. 6) | ||
| + | * ''' ПЧ ''' -- задача распознавания простоты числа (стр. 8) | ||
| + | * ''' ДМТ ''' -- детерминированная машина Тьюринга (стр. 9) | ||
| + | * ''' НДМТ ''' -- недетерминированная машина Тьюринга (стр. 9) | ||
* ''' ЛП ''' -- линейное программирование (стр. 25) | * ''' ЛП ''' -- линейное программирование (стр. 25) | ||
* '''озЛП''' -- основная задача линейного программирования (стр. 25) | * '''озЛП''' -- основная задача линейного программирования (стр. 25) | ||
| Строка 8: | Строка 12: | ||
* '''ЦЛП''' -- целочисленное линейное программирование (стр. 55) | * '''ЦЛП''' -- целочисленное линейное программирование (стр. 55) | ||
* '''БЛП''' -- булево линейное программирование (стр. ??) | * '''БЛП''' -- булево линейное программирование (стр. ??) | ||
| + | |||
| + | == Математические обозначения == | ||
| + | |||
| + | * <math>\Pi</math> -- массовая задача (стр. 4) | ||
| + | * <math>I \in \Pi</math> -- индивидуальная задача (стр. 4) | ||
| + | * <math>\Sigma</math> -- алфавит кодирования (стр. 7) | ||
| + | * <math>e</math> -- кодировка задачи <math>\Pi</math> (стр. 7) | ||
| + | * <math>L(\Pi, e)</math> -- язык задачи (стр. 7) | ||
| + | * <math>T_A(n)</math> -- временная сложность алгоритма <math>A</math> (стр. 8) | ||
| + | * <math>\Pi</math> -- массовая задача (стр. 4) | ||
| + | |||
| + | == Классы сложности задач == | ||
| + | * '''P''' -- класс полиномиальных разрешимых задач (стр. 8) | ||
| + | * '''NP''' -- класс недетерминированно полиномиальных разрешимых задач (стр. 9, 10) | ||
Версия 16:28, 8 июня 2009
К каждому определению в скобочках указывается номер страницы в методичке, на которой впервые данное определение встречается
Сокращения
- КМ (ЗК) -- коммивояжёр (задача о коммивояжёре) (стр. 6)
- ПЧ -- задача распознавания простоты числа (стр. 8)
- ДМТ -- детерминированная машина Тьюринга (стр. 9)
- НДМТ -- недетерминированная машина Тьюринга (стр. 9)
- ЛП -- линейное программирование (стр. 25)
- озЛП -- основная задача линейного программирования (стр. 25)
- ЗМП -- задача математического программирования (стр. 39)
- ЦЛП -- целочисленное линейное программирование (стр. 55)
- БЛП -- булево линейное программирование (стр. ??)
Математические обозначения
- Π -- массовая задача (стр. 4)
-
-- индивидуальная задача (стр. 4)
- Σ -- алфавит кодирования (стр. 7)
- e -- кодировка задачи Π (стр. 7)
- L(Π,e) -- язык задачи (стр. 7)
- TA(n) -- временная сложность алгоритма A (стр. 8)
- Π -- массовая задача (стр. 4)
Классы сложности задач
- P -- класс полиномиальных разрешимых задач (стр. 8)
- NP -- класс недетерминированно полиномиальных разрешимых задач (стр. 9, 10)
