ОСНОВИ ТЕОРІЇ АЛГОРИТМІЗАЦІЇ
1. Поняття та властивості алгоритму
2. Способи опису алгоритмів
3. Базові алгоритмічні конструкції
4. Приклади побудови алгоритмів
Загальні поняття та визначення
l Алгоритм – це точний, з однозначним трактуванням опис послідовності дій, які треба виконати над початковими величинами, щоб отримати шуканий результат
Властивості алгоритму:
l Детермінованість (визначеність) – однозначність результату обчислювального процесу при заданих початкових даних;
l Дискретність - алгоритм розбивається на певні елементарні операції, кількість яких є скінченою величиною;
l Масовість - алгоритм розв'язування задач певного класу працює для різних початкових величин;
l Результативність - шуканий результат отримується завжди і за скінчену кількість кроків.
Форми запису алгоритмів
l Словесний опис послідовності обчислень
l Алгоритмічною мовою (запис здійснюється з дотриманням синтаксичних та семантичних конструкцій певної мови програмування)
l Псевдокодом (дотримуватися щойно згаданих конструкцій бажано, але не обов'язково, головний акцент робиться на сприйнятті записаного людиною)
l Схематичне зображення – це графічне подання усіх його кроків за допомогою відповідних геометричних об'єктів
l Схематичне зображення алгоритму називають блок-схемою
Основні графічні символи:
| l передбачають лише написи «початок» на початку алгоритму та «кінець» наприкінці. | |
| l служать для позначення введення вхідних величин та виведення результатів. | |
| l служать для виконання операції або групи операцій, завдяки яким змінюється значення, форма подання або розташування даних. | |
| l Вибір напрямку виконання алгоритму залежно від виконання деяких умов. Всередині блоку записують логічні вирази. Блок має два виходи: «так» (якщо умова виразу виконується) і «ні» (якщо умова виразу не виконується). | |
| l У блоці вказують як змінюється певна змінна | |
| l Виведення результатів на друк | |
| l Вказують на окремо описаний елемент алгоритму | |
| l Лінії потоку – вказують на послідовність зв'язків між символами | |
| l З'єднувач – вказує на зв'язок між розірваними лініями потоку | |
| l Міжсторінковий з'єднувач – вказує на зв'язок між розірваними лініями потоку, які знаходяться на різних сторінках | ||
| l Використовують для пояснення елементів алгоритму | |
Правила використання графічних символів:
l Дії, визначені на кроці алгоритму, записують у середину відповідного блока
l Кожен блок нумерується
l Блоки з'єднують лініями потоку
l Послідовність виконання операцій вказують стрілкою на лінії потоку
l Напрям зверху до низу і зліва на право вважають основними (стрілку на лінії потоку можна не ставити)
l Стрілка ставиться обов'язково коли напрям є неосновним, або відбувається зміна напряму лінії потоку
Розрив лінії потоку
l Розрив лінії потоку позначають з'єднувачами. У середині з'єднувача вказують номер блоку, що знаходиться на протилежному боці розриву
l Якщо лінію потоку продовжують на іншу сторінку, то використовують міжсторінковий з'єднувач. У середині з'єднувача вказують номер сторінки, а під ним – номер відповідного блоку.
l Гострий кут міжсторінкового з'єднувача вказує на напрям наступної операції
Базові алгоритмічні конструкції
l Алгоритмічна конструкція визначає порядок виконання операцій, передбачених алгоритмом
l Базовими алгоритмічними конструкціями є:
Ø лінійна
Ø розгалужена
Ø циклічна
l Лінійна алгоритмічна конструкція – це така конструкція, яка передбачає виконання операцій у порядку їх запису
Розгалужена конструкція
l Розгалуженою називається така алгоритмічна конструкція, яка передбачає у процесі виконання операцій вибір кількох можливих варіантів продовження роботи залежно від результату перевірки виконання певних умов.
l Розгалужена алгоритмічна конструкція, що складається лише з двох гілок, має назву простої, якщо гілок більш ніж дві - складної.
Циклічна конструкція
l Циклічною називається така алгоритмічна конструкція, яка передбачає виконання декілька разів однієї й тієї ж послідовності дій.
l Керування кількістю повторів циклу здійснюється за допомогою змінної, яка має назву параметра циклу.
l При кожному повторі циклу значення цієї змінної змінюється на величину, яка називається кроком циклу.
l Порядок дій, що виконуються у циклі, називається тілом циклу.
l Цикл припиняється, коли значення параметра циклу досягає певного значення, за якого забезпечується виконання логічної умови припинення циклу.
