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