Формалізація поняття алгоритму
Глава III. Теорія алгоритмів
Поняття "алгоритм" належить до основних понять математики і займає одне з центральних місць у обчислювальній математиці.
Ще в IX столітті арабський вчений Мухаммед бен-муса аль-Хорезмі розробив систему правил чотирьох арифметичних дій над числами у десятковій позиційній системі числення. Ці правила наказували сувору послідовність дій над вихідними даними - числами для отримання шуканого результату - числа. Ці правила отримали назву "алгоритм" на честь арабського імені Аль-Хорезмі.
До 1920-х років поняття алгоритму зустрічалося в математичній літературі тільки в контексті: для вирішення проблеми є алгоритм, що складається з наступної послідовності дій - роби так, потім так і так далі і отримаєш необхідний результат. Інакше кажучи, тоді користувалися інтуїтивним визначенням алгоритму:алгоритм— це загальний, одноманітний, точно встановлений спосіб розв'язання будь-якого завдання з цієїмасової проблеми- нескінченного безлічі однотипних завдань.
Таким чином, алгоритм завжди пов'язаний із вирішенням масової проблеми. Завдання такого класу відрізняються один від одного значеннями параметрів, що входять до них. Приклади алгоритмів: вилучення квадратного кореня, обчислення похідної, знаходження циклу ейлера в ейлеровому графі і т.п. Наведене визначення алгоритму перестав бути суворим, оскільки у ньому зустрічаються слова, точний зміст яких встановлено, наприклад " спосіб " . Проте навіть за такого визначення можна виділити деякі характерні риси алгоритму:
1. Дискретність. Алгоритм складається з окремих елементарних дій, що виконуються по кроках.
2. Детермінованість.Між усіма величинами, одержуванимиалгоритмом, існує жорсткий причинний зв'язок. Кожна наступна величина виходить із значень попередніх за певним, як правило, простим законом.
3. Масовість.Початкова система величин вибирається з деякої множини. Початкові умови можуть змінюватись у нескінченних межах.
4. Результативність (збіжність).Обов'язковою є зупинка алгоритмічного процесу після кінцевого числа кроків із зазначенням досягнутого конструктивного об'єкта у вигляді шуканого результату.
У сучасній математиці вихідними даними та результатами роботи алгоритму стали різні конструктивні об'єкти математики: числа та багаточлени, матриці та графи, слова та тексти. Ці конструктивні об'єкти формуються за певними правилами елементарних об'єктів. Перетворення конструктивного об'єкта, що відбувається за один крок, носить локальний характер, тобто перетворенню піддається не весь об'єкт, а лише його частина: стовпець або рядок матриці, фрагмент графа, частина слова або тексту і т.п. Процес перетворення конструктивного об'єкта, що включає задану послідовність кроків, називаютьалгоритмическим процесом.
Інтуїтивне поняття алгоритму працює, коли йдеться про знайдений алгоритм вирішення конкретної проблеми. Положення суттєво змінюється, якщо виникає алгоритмічна задача, розв'язання якої не знайдено, і потрібно встановити, чи вона має рішення. І тут треба довести чи існування алгоритму, чи його відсутність. Перше можна зробити шляхом фактичного опису процесу, що вирішує завдання. У цьому випадку достатньо інтуїтивного поняття алгоритму, щоб переконатися в тому, що описаний процес є алгоритмом. Довести неіснування алгоритму в такий спосіб неможливо. Для цього необхідне точне формальневизначення. Такого визначення не було до середини 30-х років ХХ століття. Потім майже одночасно рядом математиків було запропоновано кілька визначень алгоритму (іншими словами, було запропонованоформалізація поняття алгоритму).
Перше визначення - через рекурсивні функції - пов'язує поняття алгоритму з числовими функціями, що визначаються на безлічі цілих позитивних чисел і приймають значення на тій самій множині (американські математики А. Черч і С. К. Кліні, спираючись на більш ранні роботи Ж. Ербрана та К. Геделя).
Друге визначення - машина Тьюринга - пов'язує поняття алгоритму з механічним пристроєм, здатним виконувати дискретно елементарні події над елементарними об'єктами (англійський математик A.M. Т'юрінг [1]).
3-тє визначення - як деякого набору правил, званих системою продукцій (запропонував американський математик Еге. Пост)
Четверте визначення - нормальний алгоритм Маркова - пов'язує поняття алгоритму з класом словникових перетворень в результаті заміни частини слова або всього слова іншим (А.А. Марков [2]).
Існування різних визначень поняття алгоритму має свої переваги, т.к. для вирішення різних завдань зручно використовувати різні найбільш підходящі для цього випадку визначення.
Довести, що запропоновані математично строгі конструкції справді є формалізацією змістовного поняття алгоритму не можна, оскільки, з одного боку, є суворі визначення, з другого - наші інструктивні ставлення до поняття алгоритму, які можуть бути предметом математичного розгляду.
Така ситуація не є незвичайною для математики і виникла не вперше – багато математичних визначень є формалізацією наших змістовних.уявлень про аналізовані явища. Наприклад, суворе математичне визначення безперервності функціїf(z) на відрізку [а,b]
конкретизує наше уявлення про безперервність ліній, які є графіками цих функцій.
У тому, що запропоновані визначення поняття алгоритму є тим, що потрібно, і відповідають змістовним математичним уявленням, нас переконують такі факти.
По-перше, було доведено, що всі запропоновані суворі визначення поняття алгоритму, незважаючи на їх різні форми, еквівалентні між собою. Тобто, якщо існує алгоритм у сенсі одного визначення, то існують алгоритми й у сенсі інших визначень.
По-друге, будь-який із відомих у математиці алгоритмів, а таких алгоритмів за багато років існування математики накопичилося досить багато, може бути формалізований у рамках запропонованих визначень. І зовсім не видно, як може бути заданий алгоритм, що не вкладається в рамки цих формалізації.
По-третє, все подальше розвиток теорії алгоритмів, що базується на цих визначеннях, переконує нас у правильності запропонованих визначень.
Після того як формальне визначення поняття алгоритму було надано, з'явилася можливість доводити, що деякі масові проблеми не мають алгоритмічного вирішення. І такі докази справді були майже одразу отримані. Перше їх (1936 р.) належить А. Черчу. Він показав, що обчислення предикатів алгоритмічно нерозв'язне. Зауважимо, що відсутність алгоритму розв'язання масової проблеми не означає, що не можна вирішити кожне конкретне завдання цієї проблеми, а свідчить лише про відсутність єдиного методу вирішення всіх цих завдань.
Кожному з наведених вище 4 визначень алгоритмувідповідає власний тип універсальної алгоритмічної моделі. Далі розглянемо докладніше перші два типи моделей.
Список вправ на тему“Теорія алгоритмів”
26. Яка функція виходить із j та y за допомогою схеми примітивної рекурсії, якщо:
а) , ; б) , ?
27.Довести, що такі функції примітивно рекурсивні:
а Б В Г) ,
д) - число дільників числах, де .
28.Визначте наступні функції за допомогою обмеженого оператора мінімізації
а); б).
29.Довести рівності, якщо
а) , ; б) , .
30.Складіть програму "ліве зрушення" для машини Тьюринга з алфавітомА=: 01x q10Þq001>x0.
31.Машина ТьюрингаТпрацює в алфавітіА=. Безліч внутрішніх станів машиниQ=q1,q2>. Функціональна схема цієї машини представлена таблиці.