Головна ⇒ 📌Інформатика ⇒ Алгоритм і його виконання

Алгоритм і його виконання

Розділ 1 Алгоритми та їх виконавці

2. Алгоритм і його виконання

ТИ ДІЗНАЄШСЯ:

Вивчаємо

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

В інформатиці інструкцію називають алгоритмом, якщо вона складається із скінченної послідовності команд, спрямованих на отримання певного результату.

Люди часто створюють і виконують алгоритми на роботі, вулиці, удома. Ти також щоденно зустрічаєшся з алгоритмами.

Наприклад, готуючи бутерброд, ти дотримуєшся алгоритму. На малюнку 7 відображено виконання відповідних команд.

Словами

його можна описати так:

1. Узяти шматок хліба.

2. Покласти на хліб листок салату.

3. Покласти зверху котлету.

4. Покласти зверху шматок сиру.

5. Покласти на сир шматок помідора.

6. Накрити іншим шматком хліба.

На уроці математики ти використовуєш такий алгоритм для переведення мішаного числа в неправильний дріб:

1. Помножити цілу частину мішаного числа на знаменник дробової частини.

2. Додати до отриманого результату Чисельник дробової частини.

3. Записати отримане число в чисельник дробу-результату.

class=""/>

Maл. 7

4. Залишити знаменник без змін.

Наведені приклади алгоритмів мають спільні ознаки:

– кожна команда є зрозумілою для виконавця;

– нова команда не розпочинається, поки не завершено попередню;

– кількість команд обмежена і їх можна виконати за досить короткий час;

– послідовне виконання всіх команд приводить до отримання результату.

Алгоритм це скінченна послідовність команд, виконання яких приводить до розв’язання поставленої задачі.

Слово алгоритм походить від імені перського вченого, астронома і математика Аль-Хорезмі. Приблизно 825 р. він сформулював правила виконання дій над числами, якими користувалися в Стародавній Індії.

У якій формі можна подати алгоритм?

Алгоритми можна подавати в різних формах. Наприклад, наведений приклад алгоритму переведення мішаного числа у неправильний дріб записано у вигляді послідовності команд, кожна з яких має свій порядковий номер і сформульована мовою людського спілкування. Це словесна форма подання алгоритму.

Алгоритм можна подавати також графічно. Наприклад, на малюнку 8 графічно подано розв’язання старовинної задачі.

Човняру з лівого берега на правий потрібно перевезти в човні через річку вовка. козу і капусту. У човні крім човняра уміщується або лише вовку або лише коза, або лише капуста. Як це зробити, якщо на березі неможна залишати козу з вовком або козу з капустою?

Вибір форми подання алгоритму залежить від його виконавця. Так, алгоритм евакуації учнів з приміщення школи при виникненні надзвичайних ситуацій подають у графічній формі, а для пожежників цей алгоритм записують словесно у вигляді інструкцій.

Хто або що може бути виконавцем алгоритму?

Створюють алгоритми люди. А виконують їх люди й різні пристрої, якими управляють люди – комп’ютери, роботи, верстати, супутники, складна побутова техніка та навіть дитячі іграшки. Наприклад, прання білизни за допомогою пральної машини, зображеної на малюнку, можливе за умови виконання людиною й машиною вказаних алгоритмів:

Виконавець алгоритму – це об’єкт, здатний виконати команди алгоритму.

Об’єктом може бути людина, машина або пристрій.

Які особливості структури слідування при графічному поданні, алгоритмів?

Команди алгоритмів можна умовно об’єднати у блоки – алгоритмічні структури. Для кожної структури для зручності вводять свої графічні позначення, за допомогою яких будь-який алгоритм можна подати наочно. Якщо команди виконуються послідовно, кожна наступна розпочинається після завершення попередньої і виконується тільки один раз, – маємо алгоритмічну структуру слідування. Таку структуру графічно позначають у вигляді послідовності прямокутників, у кожному з яких прописується команда або набір команд для отримання певного результату. У свою чергу, кожну задачу, для виконання якої складатиметься алгоритм, також можна подати у вигляді прямокутника. Наприклад, алгоритм початку гри в шахи можна подати так:

