7.2. Алгоритми.

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

Поняття алгоритму таке ж основоположне для інформатики, як і поняття інформації. Саме тому важливо в нім розібратися.

Назва "алгоритм" відбулася від латинської форми імені найбільшого середньоазіатського математика Мухаммеда ібн Муса ал-Хорезмі (Alhorithmi), що жив в 783‑850 рр. У своїй книзі "Про індійській рахунок" він виклав правила запису натуральних чисел за допомогою арабських цифр і правила дій над ними "стовпчиком", знайомі тепер кожному школяру. У XII столітті ця книга була перекладена на латинь і набула широкого поширення в Европе.

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

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

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

Це — не визначення в математичному сенсі слова, а, швидше, опис інтуїтивного поняття алгоритму, що розкриває його суть.

Порядок виконання алгоритму:

• Дії в алгоритмі виконуються в порядку їх запису

• Не можна міняти місцями ніякі дві дії алгоритму

• Не можна не закінчивши однієї дії переходити до наступної

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

Існує багато тлумачень алгоритму. Наприклад:

«Алгоритм — це всяка система обчислень, що виконуються по строго заданим правилам, яка після якого-небудь числа кроків свідомо приводить до рішення поставленої задачі.» (А. Колмогоров) 

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

«Алгоритм — строго детермінована послідовність дій, що описує процес перетворення об'єкту з початкового стану в кінцевий, записана за допомогою зрозумілих виконавцеві команд.» (Угріновіч Микола Дмитрович) 

«Алгоритм — це послідовність дій, направлених на отримання певного результату за кінцеве число кроків.» (Roxanstudio) 

«Алгоритм є формалізована послідовність дій (подій). Алгоритм може бути записаний словами і зображений схематично. Практично будь-яка невипадкова повторювана дія піддається опису через алгоритм.» ([grey_olli]) 

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

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

Виконавець алгоритму

Виконавець алгоритму — це деяка абстрактна або реальна (технічна, біологічна або біотехнічна) система, здатна виконати дії, що наказують алгоритмом.

Виконавця характеризують:

• середовище;

• елементарні дії;

• система команд;

• відмови.

Середовище — це "житло" виконавця. Наприклад, для виконавця Робот зі шкільного підручника середовище — це нескінченне клітинне поле. Стіни і закрашені клітки теж частина середовища. А їх розташування і положення самого Робота задають конкретний стан середовища.

Система команд. Кожен виконавець може виконувати команди тільки з деякого строго заданого списку — системи команд виконавця. Для кожної команди мають бути задані умови застосовності (у яких станах середовища може бути виконана команда) і описані результати виконання команди. Наприклад, команда Робота "вгору" може бути виконана, якщо вище за Робота немає стіни. Її результат — зсув Робота на одну клітку вгору.

Після виклику команди виконавець здійснює відповідну елементарну дію.

Відмови виконавця виникають, якщо команда викликається при неприпустимому для неї стані середовища.

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

Основні властивості алгоритмів наступні:

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

2.   Дискретність (переривчатість, нарізність) — алгоритм повинен представляти процес рішення задачі як послідовне виконання простих (або раніше визначених) кроків (етапів).

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

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

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

Способи запису алгоритмів.

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

• словесна (запис на природній мові);

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

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

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

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

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

Алгоритм може бути наступним:

• задати два числа;

• якщо числа рівні, то взяти будь-яке з них за відповідь і зупинитися, інакше продовжити виконання алгоритму;

• визначити більше з чисел;

• замінити більше з чисел різницею більшого і меншого з чисел;

• повторити алгоритм з кроку 2.

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

Словесний спосіб не має широкого розповсюдження, оскільки такі описи:

• строго не формалізуються;

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

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

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

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

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

Блок "рішення" використовується для позначення переходів управління по умові. У кожному блоці "рішення" мають бути вказані питання, умова або порівняння, які він визначає.

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

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

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

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

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

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

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

Прикладом псевдокоду є шкільна алгоритмічна мова в російській нотації (шкільна АМ), описаний в підручнику А.Г. Кушніренко та ін. "Основи інформатики і обчислювальної техніки", 1991. Цю мову надалі ми називатимемо просто "алгоритмічна мова".

Основні службові слова

Загальний вид алгоритму:

алг назва алгоритму (аргументи та результат) дано умови застосування алгоритму необхідно ціль віконання алгоритму поч опис проміжних величин | послідовність команд (тіло алгоритму) кін

Частина алгоритму від слова алг до слова нач називається заголовком, а частина, увязнена між словами  нач  і  кон  — тілом алгоритму.

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

Приклади речень алг:

                  алг Об'єм та площа циліндру ( арг дійсн R, H,  рез дійсн V, S )                   алг Корені КвРів ( арг дійсн а, b, c,  рез дійсн x1, x2,  рез літ t )                   алг Виключити елемент ( арг ціл N,  арг рез дійсн таб А[1:N] )                   алг Диагональ ( арг ціл N,  арг ціл таб A[1:N,  1:N],  рез літ Відповідь )

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

• алг Заміна (арг літ Str1, Str2, арг рез літ Text)

    дано | довжина підстрок Str1 і Str2 співпадають

    необхідно | повсюди в строці Text підстроку Str1 заміннити на Str2

• алг Число максимумів (арг ціл N, арг дійс таб A[1:N], рез ціл K)

    дано | N>0

    необхідно | К — число максимальних елементів в таблиці А

• алг Опір (арг дійс R1, R2, арг ціл N, рез дійс R)

    дано | N>5, R1>0, R2>0

    необхідно | R — Опір схеми

Тут в реченях дано і необхідно після знаку "|" записані коментарі. Коментарі можна поміщати в кінці будь-якого рядка. Вони не обробляються транслятором, але істотно полегшують розуміння алгоритму.