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

Міністерство освіти та науки України

Вінницький національний технічний університет

Кафедра Комп’ютерних наук

Лабораторна робота №1

З дисципліни «Теорія алгоритмів»

Тема : “ Аналіз основних підходів щодо уточнення поняття „алгоритм”, а

також основних властивостей та форм подання алгоритмів ”.

Виконала студентка групи 2КН-21б :

Примак А.В

Перевірив викладач :

Денисюк В.О

Вінниця – 2022

Лабораторна робота № 1

Тема: Аналіз основних підходів щодо уточнення поняття „алгоритм”, а також основних властивостей та форм подання алгоритмів.

Мета: проаналізувати основні підходи щодо уточнення поняття „алгоритм; проаналізувати основні властивості алгоритмів, а також визначити переваги та недоліки основних форм подання алгоритмів та областей їх застосування.

Хід роботи

1. Основні підходи щодо уточнення поняття „алгоритм” та їх особливості.

Кожен алгоритм має задовольняти ряду вимог (властивостей). Однак поняття, використані у формулюваннях цих вимог (такі, як ясність, чіткість, елементарність тощо), самі потребують уточнення. Очевидно, що їх словесні означення міститимуть нові поняття, які знову потребуватимуть уточнення,       і т. д.

Тому в ТА прийнято інший підхід: вибирається скінченний набір вхідних об'єктів, які оголошуються елементарними і кінцевий набір способів побудови з них нових об'єктів.

Так, наприклад, при уточненні поняття «дані» під даними прийнято вважати безліч слів у кінцевих алфавітах.

Для уточнення детермінованості будуть використовуватися або графічні схеми та еквівалентні їм словесні описи, або опис механізму реалізації алгоритму. Крім того, слід зафіксувати набір елементарних кроків і домовитися про організацію пам'яті. Після того як це буде зроблено і вийде конкретна алгоритмічна модель.

Такі алгоритмічні моделі претендують на право вважатися формалізацією поняття „алгоритм”.

Це означає, що вони повинні бути універсальними: допускати опис будь-яких алгоритмів. Тому може виникнути природне заперечення проти запропонованого підходу: чи не приведе вибір конкретних засобів до втрати спільності формалізації?

Якщо враховувати основні цілі, що стояли під час створення ТА (універсальність і пов’язану з ними можливість говорити в рамках будь-якої моделі про властивості алгоритмів взагалі), то це заперечення знімається.

По-перше, проводиться зведення одних моделей до інших (показується, що будь-який алгоритм, описаний засобами однієї моделі, може бути описаний і засобами іншої).

По-друге, завдяки взаємозведенню моделей у ТА вдалося виробити інваріантну щодо моделей систему понять, яка дозволяє говорити про властивості алгоритмів незалежно від того, яка формалізація алгоритму обрана. Ця система понять заснована на понятті обчислюваної функції (функції, для обчислення якої існує алгоритм).

Хоча спільність формалізації у конкретній моделі не втрачається, різний вибір вхідних засобів приводить до моделей різного виду. •

Виділяють 3 основні типи універсальних алгоритмічних моделей, що розрізняються вихідними евристичними міркуваннями відносно означення того, що таке алгоритм.

Перший тип зв'язує поняття алгоритму з найбільш традиційними поняттями математики – обчисленнями та числовими функціями.

Найбільш розвинена та вивчена модель цього типу – РЕКУРСИВНІ ФУНКЦІЇ – є історично першою формалізацією поняття алгоритму. Для вчених, яких цікавлять лише факти існування або неіснування алгоритмів (а не самі алгоритми), зовсім не обов’язково вивчати алгоритми. Досить знайти об’єкти, які існують або ні тоді, коли існують або ні алгоритми. Вважають, що такими об’єктами є рекурсивні функції.