Аналіз основних підходів щодо уточнення поняття „алгоритм”, а також основних властивостей та форм подання алгоритмів
Автор: Kayleigh • Март 23, 2023 • Лабораторная работа • 1,930 Слов (8 Страниц) • 222 Просмотры
Міністерство освіти і науки України
Вінницький національний технічний університет
Факультет інтелектуальних інформаційних технологій та автоматизації
Кафедра КН
Звіт про виконання
Лабораторної роботи з дисципліни
«Теорія алгоритмів»
Лабораторна робота №1
Виконав: ст. гр. .
Перевірив: .
Вінниця 2022
Лабораторна робота № 1
Тема: Аналіз основних підходів щодо уточнення поняття „алгоритм”, а також основних властивостей та форм подання алгоритмів.
Мета: проаналізувати основні підходи щодо уточнення поняття „алгоритм; проаналізувати основні властивості алгоритмів, а також визначити переваги та недоліки основних форм подання алгоритмів та областей їх застосування.
Звіт повинен містити
1. Тему, мету та порядок виконання роботи.
2. Основні підходи щодо уточнення поняття „алгоритм” та їх особливості.
3. Властивості алгоритмів (перерахувати ці властивості; детально проаналізувати кожну властивість; навести відповідний приклад).
4. Форми подання алгоритмів (перерахувати ці форми (як мінімум словесний, графічний, у вигляді псевдокоду та програмний); навести приклади кожної форми; детально проаналізувати переваги, недоліки та області застосування кожної з цих форм).
5. Розширені висновки з роботи.
Хід роботи
1. Основні підходи щодо уточнення поняття „алгоритм” та їх особливості.
Кожен алгоритм має задовольняти ряду вимог (властивостей). Однак поняття, використані у формулюваннях цих вимог (такі, як ясність, чіткість, елементарність тощо), самі потребують уточнення. Очевидно, що їх словесні означення міститимуть нові поняття, які знову потребуватимуть уточнення, і т. д. Тому в ТА прийнято інший підхід: вибирається скінченний набір вхідних об'єктів, які оголошуються елементарними і кінцевий набір способів побудови з них нових об'єктів. Так, наприклад, при уточненні поняття «дані» під даними прийнято вважати безліч слів у кінцевих алфавітах. Для уточнення детермінованості будуть використовуватися або графічні схеми та еквівалентні їм словесні описи, або опис механізму реалізації алгоритму. Крім того, слід зафіксувати набір елементарних кроків і домовитися про організацію пам'яті. Після того як це буде зроблено і вийде конкретна алгоритмічна модель.
Такі алгоритмічні моделі претендують на право вважатися формалізацією поняття „алгоритм”. Це означає, що вони повинні бути універсальними: допускати опис будь-яких алгоритмів. Тому може виникнути природне заперечення проти запропонованого підходу: чи не приведе вибір конкретних засобів до втрати спільності формалізації? Якщо враховувати основні цілі, що стояли під час створення ТА (універсальність і пов’язану з ними можливість говорити в рамках будь-якої моделі про властивості алгоритмів взагалі), то це заперечення знімається. По-перше, проводиться зведення одних моделей до інших (показується, що будь-який алгоритм, описаний засобами однієї моделі, може бути описаний і засобами іншої). По-друге, завдяки взаємозведенню моделей у ТА вдалося виробити інваріантну щодо моделей систему понять, яка дозволяє говорити про властивості алгоритмів незалежно від того, яка формалізація алгоритму обрана. Ця система понять заснована на понятті обчислюваної функції (функції, для обчислення якої існує алгоритм). Хоча спільність формалізації у конкретній моделі не втрачається, різний вибір вхідних засобів приводить до моделей різного виду.
...