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

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

- словесний;

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

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

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

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

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

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

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

Задача. Дано два вектори А = (а₁, а₂, ..., а_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. Граф-схема алгоритму прикладу

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

Призначення кожного із таких блоків, а також правила їх застосування регламентовані Міждержавним стандартом Єдиної системи програмної документації (ЄСПД) ГОСТ 19.701-90. « Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».

В табл. 1 наведені позначення даного ГОСТ, які використовуються для опису алгоритмів програм.

Таблиця 1.

Графічне зображення блоку	Найменування	Функція
	Термінатор (пуск-зупинка)	Позначення початку і кінця алгоритму.
	Дані (введення-виведення)	Перетворення даних у форму, придатну для обробки (введення) або відображення результатів обробки (виведення). Використовується для позначення будь-якої операції введення / виведення.
	Процес (операторний блок)	Виконання операції або групи операцій у результаті яких змінюється значення, форма представлення або розташування даних. Типове його використання – позначення оператора присвоювання.
	Рішення (умовний блок)	Вибір подальшого напрямку виконання алгоритму залежно від умови. Використовується для позначення умовного оператора або оператора варіанта.
	Зумовлений процес (підпрограма)	Відображає виконання процесу, який складається з однієї або кількох операцій, що визначені в іншому місці програми. Використовується для позначення виклику підпрограм (процедур і функцій).
	Межі циклу	Символ складається з двох частин - відповідно, початок і кінець циклу - операції, що виконуються всередині циклу, розміщуються між ними. Умови циклу і збільшення записуються всередині символу початку або кінця циклу - в залежності від типу організації циклу.
	З'єднувач	Відображає зв'язок між перерваними лініями потоку інформації (наприклад, на іншій сторінці).
	Коментар	Використовується для надання більш детальної інформації про кроки, процеси або групи процесів.
Розмір а повинен вибиратися з ряду 10, 15, 20 мм. Допус­кається збільшувати розмір а на число, кратне 5. Роз­мір b дорівнює 1,5а. При ручному виконанні схем алгоритмів допускається встановлювати b рівним 2a.

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

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

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

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

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

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

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

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

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

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

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

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

1) блок-схема повинна містити одну початкову, одну кінцеву й кінцеве число інших вершин;

2) входи ій виходи різних вершин з'єднуються дугами, спрямованими тільки від виходу до входу;

3) кожен вихід будь-якої вершини з'єднується тільки з одним входом;

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

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

Приклад блок-схеми алгоритму обчислення коренів квадратного рівняння представлений на рис. 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-схема алгоритму задачі

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

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