ПОИСК Статьи Рисунки Таблицы Что такое алгоритм из "Классические и квантовые вычисления" Неформально алгоритм — это однозначно определённая совокупность инструкций ио преобразованию исходных данных в результат, причём все инструкции элементарны, т. е. нри их выполнении нам придётся только механически следовать ирединсаниям, как если бы мы были роботами от нас не потребуется ни нонимання, ни искусства, ни изобретательности [5, с. 270]. [c.17] Дадим теперь формальное определение алгоритма. [c.18] Если МТ останавливается, используемая часть леиты в достигнутом иеред остановкой состоянии называется результатом работы МТ. [c.19] Определение 1.1. Частичная функция / пз А в А называется вы-чис.лимой, если сун ествует мангина Тьюринга М, для которой 1рм = / При этом будем говорить, что / вычислима на М. [c.20] Пе все функции вычислимы. Это ясно пз сравнения мощности множества функций (континуум) и мощности множества машин Тьюринга (счётное множество). Более интересные примеры см. в задачах 1.3-1.5. [c.20] Понятия вычислимой функции н разрешимого предиката будут использоваться и для функций (предикатов) от многих переменных. [c.20] Предикат от нескольких переменных разрешим, если его характеристическая функция вычислима. [c.20] Не вдаваясь в обсужденне тезиса Чёрча, заметим, что в настоящее время нет серьёзных оснований подвергать его сомнению. Все известные в настоящее время алгоритмы реализуются машинами Тьюринга. Подробное изложение теории алгоритмов читатель может найти в книгах [1, 5, б, 10, 13, 16, 17]. Мы же ограничимся краткими неформальными пояснениями приёмов программирования на машннах Тьюринга. [c.21] Представив себя в такой ситуации, легко сообразить, что можно, запоминая несколько символов, выполнять любые действия иа ограниченном количестве подряд идущих страниц можно ставить на страницах дополнительные пометки (ограниченное количество на каждой) можно листать тетрадь, нока не найдётся нужная пометка можно копировать символы на свободные страницы тетради. Свободные места иа страницах можно также использовать для хранения вспомогательных слов произвольной длины (как и входное слово, они записываются по одному символу на страницу), над которыми может поработать другой человек (это называется вызов нодирограммы ). В частности, эти вспомогательные слова позволяют поддерживать счётчики (целочисленные переменные). Пспользуя счётчики, можно адресоваться к ячейкам памяти по их номеру. [c.21] Формализовать это понятие непросто. Принятый сейчас способ состоит в том, что выделяются классы тех функций илн предикатов, вычисление которых возможно при задаваемых ограничениях на потребляемые ресурсы. Принадлежность функции тому или иному слож-ностному классу служит удобной характеристикой возмои ностей её эффективного вычисления, не связанной с конкретными реализациями алгоритмов. [c.22] Наиболее важные классы получаются, если накладывать ограничения иа рост времени работы и/или используемой памяти в зависимости от длины входного слова. А наиболее важное различие между эффективными и неэффективными вычислениями задаётся функциями полиномиального роста. Функция /(п) — полиномиального роста, если для некоторой константы (I ири достаточно больших п выполняется неравенство /(п) С п . В этом случае будем использовать обозначение /(п) = ро1у(п). [c.22] Определение 1.3. Предикат / на множестве Ш принадлежит классу Р (и называется полиномиально вычислимым), если его характеристическая функция вычислима на машине Тьюринга М, для которой Тм(п) = ро1у(п). [c.22] Схема вычисляет функцию /, если для любых значений j,. . ., результатом вычисления является f(xi,. . ., х ). [c.23] Схему можно также представлять в виде ориентированного ациклического графа, у [которого вершины входной степени О (входы) помечены исходными переменными остальные вершины (функциональные элементы) помечены функциями из базиса (при этом входная степень вершины должна совпадать с количеством аргументов её пометки) рёбра помечены числами, указывающими номера аргументов вершины выходной степени О (выходы) помечены переменными, описывающими результат работы схемы. Вычисление иа графе определяется индуктивно как только известны значения всех вершин у, . . . , у , из которых ведут рёбра в данную вершину v, вершина v получает значение у = J (t/i,. . ., t/f j, где / — базисная функция, которой помечена вершина. При переходе к графу схемы мы опускаем несущественные присваивания, которые ни разу не используются иа пути к выходным вершинам, так что они никак не влияют на результат вычисления. [c.23] Вернуться к основной статье