Розділ 8

ОСНОВИ АЛГОРИТМІЗАЦІЇ ТА ПРОГРАМУВАННЯ

8. Основні поняття алгоритмізації

Чим здавна користувалися люди для виконання обчислень? Наведіть приклади.

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

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

Алгоритм — це скінченна послідовність команд (інструкцій, вказівок), виконання яких у визначеному порядку приводить до розв'язування певного завдання.

Команда — це конкретна інструкція (вказівка), що визначає, яку і як виконувати дію (операцію). Наприклад, додати два числа, зупинитися на світлофорі на червоне світло, натиснути відповідну кнопку в ліфті, вивести на екран монітора зображення піраміди.

Алгоритми завжди розробляють для певного виконавця.

Виконавцем алгоритму називають живу істоту чи пристрій, що його виконує.

Кожен виконавець володіє набором команд, які він може виконувати. Це означає, що не кожний алгоритм може бути виконаний будь-яким виконавцем. Так, алгоритм розв’язування квадратного рівняння, доступний учням 8 класу, учень 2 класу виконати не може.

Сукупність усіх команд, які може виконувати виконавець, називають системою команд виконавця.

Нині алгоритми найчастіше розробляють для їх реалізації на комп’ютері з необхідним програмним забезпеченням.

Щоб алгоритм виконав своє призначення, він має відповідати певним вимогам (властивостям). Будь-який алгоритм має сукупність властивостей. Пригадаємо основні з них.

Зазвичай команди алгоритму виконуються послідовно.

Якщо вони мають виконуватися непослідовно, то це зазначається в спеціальній команді окремо.

Алгоритм обчислення НСД двох натуральних чисел А і В (алгоритм Евкліда)

1. Порівняйте числа А і В. Якщо А = В, то перейдіть до п. 7, інакше — виконайте п. 2.

2. Якщо А > В, то перейдіть до п. 5, інакше — виконайте інструкцію п. 3.

3. Зменште значення В на значення А.

4. Перейдіть до п. 1.

5. Зменште значення А на значення В.

6. Перейдіть до п. 1.

7. Присвойте найбільший загальний дільник, який має значення А, змінній D.

8. Виведіть значення D.

9. Кінець.

Приклад 2.

Для дітей, які знають таблицю множення, сам запис А*В однозначно визначає послідовність дій для отримання правильного результату. Для дітей, які знають правила додавання чисел, але не знають таблиці множення, множення двох натуральних чисел А і В можна описати у вигляді послідовності інструкцій операцій додавання.

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

визначену систему команд (приклад 3). Отже, кожний виконавець має власну систему команд, яку він спроможний виконати. Спроба виконати алгоритм іншим виконавцем, який має іншу систему команд, може завершитися безрезультатно.

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

Приклад 3.

Один робот може виконувати команди переміщення прямо, наліво та направо на задану кількість кроків, а інший робот — ще й переміщуватися назад та виконувати стрибки.

Запитання для перевірки знань

Що називають алгоритмом?

Наведіть приклади найпростіших алгоритмів.

У якому порядку виконуються інструкції алгоритму?

Від чого залежить ступінь деталізації алгоритму?

Назвіть і поясніть основні властивості алгоритму.

Від нього залежить деталізація алгоритму?

Завдання для самостійного виконання

Опишіть алгоритм вашого шляху до школи.

Опишіть алгоритм визначення центра рівнобічного трикутника за допомогою циркуля та лінійки.

Опишіть алгоритм побудови бісектриси кута за допомогою циркуля та лінійки.

Це матеріал з підручника Інформатика 8 клас Руденко (2021)