Задачи и алгоритмы

В этом заключена суть характеристики; теперь мы перейдем к ее формализации. Входные данные вычислительной задачи могут быть закодированы в виде конеч- ной двоичной строки 5. Длина строки 5 обозначается ⅛ Задача принятия реше- ния X будет описываться множеством строк, для которых возвращается ответ «да».

Алгоритм A для задачи принятия решения получает входную строку 5 и возвраща- ет «да» или «нет» — это возвращаемое значение будет обозначаться A(5). Алгоритм A решает задачу X, если для всех строк 5 условие A(5) = да выполняется в том, и только в том случае, если 5 X.

Как обычно, мы говорим, что A имеет полиномиальное время выполнения, если существует такая полиномиальная функция p(), что для каждой входной строки 5 алгоритм A завершается для 5 не более чем за О(р(Н)) шагов. До настоящего момен- та мы занимались задачами, которые решались за полиномиальное время. В при- веденной выше записи этот факт можно выразить как множество P всех задач X, для которых существует алгоритм A с полиномиальным временем выполнения, решающий X.

<< | >>

↑

Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задачи и алгоритмы:

- Windows - Архитектура компьютера - Интернет - Информатика - Компьютер - Компьютерные и телекоммуникационные системы - Программирование - Социальные сети -

- Английский язык - Астрология - Астрономия - Биология - Военная литература - Журналистика - Компьютерная инженерия - Педагогика - Право - Психология - Социология -