Данная работа относится к области теории сложности и посвящена исследованию и сравнительному сложностному анализу классических и квинтовых алгоритмов для функции ’’EQUALITY” (EQ). Алгоритм - это определенная последовательности действий, приводящая через конечное число шагов к результату — решению задачи, для которой разработан алгоритм. Любой алгоритм должен удовлетворятся двум свойствам. Во-первых, массовость, то есть алгоритм предназначен для решения задачи с некоторым множеством допустимыx входных данных. Во-вторых, конечности, это значит, что алгоритм должен завершается за конечное число шагов. Сложности алгоритма — это функция, определяющая зависимости объёма работы, выполняемой алгоритмом, от размера входных данных. В теории сложности алгоритмов выделяют две основные меры сложности - пространственная и временная. Время определяется количеством элементарных шагов, необходимых для решения задачи, пространство определяется объёмом памяти или места на носителе данных. Эффективным алгоритмом принято называть алгоритм, сложность которого ограничена полиномом от размера задачи.
Для реализации алгоритма необходимо выбрать модель вычисления. Модели вычислений можно условно разделить на модели с памятью и модели без памяти. К первым относятся так называемые машинные, ко вторым - схемные модели вычислений. Между этими двумя классами моделей нет четких различий. В ряде случаев схемные модели можно непосредственно интерпретировать с машинной точки зрения. Типичной схемной моделью вычислений являются ветвящиеся программы. С одной стороны, ветвящаяся программа - это контактная схема, с другой стороны, в терминах ветвящихся программ естественным образом описываются машины Твюринга и автоматы. Вычислительная модель называется однородной, если один и тот же алгоритм работает на входах различной длины. В противном случае, вычислительная модель называется неоднородной. К однородным вычислительным моделям относятся, например, машины Тьюринга, классические модели конечных автоматов. Схемы из функциональных элементов, ветвящиеся программы являются неоднородными.
В данной работе рассматриваются две модели вычислений: модель ветвящихся программ и коммуникационная модель вычислений. Коммуникационная модель вычислений рассматривается при доказательстве нижних оценок сложности, а также как основа некоторых алгоритмов. В работе приводится Теорема о связи сложности ветвящейся программы и коммуникационной модели вычислений. Данная теорема была известна ранее, но в данной работе доказательство утверждения автором проведено самостоятельно.
Для указанных моделей исследуются различные алгоритмы для вычисления функции EQ. Эта функция проверки двух наборов (двух последовательностей) на эквивалентность (равенство). К функции EQ можно свести ряд других функций (например, проверка является ли слово палиндромом, проверка периодичности числовой последовательности и т.д.). Таким образом, алгоритмы для EQ можно использовать для вычисления функций, которые к ней сводятся.
Исследованы три класса алгоритмов: детерминированные, вероятностные и квантовые. Каждый класс алгоритмов описан в соответствующей главе:”Детерминированные вычисления”, ” Вероятностные вычисления” и ” Квантовые вычисления”. В главе ’’Квантовые вычисления” приводится сравнение классических (детерминированных, вероятностных) и квантовых систем. Квантовые системы базируются на законах квантовой механики, поэтому детерминированные и вероятностные системы можно объединить одним термином - ’’Классические системы”. Для каждого класса приведены различные алгоритмы для функции EQ на языке ветвящейся программы и коммуникационной модели вычисления. Приведенные алгоритмы сравниваются между собой по сложности. Отдельно рассматриваются алгоритмы, базирующиеся на хэш-функциях и кодах с исправлением ошибок. На основе этих алгоритмов предложенв1 обобщенные вероятностные и квантовые алгоритмы, основанные
на универсальных хэш-функциях и ’’хороших” кодах.
Таким образом, в данной работе исследованы различные алгоритмах для функции EQ для детерминированных, вероятностных и квантовых ветвящихся программ и коммуникационнв1х моделей вычислении, проведен их сравнительный анализ, получены верхние оценки сложности.
Таким образом, в работе были исследованы алгоритмах для функции EQ, а также проведен их сравнительный сложностной анализ. Для данной функции были рассмотрены три класса алгоритмов: детерминированные, вероятностные и квантовые.
В главе ’’Детерминированные вычисления” были рассмотрены разные алгоритмы. В первом алгоритме переменные считывались по очереди из каждой последовательности, сложность алгоритма была линейная. Также был рассмотрен алгоритм, в котором использовался естественный порядок считывания переменных, в таком случае сложность алгоритма была экспоненциальной. Таким образом, сложность вычисления функции EQ зависит от порядка считывания пеерменных.
Вероятностные алгоритмы не гарантируют абсолютно правильный ответ, но могут быть эффективнее детерминированных. Если вероятность ошибки ограничена константой, то такие алгоритмы считаются хорошими, так как путем повторения алгоритма несколько раз вероятность ошибки можно сделать сколь угодно малой. В данной работе были рассмотрены следующие вероятностные алгоритмы: ’’Тривиальный” алгоритм, алгоритм ’Сложение по модулю” и алгоритм ’’Полином”. В ’’Тривиальном” алгоритме вероятность ошибки равна O((n — l)/n). Это наихудшая ошибка любого вероятностного алгоритма, так как для того, чтобы сделать вероятность ошибки экспоненциально малой, согласно оценке Чернова, алгоритм нужно повторить к раз, где k=0(22n). В алгоритме ’’Сложение по модулю” вероятность ошибки уменьшается по сравнению с предыдущим алгоритмом и равна 0(1/п), это значительно меньше, чем в ’’Тривиальном” алгоритме. Вероятность ошибки можно уменьшить путем увеличения диапозона чисел, из которого выбирается необходимый параметр алгоритмар. В алгоритме ’’Полином” вероятность ошибки не зависит от и.
Хотелось бы также отметить особенность самих алгоритмов. В некоторых алгоритмах, а именно, ’’Сложение по модулю” и ’’Полином” использовались идеи сжатия последовательности бит. Данные идеи лежат в основе хэш- функций. Также был рассмотрен алгоритм для коммуникационной модели с тремя участниками, использующий общую последовательность случайных бит (public coin). Данный алгоритм, является основой кода Уолша-Адамара с исправлением ошибок.
В разделе ”Хэш-функции” был рассмотрен обобщенный алгоритм, основанный на вероятностном выборе хэш-функций из универсального множества хэш-функций. В разделе ’’Коды с исправлением ошибок” рассмотрен алгоритм с ’’избыточными” битами. Таким образом, в результате сравнения предложенных вероятностных алгоритмов, было показано, что наилучшим вероятностным алгоритмом является алгоритм ’’Полином”. Были получены верхние оценки алгоритмов, проведена классификация алгоритмов.
Также были рассмотрены алгоритмы и для квантовых моделей. Предложена квантовая модификация алгоритмов, изложенных в главе ’Вероятностные вычисления”, а именно, ’’Тривиальный алгоритм”, алгоритм ’Сложение по модулю” и алгоритм ’’Полином” были изложены на квантовом языке. Квантовые алгоритмы были разбиты на две основные группы: Тривиальные алгоритмы и Эффективные алгоритмы. Под ’’Тривиальным” алгоритмом мы понимали такой алгоритм, в котором вычисление функции EQ основано на прямом сравнении элементов последовательности. В противоположность ’’Тривиальным” алгоритмам, ’’Эффективные ” алгоритмы, в которых сравниваются не сами последовательности, а некоторые функции от них.
В разделе ’’Тривиальные алгоритмы” были рассмотренны несколько видов алгоритмов, а именно, алгоритмы, использующие дополнительную память, алгоритм, который не использует дополнительную память, но изменяет входные кубиты, квантово-вероятностные алгоритмы, квантовый тривиальный алгоритм, использующий суперпозицию и квантовый алгоритм с промежуточным измерением.
В разделе ” Эффективные алгоритмы” рассмотрены квантовые алгоритмах ’’Сложение по модулю ” и ’’Полином ”. Коммуникационная сложности этих алгоритмов O(log n), а ошибка - константная. Выяснено, что основой рас- смотренных эффективных алгоритмов является использование квантовых хэш-функций. Также разработан метод построения эффективных квантовых алгоритмов, основанных на использовании’’хороших” кодов. Получены верхние оценки, проведен сравнительный анализ алгоритмов, а также разработан метод построения эффективного квантового алгоритма, использующий ’’хорошие” коды.
Таким образом, в работе исследованы три класса алгоритмов для функции EQ: детерминированные, вероятностные и квантовые. Проведено сравнение вероятностных и детерминированных алгоритмов. Сделан вывод, что использование вероятностных алгоритмов позволяет заметно уменьшить сложность алгоритма, повысить точность алгоритма можно путем повтора алгоритма. Также были исследованы квантовые алгоритмы, которые по своей природе значительно отличаются от классических. Были найдены такие алгоритмы, которые с высокой точностью выдают правильный ответ, разработан метод построения эффективных квантовых алгоритмов.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
