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

В этом заключена суть характеристики; теперь мы перейдем к ее формализации. Входные данные вычислительной задачи могут быть закодированы в виде конеч- ной двоичной строки 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

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

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. АЛГОРИТМ
  3. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  7. Алгоритм избавления от боли
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.