Материал из eSyr's wiki.

Теормин

Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.

Массовая задача П:

• список свободных параметров;
• формулировка свойств, которым должно удовлетворять решение задачи.

P есть множество индивидуальных задач . Индивидуальная задача получается, всем всем параметрам присвоить конкретные значения. Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: называется кодировкой задачи П. Алгоритм А решает массовую задачу П, если для любой  : А применим к I, то есть останавливается за конечное число шагов .

Кодировка задачи P: Отобраение

tA() - число шагов алгоритма А для входа E*. Временная сложность Невозможно разобрать выражение (неизвестная ошибка): TA­(n) = max {tA() для ||n} .