М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 45
Текст из файла (страница 45)
Функция, вычисляемая семейством схем (С„), — это такая функция С( ), что С(х) = С„(х), если число х содержит п битов. Если, например, ф— схема, возводящая в квадрат 180 Глава 3. Введение в информатику и битовое число, то семейство схем (С„) вычисляет функцию С(х) = хз, где х — натуральное число. Недостаточно однако рассматривать произвольные семейства схем; на практике нам нужен алгоритм для построения схемы. В самом деле, если не налагать на семейство схем никаких ограничений, то мы сможем вычислять любую функцию в том числе и такую, про которую нельзя надеяться, что ее удастся вычислить с помощью разумной вычислительной модели. Пусть, например, 6„(х) — функция остановки, ограниченная на п-битовые значения х.
Тогда ܄— функция, переводящая и битов в 1 бит, и мы доказали, что существует схема С„, вычисляющая Ь„( ). Следовательно, семейство схем (С„) вычисляет функцию остановки! Однако мы не можем использовать это семейства схем для решения проблемы остановки, так как не указали алгоритм, позволяющий построить схему С„для всех значений и. Если добавить условие, что такой алгоритм должен существовать, то мы придем к понятию равномерного семейства схем. Семейство схем (С„) называется однороднььм семейством схем, если существует выполнимый на машине Тьюринга алгоритм, который, получив на входе и, генерирует описание схемы С„.
Иными словами, на выходе алгоритма получается описание того, какие элементы содержатся в схеме С„, как они связаны друг с другом, какие нужны вспомогательные биты, где используются операции РАМОПТ и СКОЯЯОУЕК и откуда надо считывать выходные биты. Например, описанное выше семейство схем, возводящих и-битовые числа в квадрат, бесспорно является однородным, так как существует алгоритм, который по данному и выдает описание схемы, возводящей в квадрат и-битовые числа.
Вы можете рассматривать такой алгоритм как средство, с помощью которого инженер может получить описание такой схемы (а, следовательно, и построить ее) для произвольного и. Напротив, семейство схем, не являющееся однородным, называется неоднородным. В этом случае не существует алгоритма построения схемы для произвольного и, что не позволяет инженеру построить схемы для вычисления функций, например функции остановки. На интуитивном уровне однородное семейство схем — это семейство, которое можно получить с помощью какого-либо разумного алгоритма.
Можно показать, что класс функций, вычислимых с помощью однородных семейств схем, в точности совпадает с классом функций, вычислимых с помощью машины Тьюринга. Если наложить условие однородности, то результаты, полученные с использованием модели вычислений, основанной иа машине Тьюринга, обычно можно непосредственно распространить на схемную модель, и обратно. Позже мы рассмотрим вопросы однородности для случая схемкой модели квантовых вычислений. 3.2 Анализ вычислительных задач При анализе вычислительных задач нужно ответить на три фундаментальных вопроса. 3.2.
Анализ вычислительных задач 181 1. Что такое вычислительная задача? Перемножение двух чисел — вычислительная задача; написание компьютерной программы, предназначенной преюойти человеческие возможности в написании стихов, — тоже. Чтобы можно было продвинуться в общей теории анализа вычислительных задач, мы выделим специальный класс задач, называемых задачами разрсшснид и именно на них сосредоточим свой анализ.
Такое ограничение дает возможность развить элегантную и богатую теорию; что еще важнее, эта теория имеет приложения, далеко выходящие за рамки задач разрешения. 2. Как построить алгоритмы, решающие данную вычислительную задачу? Какие алгоритмы можно использовать для решения данной задачи? Существуег ли общий метод, позволяющий решить широкий класс задач? На чем может быть основана наша уверенность в том, что алгоритм ведет себя именно так, как требуется? 3. Каковы миниманьные ресурсы, необходимые для решения данной вычислительной задачи? При выполнении алгоритма используются различные ресурсас время, память, энергия.
В различных ситуациях может быть желательно минимизировать потребление тех нли иных из этих ресурсов. Можно ли классифицировать задачи, исходя из количества ресурсов, необходимых для нх решения? В нескольких последующих разделах мы исследуем эти вопросы, особенно первый и третий, хотя первый вопрос, «что такое вычиолительная задача», является, возможно, наиболее фундаментальным, мы отложим ответ на него до подразд. 3.2.3, а предварительно введем некоторые понятия, связанные с количественной оценкой ресурсов (подразд. 3.2.1), и сделаем обзор основных путей «аварии сложности вычислений (подрэзд.
3.2.2). Второй вопрос (как построить хорошие алгоритмы) является предметом рассмотрения большого количества исследователей, и в этом кратком введении мы не можем даже начать описание основных идей, используемых при разработке хороших алгоритмов. Если вы интересуегесь этим прекрасным предметом, мы отсылаем вас к разделе «История и дополнительная литература», приведенному в конце главы. Ближе к этой тематике мы подойдем позже, когда будем рассматривать квантовые алгоритмы. Подход, используемый при построении квантовых алгоритмов, обычно представляет собой соединение глубоких идей, применяемых при разработке алгоритмов для классических компьютеров, и новых, полностью квантовомеханических приемов.
По этой причине, а также поскольку разработка квантовых алгоритмов во многих отношениях весьма близка к разработке классических алгоритмов, мы призываем вас ознакомиться хотя бы с основными идеями разработки алгоритмов. Третий вопрос (каковы минимальные ресурсы, необходимые для решения данной вычислительной задачи) рассматривается в нескольких следующих разделах. Пусть, например, у нас есть два числа, каждое длиной и битов, и мы хотим их перемножить. Если умножение производится на одноленточной ма- 182 Глава 3.
Введение в информатику шине Тьюринга, сколько операций необходимо произвести, чтобы получить результат? Сколько места на ленте машины Тьюринга будет использовано в процессе этого умножения? Эти примеры показывают, какого типа вопросы о ресурсах мы будем задавать. Вообще говоря, компьютеры пользуются ресурсами многих различных видов, но мы в основном сосредоточим внимание на времени, памяти и энергии. Время и память были двумя основными видами ресурсов, которым уделялось внимание при анализе алгоритмов; мы посвятим им подразд. 3.2.2-3.2.4. Энергией обычно интересовались меньше; однако же изучение энергетических затрат мотивирует понятие обратимого классического вычисления, которое, в свою очередь, необходимо для квантовых вычислений, так что мы рассмотрим вопросы затрат энергии при вычислениях в подразд. 3.2.5 довольно подробно. 3.2.1 Как количественно оценивать компьютерные ресурсы Различные вычислительные модели требуют различных затрат ресурсов.
Даже простой переход от одноленточной машины Тьюринга к двухленточной, может изменить объем ресурсов, требуемых при решении данной задачи. Для очень хорошо понятой вычислительной задачи (например, такой, как сложение целых чисел) такие различия между моделями могут представлять интерес. Однако для первичного понимания задачи лучше оценивать требуемые ресурсы способом, независимым от более или менее тривиальных изменений в модели. Одним из средств, применяемых для такой оценки, являются асимотоглнческие обозяаченпл, с помощью которых можно описать существенную часть поведения функции. Эти обозначения можно, например, использовать для того, чтобы указать, сколько по существу операций использует алгоритм, не занимаясь точным подсчетом времени его работы. В настоящем разделе мы подробно опишем эти обозначения и применим их к простой задаче, иллюстрирующей количественно оценку вычислительных ресурсов, — анализу алгоритмов сортировки последовательности слов в алфавитном порядке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
