Методы Оптимизации, Теормин
Материал из eSyr's wiki.
Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.
Массовая задача П:
- список свободных параметров;
- формулировка свойств, которым должно удовлетворять решение задачи.
P есть множество индивидуальных задач 
. Индивидуальная задача получается, всем всем параметрам присвоить конкретные значения.
Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: 
называется кодировкой задачи П.
Алгоритм А решает массовую задачу П, если для любой : А применим к I, то есть останавливается за конечное число шагов .
Кодировка задачи P:
Отобраение 
, обладающее следующими свойствами:
- Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
- e,e − 1 -- полиномиально вычислимы
- Кодировка не избыточна, то есть для любой другой кодировки e1, удовлетворяющей 1 и 2 условиям справедливо:
Язык массовой задачи -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания):
Язык алгоритма -- множество слов, принимаемых А
Алгоритм A решает массовую задачу П, с кодировкой e, если L(e,P) = L(A)
tA(s) - число шагов алгоритма А для входа
(число шагов).
Временная сложность 
.
Задачи распознавания свойств. Классы P и NP.
Задача расползавания свойств: Это задачи ответ на которые должен быть -- "да", "нет"
Из ИЗ выделим такие задачи, которые дают ответ -- "да". Обозначим множество таких задач -- Y
Пусть D -- всевозможное значенте параметров задачи.
Формально ЗРС определяются следующей парой: [D(П), Y(П)]
Класс полиномиально разрешимых задач
Это такие задачи, временной сложность алгоритма решения которых ограниченна полиномом.
Например, к таким задачам отосится задача распознавания четности числа.
Теорема об экспоненциальной временной оценке для задач из класса NP.
Для любой П из NP существует ДМТ A, решающая ее с не более чем экспоненциальной временной сложностью: Невозможно разобрать выражение (неизвестная ошибка): T_{A}(n) <= 2{{p(n)} .
