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

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

• словесний;

• словесно-формульний;

• графічна схема;

• блок-схема;

• операторна схема;

• НІРО-схема;

• таблиця рішень, тощо.

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

Задача. Дано два вектори А = (а₁, а₂, ..., а_n) та В = (b₁, b₂, ..., b_n). Знайти вектор С, елементи якого обчислюються за формулою с_i = а_i+b_i.

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

Приклад словесного опису алгоритму:

1. Покладемо i рівним 1.

2. Покладемо с_i  рівним а_i+b_i.

3. Перевіримо, чи i дорівнює n. Якщо так, то обчислення припиняємо. Якщо ні, то збільшуємо i на 1 та переходимо до п. 2.

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

Для визначення порядку вводять мітки Q1, Q2, .... Якщо не вказано, до якої мітки переходити, то вважається, що це перехід до наступної дії.

Приклад словесного-формульного опису алгоритму:

i = 1

Q1 : c_i = а_i+b_i .

Якщо i = n, то перейти до Q3 , інакше — до Q2.

Q2 : i = i + 1. Перейти до Q1.

Q3 : Закінчити обчислювання.

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

Приклад граф-схеми алгоритму представлений на рис. 3.

Рис. 3. Граф-схема алгоритму прикладу

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

На зв'язках, що визначають послідовність виконання блоків, стрілки не обов'язкові, якщо їх напрям відповідає просуванню "зверху-вниз" і "зліва-направо" і, якщо вони не мають зламів. В інших випадках їх напрямок обов'язково позначають стрілкою. Лінію потоку, як пра­вило, підводять до середини символу. Відстань між паралельними лініями потоку має бути не меншою 3 мм, між іншими символами — не меншою 5 мм.

У табл. 1 наведено символи, що найчастіше викорис­товуються в блок-схемах алгоритмів. Розмір а має вибиратися з ряду 10, 15, 20 мм. Допус­кається збільшувати розмір а на число, кратне 1. Роз­мір b = 1,5а.

Таблиця 1.

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

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

Умовний блок позначається ромбом, в який вписується деяка умова. Оскільки результатом перевірки умови може бути або "так", або "ні" ("істина" або "хибність", "0" або "1"), блок має два відповідних цим відповідям виходи (рис. 4).

Рис. 4. Умовний блок

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

Рис. 5. Поєднання зображення входів

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

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

Конфігурація та розміщення блоків визначені відповідними стандартами ЄСПД (Єдиної системи програмної документації), зокрема, ДСТ 19002-80.

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

Приклад блок-схеми алгоритму представлений на рис. 6.

Рис. 6. Блок-схема алгоритму прикладу

Операторні схеми. Це послідовність операторів певних типів (всі перетворення інформації подають у вигляді послідовності допустимих операцій).

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

Розрізняють такі основні типи операторів:

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

• Оператори перевірки логічних умов. Визначають порядок дій алгоритму. Позначаються малими літерами, а умова записується у дужках поряд, наприклад: p (a > 0).

• Оператори переадресації. Змінюють значення різних параметрів. Вони позначаються літерою F, а в дужках поряд вказують параметр. Величину, на яку змінюється параметр, задають у вигляді степеня. Наприклад: F1(i) = F(i), F2(i), F-1(i). Тут параметр і змінюється відповідно на 1, 2, –1.

• Оператори переносу. Замінюють значення одного параметра значенням іншого, наприклад: [a, b] параметр b замінюється на а.

• Оператори формування. Присвоюють початкові значення параметрів, наприклад, {5ai}.

Оператори виконуються у тому порядку, у якому записані. Щоб змінити порядок їх виконання, використовують пари стрілок, які мають свої номери: ai — звідки переходити; ai — куди переходити за i-ю стрілкою.

Нехай D_i — обчислює величину c_i = а_i+b_i. Тоді алгоритм визначається такою операторною схемою:

{1ai}a1DiF(i) p(i>n) a1 останов.

НІРО-схеми (Hierarchy Input Process Output). Це таблиця, кожний рядок якої містить вказівки щодо вхідної інформації, дії над нею та вихідної інформації.

Алгоритм розв’язання задачі у вигляді НІРО-схеми зображено на рис. 7.

Тут  означає «поле 1, де міститься n», - означає «поле 2 розміщення елементів масиву а» і т.д.

У лівій колонці 1 означає, що використовується значення з поля 1, тобто n і т.д.

У середній колонці

Повторити для  елемента А ввести елемент  к Повторень

означає: «Повторити для кожного елемента масиву А дію вводу. Кінець повторень». Стрілка вказує, з якого поля треба взяти кількість елементів масиву. Взагалі,  означає «для всіх» або «для кожного».

Рис. 7. HIPO-схема алгоритму задачі

Таблиці рішень. Це табличне представлення алгоритму прийняття рішень у процесі перетворення інформації.

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