Зверни увагу, що подана структура слідування має стрілку на вході й на виході. Це тому, що кожна задача, для розв’язування якої складається алгоритм, може складатися не лише з підзадач, але й сама, у свою чергу, може бути підзадачею.

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

Наприклад, якщо формально виконати алгоритм: задумати число -> додати до нього 3 -> від того, що вийшло, відняти 1 -> до того, що вийшло > додати2 ->до того, що вийшло, додати 1 -> до того> що вийшло> до дати 2 -> від того > що вийшло, відняти задумане число -> назвати отримане число, то отримаємо число 7 (перевір це самостійно).

Діємо

Вправа 1. Черговий учень.

Завдання. Із запропонованого набору команд вибери ті, які входять до системи команд чергового учня на уроці фізичної культури, та створи презентацію “Черговий учень”.

1. Завантаж, презентацію Команди, що міститься в папці Алгоритми і виконавці на Робочому столі.

2. Розглянь команди, подані на другому слайді. Видали ті, що не входять до системи команд чергового учня на уроці фізичної культури.

3. Упорядкуй решту команд так, щоб скласти алгоритм дій чергового на початку уроку фізичної культури.

4. Збережи файл презентації з іменем Черговий учень.

Вправа 2. Побудова середини відрізка.

Завдання. Виконай побудову середини відрізка за допомогою циркуля й лінійки.

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

1. Перевір, чи можеш ти виконати дії, які входять до системи команд заданого виконавця.

2. Виконай такий алгоритм:

1) Зобразити дві точки А і В. Накреслити відрізок АВ.

2) Поставити вістря циркуля в точку А.

3) Розхилити циркуль до точки В.

4) Побудувати коло.

5) Поставити вістря циркуля в точку В.

6) Побудувати коло.

7) Позначити точки перетину кіл Q і Р.

В) Провести пряму QP.

9) Позначити точку О – точку перетину прямої QP та відрізка А В.

3. Перевір, чи можна замість креслярських інструментів використати інструменти побудови графічного редактора Paint і виконати алгоритм побудови малюнка 9 не в робочому зошиті, а на полотні графічного редактора. Як при цьому може змінитися система команд виконавця і сам алгоритм?

Мал. 9

Обговорюємо

1. Що називають алгоритмом? Коли ти у своєму житті виконував алгоритми? Наведи приклади.

2. У якій формі можна подати алгоритм? Наведи приклади.

3. Чи кожну інструкцію можна назвати алгоритмом? Поясни відповідь.

4. Хто або що може бути виконавцем алгоритму?

5. Поясни, що означає виконати послідовність дій формально. Наведи приклади зі свого життя.

6. Чим відрізняється виконавець команди від виконавця алгоритму? Наведи приклади.

Працюємо в парах

1. Створіть і розкажіть одне одному алгоритм збереження нового телефонного номера у списку контакті в свого мобільного телефона. Скільки він має команд? Хто може бути виконавцем такого алгоритму?

2. Обговоріть, які команди слід подати на запропонованих схемах, щоб отримати відповідні алгоритми:

А) переходу вулиці без світлофора:

Б) побудови кута заданої градусної міри:

В) вмикання комп’ютера:

3. Склади для своєї бабусі алгоритм перегляду фотографій на цифровому фотоапараті. Запропонуй його своему однокласнику. Переконайся, що він може назвати систему команд виконавця такого алгоритму та виконати запропоновані команди. Обговоріть, що означатиме для твоєї бабусі формальне виконання цього алгоритму.

Досліджуємо

Вправа 3. Графічна форма подання алгоритму.

Завдання. Учень шостого класу Максим для своєї молодшої сестри вирішив подати у графічній формі алгоритм збереження файла, створеного в графічному редакторі, з новим ім’ям і в іншій папці. Проаналізуй, яку із запропонованих схем (мал. 10) він зможе використати для цього.