Зміст
Введення. Функції алгебри логіки.
Розкладання функцій за змінними. Досконала діз'юнктівная нормальна форма.
Висновки за першими двома темами. СКНФ.
Разрешімoсть завдань в класичній теорії алгоритмів.
Трудомісткість алгоритмів.
Пам'ять і час як кількісна характеристика алгоритму. (Стосовно до машини Тьюринга і сучасним ЕОМ).
Трудомісткість алгоритму на прикладі RSA, квантові комп'ютери.
Висновок.
Введення. Функції алгебри логіки
Будь-яка формула алгебри логіки залежить від змінних висловлювань x 1, x 2 ... x n, повністю визначають значення входять до неї простих висловлювань, отже, її можна розглядати як функцію цих висловлювань. Такі функції, які як і їх змінні приймають значення " 0 " або " 1 " , Називають функціями алгебри логіки або логічними функціями. Ці функції позначаються f (x 1 ... x n).
Логічна змінна може приймати два значення, тоді з n-змінних можна скласти N = 2 n комбінацій з " 0 " і " 1 " , Які прийнято називати наборами змінних, і кажуть, що функція f визначена на множині наборів. Поскільки функція приймає два значення, то на N наборів можна побудувати M = m N різних функцій.
Приклад. Якщо n = 1, то наборів N = 2, а функцій M = 4
n = 2 N = 4 M = 16
n = 4 N = 8 M = 256
Елементарні функції - логічні функції однієї або двох змінних.
Побудована при n = 1 функцію f (x).
Тут f 1 (x) = 0 - константа " 0 " ;
f 2 (x) = 1 - константа " 1 " ;
f 3 (x) = x - функція x
f 5 (x) = Øx - заперечення.
Аналогічно, при n = 2 отримуємо:
f 5 (x, y) = xÈy
f 6 (x, y) = x × y
f 7 (x, y) = x ® y
f 8 (x, y) = y ® x
f 10 (x, y) = Ø f 9 (x, y) = xÅy - сума по модулю "два".
f 11 (x, y) = Øf 10 (x, y) = x ½ y - Штрих Шеффера.f 9 (x, y) = x ~ yf 12 (x, y) = Øf 5 (x, y) = x ¯ y - стрілка Пірса.
Таким чином, при зростанні числа змінних, число рядків значно збільшується, тому частіше використовують завдання у вигляді логічної функції - такий запис називається аналітичною.
Розкладання функцій за змінними. Досконала діз'юнктівная нормальна форма.
Введемо позначення x 0 = Øx, x 1 = x. Нехай а - параметр, що дорівнює 0 або 1. Тоді x A = 1, якщо x = а, і x A = 0, якщо х ¹ а.
Теорема. Будь-яка логічна функція f (x 1, ..., x n) мо-же бути представлена в наступному вигляді:
де n ³ m, а диз'юнкція береться за всіма 2 m набором значень змінних х 1, ..., х m.
Це рівність називається розкладанням по змінним х 1, ..., х т. Наприклад, при n = 4, m = 2 розкладання має вигляд:
f (x 1, x 2, x 3, x 4) = Øx 1 Øx 2 f (0, 0, x 3, x 4) È Øx 1 x 2 f & (0,1, x 3, x 4) È x 1 Øx 2 f (1,0, x 3, x 4) È x 1 x 2 f (1,1, x 3, x 4)
Теорема доводиться підстановкою в обидві частини рівності довільного набору всіх п змінних.
При m = 1 з отримуємо розкладання функції з однією змінною
Ясно, що аналогічне розкладання справедливо для будь-якої з п змінних. Інший важливий випадок - розкладання по всіх п змінним (т = п). При цьому всі змінні в правій частині (3.4) отримують фіксовані значення та функції в кон'юнкції правої частини стають рівними 0 або 1, що дає:
де диз'юнкція береться за всіма розділами
на яких f = 1. Таке розкладання називається досконалою диз'юнктивної нормальною формою (СДНФ) функції f. СДНФ функції f містить рівно стільки кон'юнкція, скільки одиниць у таблиці f; кожному одиничному набору 
відповідає кон'юнкція всіх змінних, в якій Xi взято з запереченням, якщо s i = 0, і без заперечення, якщо s i = l. Таким чином, існує взаємно однозначна відповідність між таблицею функції f (x 1, ..., х п) і її СДНФ, і, отже, СДНФ для всякої логічної функції єдина (точніше, єдина з точністю до порядку букв і кон'юнкція: це означає , що зважаючи на комутативності диз'юнкції і кон'юнкції формули, одержувані з попередньої формули перестановкою кон'юнкція і літер у кон'юнкції, не розрізняються і вважаються однією і тією ж СДНФ). Єдина функція, яка не має СДНФ - це константа 0.
Формули, що містять, крім змінних (і, зрозуміло, дужок), тільки знаки функцій диз'юнкції, кон'юнкції і заперечення, будемо називати булевими формулами (нагадаємо, що знак кон'юнкції, як правило, опускається). Попередня формула призводить до важливої теоремі.
Теорема. Будь-яка логічна функція може бути представлена булевої формулою, тобто як суперпозиція кон'юнкції, диз'юнкції і заперечення.
Дійсно, для будь-якої функції, крім константи 0, таким поданням може служити її СДНФ. Константу 0 можна уявити булевої формулою Ø xx.
А чому ж формула називається "досконалої"? Досконалої називається тому, що вона має 4 властивості досконалості.
1. У формулі всі кон'юнкції різні.
2. У кон'юнкції всі змінні різні.
3. В одній кон'юнкції не зустрічаються змінні разом з їх запереченням.
4. У кон'юнкції стільки змінних, скільки в вихідної функції f, тобто n. (Число змінних у функції є ранг цієї функції).
У таблиці істинності визначають одиничні набори. З змінних утворюють кон'юнкції наступним чином: якщо змінна = 1, то пишемо x, якщо ¹ 1, то пишемо Ø x. Отримані кон'юнкції об'єднуємо знаком диз'юнкції.
У результаті отримуємо наступну СДНФ:
f (x, y, z) = (Ø xyz) È (x Ø yz) È (xy Ø z) È (xyz)
Висновки за першими двома темами.
Логічна змінна може приймати два значення, тоді з n-змінних можна скласти N = 2 n комбінацій з "
Так само буває проблематично, а часом навіть і неможливо побудувати СДНФ не використовую таблиці істинності.
Так само існує СКНФ - Цілковита Кон'юнктивна Нормальна Формула. Я не став зупинятися на ній більш докладно, тому що вона дуже схожа на СДНФ, з тією лише різницею, що складається з кон'юнктивні елементів диз'юнкції. Відповідні зміни будуть і при отриманні СКНФ з таблиці істинності.
Таким чином отримуємо таку СКНФ:
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 значноє - за 10 25 років. (Для порівняння вік Всесвіту ~ 10 10 років.).
Тому криптографічні алгоритми, подібні 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.
Введення. Функції алгебри логіки.
Розкладання функцій за змінними. Досконала діз'юнктівная нормальна форма.
Висновки за першими двома темами. СКНФ.
Разрешімoсть завдань в класичній теорії алгоритмів.
Трудомісткість алгоритмів.
Пам'ять і час як кількісна характеристика алгоритму. (Стосовно до машини Тьюринга і сучасним ЕОМ).
Трудомісткість алгоритму на прикладі RSA, квантові комп'ютери.
Висновок.
Введення. Функції алгебри логіки
Будь-яка формула алгебри логіки залежить від змінних висловлювань x 1, x 2 ... x n, повністю визначають значення входять до неї простих висловлювань, отже, її можна розглядати як функцію цих висловлювань. Такі функції, які як і їх змінні приймають значення "
Логічна змінна може приймати два значення, тоді з n-змінних можна скласти N = 2 n комбінацій з "
Приклад. Якщо n = 1, то наборів N = 2, а функцій M = 4
n = 2 N = 4 M = 16
n = 4 N = 8 M = 256
Елементарні функції - логічні функції однієї або двох змінних.
Побудована при n = 1 функцію f (x).
| X | f 1 | f 2 | f 3 | f 4 |
| 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
f 2 (x) = 1 - константа "
f 3 (x) = x - функція x
f 5 (x) = Øx - заперечення.
Аналогічно, при n = 2 отримуємо:
f 5 (x, y) = xÈy
f 6 (x, y) = x × y
f 7 (x, y) = x ® y
f 8 (x, y) = y ® x
f 10 (x, y) = Ø f 9 (x, y) = xÅy - сума по модулю "два".
f 11 (x, y) = Øf 10 (x, y) = x ½ y - Штрих Шеффера.f 9 (x, y) = x ~ yf 12 (x, y) = Øf 5 (x, y) = x ¯ y - стрілка Пірса.
Таким чином, при зростанні числа змінних, число рядків значно збільшується, тому частіше використовують завдання у вигляді логічної функції - такий запис називається аналітичною.
Розкладання функцій за змінними. Досконала діз'юнктівная нормальна форма.
Введемо позначення x 0 = Øx, x 1 = x. Нехай а - параметр, що дорівнює 0 або 1. Тоді x A = 1, якщо x = а, і x A = 0, якщо х ¹ а.
Теорема. Будь-яка логічна функція f (x 1, ..., x n) мо-же бути представлена в наступному вигляді:
де n ³ m, а диз'юнкція береться за всіма 2 m набором значень змінних х 1, ..., х m.
Це рівність називається розкладанням по змінним х 1, ..., х т. Наприклад, при n = 4, m = 2 розкладання має вигляд:
f (x 1, x 2, x 3, x 4) = Øx 1 Øx 2 f (0, 0, x 3, x 4) È Øx 1 x 2 f & (0,1, x 3, x 4) È x 1 Øx 2 f (1,0, x 3, x 4) È x 1 x 2 f (1,1, x 3, x 4)
Теорема доводиться підстановкою в обидві частини рівності довільного набору всіх п змінних.
При m = 1 з отримуємо розкладання функції з однією змінною
Ясно, що аналогічне розкладання справедливо для будь-якої з п змінних. Інший важливий випадок - розкладання по всіх п змінним (т = п). При цьому всі змінні в правій частині (3.4) отримують фіксовані значення та функції в кон'юнкції правої частини стають рівними 0 або 1, що дає:
де диз'юнкція береться за всіма розділами
Формули, що містять, крім змінних (і, зрозуміло, дужок), тільки знаки функцій диз'юнкції, кон'юнкції і заперечення, будемо називати булевими формулами (нагадаємо, що знак кон'юнкції, як правило, опускається). Попередня формула призводить до важливої теоремі.
Теорема. Будь-яка логічна функція може бути представлена булевої формулою, тобто як суперпозиція кон'юнкції, диз'юнкції і заперечення.
Дійсно, для будь-якої функції, крім константи 0, таким поданням може служити її СДНФ. Константу 0 можна уявити булевої формулою Ø xx.
А чому ж формула називається "досконалої"? Досконалої називається тому, що вона має 4 властивості досконалості.
1. У формулі всі кон'юнкції різні.
2. У кон'юнкції всі змінні різні.
3. В одній кон'юнкції не зустрічаються змінні разом з їх запереченням.
4. У кон'юнкції стільки змінних, скільки в вихідної функції f, тобто n. (Число змінних у функції є ранг цієї функції).
У таблиці істинності визначають одиничні набори. З змінних утворюють кон'юнкції наступним чином: якщо змінна = 1, то пишемо x, якщо ¹ 1, то пишемо Ø x. Отримані кон'юнкції об'єднуємо знаком диз'юнкції.
x | y | Z | f | |
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 0 | |
| 0 | 1 | 1 | 1 | Ø xyz |
| 1 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | x Ø yz |
| 1 | 1 | 0 | 1 | xy Ø z |
| 1 | 1 | 1 | 1 | xyz |
f (x, y, z) = (Ø xyz) È (x Ø yz) È (xy Ø z) È (xyz)
Висновки за першими двома темами.
Логічна змінна може приймати два значення, тоді з n-змінних можна скласти N = 2 n комбінацій з " 0 " і " 1 " , Які прийнято називати наборами змінних, і кажуть, що функція f визначена на множині наборів. Оскільки функція приймає два значення, то на N наборів можна побудувати M = m N різних функцій. Стає очевидно, що чим більше змінних містить функція, тим більш громіздкою стає таблиця істинності. Тому частіше використовують аналітичну форму запису. Але машинам (тим же ЕОМ) незрозуміла така форма запису і все одно необхідно будувати таблиці істинності, що часом може віднімати значно часу. Про це мова піде трохи нижче.
Так само буває проблематично, а часом навіть і неможливо побудувати СДНФ не використовую таблиці істинності. Так само існує СКНФ - Цілковита Кон'юнктивна Нормальна Формула. Я не став зупинятися на ній більш докладно, тому що вона дуже схожа на СДНФ, з тією лише різницею, що складається з кон'юнктивні елементів диз'юнкції. Відповідні зміни будуть і при отриманні СКНФ з таблиці істинності.
x | Y | Z | f | |
| 0 | 0 | 0 | 0 | хÈyÈz |
| 0 | 0 | 1 | 0 | xÈyÈ Øz |
| 0 | 1 | 0 | 0 | xÈ ØyÈz |
| 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 0 | ØxÈ yÈ z |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 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 значноє - за 10 25 років. (Для порівняння вік Всесвіту ~ 10 10 років.).
Тому криптографічні алгоритми, подібні 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.