Методы Оптимизации, Теормин

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

Версия от 06:36, 7 июня 2009; Tehhi (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Теормин

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

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

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

P есть множество индивидуальных задач $I \in P$ . Индивидуальная задача получается, всем всем параметрам присвоить конкретные значения.

Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: $P \rightarrow E*$ называется кодировкой задачи П.

Алгоритм А решает массовую задачу П, если для любой $I \in P$ : А применим к I, то есть останавливается за конечное число шагов .

Кодировка задачи P: Отобраение $e: P \rightarrow E*$ , обладающее следующими свойствами:

Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
$e, e - 1$ -- полиномиально вычислимы
Кодировка не избыточна, то есть для любой другой кодировки $e 1$ , удовлетворяющей 1 и 2 условиям справедливо:

$\exists p(.): \forall I 'in P |e(I)| < p(e_{1}(I))$

Язык массовой задачи -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания): Невозможно разобрать выражение (неизвестная ошибка\n): L(P, e) = e(Y(P)) = {\sigma \in E*: \sigma = e(I), I \n Y(I)}

Язык алгоритма -- множество слов, принимаемых А

Алгоритм A решает массовую задачу П, с кодировкой e, если $L (e, P) = L (A)$

$t A (σ)$ - число шагов алгоритма А для входа $\sigma \in E*$ (число шагов).