Методы Оптимизации, Теормин
Материал из eSyr's wiki.
Теормин
Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.
Массовая задача П:
- список свободных параметров;
- формулировка свойств, которым должно удовлетворять решение задачи.
П есть множество индивидуальных задач Невозможно разобрать выражение (неизвестная ошибка): I \in П . Индивидуальная задача получается, всем всем параметрам присвоить конкретные значения. Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: Невозможно разобрать выражение (неизвестная ошибка): П \rightarrow E*
называется кодировкой задачи П.
Алгоритм А решает массовую задачу П, если для любой Невозможно разобрать выражение (неизвестная ошибка): I \in П
: А применим к I, то есть останавливается за конечное число шагов .
Кодировка задачи П
tA() - число шагов алгоритма А для входа E*. Временная сложность Невозможно разобрать выражение (неизвестная ошибка): TA(n) = max {tA() для ||n} .
