• Основні  визначення, властивості та   способи задання
  • 10.1. Поняття про алгоритм.  Еволюція тлумачення та властивості
  • 10.2. Способи задання алгоритмів

Основні  визначення, властивості та   способи задання

Поняття алгоритму належить не лише до фундаментальних наукових понять, а й до людських надбань. Ми в оточенні різноманітності алгоритмів у всіх сферах життя і діяльності. Наші дії багато в чому доведені до несвідомого автоматизму й ми часом і не усвідомлюємо, що вони вже регламентовані тим чи іншим алгоритмом. Адже життя кожного із нас складається з виконання повсякденних алгоритмів, починаючи із засвоєння алгоритмів дитинства, як – от складання пірамідки, і закінчуючи пошуком алгоритмів для вирішення наукових проблем. Узагалі будь-яку людську діяльність можна подати у вигляді алгоритмічного процесу. Автори огляду основних досягнень теорії алгоритмів [1] стверджують: "Алгоритмічні концепції відіграють у процесі навчання і виховання сучасної людини фундаментальну роль, порівнянну лише з роллю писемності".

На одній із наукових конференцій (1984 р.) академік А. А. Самарський зобразив на слайді Інформатику красунею, яка мчить по неосяжному науковому океану на трьох китах. Імена тих китів: Модель, Алгоритм, Програма. Центральний кит - теорія алгоритмів, поєднавшись із математичною логікою, становлять теоретичний фундамент сучасних комп’ютерних наук.

І хоча інтуїтивно поняття алгоритму зрозуміле, мабуть, кожному, формально визначити цей об’єкт у нетривіальній теорії алгоритмів зовсім не так просто, як здається на перший погляд. По-перше, насторожує надмірна популярність цього поняття і, як у таких випадках кажуть, його розширене тлумачення. Так, вам могли траплятися такі різні алгоритми : “алгоритм Евкліда“, “алгоритм шахіста“ , “алгоритм пошуку інформації“, “алгоритм, як бути красунею“ та інші. По-друге, алгоритми, як самі по собі суть об’єкти специфічного типу, які важко описати математично. Вони мають нетипову для математичних об’єктів властивість, а саме семантичну властивість “мати зміст“. У цьому відношенні теорія алгоритмів подібна до математичної логіки. Із семантичними об’єктами, що несуть у собі зміст, математики, ще не звикли поводитися. Сенс терму або формули в математичній логіці “вказівний“: терм вказує на річ (тобто позначає), а формула - на факт. Сенс алгоритму “наказовий“: алгоритм повинен бути виконаний. Таким чином, теорія, що вивчає алгоритми, може трактуватися як свого роду лінгвістика наказових пропозицій.  І, по-третє, теорія алгоритмів виникла на стику математики та інформатики. Тому вчені з обох боків “тягнули до себе ковдру“ при побудові теорії алгоритмів. Цю специфіку можна помітити, вивчаючи монографії та підручники з теорії алгоритмів. Залежно від того, ким вони написані - математиками чи знавцями інформатики, ми відчуваємо особливість змісту матеріалу, відображеного в них [1-5].

У сучасності слово “алгоритм“ як науковий термін вийшло за межі математики. Цей термін застосовується в найрізноманітніших галузях науки і техніки, розуміючи при цьому точно сформульоване правило, призначення якого – керувати діями для досягнення необхідного результату.

 

10.1. Поняття про алгоритм.  Еволюція тлумачення та властивості

Поняття “ алгоритм “ - концептуальна основа різноманітних процесів у інформатиці. Саме наявність алгоритмів і забезпечує можливість автоматизації. Більше того, значною мірою  теорія алгоритмів допомагає для проникати математичним методам у всі сфери життя і науки, навіть біологію, лінгвістику, економіку аж до філософії природознавства [ 1-12].

