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

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

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

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

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

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

застосування.

Основні теоретичні відомості

Поняття алгоритму є центральним об’єктом спеціального розділу

математики – теорії алгоритмів. Першим алгоритмом, що дійшов до

нас, в його інтуїтивному розумінні, вважається запропонований Евклідом

у III столітті до нашої ери алгоритм пошуку найбільшого загального дільника двох чисел. Протягом тривалого часу, аж до початку XX століття

слово „алгоритм” вживалося у поєднанні „алгоритм Евкліда”, а для опису

покрокового розв’язання інших математичних задач використовувалося

слово „метод”.

Початковою точкою відліку сучасної теорії алгоритмів вважать роботу німецького математика К. Геделя (1931 р. – теорема про неповноту

символічних логік), в якій було показано, що деякі математичні проблеми

не можуть бути розв’язані алгоритмами з певного класу. Ця робота дала

поштовх до пошуку і аналізу різних формалізацій алгоритму.

Перші фундаментальні роботи з теорії алгоритмів були опубліковані

незалежно в 1936 році А. Тьюрінгом, А. Черчем та Е. Постом. Запропоновані ними машина Тьюрінга, машина Поста і лямбда-числення Черча

були еквівалентними формалізаціями алгоритму. Сформульовані ними

тези (Поста і Черча-Тьюрінга) постулювали еквівалентність запропонованих ними формальних систем та інтуїтивного поняття алгоритму. Важливим розвитком цих робіт стало формулювання і доведення алгоритмічно нерозв’язуваних проблем.

У 1950-і роки істотний внесок в теорію алгоритмів внесли Н. Колмогоров і А. Марков.

До 1970-х років сформувалися такі три напрями в теорії алгоритмів.

1. Класична теорія алгоритмів (формулювання завдань у термінах

формальних мов, поняття задачі розв’язності, введення класів складності,

2

формулювання проблеми P=NP, відкриття класу NP-повних задач та його

дослідження).

2. Теорія асимптотичного аналізу алгоритмів (поняття складності

і трудомісткості алгоритму, критерії оцінювання алгоритмів, методи

отримання асимптотичних оцінок), у розвиток якої зробили істотний внесок Д. Кнут, А. Ахо, Д. Хопкрофт, Д. Ульман.

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

Кнута „Искусство программирования для ЭВМ”.

У загальному випадку теорія алгоритмів розглядає такі питання як

формалізація поняття „алгоритм” та дослідження формальних алгоритмічних систем; формальне доведення алгоритмічної нерозв’зуваності ряду

завдань; класифікація завдань, визначення і дослідження класів складності; асимптотичний аналіз складності алгоритмів; дослідження та аналіз

рекурсивних алгоритмів; отримання явних функцій трудомісткості для

порівняльного аналізу алгоритмів; розробка критеріїв порівняльного оцінювання якості алгоритмів.

Одержані в теорії алгоритмів теоретичні результати знаходять достатньо широке практичне застосування. При цьому під час дослідження деякого завдання результати теорії алгоритмів дозволяють відповісти на

ряд важливіших питань. Чи є це завдання принципово алгоритмічно

розв’язним? І якщо так – то чи не належить воно до класу NP–повних завдань, при ствердній відповіді на яке можна говорити про істотні часові

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

можливим раціональний вибір алгоритму (з відомої множини алгоритмів)

розв’язання даної задачі з урахуванням особливостей їх застосування;

отримання часових оцінок розв’язання складних задач; отримання вірогідних оцінок неможливості розв’язання деякої задачі за певний час; розробку та вдосконалення ефективних алгоритмів на основі практичного