Полная версия

Главная arrow Информатика arrow Введение в курс метрической теории и метрологии программ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Дополнительные сведения об алгоритмической сложности

А. Определение.

Введение понятия алгоритмической сложности объекта существенным образом опирается на понятие вычислимой функции, формализация которого в свою очередь осуществлена в рамках многих подходов [7, 30]. Наиболее известные из них - это теория машин Тьюринга, теория частично-рекурсивных функций и теория нормальных алгоритмов Маркова. С формально-логической точки зрения эти концепции эквивалентны, однако для первого знакомства наиболее удобной представляется трактовка вычислимых функций в терминах вычислительных устройств.

Теоретически любая универсальная вычислительная машина, имеющая неограниченные ресурсы, может быть использована для этой цели. Функция /называется вычислимой, если в системе команд такой машины существует программа, которая за конечное время сопоставляет входу х выход у =Дх), когда х е Df, и не останавливается (не находит решения) для всякого х Df. Иначе / называется невычислимой.

Если программу р, написанную в системе команд некоторой машины а, трактовать как число, то зависимость между входом х, р и выходом у можно формально записать в виде функции сра(х,р) = у (называемой, кстати, в соответствии с одним из упомянутых подходов, частично-рекурсивной). Очевидно, что одной из главных характеристик сложности решения задачи является кратчайшая длина программы для машины с выбранной системой команд. При этом вход х, принадлежащий некоторому множеству X, можно трактовать как задачу из класса X, а у - ее решение - как элемент некоторого множества Y. В других случаях удобнее считать х и у последовательностями в некотором алфавите, интерпретируемыми в соответствии с конкретной постановкой вопроса. Тогда вместо алгоритма решения задачи говорят об алгоритме восстановления последовательности yeY по последовательности х g X (или по коду объекта х код объекта у). Пусть ?(р) - длина программы р в двоичном представлении, т. е. число входящих в него нулей и единиц; S - множество всех допустимых программ. Тогда под сложностью вычисления решения у задачи х (можно также сказать восстановления последовательности у по последовательности х) будем понимать минимальную длину допустимой программы р машины с системой команд а, если Фа(р,х) = У ? Формальная запись этого определения сложности вычисления решения у задачи х имеет вид

Величину К($а (у | х) называют алгоритмической сложностью. Очевидно, что речь идет не о сложности алгоритма решения массовой задачи класса X, а об алгоритмическом способе описания объектов. При этом длина его зависит от индивидуальных задач х е X.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>