Поняття алгоритму формувалося з найдавніших часів і до тридцятих років  ХХ ст., у науковому колі склалось інтуїтивне уявлення про цей об’єкт.         Одним із найдавніших алгоритмів,  у його інтуїтивному розумінні, як скінченної послідовності елементарних дій, що вирішують поставлене завдання, вважається алгоритм знаходження найбільшого спільного дільника двох чисел (алгоритм Евкліда). Відзначимо, що протягом тривалого часу, аж до початку XX століття, термін “алгоритм“ вживався лише в стійкому сполученні “алгоритм Евкліда“, хоча історично встановлено, що задовго до Евкліда цей алгоритм був уже відомий, наприклад, Аристотелю.  

Змістовні явища, що привели до утворення поняття “алгоритм“, простежуються в математиці впродовж усього часу її існування. Саме слово “алгоритм“, як стверджують історики та математики, з'явилося декілька століть тому й означало не термін, а ім'я. Узбецький математик Аль-Хорезмі, вчений, якому математика й людство зобов'язані багатьма відкриттями, був відомий європейським математикам у латинській транскрипції як Алгоризмі. А повне його ім'я - Абу Абдулла Абу Джафар Мухаммад ібн Муса аль-Хорезмі (близько 780 р. — близько 850 р. ) - у перекладі буквально - батько Абдулли, Мухаммед, син Муси, уродженець Хорезмі. Його книга - “Хисаб аль-джабр у аль-мукабаля“ . Саме із трактату Аль-Хорезмі з арифметики почалося знайомство Європи з алгоритмами - строгими процедурами для виконання арифметичних операцій. Тобто алгоритм, точніше алгоризм, розуміли як керівництво для вирішення завдань.

Подальший розвиток математики затвердив ту думку, що вирішення будь-якої проблеми повинне бути алгоритмічним. Р. Декарт, Г. Ф. Лейбніц,

Д. Гільберт стимулювали алгоритмічні дослідження. В 1900 на Другому міжнародному конгресі математиків (Париж) Давид Гільберт сформулював 23 важливі математичні проблеми, знаходження алгоритму розв'язування яких, на його думку, сприяло б подальшому розвитку математики.

Саме в ті часи були поширені дві точки зору :

1.    Усі проблеми є алгоритмічно розв’язними. Просто ще не існують знання для побудови алгоритму.

2.    Існують класи завдань, для вирішення яких взагалі не існує алгоритмів. Це дуже сильне твердження, тому що воно поширюється на все майбутнє.

Для доведення не існування алгоритму потрібно було мати його точне математичне визначення, тому  після сформування поняття алгоритму як нової та окремої сутності першочерговою постала проблема знаходження адекватних формальних моделей алгоритму та дослідження їх властивостей. Формальні моделі були запропоновані як для первісного поняття алгоритму, так і для похідного поняття алгоритмічно обчислюваної функції. Вперше алгоритм як термін з’явився у працях Е. Бореля (1912) та Г. Вейля (1921).

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

Перші фундаментальні праці з теорії алгоритмів були опубліковані незалежно в 1935-37 роках А. Тюрінгом, А. Черчем, С. Кліні, К. Гьоделем і

Е. Постом. Запропоновані ними машина Тюрінга, машина Поста, частково рекурсивні функції й лямбда-вирахування Черча були еквівалентними формалізмами алгоритму. Сформульовані ними тези (Поста й Черча-Тюрінга) постулювали еквівалентність запропонованих ними формальних систем та інтуїтивного поняття алгоритму. Важливим розвитком цих праць стало формулювання й доведення алгоритмічно нерозв'язних проблем. У 1950-ті - роки істотний внесок у теорію алгоритмів зробили праці

А. М. Колмогорова та А. А. Маркова (молодшого), а в 1970-х роках у теорії алгоритмів плідно працював Ю. В. Матіясевич, зокрема над розв’язанням проблем Гільберта.

Запропоноване А. Марковим поняття “нормального алгоритму“ є величезним внеском у світову науку, а А. Колмогорову належить пріоритет у визначенні загального поняття алгоритму та  створення теорії складності конструктивних об’єктів.

У 1960-70-ті роки сформулювалися такі напрямки в теорії алгоритмів:

•  Класична теорія алгоритмів (викладення завдання у термінах формальних мов, поняття задачі вирішення, введення класів складності, формулювання в 1965 році Едмондсом проблеми P=NP, відкриття класу NP-повних задач і його дослідження)[1].
•  Теорія асимптотичного аналізу алгоритмів (поняття складності й трудомісткості алгоритму, критерії оцінки алгоритмів, методи одержання асимптотичних оцінок, зокрема для рекурсивних алгоритмів, асимптотичний аналіз трудомісткості або часу виконання), у розвиток якої зробили істотний внесок Кнут, Ахо, Хопкрофт, Ульман [2,4].
• Теорія практичного аналізу обчислювальних алгоритмів (одержання явних функцій трудомісткості,  практичні критерії якості алгоритмів, методика вибору раціональних алгоритмів), основними роботами в цьому напрямку, мабуть, потрібно вважати фундаментальні праці [1,2].

Відтодібагато вчених були причетними до розвитку теорії алгоритмів. Необхідно відзначити також чималий внесок у теорію алгоритмів, зроблений Д. Кнутом, A. Ахо і Дж. Ульманом. Потрібно пригадати і друге видання книги “Алгоритми: побудова й аналіз“ Томаса Х. Кормена, і праці Чарльза І. Лейзерсона, Рональда Л. Ривеста, Кліффорда Штайна.

Учені, що упорядковували теорію алгоритмів, рано чи пізно стикалися з тим, що потрібно означити об’єкт  досліджень. Виявилося, що всі різноманітні  означення, подані ними щодо алгоритму, є еквівалентними поняттями,  й чудовим науковим результатом є доведення еквівалентності цих формальних визначень у змісті їх  рівнозначності. Наводячи всі означення, як кажуть математики, “до загального знаменника“, можна дати загальне визначення алгоритму:

Алгоритм – спосіб перетворення інформації за правилами, сформульованими певною мовою.

Незважаючи на зусилля дослідників, відсутнє єдине вичерпно строге визначення поняття алгоритму. Всі вони є інтуїтивними, так само й те, що наведене вище. Інтуїтивно кажучи, щоб отримати розв’язок будь-якої задачі потрібно виконати дії за строго визначеним формальним приписом. Цей формальний припис і є алгоритмом.

У загальному випадку зрозуміло, що алгоритм – це детермінована процедура, яку можна застосувати до будь-якого елемента певного класу символьних входів і яка для кожного такого входу видає через скінченне число дій (кроків) відповідний результат своєї дії. Нехай D - область (множина) вихідних даних завдання, а R - множина можливих результатів, тоді ми можемо говорити, що алгоритм А здійснює відображення А : D  ® R.

Будь-який алгоритм повинен мати такі основні властивості:

Визначеність (однозначність) - кожна команда алгоритму однозначно визначає дії виконавця і не припускає подвійного тлумачення.

Дискретність – можливість розбивки алгоритму на скінченну кількість етапів, причому результати попереднього етапу є вихідними для наступного.

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

Зрозумілість – алгоритм повинен бути зрозумілим конкретному виконавцеві, який повинен виконати кожну команду алгоритму в строгій відповідності із призначенням.

Результативність (збіжність) – виконання алгоритму повинне закінчуватися результатом або інформацією про те, що не може бути отриманим результат.

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

 Приклад 10.1. Розглянемо алгоритм Евкліда знаходження найбільшого спільного дільника двох натуральних чисел a і в ( НСД (а, в)). Цей алгоритм переробляє слова виду (а,в) у алфавіті, що складається з 10 цифр, дужок “ (“ та “)“, знака пунктуації “ , “, у слова того самого алфавіту (результатом буде слово із цифр). Скінченна система правил, що визначають цей алгоритм, складатиметься з правила ділення, визначення остачі від ділення  і правила визначення, коли алгоритм закінчує роботу і видає результат.

Приклад 10.2. Розглянемо процес приготування страви швидкого харчування : 1. Висипати в порожній посуд вміст пакетика. 2. Залити в ємність 200 мл гарячої води. 3. Ретельно перемішати. Щоб виконати скінченну систему правил за цим “алгоритмом», потрібно проробити суто механічні дії.

Проте останній приклад не є алгоритмом у тому сенсі, що ми визначили. Оскільки він не відповідає всім вимогам до його властивостей, дамо йому визначення “майже“ алгоритм, так само як і медичним рецептам. Подумайте чому саме? Хоча такий розподіл.

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

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

 

10.2. Способи задання алгоритмів

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

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

Існує декілька методів запису або подання алгоритмів. Вибір методу залежить від виконавця й представлених розробником алгоритмів варіантів подання.

Перший спосіб задання алгоритмів - це словесно-формульний (опис здійснюється у словесній формі з використанням математичних або інших формул). Він  описує  виконання дій алгоритму в певній послідовності за допомогою слів і пропозицій природної мови.  Форма викладу довільна і встановлюється розробником. У математиці наявність формул дозволяє розв'язати задачу, навіть “не використовуючи слів“.

Приклад 10.3. Записати алгоритм знаходження найбільшого спільного дільника (НСД) двох натуральних чисел (алгоритм Евкліда).

Розв’язання. Алгоритм може бути поданий таким чином:
1. Поставити два числа.
2. Якщо числа однакові, то взяти будь-яке з них як відповідь і зупинитися, інакше продовжити виконання алгоритму.
3. Визначити більше із чисел.
4. Замінити більше із чисел різницею більшого і меншого із чисел.
5. Повторити алгоритм з кроку 2.

Другий спосіб задання алгоритмів - це подача алгоритму у вигляді таблиць, формул, схем, рисунків тощо. Наприклад, всіх нас навчали в дитячому садочку правил поведінки на дорозі. І найкраще діти, вочевидь, сприймають алгоритм, поданий у вигляді схематичних малюнків. Дивлячись на них, дитина, а потім і доросла людина, відпрацьовує ту лінію поведінки, що їй пропонується.

Третій спосіб задання алгоритмів - це запис алгоритмів за допомогою блок-схеми. Цей метод був запропонований в інформатиці для наочності подання алгоритму за допомогою набору спеціальних блоків. Блок-схема – це таке графічне подання алгоритму, при якому розв'язання задачі зображується у вигляді різних геометричних фігур, усередині яких записані тексти, що разом із формою фігури пояснюють дію, яку потрібно виконати, та взаємозв’язків між ними.

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

Приклад 10.4. Використовуючи необхідні для представлення блоки, можна подати, наприклад, алгоритм чищення картоплі в такому вигляді:

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

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

У ряді випадків псевдокодом називають систему команд абстрактної машини, наприклад, P-код, псевдокод вигаданої машини MIX і т. д. На відміну від псевдокоду неформального характеру такий псевдокод уже строго формалізований і може бути трансльований у працюючу програму за наявності програми-емулятора даної гіпотетичної машини.

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

Приклад 10.5. Записати на псевдокоді алгоритм Евкліда – знаходження найбільшого спільного дільника двох чисел.

Розв’язання.

1 функція нсд(a, b)

2    якщо b = 0

3       поверни a

4   інакше

5       поверни нсд(b, a mod b)

Ви, мабуть, помітили, що цей варіант алгоритму відрізняється від алгоритму, поданого під час розв’язання прикладу 10.1. Насправді існує декілька варіантів написання алгоритму Евкліда, в даному разі записано у псевдокоді рекурсивний варіант.

П'ятий спосіб, максимально наближений до комп'ютера, задання алгоритмів - це мови програмування. Справа в тому, що найчастіше у практиці виконавцем створеного людиною алгоритму є машина, і тому він повинен бути написаний мовою, зрозумілою для комп'ютера, тобто мовою програмування. Мова програмування - це знакова система, призначена для опису процесів вирішення завдань та їх реалізації на ЕОМ. Реалізація означає, що описи можуть бути введені в ЕОМ і однозначно нею зрозумілі. До мов програмування належать мови команд або машинні мови та мови високого рівня.