1. Поняття алгоритму. Властивості алгоритмів. Базові структури алгоритмів та їх основні властивості.
Термін алгорипім виник задовго до появи комп'ютерів, і походить від імені давнього філософа й математика з Хорезму, шо жив у IX ст. — Аль-Хорезмі.
Алгоритм — це точний і зрозумілий опис послідовності дій над заданими об'єктами, що дає змогу одержати кінцевий результат. Синонімом алгоритму можуть бути слова: спосіб, рецепт.
Алгоритм дає змогу формалізувати виконання інформаційного процесу, тобто виконавець алгоритму може виконувати алгоритм формально, не вникаючи в зміст поставленої задачі.
Кожен алгоритм має задовольняти певні властивості.
Дискретність. Будь-який алгоритм може бути розбитий на окремі кроки — закінчені дії. Перехід до наступного кроку можливий лише після завершення попереднього.
Визначеність (чи детермінованість). Кожна команда алгоритму повинна однозначно визначати певну дію і не допускати двоякого тлумачення. Строго визначеним повинен бути і порядок виконання операцій.
Результативність. Виконання алгоритму має приводити до конкретного результату — розв'язку задачі, якщо навіть він дає і результати, які можуть виявитися і неправильними. Розв'язком задачі може бути також повідомлення про те, що задача розв'язку не має.
Масовість. За допомогою алгоритму можна розв'язувати не одну конкретну задачу, а безліч однотипних задач. Властивість масовості збільшує практичну цінність алгоритму.
Скінченність. Виконання алгоритму повинно завершитися за скінченну кількість кроків. Виконання алгоритму не може закінчуватися невизначеною ситуацією або ж зовсім не закінчуватися.
Правильність. Алгоритм правильний, якщо його виконання забезпечує досягнення мети.
Формальність. Будь-який виконавець, здатний сприймати і виконувати вказівки алгоритму (навіть не розуміючи їх змісту), діючи за алгоритмом, зможе виконати поставлене завдання.
Під час складання алгоритмів треба пам'ятати, що одна й та сама задача може бути успішно розв'язана за допомогою алгоритмів, що відрізняються один від одного. При виборі алгоритму треба насамперед зважати на вимоги компактності алгоритму і легкості його розуміння. Ці вимоги можна задовольнити, якщо дотримуватися структурного підходу, в основі якого лежить твердження, що алгоритм будь-якого ступеня складності можна виразити за допомогою трьох базових структур: слідування, розгалуження і циклу.
Слідування. Операція S подається у вигляді послідовності двох (або більше) виконуваних одна за одною простіших операцій S1, S2,...., SN.
Розгалуження (вибір). Для виконання операції S треба спочатку визначити, хибне чи істинне деяке твердження Р. Якщо твердження Р істинне, то виконується вказівка S1 і на цьому операція S закінчується. Якщо твердження Р хибне, то виконується вказівка S2 і на цьому виконання вказівки S закінчується.
Повне розгалуження Неповне розгалуження
Повторення (цикли). Розрізняють два види циклів — цикл-ПОКИ і цикл-ДО
а) У структурі цикл-ПОКИ для виконання вказівки S спочатку треба визначити, істинне чи хибне твердження Р. Якщо Р істинне, то виконується вказівка S1 і знову повертаються до визначення істинності твердження Р. Якщо ж твердження Р хибне, то виконання вказівки S вважається закінченим.
б) У структурі цикл-ДО спочатку виконується вказівка S1, а потім визначається істинність твердження Р. Якщо твердження Р хибне, то знову виконується вказівка S1 і визначається істинність твердження Р. Якщо ж твердження Р істинне, то виконання вказівки 51 вважається закінченим.
цикл-ДО
Основною властивістю базових алгоритмічних структур є те, що кожна з них має єдиний вхід та єдиний вихід. Для побудови алгоритмів з використанням цих структур дозволяється тільки заміняти будь-яку окрему вказівку алгоритму сукупністю більш простих вказівок, яка являє собою одну із базових структур алгоритмів. Будь-який алгоритм може бути побудованим з використанням тільки вказаних базових структур.