Файл: M51_21_-_kopia.pdf

11 

 
1.3  

Цілі і завдання теорії алгоритмів 

Можна  виділити  наступні  цілі  і  співвіднесені  з  ними  завдання,  які 

вирішуються в теорії алгоритмів: 

• 

формалізація  поняття  «алгоритм»  і  дослідження  формальних 

алгоритмічних систем; 

• 

формальний доказ алгоритмічної нерозв'язності ряду задач; 

• 

класифікація завдань, визначення і дослідження класів складності;  

• 

вивчення поняття складності алгоритмів; 

• 

дослідження і аналіз рекурсивних алгоритмів; 

• отримання явних функцій трудомісткості в цілях порівняльного аналізу 

алгоритмів; 

• розробка критеріїв порівняльної оцінки якості алгоритмів.  

 
 
1.4 

Практичне застосування результатів теорії алгоритмів 

Виділяють наступні два аспекти: 
 
Теоретичний  аспект:  при  дослідженні  деякої  задачі  результати  теорії 

алгоритмів  дозволяють  відповісти  на  питання  чи  є  ця  задача  в  принципі 
алгоритмічно вирішуваною. 

У разі алгоритмічної розв'язності задачі – наступне важливе питання про 

приналежність  цього  завдання  до  класу  NP-повних  задач,  при  позитивному 
відповіді  на  який,  можна  говорити  про  істотні  тимчасових  витратах  для 
отримання точного рішення для великих розмінностей вихідних даних. 

 
Практичний аспект: методи та методики теорії алгоритмів  дозволяють 

здійснити: 

•  раціональний  вибір  з  відомої  безлічі  алгоритмів  вирішення  даного 

завдання  з  урахуванням  особливостей  їх  застосування  (наприклад,  при 
обмеженнях на розмірність вихідних даних або обсягу додаткової пам'яті);  

• отримання тимчасових оцінок вирішення складних завдань; 
• отримання достовірних оцінок неможливості вирішення деякої задачі за 

певний час, що важливо для криптографічних методів;  

•  розробку  і  вдосконалення  ефективних  алгоритмів  рішення  задач  в 

області обробки інформації на основі практичного аналізу. 

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