АЛГОРИТМА СЛОЖНОСТЬ это:

АЛГОРИТМА СЛОЖНОСТЬ

описания - величина, характеризующая длину описания алгоритма. В зависимости от точной концепции алгоритма А. с. описания уточняется по-разному. Единого достаточно устоявшегося уточнения к настоящему моменту (1977) не существует. Ниже рассмотрены наиболее часто встречающиеся случаи.

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

Предложено также и аксиоматическое определение А. с. описания (см. [2]). Рассмотрим это определение применительно к машинам Тьюринга. Пусть - естественная нумерация машин Тьюринга, характеризующаяся тем, что по номеру машины можно эффективно восстановить саму машину (т. е. ее программу), а по машине (т. е. программе) - ее номер. Общерекурсивная функция наз. мерой сложности машин (при этом наз. сложностью машины ) тогда и только тогда, когда: а) для любого усуществует не более чем конечное число машин, имеющих сложность у;б) существует эффективная процедура, позволяющая определить для любого увез те машины, к-рые имеют сложность у.

Пусть s - произвольная мера сложности машин Тьюринга. Если U - произвольный эффективно (т. е. алгоритмически) перечнслимый бесконечный подкласс машин Тьюринга, то существует машина Т, принадлежащая U, и существует машина Т' (не обязательно из U).такая, что Т' и Т вычисляют одну и ту же функцию, и сложность Т' значительно меньше, чем сложность Т. Отсюда, в частности, вытекает существование примитивно рекурсивных функций, наименьшая сложность к-рых в примитивно рекурсивной форме (т. е. через схемы примитивной рекурсии) значительно больше, чем их наименьшая сложность в общерекурсивной форме (т. е. через схемы общей рекурсии). Пусть под сложностью нормальных алгорифмов и машин Тьюринга понимаются, соответственно, длина изображения и число внутренних состоянии, Тогда любую функцию алгебры логики от N переменных (см. Булева функция).можно реализовать (см. [3]): а) нормальным алгорифмом в m-буквенном алфавите со сложностью б) машиной Тьюринга с m-буквенным внешним алфавитом со сложностью .

С 60-х гг. 20 в. начато изучение сложности алгоритмов, решающих конечные куски алгоритмически неразрешимых массовых проблем (так наз. ограниченные ал-горитмич. проблемы). А. А. Марков рассмотрел следующую задачу: для любой функции алгебры логики от Nпеременных построить изображение нормального алгорифма в алфавите реализующего данную функцию и имеющего минимальную сложность среди всех таких алгорифмов. Показано (см. [1], [4]), что сложность нормального алгорифма, решающего эту задачу, имеет порядок 2N. Изучен также вопрос о сложности алгоритмов, решающих для первых пнатуральных чисел проблему вхождения в рекурсивно перечислимое множество (сложность n-кусков рекурсивно перечислимых множеств). Показано, что в случае нормальных алгорифмов эта сложность по порядку не превосходит п что в общем случае эта оценка не может быть понижена. В то же время существуют множества, задаваемые с помощью достаточно простых логич. средств, к-рые имеют сложность n-кусков порядка n. Показано также, что при общерекурснвном ограничении времени работы алгорифмов сложность n-кусков рекурсивно перечислимых множеств может возрастать экспоненциально и по порядку достичь величины п.

Понятие А. с. описания используется в основном при уточнении вопроса о том, какова минимальная сложность алгоритма, строящего тот или иной конечный объект. Эту минимальную сложность часто наз. просто сложностью конечного объекта (при данном уточнении понятия А. с. описания).

Определение сложности конечных объектов впервые было предложено А. Н. Колмогоровым (см. Алгоритмическая теория информации). Оказывается, что между сложностью по Колмогорову, сложностью этих же объектов, выражаемой через длину изображения нормального алгорифма в m-буквенном алфавите, и сложностью , выражаемой числом внутренних состояний машины Тьюринга с m-буквенным внешним алфавитом, существуют асимптотически точные соотношения


Лит.:[1] Марков А. А., "Изв. АН СССР. Сер. матем.", 1967, т. 31, № 1, с. 168-208; [2] Блюм М., сб. "Проблемы математической логики", М., 1970, с. 423-31; [3] Кузьмин В. А., сб. ((Проблемы кибернетики", 1965, вып. 13, с. 75-96; [4] Петри Н. В., "Докл. АН СССР", 1969, т. 185, № 1, с. 37-39; [5] Звонкий А. К., Левин Л. А., "Успехи матем. наук", 1970, т. 25, вып. 6, с. 85-127.

Я. М. Барздинъ.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "АЛГОРИТМА СЛОЖНОСТЬ" в других словарях:

  • АЛГОРИТМА СЛОЖНОСТЬ — вычислений функция, дающая числовую оценку трудности (громоздкости) процессов применения алгоритма к исходным данным. Уточнением А. с. вычислений служит понятие сигнализирующей функции (или просто сигнализирующей) функции, к рая задается… …   Математическая энциклопедия

  • сложность (алгоритма или математической задачи) — — [http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23] Тематики защита информации EN complexity …   Справочник технического переводчика

  • Сложность вычисления (битовая) — Для оценки качества быстрого метода или алгоритма используется функция сложность вычисления (битовая). Будем считать, что числа записаны в двоичной системе счисления, знаки которой и называются битами. Опр.1. Запись знаков , сложение, вычитание и …   Википедия

  • СЛОЖНОСТЬ ОПЕРАТОРСКОЙ ДЕЯТЕЛЬНОСТИ — совокупность объективных факторов, влияющих на качество и продолжительность выполнения человеком требуемых функций в СЧМ. С. о. д. разделяется на несколько видов, каждый из которых характеризуется совокупностью факторов, определенным образом… …   Энциклопедический словарь по психологии и педагогике

  • Сложность алгоритма — …   Википедия

  • Вычислительная сложность — В информатике и теории алгоритмов вычислительная сложность алгоритма это функция, определяющая зависимость объёма работы, выполняемой некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией… …   Википедия

  • Временная сложность алгоритма — Содержание 1 Временная и пространственная сложности 1.1 Асимптотическая сложность 1.2 Примеры …   Википедия

  • Экспоненциальная сложность — или экспоненциальное время в теории сложности алгоритмов, время решения задачи, ограниченное экспонентой от размерности задачи. Другими словами, если размерность задачи возрастает линейно, время её решения возрастает экспоненциально. Различие… …   Википедия

  • Колмогоровская сложность — В алгоритмической теории информации колмогоровская сложность объекта (такого, как текст) есть мера вычислительных ресурсов, необходимых для точного определения этого объекта. Колмогоровская сложность также известна как описательная сложность,… …   Википедия

  • временная сложность (алгоритма) — — [http://www.rfcmd.ru/glossword/1.8/index.php?a=index&d=4748] Тематики защита информации EN time complexity …   Справочник технического переводчика

Книги

Другие книги по запросу «АЛГОРИТМА СЛОЖНОСТЬ» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»