Содержание
Введение. Функции алгебры логики.
Разложение функций по переменным. Совершенная дизъюнктивнаянормальная форма.
Выводы по первым двум темам. СКНФ.
Разрешимoстьзадач в классической теории алгоритмов.
Трудоемкость алгоритмов.
Память и время как количественная характеристика алгоритма. (применительнок машине Тьюринга и современным ЭВМ).
Трудоемкость алгоритма на примере RSA, квантовые компьютеры.
Вывод.
Введение.Функции алгебры логики
Любая формула алгебрылогики зависит от переменных высказываний x1, x2… xn, полностью определяющих значение входящих в неё простых высказываний,следовательно, её можно рассматривать как функцию этих высказываний. Такиефункции, которые как и их переменные принимают значение “0” или “1”, называют функциями алгебры логики или логическими функциями. Эти функции обозначаются f(x1… xn).
Логическая переменнаяможет принимать два значения, тогда из n-переменных можно составить N= 2nкомбинаций из “0” и “1”, которые принято называть наборами переменных, иговорят, что функция f определена намножестве наборов. Посколько функция принимает два значения, то на N наборов можно построить M= mNразличных функций.
Пример. Если n=1, то наборов N=2, а функций M=4
n=2 N=4 M=16
n=4 N=8 M=256
Элементарные функции — логические функции одной или двух переменных.
Постороим при n=1 функцию f(x).X
f1
f2
f3
f4 1 1 1 1 1
Здесь f1(x)=0– константа “0”;
f2(x)= 1 –константа “1”;
f3(x)= x – функция x
f5(x)= Øx – отрицание.
Аналогично, при n=2 получаем:
f5(x,y)=xÈy
f6(x,y)=x×y
f7(x,y)=x®y
f8(x,y)=y®x
f10(x,y)= Ø f9(x,y)=xÅy – сумма по модулю “два”.
f11(x,y)=Øf10(x,y)=x½y – Штрих Шеффера.f9(x,y)=x~y f12(x,y)=Øf5(x,y)=x¯y – стрелка Пирса.
Такимобразом, при возрастании числа переменных, число строк значительноувеличивается, поэтому чаще используют задание в виде логической функции –такая запись называется аналитической.
Разложение функций попеременным. Совершенная дизъюнктивная нормальная форма.
Введем обозначение x0=Øx, x1=x. Пусть а — параметр, равный 0 или 1.Тогда xA=1, если x=а, и xA=0,если х¹а.
Теорема. Всякая логическаяфункция f(x1,…, xn) мо-жет быть представлена вследующем виде:
/>
где n ³ m, а дизъюнкция берется по всем 2m наборам значенийпеременных х1, ..., хm.
Это равенство называетсяразложением по переменным х1, ..., хт. Например, при n=4,m=2 разложение имеет вид:
f(x1,x2, x3, x4)= Øx1 Øx2 f(0, 0, x3,x4) È Øx1 x2 f & (0,1,x3,x4)È x1 Øx2 f(1,0,x3,x4)È x1 x2 f(1,1,x3,x4)
Теорема доказываетсяподстановкой в обе части равенства произвольного набора всех п переменных.
При m=1 из получаем разложение функции поодной переменной
/>
Ясно, что аналогичноеразложение справедливо для любой из п переменных. Другой важный случай —разложение по всем п переменным (т=п). При этом все переменные в правой части(3.4) получают фиксированные значения и функции в конъюнкциях правой частистановятся равными 0 или 1, что дает:
/>
где дизъюнкция берется повсем наборам /> на которых f=1. Такое разложение называетсясовершенной дизъюнктивной нормальной формой (СДНФ) функции f. СДНФ функции f содержит ровно столько конъюнкций,сколько единиц в таблице f;каждому единичному набору /> соответствует конъюнкция всехпеременных, в которой Xiвзято с отрицанием, если si = 0, и безотрицания, если si = l. Таким образом, существует взаимнооднозначное соответствие между таблицей функции f (x1, ..., хп) и ее СДНФ, и,следовательно, СДНФ для всякой логической функции единственна (точнее,единственна с точностью до порядка букв и конъюнкций: это означает, что ввидукоммутативности дизъюнкции и конъюнкции формулы, получаемые из предыдущейформулы перестановкой конъюнкций и букв в конъюнкции, не различаются исчитаются одной и той же СДНФ). Единственная функция, не имеющая СДНФ – этоконстанта 0.
Формулы, содержащие,кроме переменных (и, разумеется, скобок), только знаки функций дизъюнкции,конъюнкции и отрицания, будем называть булевыми формулами (напомним, что знакконъюнкции, как правило, опускается). Предыдущая формула приводит к важнойтеореме.
Теорема. Всякаялогическая функция может быть представлена булевой формулой, то есть каксуперпозиция конъюнкции, дизъюнкции и отрицания.
Действительно, для всякойфункции, кроме константы 0, таким представлением может служить её СДНФ.Константу 0 можно представить булевой формулой Ø xx.
А почему же формуланазывается “совершенной”? Совершенной называется потому, что она имеет 4свойства совершенства.
1. В формуле всеконъюнкции разные.
2. В конъюнкции всепеременные разные.
3. В однойконъюнкции не встречаются переменные вместе с их отрицанием.
4. В конъюнкциистолько переменных, сколько в исходной функции f, то есть n.(Число переменных в функции есть ранг этой функции).
В таблице истинностиопределяют единичные наборы. Из переменных образуют конъюнкции следующимобразом: если переменная = 1, то пишем x, если ¹ 1, то пишем Ø x. Полученные конъюнкции объединяемзнаком дизъюнкции. x y Z f 1 1 1 1 1 Ø xyz 1 1 1 1 x Ø yz 1 1 1 xy Ø z 1 1 1 1 xyz
В результате получаемследующую СДНФ:
f(x, y, z) = (Ø xyz) È (x Ø yz) È (xy Ø z) È (xyz)
Выводы попервым двум темам.Логическаяпеременная может принимать два значения, тогда из n-переменныхможно составить N= 2n комбинаций из “0” и “1”, которые принято называть наборами переменных, и говорят, что функция f определена намножестве наборов. Поскольку функция принимает два значения, то на Nнаборов можно построить M= mNразличныхфункций. Становится очевидно, что чем больше переменных содержит функция, темболее громоздкой становится таблица истинности. Поэтому чаще используют аналитическуюформу записи. Но машинам (тем же ЭВМ) непонятна такая форма записи и всё равнонеобходимо строить таблицы истинности, что порою может отнимать значительновремени. Об этом речь пойдет чуть ниже.
Так же бываетпроблематично, а порою даже и невозможно построить СДНФ не использую таблицыистинности.
Так же существует СКНФ – Совершенная КонъюнктивнаяНормальная Формула. Я не стал останавливаться на ней более подробно, так какона очень похожа на СДНФ, с той лишь разницей, что состоит из конъюнктивныхэлементов дизъюнкции. Соответствующие изменения будут и при получении СКНФ изтаблицы истинности. x Y Z f хÈyÈz 1 xÈyÈ Øz 1 xÈ ØyÈz 1 1 1 1 ØxÈ yÈ z 1 1 1 1 1 1 1 1 1 1
Таким образом получаемследующую СКНФ:
f(x,y,z)=(хÈyÈz)^(xÈyÈ Øz)^(xÈ ØyÈz)^(Ø xÈ yÈ z)
Разрешимoсть задач в классической теорииалгоритмов
В классической теории алгоритмов задачасчитается разрешимой, если существует решающий ее алгоритм. Однако дляреализации некоторых алгоритмов при любых разумных с точки зрения физикипредположениях о скорости выполнения элементарных шагов может потребоватьсябольше времени, чем по современным воззрениям существует вселенная. Поэтомувозникает потребность конкретизировать понятие разрешимости и придать емуоценочный, количественный характер, введя такие характеристики алгоритмов,которые позволяли бы судить о возможности и целесообразности их практическогоприменения.
Среди различных возможных характеристикалгоритмов наиболее важными с прикладной точки зрения являются две: время ипамять, расходуемые при вычислении. Физическое время вычисления алгоритма характеризуетсяпроизведением tt, где t — число действий (шагов) вычисления, а t — среднее физическое время реализации одного шага.Число шагов t определяется описанием алгоритма в даннойалгоритмической модели, это — величина математическая, не зависящая отособенностей физической реализации модели. Напротив, t зависит от реализации и определяется скоростьюобработки сигналов в элементах, записи и считывания информации и т. д. Поэтомучисло действий t можно считать математическим временем вычисленияалгоритма, определяющим физическое время вычисления с точностью до константы t, зависящей от реализации.
Память какколичественная характеристика алгоритма
Память как количественнаяхарактеристика алгоритма определяется количеством S единиц памяти (ячеек ленты машины Тьюринга или машинных словв современных ЭВМ), используемых в процессе вычисления алгоритма. Ясно, что этавеличина по порядку не может превосходить числа шагов вычисления: mt ³ s, где m — максимальное число единиц памяти,используемых в данной машине на одном шаге. Напротив, t может существенно превосходитьs, например, возможно соотношение t ³ s^c. С этой точки зрения время болеетонко отражает сложность алгоритма, чем память; и это — одна из причин, покоторой исследованию временных характеристик алгоритма уделяется большеевнимание. Существуют и другие, прикладные причины (в частности, то, что, грубоговоря, память дешевле времени), которые здесь обсуждаться не будут. Так илииначе, здесь будет идти речь о трудоемкости алгоритмов и задач, решаемыхалгоритмами.
Итак, трудоемкостьалгоритма — это число элементарных действий, выполненных при его вычислении.
Полной характеристикойконкретного варианта задачи является его формальное описание. Характеристикойсложности описания можно считать его объем, который иногда называютразмерностью задачи (например, для изоморфизма графов размерностью задачи можносчитать число символов в матрицах смежности графов); тогда исследованиетрудоемкости алгоритма рассматривается как исследование зависимоститрудоемкости вычисления от размерности задачи, решаемой алгоритмом.
И в математике, и напрактике в конечном счете нас интересуют не алгоритмы сами по себе, а задачи,которые они решают. Одна и та же задача может решаться различными алгоритмами ина разных машинах. Если машина М зафиксирована, то трудоемкостью данной задачиотносительно машины М называется минимальная из трудоемкостей алгоритмов,решающих задачу на машине М. Задач, трудоемкость которых была бы определенаточно, довольно мало; хорошим результатом считается определение ее по порядку,т. е. с точностью до множителя, ограниченного некоторой константой. Чащеудается оценить ее сверху или снизу. Оценку сверху получают, указав конкретныйалгоритм решения задачи: по определению, трудоемкость задачи не превосходиттрудоемкости любого из решающих ее алгоритмов. Оценки трудоемкости снизу — гораздо более трудное дело; их получают обычно из некоторых общих соображений(например, мощностных или информационных). О них здесь говорить не будем.
Можно ли говорить обинвариантности теории трудоемкости вычислений? Иначе говоря, возможны лиутверждения о трудоемкости вычислений, сохраняющиеся при переходе к любойалгоритмической модели? Что касается прямых количественных оценок, тоинвариантами не являются не только константы, но и степени. Например, доказано,что трудоемкость распознавания симметричности слова длины п относительно егосередины на машине Тьюринга не меньше, чем с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, оперирующиедостаточно длинными ключами, считались абсолютно надежными и использовались вомногих приложениях. Пока не были придуманы квантовые компьютеры.
Оказывается, используязаконы квантовой механики, можно построить такие компьютеры, для которых задачафакторизации не составит большого труда. Согласно оценкам, квантовый компьютерс памятью объемом всего лишь в 10 тысяч квантовых битов способен разложить1000-значное число на простые множители всего за несколько часов.
По мере распространениякомпьютеров ученые, занимавшиеся квантовыми объектами, пришли к выводу оневозможности рассчитать состояние эволюционирующей системы, состоящей всего издесятков взаимодействующих частиц, например молекул метана. Объясняется этотем, что для полного описания сложной системы необходимо держать в памятикомпьютера очень большое количество переменных, так называемых квантовыхамплитуд. Возникла парадоксальная ситуация: зная уравнение эволюции, знаяначальное состояние системы и все взаимодействия частиц, практически неважновычислить её будущее, даже если система состоит из 30 электронов впотенциальной яме, а в распоряжении имеется суперкомпьютер с оперативнойпамятью, число битов которой равно числу атомов в видимой области Вселенной. Ив то же время для исследования динамики такой системы можно просто поставитьэксперимент с 30 электронами, поместив их в данные условия. Так и появиласьидея использования квантовых процессов для практических вычислений. Первым этупроблему поднял русский математик Ю.И. Манин. Большое внимание к разработкеквантовых компьютеров привлек лауреат Нобелевской премии Р.Фейнман. Благодаряего авторитетному призыву число специалистов, обративших внимание на квантовыевычисления, увеличилось во много раз.
Не буду останавливатьсяна устройстве квантового компьютера, скажу лишь, что стали возможны такиеоперации, не имеющие классических аналогов, например стало возможным задатьоперациюÖNOTтак, чтобы ÖNOT*ÖNOT = NOT.
Вывод
Таким образом, мы напримерах разобрались в трудоемкости и громоздкости некоторых алгоритмовприменительно к некоторым машинам, а так же в зависимости сложности логическихфункций от количества переменных, образующих эту функцию.
Литература
1. Гилл А. Введениев теорию конечных автоматов. М.: Наука, 1966.
2. Гэри М., ДжонсонД., Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
3. Кузнецов О.П.,Адельсон-Вельский Г.М., Дискретная математика для инженера. М.:Энергоатомиздат, 1988.
4. Манин Ю.И.Вычислимое и невычислимое. М.: Сов.радио, 1964.
5. И.фон НейманМатематические основы квантовой механики. М.: Наука, 1964.
6. Р.ФейнманМоделирование физики на компьютерах. Квантовый компьютер и квантовыевычисления. Ижевск: РХД, 1999.
7. Р.ФейнманКвантово-механические компьютеры. Там же.
8. В.В.Белокуров,О.Д.Тимофеевский, А.О.Хрусталев Квантовая телепортация – обыкновенное чудо.Ижевск: РХД, 2000.
9. А.Китаев, А.Шеня, М.Вялый Классические квантовые вычисления. М.: МЦНМО-ЧеРо, 1999.