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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.)
(Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.)
Строка 8: Строка 8:
P есть множество индивидуальных задач <math>I \in P</math>. Индивидуальная задача получается, всем всем параметрам присвоить конкретные значения.
P есть множество индивидуальных задач <math>I \in P</math>. Индивидуальная задача получается, всем всем параметрам присвоить конкретные значения.
 +
Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: <math>P \rightarrow E*</math> называется кодировкой задачи П.
Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: <math>P \rightarrow E*</math> называется кодировкой задачи П.
 +
'''Алгоритм А решает массовую задачу''' П, если для любой <math>I \in P</math> : А применим к I, то есть останавливается за конечное число шагов .
'''Алгоритм А решает массовую задачу''' П, если для любой <math>I \in P</math> : А применим к I, то есть останавливается за конечное число шагов .
-
Кодировка задачи P:
+
'''Кодировка задачи P''':
-
Отобраение
+
Отобраение <math>e: P \rightarrow E* </math>, обладающее следующими свойствами:
 +
 
 +
* Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
 +
* <math>e, e^{-1}</math> -- полиномиально вычислимы
 +
* Кодировка не избыточна, то есть для любой другой кодировки <math>e_1</math>, удовлетворяющей 1 и 2 условиям справедливо:
 +
<math>\exists p(.): \forall I 'in P |e(I)| < p(e_{1}(I))</math>
 +
 
 +
'''Язык массовой задачи''' -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания):
 +
<math>L(P, e) = e(Y(P)) = {\sigma \in E*| \sigma = e(I), I \n Y(I)}</math>
 +
 
 +
'''Язык алгоритма''' -- множество слов, принимаемых А
 +
 
 +
Алгоритм A '''решает''' массовую задачу П, с кодировкой e, если <math>L(e, P) = L(A)</math>
 +
 
 +
<math>t{A}(\sigma)</math> - число шагов алгоритма А для входа<math>\sigma \in E*</math> (число шагов).
-
tA() - число шагов алгоритма А для входа E*. Временная сложность <math>TA­(n) = max {tA() для ||n}</math>.
+
Временная сложность <math>TA­(n) = max {tA(\sigma)} \sigma /in E*& |\sigma| < n</math>.

Версия 06:35, 7 июня 2009

Теормин

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

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

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

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

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

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

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

  • Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
  • e,e − 1 -- полиномиально вычислимы
  • Кодировка не избыточна, то есть для любой другой кодировки e1, удовлетворяющей 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)

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

Временная сложность Невозможно разобрать выражение (неизвестная ошибка): TA­(n) = max {tA(\sigma)} \sigma /in E*& |\sigma| < n .

Личные инструменты
Разделы