Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Введение в курс метрической теории и метрологии программ

НЕОБХОДИМЫЕ СВЕДЕНИЯ ИЗ АЛГОРИТМИЧЕСКОЙ ТЕОРИИ СЛОЖНОСТИ И ИНЖЕНЕРНОЙ ПСИХОЛОГИИ

1.1. Определение алгоритмической сложности

Это понятие играет в информатике такую же фундаментальную роль, как энергия или энтропия в технике. В обычном словоупотреблении термин «сложность» имеет множество оттенков. Математическая формализация данного понятия базируется на идее описания: очевидно, что чем сложнее объект, тем длиннее описывающий его текст. Однако решающую роль при таком подходе имеет выбор способа описания. Ограничим, с целью определенности, множество «объектов» различными символьными строками, т. е. типичными объектами информатики. Пусть, например,

  • 0011001100110011.....,
  • 101101101101101.......,
  • 1101110010100011.....
  • - начальные фрагменты двоичных последовательностей. Первые два из них, будучи периодическими, могут быть «описаны» такими псевдопрограммами, как «печать 0011 п раз», «печать 101 п раз», где п - произвольное целое число. Однако в случае третьей последовательности из-за нерегулярности может оказаться, что более короткая запись, чем сама последовательность, в принципе невозможна. Рассмотрим еще один пример. Основание натуральных логарифмов е = 2,711828.... имеет бесконечное число цифр, но описывается конечной формулой (алгоритмом)

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

где р - программа (код), по которой ср восстанавливает х; /(/?) - ее длина (количество двоичных разрядов), a Z - множество всех допустимых программ.

Это формально-математическое определение имеет простую содержательную трактовку: за меру сложности произвольной последовательности символов из некоторого фиксированного алфавита принимается длина (количество двоичных разрядов) самой короткой программы, генерирующей эту последовательность (как это показано в приведенных выше примерах).

Из этого определения видно, что речь идет не о сложности алгоритмов, а об алгоритмическом подходе к определению понятия сложности.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы