Основні типи алгоритмічних моделей

ТЕМА 1. АЛГОРИТМИ

Поняття алгоритму

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

Під алгоритмом також розуміють:

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

– правила виконання основних операцій обробки даних;

– опис обчислень за математичними формулами.

Термін "алгоритм" походить від "algorithmi" – латинської форми написання імені великого математика аль-Хорезмі, який сформулював правила виконання арифметичних дій. Тому спочатку під алгоритмом розуміли тільки правила виконання чотирьох арифметичних дій над багатоцифровими числами в десятковій системі числення. Зараз він є одним із фундаментальних понять інформатики.

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

Прикладом алгоритму може служити алгоритм "Переправа". На лівому березі річки знаходяться дві молодих людини зі своїми дівчатами (рис.1). Всім потрібно перебратися на правий берег, але в човні тільки два місця. Кожна дівчина не хоче залишатися на березі без свого молодого чоловіка, якщо на цьому ж березі знаходиться інша молода людина. Як всім переплисти на інший берег?

Рішення: Позначимо дівчат і молодих людей Д1, Д2, М1, М2, переїзд на правий берег →, переїзд на лівий берег ←. Можна записати алгоритм:

1) Д1, Д2 →

2) Д1 ←

3) М1, М2 →

4) М1 ←

5) Д1, М1 →

У 30-х роках минулого століття зародилася і бурхливо розвивається наука, яка називається теорією алгоритмів.

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

На основі формалізації поняття алгоритму можливі наступні дії:

– порівняння алгоритмів за їх ефективністю;

– перевірка їх еквівалентності;

– визначення областей застосування.

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

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

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

Вимоги до алгоритмів

Основні вимоги до алгоритмів.

1. Кожен алгоритм має справу з даними – вхідними, проміжними, вихідними. Для того, щоб уточнити поняття даних, фіксується алфавіт вихідних символів (цифри, букви і т.п.) і вказуються правила побудови алгоритмічних об'єктів. Типовим використовуваним засобом є індуктивна побудова. Наприклад, визначення ідентифікатора в Паскалі, Сі: ідентифікатор – це або буква, або ідентифікатор, до якого приписана праворуч або буква, або цифра. Інший випадок алгоритмічних об'єктів – формули.

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

3. Алгоритм складається з окремих елементарних кроків, причому множина різних кроків, з яких складений алгоритм, скінченні. Типовий приклад множини елементарних кроків – система команд процесора.

4. Послідовність кроків алгоритму детермінована, тобто після кожного кроку вказується, який крок слід виконувати далі, або вказується, коли слід роботу алгоритму вважати закінченою.

5. Алгоритм повинен бути результативним, тобто зупинятися після скінченного числа кроків (залежного від вхідних даних) з видачею результату. Дана властивість іноді називають збіжністю алгоритму.

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

Вимога 1 відповідає цифровій природі ПК, вимога 2 – пам'ять ПК, вимога 3 – програмі машини, вимога 4 – її логічній природі, вимоги 5, 6 – обчислювальному пристрою та його можливостям.

Властивості алгоритмів

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

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

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

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

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

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

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

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

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

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

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

Основні типи алгоритмічних моделей

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

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

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

Третій тип алгоритмічних моделей – це перетворення слів у довільних алфавітах, в яких операціями є заміни фрагментів слів іншим словом. Основною теоретичною моделлю цього типу є нормальні алгоритми Маркова.

Теорія алгоритмів має істотний вплив на розвиток ЕОМ і практику програмування. В теорії алгоритмів передбачені основні концепції, які закладені в апаратуру і мови програмування ЕОМ. Згадувані вище основні алгоритмічні моделі математично еквівалентні. Але на практиці вони істотно розрізняються ефектами складності, що виникають при реалізації алгоритмів, і породили різні напрямки в програмуванні. Так, мікропрограмування будується на ідеях машин Тьюринга, структурне програмування запозичило свої конструкції з теорії рекурсивних функцій, мови символьної обробки інформації (РЕФАЛ, ПРОЛОГ) беруть початок від нормальних алгоритмів Маркова та систем Посту. На основі теорії алгоритмів в даний час отримані практичні рекомендації, що набувають все більшого поширення в області проектування і розробки програмних систем. Результати теорії алгоритмів набувають особливого значення для криптографії.

Форми подання алгоритмів

На практиці найбільш поширеним є такі форми подання алгоритмів:

– словесна (записи природною мовою);

– графічна (зображення з графічних символів);

– псевдокод (напівформалізований опис алгоритмів умовною алгоритмічною мовою, який включає в себе як елементи мови програмування, так і фрази природної мови, загальноприйняті математичні позначення та ін.);

– програмна (тексти мовою програмування).

Словесний спосіб запису алгоритмів – це опис послідовних етапів обробки даних. Алгоритм задається у довільному викладі природною мовою.

Словесний спосіб не набув поширення з наступних причин:

– такі описи строго не формалізуються;

– страждають багатослівністю записів;

– допускають неоднозначність тлумачення окремих записів.

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

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

У табл. 1 наведені найбільш часто вживані блоки, конфігурація яких відповідає ГОСТ 19.701–90 "Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения".

Таблиця 1

Позначення блоку	Виконувана функція
	Початок або Кінець алгоритму
	Обчислювані дії
	Перевірка умови: вибір одного з двох напрямків
	Введення або Вивід даних
	Організація циклічних процесів
	Напрямок ліній потоку – стрілки

Побудова блок-схеми виконується з урахуванням наступних рекомендацій:

1. Блок-схема будується зверху вниз.

2. У будь-який блок-схемі є один елемент, відповідний початку, і один елемент, відповідний кінця.

3. Повинен бути хоча б один шлях з початку блок-схеми до будь-якого елементу.

4. Повинен бути хоча б один шлях від кожного елемента блок-схеми в кінець блок-схеми.

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

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