СРАВНЕНИЕ ОЦЕНОК СЛОЖНОСТИ ХОЛСТЕДА И КОЛМОГОРОВА с
Скачать PDF
Аннотация: Исследуется относительно новый метод оценки сложности программ по Холстеду. Описан метод оценки вычислительной сложности по Колмогорову. Показана близость идей оценки. В одном случае (Колмогоров) оценивается обрабатываемая последовательность и программная последовательность. В другом случае (Холстед) оценивается программная последовательность и последовательность словаря или алфавита. Показана целесообразность введения термина программная конструкция, чтобы отличать описание программы от ее реализации.
Ключевые слова: программа, стандартизация, сложность, Колмогоровская сложность, сложность по Холстеду, программная конструкция
Для цитирования: Цветков В.Я., Терентьев П.В. Сравнение оценок сложности холстеда и колмогорова с // Электронный научный журнал «ИТ-Стандарт». – 2019. – № 1. – С. .