Представление логических функций от большого числа переменных

Можно ли говорить об инвариантности теории трудоемкости вычислений? Иначе говоря, возможны ли утверждения о трудоемкости вычислений, сохраняющиеся при переходе к любой алгоритмической модели? Что касается прямых количественных оценок, то инвариантами не являются не только константы, но и степени. Например, доказано, что трудоемкость распознавания симметричности слова длины п относительно его се

редины на машине Тьюринга не меньше, чем сn^2, тогда как для любой ЭВМ, имеющей доступ к памяти по адресу, допускающей операции над адресами, легко написать программу, решающую эту задачу с линейной трудоемкостью.

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

До сих пор в явном виде была описана только одна абстрактная машина - машина Тьюринга. Однако неявно использовалась машина другого типа, гораздо более близкая к современным ЭВМ, в которой возможен доступ к памяти по адресам. Такая машина, называе-мая машиной с произвольным доступом к памяти, может на следующем шаге переходить к любой ячейке с указанным адресом (команды условного и безусловного переходов) и реализовать команды-операторы. Возможны различные варианты моделей машины с произвольным доступом к памяти; в более сложных вариантах допускаются операции над адресами. Здесь мы не будем рассматривать все эти варианты, ограничившись фиксацией лишь одной простой модели - машины элементарных логических операций, или кратко L-машины. Относительно других моделей абстрактных машин ограничимся констатацией их основных свойств, которых будет достаточно при последующих рассмотрениях. Будем считать, что каждая машина имеет конечное число устройств (головок, устройств управления головками, процессоров- устройств, выполняющих элементарные операции, и т. д.), каждое устройство и каждая ячейка памяти могут находиться в одном из конечного числа возможных состояний (состояние ячейки памяти - это записанный в ней символ), и выполнение любого элементарного действия (шага) зависит от информации из конечного числа ячеек памяти, ограниченного некоторой константой m. Будем говорить, что все ячейки читаются на данном шаге. Полное состояние машины, т. е. набор состояний устройств, состояний ячеек памяти и указание ячеек, читаемых в настоящий момент, называется конфигурацией машины.

И наконец, еще одно вступительное замечание. Алгоритм, осуществляемый машиной, может быть реализован двояким образом: он может быть "встроен" в управляющее устройство или записан в памяти машины. В первом случае машина является специализированной и может выполнять только данный алгоритм; чтобы изменить алгоритм, надо поменять управляющее устройство. Таковы машины Тьюринга. Во втором случае запись алгоритма в памяти называется программой, а сама машина - программируемой; алгоритм, встроенный в управляющее устройство, решает задачу исполнения программ, записанных в памяти машины. Такова универсальная машина Тьюринга и все реальные универсальные ЭВМ. В обоих случаях начальная конфигурация машины - состояния всей памяти и всех устройств - полностью определяет процесс вычисления.

Машина элементарных логических операций (L-машина) - это машина с произвольным доступом к памяти, имеющая следующую систему команд:

X:=0;

X:=1;

X:=y;

X:=Ø y;

X:= y & z;

X:= y È z;

“конец”

Где x, y, z – адреса ячеек памяти, := - знак присвоения.

В принципе, современные компьютеры примерно так и работают, производят манипуляции с ячейками памяти, некоторые действия.

Трудоемкость алгоритма на примере RSA, квантовые компьютеры

RSA – алгоритм шифрования с открытым ключом

Всегда поднималась проблема о безопасной передаче информации. Любая линия, по которой идет передача информации может быть прослушана, и информация может попасть к злоумышленнику. Нужен был надежный алгоритм шифрования. Сообщение можно было зашифровать каким-либо ключом и передать сообщение, а затем и ключ, но при этом всё равно оставалось возможным перехватить ключ и расшифровать сообщение. В 1970-ых годах для решения этой проблемы были предложены системы шифрования, использующие два вида ключей для одно и того же сообщения: открытый (не требующий хранения в тайне) и закрытый (строго секретный). Открытый ключ служит для зашифровки сообщений, а закрытый для его дешифровки. Вы посылаете вашему корреспонденту открытый ключ, он с помощью него шифрует сообщение и отправляет его вам. Всё, что сможет сделать злоумышленник, перехватив ключ, - это зашифровать им своё письмо и отправить его кому либо. Но расшифровать переписку он не сможет, для этого необходим закрытый ключ. Как раз такая схема и применяется в алгоритме RSA. Причем для создания пары открытого и закрытого ключа используется следующая гипотеза. Если имеется два больших (требующих больше сотни десятичных цифр для своей записи) простых числа M и K, то найти их произведение N=M*K не составит большого труда. А вот решить обратную задачу, то есть зная число большое N разложить его на простые множители M и K (так называемая задача факторизации) – практически невозможно! Именно с этой проблемой сталкивается злоумышленник, решивший “взломать” алгоритм RSA и прочитать зашифрованную с помощью него информацию: чтобы узнать закрытый ключ, зная открытый, придется вычислить M или K.

Для проверки справедливости гипотезы о практической сложности разложения на множители больших чисел проводились и до сих пор проводятся конкурсы. Рекордом считается разложение 155-значного (512-битного) числа. Вычисления велись параллельно на многих компьютерах в течении семи месяцев 1999 года. Расчеты показывают, что с использованием даже тысячи современных рабочих станций и лучшего из известного на сегодня алгоритмов одно 250-значное число может быть разложено на множители примерно за 800 тысяч лет, а 1000 значное – за 1025 лет. (для сравнения возраст Вселенной ~ 1010 лет.).

Поэтому криптографические алгоритмы, подобные RSA, оперирующие достаточно длинными ключами, считались абсолютно надежными и использовались во многих приложениях. Пока не были придуманы квантовые компьютеры.

 Скачать реферат