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

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

Версия от 06:15, 7 июня 2009; Tehhi (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Теормин

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

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

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

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

называется кодировкой задачи П.

Алгоритм А решает массовую задачу П, если для любой Невозможно разобрать выражение (неизвестная ошибка): I \in П

: А применим к I, то есть останавливается за конечное число шагов .

Кодировка задачи П

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

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