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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: = Теормин = == Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массо...)
(Определения индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.)
Строка 7: Строка 7:
* формулировка свойств, которым должно удовлетворять решение задачи.
* формулировка свойств, которым должно удовлетворять решение задачи.
-
П есть множество индивидуальных задач <math>I \in П</math>. Индивидуальная задача получается, всем всем параметрам присвоить конкретные значения.
+
P есть множество индивидуальных задач <math>I \in P</math>. Индивидуальная задача получается, всем всем параметрам присвоить конкретные значения.
-
Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: <math>П \rightarrow E*</math> называется кодировкой задачи П.
+
Пусть E - конечный алфавит, а E* - множество слов в этом алфавите. Отображение e: <math>P \rightarrow E*</math> называется кодировкой задачи П.
-
'''Алгоритм А решает массовую задачу''' П, если для любой <math>I \in П</math> : А применим к I, то есть останавливается за конечное число шагов .
+
'''Алгоритм А решает массовую задачу''' П, если для любой <math>I \in P</math> : А применим к I, то есть останавливается за конечное число шагов .
-
Кодировка задачи П
+
Кодировка задачи P:
 +
Отобраение
tA() - число шагов алгоритма А для входа E*. Временная сложность <math>TA­(n) = max {tA() для ||n}</math>.
tA() - число шагов алгоритма А для входа E*. Временная сложность <math>TA­(n) = max {tA() для ||n}</math>.

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

Теормин

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

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

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

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

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

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

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