Методы Оптимизации, Теормин
Материал из eSyr's wiki.
(→Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.) |
(→Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.) |
||
| Строка 22: | Строка 22: | ||
'''Язык массовой задачи''' -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания): | '''Язык массовой задачи''' -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания): | ||
| - | <math>L(P, e) = e(Y(P)) = {\sigma \in E* | + | <math>L(P, e) = e(Y(P)) = {\sigma \in E*: \sigma = e(I), I \n Y(I)}</math> |
'''Язык алгоритма''' -- множество слов, принимаемых А | '''Язык алгоритма''' -- множество слов, принимаемых А | ||
| Строка 30: | Строка 30: | ||
<math>t{A}(\sigma)</math> - число шагов алгоритма А для входа<math>\sigma \in E*</math> (число шагов). | <math>t{A}(\sigma)</math> - число шагов алгоритма А для входа<math>\sigma \in E*</math> (число шагов). | ||
| - | Временная сложность <math>TA(n) = max {tA(\sigma)} \sigma /in E*& | + | Временная сложность <math>TA(n) = max {tA(\sigma)} \sigma /in E* & \sigma < n</math>. |
Версия 06:36, 7 июня 2009
Теормин
Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.
Массовая задача П:
- список свободных параметров;
- формулировка свойств, которым должно удовлетворять решение задачи.
P есть множество индивидуальных задач 
. Индивидуальная задача получается, всем всем параметрам присвоить конкретные значения.
Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: 
называется кодировкой задачи П.
Алгоритм А решает массовую задачу П, если для любой : А применим к I, то есть останавливается за конечное число шагов .
Кодировка задачи P:
Отобраение 
, обладающее следующими свойствами:
- Возможность однозначно декодировать, то есть у двух различных ИЗ не может быть одинаковых кодировок.
- e,e − 1 -- полиномиально вычислимы
- Кодировка не избыточна, то есть для любой другой кодировки e1, удовлетворяющей 1 и 2 условиям справедливо:
Язык массовой задачи -- это множество правильных слов, то есть слов, соответствующих ИЗ, имеющим положительный ответ(подразумевается задача распознавания): Невозможно разобрать выражение (неизвестная ошибка\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(σ) - число шагов алгоритма А для входа
(число шагов).
Временная сложность Невозможно разобрать выражение (неизвестная ошибка): TA(n) = max {tA(\sigma)} \sigma /in E* & \sigma < n .
