Редактирование: Методы оптимизации, обозначения
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 7: | Строка 7: | ||
* ''' ДМТ ''' -- детерминированная машина Тьюринга (стр. 9) | * ''' ДМТ ''' -- детерминированная машина Тьюринга (стр. 9) | ||
* ''' НДМТ ''' -- недетерминированная машина Тьюринга (стр. 9) | * ''' НДМТ ''' -- недетерминированная машина Тьюринга (стр. 9) | ||
- | * ''' ВЫП ''' -- проверить на выполнимость конечной КНФ (стр. 14) | ||
- | * ''' ЦЛН ''' -- задача о целочисленном решении сислемы линейных неравенств (стр. 15) | ||
- | * ''' БЛН ''' -- задача о булевом решении сислемы линейных неравенств (стр. 16) | ||
- | * ''' 3-ВЫП ''' -- проверить на выполнимость конечной КНФ от ровно трёх переменных (стр. 17) | ||
- | * ''' ЗР ''' -- задача о рюкзаке (стр. 19) | ||
- | * ''' ПППС ''' -- полностью полиномиальная приближенная схема (стр. 24) | ||
* ''' ЛП ''' -- линейное программирование (стр. 25) | * ''' ЛП ''' -- линейное программирование (стр. 25) | ||
* '''озЛП''' -- основная задача линейного программирования (стр. 25) | * '''озЛП''' -- основная задача линейного программирования (стр. 25) | ||
* '''ЗМП''' -- задача математического программирования (стр. 39) | * '''ЗМП''' -- задача математического программирования (стр. 39) | ||
- | * '''МВГ''' -- метод ветвей и границ (стр. 54) | ||
* '''ЦЛП''' -- целочисленное линейное программирование (стр. 55) | * '''ЦЛП''' -- целочисленное линейное программирование (стр. 55) | ||
* '''БЛП''' -- булево линейное программирование (стр. ??) | * '''БЛП''' -- булево линейное программирование (стр. ??) | ||
- | * '''ДП''' -- динамическое программирование (стр. 59) | ||
== Математические обозначения == | == Математические обозначения == | ||
Строка 29: | Строка 21: | ||
* <math>L(\Pi, e)</math> -- язык задачи (стр. 7) | * <math>L(\Pi, e)</math> -- язык задачи (стр. 7) | ||
* <math>T_A(n)</math> -- временная сложность алгоритма <math>A</math> (стр. 8) | * <math>T_A(n)</math> -- временная сложность алгоритма <math>A</math> (стр. 8) | ||
- | * <math> | + | * <math>\Pi</math> -- массовая задача (стр. 4) |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
== Классы сложности задач == | == Классы сложности задач == | ||
* '''P''' -- класс полиномиальных разрешимых задач (стр. 8) | * '''P''' -- класс полиномиальных разрешимых задач (стр. 8) | ||
* '''NP''' -- класс недетерминированно полиномиальных разрешимых задач (стр. 9, 10) | * '''NP''' -- класс недетерминированно полиномиальных разрешимых задач (стр. 9, 10) | ||
- | * '''co-P''' -- класс задач, дополнительных к полиномиально разрешимым задачам (стр. 12) | ||
- | * '''co-NP''' -- класс задач, дополнительных к недетерменированно полиномиально разрешимым задачам (стр. 12) | ||
- | * '''NC''' (Nick Сlass) -- класс задач, решаемых за время, ограниченное полиномом от '''логарифма''' длины входа и требующих полиномиальной памяти.(стр. 19) | ||
- | * '''NPC''' -- класс '''NP'''-полных задач (стр. 14) | ||
- | * '''PSPACE''' -- класс задач, требующих для решения не более чем полиномиальной памяти (стр. 19) | ||
- | {{Курс Методы оптимизации}} |