ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2342
Скачиваний: 1
31
Теорема 3.1.
Не існує алгоритму (машини Тьюринга), що дозволяє за описом
довільного алгоритму і його вхідних даних (і алгоритм і дані задані
символами на стрічці машини Тьюринга) визначити, чи зупиняється цей
алгоритм на цих даних або працює нескінченно.
Таким чином, фундаментально алгоритмічна нерозв'язність пов'язана з
нескінченністю виконуваних алгоритмом дій, тобто неможливістю
передбачити, що для будь-яких вхідних даних рішення буде отримано за
кінцеву кількість кроків.
Тим не менш, можна спробувати сформулювати причини, що ведуть до
алгоритмічної нерозв'язності. Ці причини достатньо умовні, оскільки всі
вони зводяться до проблеми зупину, однак такий підхід дозволяє більш
глибоко зрозуміти природу алгоритмічної нерозв'язності:
а) Відсутність загального методу розв'язання задачі
Проблема 1: Розподіл дев'яток в запису числа π
Визначимо функцію f (n) = i, де n – кількість дев'яток поспіль у
десятинному запису числа π, а i – номер самої лівої дев'ятки з n дев'яток
підряд: π = 3,141592 ... f (1) = 5.
Задача полягає в обчисленні функції f (n) для довільно заданого n.
Оскільки число π є ірраціональним і трансцендентним, то ми не знаємо
жодної інформації про розподіл дев'яток (так само як і будь-яких інших цифр)
в десятковому запису числа π.
Обчислення f (n) пов'язане з обчисленням наступних цифр в розкладанні
π, до тих пір, поки ми не виявимо n дев'яток поспіль, однак у нас немає
загального методу обчислення f (n), тому для деяких n обчислення можуть
тривати нескінченно.
Не знаємо в принципі (за природою числа π) чи існує рішення для всіх n.
Проблема 2: Обчислення досконалих чисел
Досконалі числа – це числа, які дорівнюють сумі своїх дільників,
наприклад:
28 = 1 +2 +4 +7 +14.
Визначимо функцію S(n) = n-ое за рахунком досконале число і
сформулюємо задачу обчислення S(n) по довільно заданому n. Немає
32
загального методу обчислення досконалих чисел, навіть не відома множина
досконалих чисел. Тому алгоритм повинен перебирати всі числа поспіль,
перевіряючи їх на досконалість. Відсутність загального методу рішення не
дозволяє відповісти на питання про умову зупинення алгоритму. Якщо
перевірили М чисел при пошуку n-го досконалого числа – чи означає це, що
його взагалі не існує?
Проблема 3: Десята проблема Гільберта
Нехай заданий многочлен n-го ступеня з цілими коефіцієнтами – P, чи
існує алгоритм, який визначає, чи має рівняння P = 0 рішення в цілих числах?
Ю.В. Матіясевіч [3] показав, що такого алгоритму не існує, тобто
відсутній загальний метод визначення цілих коренів рівняння P = 0 за його
цілочисловим коефіцієнтами.
б) Інформаційна невизначеність завдання
Проблема 4: Позиціонування машини Посту на останньому
позначеному ящику
Нехай на стрічці машини Посту задані набори помічених ящиків
(кортежів) довільної довжини з довільними відстанями між кортежами і
каретка знаходиться у самого лівого поміченого ящика. Задача полягає в
установці каретки на самий правий позначений ящик останнього кортежу.
Спроба побудови алгоритму, що вирішує це завдання, призводить до
необхідності відповіді на питання – чи немає більше на стрічці кортежів або
вони є десь правіше, коли після виявлення кінця кортежу ми зрушили вправо
по порожніх ящиках на М позицій і не виявили початок наступного кортежу?
Інформаційна невизначеність задачі полягає у відсутності інформації або
про кількість кортежів на стрічці, або про максимальні відстані між
кортежами. За наявності такої інформації (при дозволі інформаційної
невизначеності) задача стає алгоритмічно розв’язаною.
в) Логічна нерозв'язність
Проблема 5: Проблема еквівалентності алгоритмів
За двома довільно заданими алгоритмами (наприклад, для двох машин
Тьюринга) визначити, чи будуть вони видавати однакові вихідні результати на
будь-яких вхідних даних.
33
Проблема 6: Проблема тотальності
За довільно заданим алгоритмом визначити, чи буде він зупинятися на
всіх можливих наборах вхідних даних. Інше формулювання цього завдання –
чи є частковий алгоритм Р усюди визначеним?
3.4 Питання для самоконтролю
1)
Формальний опис машини Тьюринга.
2)
Функція переходів в машині Тьюринга.
3)
Поняття про алгоритмічно нерозв'язні проблеми.
4)
Проблема позиціонування в машині Тьюринга.
34
4.
ВСТУП ДО АНАЛІЗУ АЛГОРИТМІВ
4.1 Порівняльні оцінки алгоритмів
При використанні алгоритмів для вирішення практичних завдань
виникає проблема раціонального вибору алгоритму розв'язання задачі.
Рішення проблеми вибору пов'язане з побудовою системи порівняльних
оцінок, яка спирається на формальну модель алгоритму
Будемо розглядати в подальшому правильні і фінітні алгоритми, тобто
алгоритми, що дають 1-рішення загальної проблеми.
В якості формальної системи будемо розглядати абстрактну машину, що
включає процесор з фон-Нейманівською архітектурою, яка підтримує
адресну пам'ять і набір «елементарних» операцій співвіднесених з мовою
високого рівня.
Припущення:
•
кожна команда виконується не більше ніж за фіксований час;
•
вхідні дані алгоритму представляються машинними словами по β бітів
кожне.
Конкретна проблема задається N словами пам'яті, таким чином, на вході
алгоритму – Nβ = N * β біт інформації. Відзначимо, що в ряді випадків,
особливо при розгляді матричних задач, N є мірою довжини входу алгоритму,
що вказує на лінійну розмірність.
Програма, що реалізує алгоритм для вирішення загальної проблеми
складається з М машинних інструкцій з βм бітів – Мβ = М * βм біт
інформації.
Крім того, алгоритм може вимагати таких додаткових ресурсів
абстрактної машини:
•
S
d
–
пам'ять для зберігання проміжних результатів;
•
S
r
–
пам'ять для організації обчислювального процесу (пам'ять,
необхідна для реалізації рекурсивних викликів і повернень).
При вирішенні конкретної проблеми, заданої N словами пам'яті алгоритм
виконує не більше, ніж кінцеву кількість «елементарних» операцій
абстрактної машини за умови розгляду тільки фінітних алгоритмів. У зв'язку
з цим введемо таке визначення.
35
Визначення 4.1 Трудомісткість алгоритму.
Під трудомісткістю алгоритму для даного конкретного входу – Fa (N),
розуміється кількість «елементарних» операцій, виконаних алгоритмом для
вирішення конкретної проблеми в даній формальній системі [5].
Комплексний аналіз алгоритму може бути виконаний на основі
комплексної оцінки ресурсів формальної системи, необхідних алгоритмом
для вирішення конкретних проблем. Очевидно, що для різних областей
застосування ваги ресурсів будуть різні, що призводить до наступної
комплексної оцінки алгоритму:
ψ
Α
=
c
1
* F
a
(N) + c
2
*
Μ
+ c
3
* S
d
+ c
4
* S
r
,
де c
i
–
вага ресурсів різного виду.
4.2.
Система позначень в аналізі алгоритмів
При більш детальному аналізі трудомісткості алгоритму виявляється, що
не завжди кількість елементарних операцій, виконуваних алгоритмом на
одному вході довжини N, збігається з кількістю операцій на іншому вході
такої ж довжини. Це призводить до необхідності введення спеціальних
позначень, що відображають поведінку функції трудомісткості даного
алгоритму на вхідних даних фіксованої довжини.
Нехай DА – безліч конкретних проблем даної задачі, заданий у
формальній системі. Нехай D ∈ DА – завдання конкретної проблеми і | D | =
N [5].
У загальному випадку існує власна підмножина DА, що включає всі
конкретні проблеми, які мають потужність N:
−
позначимо цю підмножину через DN:DN ={D∈D
N
,: |D|=N};
−
позначимо потужність множини DN через MDN → MDN = |DN|.
Тоді даний алгоритм, вирішуючи різні завдання розмірності N, буде
виконувати в якомусь випадку найбільшу кількість операцій, а в якомусь
випадку найменшу кількість операцій.
Введемо такі позначення: