області обробки інформації на основі практичного аналізу.
12
1.5
Формалізація поняття алгоритму
У всіх сферах своєї діяльності, і зокрема в сфері обробки інформації, людина стикається з різними способами або методиками вирішення завдань.
Вони визначають порядок виконання дій для одержання бажаного результату.
Їх можна трактувати як початкове або інтуїтивне визначення алгоритму.
Для того щоб дати точне поняття алгоритму, необхідно визначити, як задаються дані, з якими буде працювати виконавець, і як задаються елементарні кроки, з яких складається алгоритм. В якості даних будемо розглядати конструктивні об'єкти.
Будь-який об'єкт може бути описаний деяким набором фраз на деякій мові, інакше кажучи, представлений (закодований) ланцюжком символів. Це досить загальний підхід.
Якщо об'єкт – число, то його можна записати в десятковій або двійковій формі, тобто ланцюжком символів алфавіту {0,1}.
Якщо об'єкт – програма, то вона є ланцюжком символів в алфавіті, що містить букви, цифри і спеціальні символи.
Якщо об'єкт – зображення, то він представляється масивом пікселів, а кожен піксель – трьома числами (інтенсивностями червоного, зеленого і синього кольорів). Тобто зображення також може бути закодовано рядком символів. Сучасні високоякісні системи цифрового запису звуку показують, що і цей об'єкт може бути адекватно описаний рядком символів.
Хоча уявлення даних – самостійна проблема в комп'ютерних науках, а ефективне представлення – це значною мірою мистецтво програміста, тим не менш, можна стверджувати, що існує універсальний спосіб представлення даних – словами в деякому алфавіті.
Таким чином, можна вважати, що алгоритм – це перетворення слів із заданого алфавіту: вихідне слово переробляється (листується) алгоритмом в результуюче слово. Яким би не був кінцевий алфавіт, будь-який його символ може бути закодований за допомогою двійкового алфавіту. Інакше кажучи, вхідні дані алгоритму можуть бути представлені кінцевої ланцюжком бітів.
Те ж саме можна сказати і про вихідних даних. Кінцева ланцюжок бітів може
інтерпретуватися як ціле невід'ємне число.
З цього можна зробити важливий висновок: будь-якому алгоритму
може бути поставлена у відповідність функція, що відображає безліч
невід'ємних цілих чисел.
13
Зворотне не стверджується. Більш того, існують функції, не обчислювані ніяким алгоритмом. Обчислюваною функцією будемо називати функцію, обчислювану деяким алгоритмом.
Деякі додаткові вимоги призводять до неформального визначенням алгоритму.
Визначення 1.1
Алгоритм – це заданий на деякій мові вираз, що задає кінцеву послідовність здійсненних елементарних операцій для вирішення завдання, загального для класу можливих вхідних даних.
Нехай D – область (безліч) вхідних даних завдання, а R – множина можливих результатів, тоді можна говорити, що алгоритм здійснює відображення
D → R.
Оскільки таке відображення може бути не повним, то вводяться наступні поняття.
Визначення
1.2
Алгоритм називається частковим алгоритмом, якщо ми отримуємо результат тільки для деяких d є D і повним алгоритмом, якщо алгоритм отримує правильний результат для всіх d є D.
Незважаючи на зусилля дослідників відсутнє одне визначення поняття алгоритм. В теорії алгоритмів були введені різні формальні визначення алгоритму і дивним науковим результатом є доказ еквівалентності цих формальних визначень у розумінні їх рівноміцності. Варіанти словесного визначення алгоритму належать російським вченим А.Н. Колмогорову і А.А.
Маркову [7].
Визначення
1.3
(
Колмогоров): Алгоритм – це будь-яка система обчислень, що виконуються за строго визначеними правилами, яка після деякого числа кроків свідомо призводить до вирішення поставленого завдання.
Визначення 1.4 (Марков): Алгоритм – це точне розпорядження, що визначає обчислювальний процес, який йде від варійованих вхідних даних до шуканого результату.
14
Різні визначення алгоритму, в явній або неявній формі, постулюють наступний ряд вимог:
• алгоритм повинен містити кінцеву кількість елементарних записів
(виконай-експортуй), тобто задовольняти вимогу кінцівки запису;
• алгоритм повинен виконувати кінцеву кількість кроків при вирішенні завдання, тобто задовольняти вимогу кінцівки дій;
• алгоритм повинен бути єдиним для всіх допустимих вхідних даних, тобто задовольняти вимогу універсальності;
• алгоритм повинен призводити до правильного рішення стосовно поставленого завдання, тобто задовольняти вимогу правильності.
Інші формальні визначення поняття алгоритму пов'язані з введенням спеціальних математичних конструкцій (машина Посту, машина Тьюринга, рекурсивно-обчислюваної функції Черча) і постуліруванням тези про еквівалентність такого формалізму і поняття «алгоритм».
1.6
Питання для самоконтролю
1)
Історичні аспекти створення та розробки теорії алгоритмів.
2)
Цілі і завдання класичної теорії алгоритмів.
3) Цілі і задачі теорії асимптотичного аналізу алгоритмів.
4)
Цілі і завдання практичного аналізу алгоритмів.
5)
Теоретичний і практичний аспекти застосування результатів теорії алгоритмів.
6) Формалізація алгоритму, визначення Колмогорова і Маркова.
7)
Основні вимоги до алгоритмів.
8)
Три типи алгоритмів.
15
2. МАШИНА ПОСТА
2.1 Основні поняття та операції
Пост розглядає загальну проблему, що складається з безлічі конкретних проблем. При цьому рішення загальної проблеми це таке рішення, яке доставляє відповідь для кожної конкретної проблеми.
Наприклад, рішення рівняння 3*х +9 = 0 – це одна з конкретних проблем, а рішення рівняння a * x + b = 0 – це загальна проблема.
Алгоритм (сам термін «алгоритм» не використовується Постом) повинен бути універсальним, тобто повинен бути співвіднесений із загальною проблемою.
Основні поняття алгоритмічного формалізму Посту – це простір символів (мова L), в якому задається конкретна проблема. Відповіддю є і набір інструкцій або операцій в просторі символів, які задають як самі операції, так і порядок виконання інструкцій.
Рис. 2.1. Постовський простір символів.
Постовський простір символів – це нескінченна стрічка комірок
(ящиків). Кожен ящик або комірка можуть мати або не мати позначки див. рис. 2.1.
Конкретна проблема задається «зовнішньою силою» (термін Посту) – позначкою кінцевого кількості комірок, при цьому, очевидно, що будь-яка конфігурація починається і закінчується поміченою коміркою.
Після застосування до конкретної проблеми деякого набору інструкцій рішення представляється у вигляді набору помічених і непомічених комірок, які визначаються тією ж зовнішньою силою.
Пост запропонував набір інструкцій (елементарних операцій), які виконує «працівник» [3]. Відзначимо, що в 1936 році не було ще жодної електронної обчислювальної машини. Цей набір інструкцій є, очевидно, мінімальним набором бітових операцій:
1)
Помітити ящик, якщо він порожній.
2)
Стерти мітку, якщо вона є.
3)
Переміститися вліво на 1 ящик.
V
V
V
V
V
16 4)
Переміститися вправо на 1 ящик.
5)
Визначити чи має ящик позначку або ні, і за результатом перейти на одну з двох зазначених інструкцій.
6)
Зупинитися.
Відзначимо, що 1 і 2 інструкції включають захист від невірних ситуацій.
Програма являє собою нумеровану послідовність інструкцій, причому переходи в інструкції 5 проводяться на вказані в ній номери інших
інструкцій.
2.2 Фінітний 1 – процес
Програма (набір інструкцій у термінах Посту) є однією і тією ж для всіх конкретних проблем.
Пост вводить такі поняття:
• набір інструкцій застосовується до загальної проблеми, якщо для кожної конкретної проблеми не виникає колізій в інструкціях 1 і 2, тобто ніколи програма не стирає мітку в порожньому ящику і не встановлює мітку в позначеному ящику;
• набір інструкцій закінчується (за кінцеве кількість інструкцій), якщо виконується інструкція (6);
• набір інструкцій задає фінітний 1 – процес, якщо набір може бути використаним, і закінчується для кожної конкретної проблеми;
•
фінітний 1 – процес для загальної проблеми є 1 – рішення, якщо відповідь для кожної конкретної проблеми є правильною (це визначається зовнішньою силою).
2.3 Спосіб завдання проблеми та формулювання 1
За Постом проблема задається зовнішньою силою шляхом позначки кінцевою кількості ящиків стрічки.
Прийнято вважати, що машина працює в одиничній системі числення (0
= V; 1 = VV; 2 = VVV; 3 = VVV
V), тобто нуль представляється одним поміченим ящиком, а ціле позитивне число – поміченими ящиками в кількості на одиницю більше його значення.
17
Оскільки безліч конкретних проблем, що становлять загальну проблему
є рахунковим, то можна встановити взаємно однозначну відповідність
(биєктивне відображення) між множиною позитивних цілих чисел N і множиною конкретних проблем.
Загальна проблема називається по Посту 1-заданой, якщо існує такий
фінітний 1 – процес, що, будучи, застосованим до n є N в якості вхідної конфігурації ящиків, він задає n-ю конкретну проблему у вигляді набору помічених ящиків.
Якщо загальна проблема 1-задана і 1-розв'язана, то, поєднуючи набори
інструкцій за завданням проблеми, і її вирішенням отримуємо відповідь за номером проблеми. Це і є в термінах Посту формулювання 1.
Таким чином, гіпотеза Посту полягає в тому, що будь-які більш широкі формулювання в сенсі алфавіту символів стрічки, набору інструкцій, подання та інтерпретації конкретних проблем зводяться до формулювання 1. гіпотеза очевидно
Отже, якщо гіпотеза вірна, то будь-які інші формальні визначення, що задають певний клас алгоритмів, еквівалентні класу алгоритмів, заданих
формулюванням 1 Еміля Посту.
2.4
Принцип роботи
Машина Поста складається з каретки (каретки, яка зчитує або записує) і безмежної в обидві сторони смуги, що поділена на комірки (ящики). Кожна комірка смуги може бути або порожньою – 0, або помічено міткою – 1. За один крок каретка може переміститися на одну позицію вліво або вправо, зчитати, поставити або стерти символ в тому місті, де вона стоїть. Робота машини Посту визначається програмою, що складається з кінцевого числа рядків.
Для роботи машини необхідно задати програму і її початковий стан
(тобто стан стрічки і позиції каретки). Кареткою управляє програма, що складається з рядків команд. Кожна команда має наступний синтаксис:
Алгоритм
Програма Поста
Формулювання 1
18
i K j, де i – номер команди,
K – дія каретки,
j – номер наступної команди (перехід).
Всього для машини Поста існує шість типів команд (див. рис. 2.2):
1 – V j – поставити мітку, перейти до j-го рядка програми.
2 – X j – витерти мітку, перейти до j-го рядка програми.
3 – <- j – пересунуться вліво, перейти до j-го рядка програми.
4 – -> j – пересунуться вправо, перейти до j-го рядка програми.
5 – ? j1; j2 – якщо комірка немає мітки, то перейти до j1-го рядка програми, інакше перейти до j2-го рядка програми.
6 – ! – кінець програми (стоп).
У команди «стоп» посилань нема.
Після запуску можливі варіанти:
• робота може закінчитися командою, що не виконується (витирання
існуючою мітки або записування в помічене поле);
• робота може закінчитися командою Stop;
• робота ніколи не закінчиться.
19
Рис. 2.2. Шість команд машини Поста.
20
У кожен момент часу каретка («-») знаходиться над однією з клітин стрічки і, як кажуть, обдивляється її. Інформація про місця розташування каретки разом із станом стрічки характеризує стан машини Посту рис. 2.3.
«-»
Рис. 2.3. Стан машини Посту.
Ситуації, в яких каретка повинна наносити мітку там, де вона вже є, або навпаки, витирати мітку там, де її немає, є аварійними (недопустимими).
Програмою для машини Поста називають не порожній список команд, такій, що :
− на n-м місті команда с номером n;
− номер кожної команди співпадає з номером будь-якої команди списку.
З точки зору властивостей алгоритмів, що вивчаються за допомогою машини Посту, найбільший інтерес представляють причини зупинки машини при виконанні програми:
−
останов по команді "стоп". Такій останов називається результативним і вказує на коректність алгоритму (програми);
−
останов при виконанні неприпустимою команди. В цьому випадку останов називається без результативним;
−
машина не зупиняється ніколи. У цьому і в попередньому випадку ми маємо справу з некоректним алгоритмом (програмою).
Будемо розуміти під початковим станом каретки її становище проти порожньої клітини лівіше найлівішої мітки на стрічці.
Число k представляється на стрічці машини Посту (k + 1) мітками, що йдуть підряд. Одна мітка означає число «0». Між двома числами робиться
інтервал як мінімум з однієї порожньої секції на стрічці.
Наприклад, запис чисел 3 і 5 на стрічці машини Посту буде виглядати так:
21
Рис. 2.4. Запис чисел 3 і 5 на стрічці машини Поста.
Система запису чисел, що використовується в машині Посту є непозиційною.
Складемо програму для додавання до довільного числа одиниці.
Припустимо, що на стрічці записано тільки одне число і каретка знаходиться над однією з клітин, в якій знаходиться мітка, що належить цьому числу:
Рис. 2.5. Збільшення числа на одиницю.
Для рішення задачі можна перемістити каретку вліво (або вправо) до першої порожньої клітинки, а потім нанести мітку див. рис. 2.5-2.7.
Програма, що додає до числа мітку справа, має вигляд:
Рис. 2.6. Текст програми, що додає мітку справа.
Програма, що додає до числа мітку зліва, має вигляд:
Рис. 2.7. Текст програми, що додає мітку зліва.
22
Різниця тільки в напрямку руху каретки в першій команді.
Машину Посту можна розглядати як спрощену модель ЕОМ. Справді, як
ЕОМ, так і машина Посту мають:
• неподільні носії інформації (клітини – біти), які можуть бути заповненими або незаповненими;
• обмежений набір елементарних дій – команд, кожна з яких виконується за один такт (крок).
Обидві машини працюють на основі програми. Проте в машині Посту
інформація розташовується лінійно і читається поспіль, а в ЕОМ можна читати інформацію за адресою; набір команд ЕОМ значно ширше і виразніше, ніж команди машини Посту, і т.д.
Приклад.
Віднімання натуральних чисел P — Q.
Будемо представляти натуральне (ціле невід’ємне) число P набором з
P+1 одиниць і розділять числа нулем. Початкове положення каретки помічено символом «v» v
00111110111000
P Q
Додавання двох чисел є тривіальним — достатньо поставити 1 між ними
і стерти два останніх правих символи у Q.
Програма віднімання складається з послідовного затирання крайніх лівих міток у Q і правих у P:
1. 0 – витираємо лівий символ у Q
2. →
3. ? 4, 5 4. Stop – стоп, якщо затерли Q=0 5. ←
6. ? 5, 7 – цикл пошуку P
7. 0 – витираємо правий символ у P
8. →
9. ? 8, 1 – шукаємо Q
23
Відмітимо, що номер команди переходу не вказується, якщо перехід відбувається на наступний по порядку рядок (для наочності тексту). В 6-ому рядку можливе за циклювання, якщо Q > P (можна добавити перевірку)
Обґрунтування цієї гіпотези відбувається сьогодні не шляхом строго мате-автоматичного доведення, а на шляху експерименту. Дійсно, всякий раз, коли вказується алгоритм, його можна перевести в форму програми машини
Посту, яка призводить до того ж результату.
2.5
Питання для самоконтролю
1)
Поняття загальної та конкретної проблеми по Посту.
2)
Простір символів і примітивні операції в машині Поста.
3)
Поняття фінітного 1-процесу в машині Поста.
4)
Способи завдання проблем і формулювання 1.
5)
Гіпотеза Поста.
24
3.
МАШИНА ТЬЮРІНГА ТА ПРОБЛЕМИ, ЯКІ НЕ
РОЗВ’ЯЗУЮТЬСЯ АЛГОРИТМІЧНО
3.1. Машина Тьюринга
Алан Тьюринг (Turing) в 1936 році опублікував у працях Лондонського математичного товариства статтю, яка нарівні з роботами Посту і Черча, лежить в основі сучасної теорії алгоритмів.
Модель обчислень, в якій кожен алгоритм розбивався на послідовність простих, елементарних кроків і була логічною конструкцією, названої згодом машиною «Тьюринга».
Машина Тьюринга – це математична побудова, математичний апарат
(аналогічний, наприклад, апарату диференціальних рівнянь), створений для вирішення певних завдань. Цей математичний апарат був названий "
машиною" з тієї причини, що за описом його складових частин і функціонуванню він схожий на обчислювальну машину. Принципова відмінність машини Тьюринга від обчислювальних машин полягає в тому, що
її запам'ятовуючий пристрій являє собою нескінченну стрічку: у реальних обчислювальних машин запам'ятовуючий пристрій може бути як завгодно великим, але обов'язково кінцевим. Машину Тьюринга не можна реалізувати саме через нескінченності її стрічки. В цьому сенсі вона потужніша будь-якої обчислювальної машини.
У кожній машині Тьюринга є дві частини:
1) необмежена в обидві сторони стрічка, розділена на клітинки;
2) автомат (каретка для зчитування / запису, керована програмою).
З кожною машиною
Тьюринга пов'язані два кінцевих алфавіту:
-
алфавіт вхідних символів A = {a0, a1, ..., am}
-
алфавіт станів Q = {q0, q1, ..., qp}.
(З різними машинами Тьюринга можуть бути пов'язані різні алфавіти A і
Q.)
Стан q0 називається пасивним. Вважається, що якщо машина потрапила в цей стан, то вона закінчила свою роботу.
Стан q1 називається початковим. Перебуваючи в цьому стані, машина починає свою роботу.
25
Вхідне слово розміщується на стрічці по одній літери в розташованих підряд клітинках. Ліворуч і праворуч від вхідного слова знаходяться тільки порожні клітинки (в алфавіт А завжди входить порожня буква а0 – ознака того, що клітинка порожня).
Автомат може рухатися вздовж стрічки вліво або вправо, читати вміст комірок і записувати в клітинку літери. Автомат кожного разу "бачить" тільки одну клітинку.
Залежно від того, яку літеру він бачить, а також залежно від свого стану qj автомат може виконувати наступні дії:
• записати нову букву в клітинку, що оглядається;
• виконати зрушення по стрічці на одну клітинку вправо / вліво або залишитися нерухомим;
• перейти в новий стан.
Тобто у машини Тьюринга є три види операцій. Щоразу для чергової пари (qj, ai) машина Тьюринга виконує команду, що складається з трьох операцій з певними параметрами.
Програми для машин Тьюринга записуються у вигляді таблиці, де перші стовпець і рядок містять літери зовнішнього алфавіту та можливі внутрішні стани автомата (внутрішній алфавіт). Вміст таблиці являє собою команди для машини Тьюринга. Літера, яку зчитує каретка в клітинці (над якою вона знаходиться в даний момент), і внутрішній стан каретки визначають, яку команду потрібно виконати. Команда визначається перетином символів зовнішнього і внутрішнього алфавітів в таблиці.
Щоб задати конкретну машину Тьюринга, потрібно описати для неї наступні складові:
1 2 3 4 5 6 7 8