Інформація про новину
  • Переглядів: 23
  • Дата: 15-10-2021, 10:29
15-10-2021, 10:29

8.1. Поняття алгоритму. Властивості алгоритмів

Категорія: Інформатика





Попередня сторінка:  7.8. Проміжні підсумки. Створення форм ...
Наступна сторінка:   8.2. Способи подання алгоритмів

Розділ 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)

 



Попередня сторінка:  7.8. Проміжні підсумки. Створення форм ...
Наступна сторінка:   8.2. Способи подання алгоритмів



^