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

Алгоритм є фундаментальним поняттям інформатики. Відомий середньоазіатський мудрець, вчений, філософ і математик Мухаммед бен Муса аль-Хорезмі у IX ст. детально розробив правила чотирьох арифметичних дій (їх можна назвати алгоритмами арифметичних дій). При перекладі його наукових трактатів вперше з’явився термін «алгоритм» (аль-Хорезмі — Algorithmi).

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

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

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

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

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

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

Основні типи алгоритмів — це три типові (базові) структури, які можна використовувати для розробки алгоритмів різного ступеня складності: лінійні, розгалуження та цикли.

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

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

Елемент даних, що має фіксоване значення, яке під час розв’язання задачі не змінюється, називають константою.

Поряд з константами широко використовуються змінні, тобто величини, що мають ідентифікатор і значення, яке може змінюватись залежно від використаних дій. У випадку, коли змінна х приймає значення, наприклад, в інтервалі від 0 до 1, тобто х є [0; 1], і змінюється з постійним кроком h_x = 0,1, її значення можна представити послідовністю із 11 чисел:

0; 0,1; 0,2; 0,3; 0,4; 0,5; 0,6; 0,7; 0,8; 0,9; 1.

Ця послідовність може зберігатися в пам’яті комп’ютера двома способами:

• всі значення змінної х зберігаються по черзі в одній комірці пам’яті і обчислюються самим комп’ютером за заданим законом змінення кроку h_х згідно з межами (х є [0; 1]);
• у пам’яті виділяється стільки комірок, скільки значень приймає змінна, тобто існує масив з 11 послідовних комірок, де для переходу від одного значення до іншого необхідно змінювати номер комірки.

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

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

x_i (і = 0…n-1), n = 11 або А_ij (і = 0…n-1, j = 0…m-1), n = 4, m = 6.

Такі масиви розрізняють за кількістю індексів, яку потрібно вказувати для звернення до їх елементів.