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

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

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

Факультет інтелектуальних інформаційних технологій та автоматизації

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

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

з теорії алгоритмів

Виконав: студент групи 3КН-21Б 

Рудь В. Ю.

Перевірив: викладач Денисюк В.О.

Вінниця-2022

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

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

Хід роботи

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

         Кожен алгоритм має задовольняти ряду вимог (властивостей). Однак поняття, використані у формулюваннях цих вимог (такі, як ясність, чіткість, елементарність тощо), самі потребують уточнення. Очевидно, що їх словесні означення міститимуть нові поняття, які знову потребуватимуть уточнення, і т. д. Тому в ТА прийнято інший підхід: вибирається скінченний набір вхідних об'єктів, які оголошуються елементарними і кінцевий набір способів побудови з них нових об'єктів. Такі алгоритмічні моделі претендують на право вважатися формалізацією поняття „алгоритм”. Це означає, що вони повинні бути універсальними: допускати опис будь-яких алгоритмів. Тому може виникнути природне заперечення проти запропонованого підходу: чи не приведе вибір конкретних засобів до втрати спільності формалізації? Якщо враховувати основні цілі, що стояли під час створення ТА (універсальність і пов’язану з ними можливість говорити в рамках будь-якої моделі про властивості алгоритмів взагалі), то це заперечення знімається. По-перше, проводиться зведення одних моделей до інших (показується, що будь-який алгоритм, описаний засобами однієї моделі, може бути описаний і засобами іншої). По-друге, завдяки взаємозведенню моделей у ТА вдалося виробити інваріантну щодо моделей систему понять, яка дозволяє говорити про властивості алгоритмів незалежно від того, яка формалізація алгоритму обрана. Ця система понять заснована на понятті обчислюваної функції (функції, для обчислення якої існує алгоритм).

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

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

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

Третій тип алгоритмічних моделей – це перетворення слів у довільних алфавітах, у яких елементарними операціями є підстановки, тобто заміни частини слова (підслова) іншим словом. Переваги цього типу – у його максимальній абстрактності та можливості застосувати поняття алгоритму до об'єктів довільної (не обов'язково числової) природи. Приклади моделей цього типу – канонічні системи Поста та нормальні алгоритми Маркова.

2. Властивості алгоритмів (перерахувати ці властивості;детально проаналізувати кожну властивість;навести відповідний приклад).

Існує 6 властивостей алгоритму:дискретність,визначеність,виконуваність,скін -

ченність,результативність і масовість.

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

Приклад:

визначимо формати змінних x, y, m (x, y – значення для порівняння, m – змінна для зберігання максимального значення);

 - отримаємо значення чисел x та y;

 - порівняємо x та y;

 - якщо x менше ніж y, то більшим є y;