Поняття алгоритму
Люди щоденно користуються різноманітними правилами, інструкціями, рецептами тощо, що складаються з певної послідовності команд (вказівок). Деякі з них настільки увійшли до нашого життя, що ми виконуємо їх майже не замислюючись, іноді кажуть, автоматично.
Так для приготування яєчні потрібно виконати послідовність команд:
1. Поставити сковороду на плиту.
2. Покласти на сковороду шматочок вершкового масла.
3. Увімкнути конфорку.
4. Чекати, поки масло на сковороді розтане.
5. Розбити два яйця і вилити їх вміст на сковороду.
6. Посолити.
7. Чекати, поки загусне білок.
8. Вимкнути конфорку.
А для того, щоб визначити вид трикутника за його кутами, якщо відомі його три сторони, потрібно виконати таку послідовність команд:
1. Визначити сторону трикутника, яка не менша кожної з двох інших.
2. Обчислити косинус кута трикутника, що лежить проти сторони, визначеної як результат виконання команди 1.
3. Якщо визначений косинус кута від’ємний, то повідомити, що даний трикутник тупокутний, якщо ні, то якщо визначений косинус кута дорівнює нулю, то повідомити, що даний трикутник прямокутний, якщо ні, то повідомити, що даний трикутник гострокутний.
Такі послідовності команд (вказівок) називають алгоритмами.
Запам’ятайте!
Алгоритм — це скінченна послідовність команд (вказівок), що визначає, які дії і в якому порядку потрібно виконати, щоб досягти поставленої мети.
Кожна команда алгоритму є спонукальним реченням, яке вказує, яку дію має виконати виконавець алгоритму. Виконавцем алгоритму може бути людина, тварина, автоматичні пристрої, такі як робот, верстат з програмним керуванням, електронна обчислювальна машина тощо.
Множину всіх команд, які може виконувати даний виконавець, називають системою команд цього виконавця.Наприклад, у систему команд виконавця, що буде виконувати другий з наведених вище алгоритмів, повинні входити такі команди:
1. Порівняти довжини сторін трикутника і вибрати з них не меншу.
2. Обчислити косинус кута трикутника за відомими трьома сторонами.
3. Порівняти число з нулем (більше нуля, менше нуля або дорівнює нулю).
4. Вивести повідомлення.
Звертаємо вашу увагу: розробляючи алгоритм, потрібно перш за все визначити, для якого виконавця він призначений, і використовувати в алгоритмі тільки ті команди, які входять до системи команд цього виконавця.
Цікаві факти з історії!
Слово алгоритм походить від імені видатного вченого середньовічного Сходу Мухаммеда ібн Муси аль-Хорезмі (783 — 850)(на рис.), який в своїх наукових працях з математики, астрономії та географії описав і використовував індійську позиційну систему числення, а також сформулював у загальному вигляді правила виконання чотирьох основних арифметичних дій: додавання, віднімання, множення і ділення. Європейські вчені ознайомились з його працями завдяки їхнім перекладам на латину. При перекладі ім’я автора було подано якAlgorithmus. Звідси й пішло слово алгоритм. А розроблені ним правила виконання арифметичних дій вважають першими алгоритмами
Властивості алгоритму
Властивостями алгоритму є дискретність, визначеність, виконуваність, скінченність, результативність і масовість.
Дискретність (лат. discretus – розділений, розривний) алгоритму означає, що його виконання зводиться до виконання окремих дій (кроків) у певній послідовності. Причому, кожна команда алгоритму повинна виконуватися за скінченний проміжок часу.
Визначеність (або детермінованість (лат. determinans – визначальний)) алгоритму означає, що для заданого набору значень початкових (вхідних) даних алгоритм однозначно визначає порядок дій виконавця і результат цих дій. Алгоритм не повинен містити команди, які можуть сприйматися виконавцем неоднозначно, наприклад, «Узяти дві-три ложки цукру», «Трохи підігріти молоко», «Вимкнути світло через кілька хвилин», «Поділити число x на одне з двох даних чисел a або b» тощо. Крім того, в алгоритмах недопустимі ситуації, коли після виконання чергової команди виконавцю неясно, яку команду він повинен виконувати наступною.
Виконуваність алгоритму означає, що алгоритм, призначений для певного виконавця, може містити тільки команди, які входять до системи команд цього виконавця. Так, наприклад, алгоритм для виконавця «Учень першого класу» не може містити команду «Побудуй бісектрису даного кута», хоча така команда може бути в алгоритмі, який призначений для виконавця «Учень восьмого класу».
Зазначимо, що виконавець повинен лише вміти виконувати кожну команду зі своєї системи команд, і не важливо, розуміє він її, чи ні. Говорять, що виконання алгоритмів виконавцем носить формальний характер: виконавець може не розуміти жодну з команд, може не знати мети виконання алгоритму, і все одно отримає результат. Так, наприклад, верстат з програмним керуванням не розуміє жодної з команд, яку він виконує, але завдяки своїй конструкції успішно виготовляє деталі.
Скінченність алгоритму означає, що його виконання закінчиться після скінченної (можливо, досить великої) кількості кроків і за скінченний час при будь-яких допустимих значеннях початкових даних. Наведені вище послідовності команд є скінченними, а наступна послідовність команд – нескінченна:
1. Взяти число 2.
2. Помножити взяте число на 10.
3. Додати до одержаного числа 5.
4. Якщо одержане число додатне, то виконати команду 3, якщо ні, то припинити виконання алгоритму.
Результативність алгоритму означає, що після закінчення його виконання обов’язково одержуються результати, які відповідають поставленій меті. Результативними вважаються також алгоритми, які визначають, що дану задачу не можна розв’язати, або дана задача не має розв’язків при заданому наборі початкових даних.
Масовість алгоритму означає, що алгоритм може бути застосований до цілого класу однотипних задач, для яких спільними є умова та хід розв’язування, і які відрізняються тільки початковими даними.
Таким, наприклад, є алгоритм розв’язування квадратного рівняння, який дозволяє знайти дійсні корені квадратного рівняння з довільними дійсними коефіцієнтами, або визначити, що при певних значеннях коефіцієнтів рівняння не має дійсних коренів. Масовим також є, наприклад, алгоритм побудови бісектриси довільного кута з використанням циркуля і лінійки.
Однак, крім масових алгоритмів, складаються і застосовуються алгоритми, які не є масовими. Таким, наприклад, є алгоритм розв’язування конкретного квадратного рівняння, наприклад, 2х2+5х+2=0 або алгоритм приготування конкретного салату (наприклад, грецького) на конкретну кількість осіб.
