Тема: алгоритми та виконавці.

Мета

навчальна: сформувати уявлення про такі поняття вказівка, алгоритм, виконавець алгоритму, система вказівок виконавця, середовище виконання алгоритму, форми подання алгоритму. Навчити:

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

розвивальна: розвивати логічне мислення на основі спостережень, порівнянь, усвідомлення отриманого матеріалу; продовжувати розвивати навички роботи з інформаційними технологіями. Подавати приклади:

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

Визначати: виконавців алгоритму та прості вказівки виконавців у визначеному навчальному середовищі виконання алгоритмів.

виховна: стимулювати інтерес до предмету, пізнавальну активність, акуратність, терпимість та інформаційну культуру учнів.

Після вивчення теми учень

має уявлення: про форми подання алгоритмів;

описує поняття:

• вказівка;
• алгоритм;
• виконавець алгоритму;
• система вказівок виконавця;
• середовище виконання алгоритму;

• вказівки від речень, що не є вказівками;
• об’єкти та події;

• зв'язок системи вказівок алгоритму та їх виконавця;
• випадки, коли виконавець не може виконати вказівку;
• роль планування в житті, зокрема при навчанні;

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

1. Організаційний момент.
2. Актуалізація опорних знань.
3. Вивчення нового матеріалу.
4. Закріплення вивченого матеріалу.
5. Підбиття підсумків уроку.
6. Домашнє завдання.

Хід уроку

1. Організаційний момент
Вітання з класом. Перевірка присутності і готовності учнів до уроку.

2. Актуалізація опорних знань

Описати такі поняття:

• клас;
• об'єкт;
• властивість;
• подія;
• метод;
• поведінка;
• обмін повідомленнями.

3. Вивчення нового матеріалу

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

1. Поставити сковороду на плиту.
2. Покласти на сковороду шматочок вершкового масла.
3. Увімкнути конфорку.
4. Почекати, поки масло на сковороді розтане.
5. Кожне з n яєць розбити, а його вміст вилити на сковороду.
6. Посолити.
7. Почекати, поки загусне білок.
8. Вимкнути конфорку.

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

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

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

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

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

Середовище виконання алгоритму — об'єкти, з якими працює виконавець у процесі виконання алгоритму.

Властивості алгоритму: дискретність, визначеність, виконуваність, скінченність, результативність, масовість, ефективність.

Дискретність (латинською discretus — розділений, розривний) алгоритму означає, що виконання алгоритму зводиться до виконання окремих дій (кроків) у певній послідовності. Причому, кожну вказівку алгоритму виконують за скінченний проміжок часу.

Визначеність (однозначність) означає, що алгоритм однозначно визначає порядок дій виконавця, результат цих дій і не потребує додаткового тлумачення. Алгоритм не може містити вказівки, які виконавець може сприймати неоднозначно. Наприклад, «Узяти 2–3 ложки цукру», «Трохи підігріти молоко», «Вимкнути світло через кілька хвилин» тощо. Крім того, в алгоритмах неприпустимі ситуації, коли після виконання чергової вказівки виконавцю незрозуміло, яку вказівку він повинен виконувати наступною.

Виконуваність означає, що алгоритм, призначений для певного виконавця, може містити лише вказівки, які входять до системи вказівок цього виконавця. Наприклад, алгоритм для виконавця «Учень шостого класу» не може містити вказівку: «Поділити даний кут навпіл за допомогою циркуля та лінійки», хоча така вказівка може бути в алгоритмі, призначеному для виконавця «учень дев'ятого класу». Зазначимо: виконавець повинен лише вміти виконувати кожну вказівку зі своєї системи вказівок. І не важливо, розуміє він її чи, ні. Інакше кажучи, виконання алгоритмів виконавцем носить суто формальний характер: виконавець може не розуміти призначення вказівок, може не знати мети виконання алгоритму, і все одно отримає результат. Наприклад, верстат з програмним керуванням — не жива істота — не розуміє жодної з вказівок, які він виконує. Але завдяки своїй конструкції успішно виготовляє деталі.

Скінченність означає, що виконання алгоритму закінчиться після скінченної (можливо, досить великої) кількості кроків і за скінченний час для довільних вхідних даних. Поданій нижче послідовності вказівок не властива скінченність.

1. Зчитати число.
2. Помножити останній результат на 2.
3. Додати до останнього результату 1.
4. Якщо останній результат додатний, то припинити виконання алгоритму.
5. Перейти до виконання пункту 2.

Щоб переконатися у нескінченності, досить за початкове число взяти –1 або –2.

Результативність алгоритму означає, що після закінчення виконання алгоритму обов’язково:

• або одержують розв'язок-результат відповідно до поставленої мети;
• або встановлюють відсутність таких розв'язків (множина розв'язків порожня);
• або встановлюють неможливість розв'язання задачі розвэі.

Масовість алгоритму означає, що алгоритм можна застосувати до цілого класу однотипних задач, для яких спільними є умова та хід розв’язування та які відрізняються лише початковими (вхідними) даними. Наприклад, алгоритмом дій, складеним для одного касира, можуть успішно скористатися всі касири супермаркету. А програмою пошуку коду і підрахунку суми вартостей товарів, придбаних покупцем, — усі комп'ютери супермаркету

Ефективність алгоритму описує час виконання і об'єм ресурсів, необхідних для виконання алгоритму: чим менше часу (часова ефективність) і ресурсів (просторова ефективність), тим ефективність вища.

Розрізняють такі (логічні) структури (вказівок) в алгоритмах:

• лінійна;
• розгалужена;
• з повторенням.

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

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

Алгоритми можна подати словесно або графічно.

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

Для посадки дерева маємо таку словесну форму алгоритму.

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

2. На дно ями на третину її глибини насипати землі з органічним добривом і перемішати.

3. Встановити саджанець вертикально корінням донизу, щоб коріння торкалася дна ямки.

4. Засипати кореневу систему землею.

5. Вилити пів-відра води на засипану кореневу систему.

Примітка. Деталізація поданого алгоритму (будь-якого кроку!) міститиме прийняття рішення щодо подальших дій, тобто розгалужену структуру. Наприклад, на першому кроці виконавець буде час від часу вимірювати глибину і ширину ями, щоб перестати копати після досягнення потрібних розмірів. Таким чином, деталізація лінійної структури матиме мішану структуру, яку називають квазілінійною (ніби лінійною).

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

У поданій нижче таблиці праворуч від зображення фігури записано назву (найменування), призначення у блок-схемі (опис структури) і словесний опис геометричної фігури, якою позначають відповідну складову алгоритму. Синім кольором описано елементи, вивчення яких передбачено у наступних класах — ознайомлення з ними можна відкласти на майбутнє.

	Термінатор — відображає вхід із зовнішнього середовища або вихід у нього (початок і кінець програми), всередині фігури записують відповідну дію: початок або кінець — овал.
	Процес (обчислення) — виконання однієї або кількох операцій, опрацювання даних, всередині фігури записують безпосередньо самі операції — прямокутник з горизонтальними та вертикальними сторонами.
	Дані — перетворення даних у форму, придатну для опрацювання (введення) або відображення (виведення). Цей символ не визначає носія даних. Для вказання типу носія даних використовують спеціальні позначення, які тут не розглянуто — паралелограм, у якому відстань між горизонтальними сторонами удвічі більша за проекцію похилої сторони на горизонталь.
	Рішення — показує рішення: функцію перемикання з одним входом і двома або більше виходами, з яких лише один буде обрано після обчислення умов, записаних всередині елемента. Вхід в елемент позначають лінією, що входить зазвичай у верхню вершину. Якщо виходів два чи три, то зазвичай кожен вихід позначають лінією, що виходить з решти вершин (бічних і нижній). Якщо виходів більше трьох, то їх показують однією лінією, що виходить з вершини (частіше нижньої) і потім розгалужується. Відповідні результати обчислень записують поруч з лініями, що відображають ці шляхи — ромб з однаково нахиленими (до горизонталі) сторонами.
	Зумовлений процес — виконання процесу, що складається з однієї або кількох операцій, визначених в іншому місці програми (у підпрограмі, модулі). Всередині символу записують назву процесу й передані в нього дані — прямокутник з горизонтальними та вертикальними сторонами, у якому проведено 2 вертикальні відрізки без порушення симетрії.
	Межа циклу — складається з двох частин — відповідно, початок і кінець циклу. Операції, що виконують усередині циклу, записують між ними. Умови циклу і збільшення записують усередині символу початку або кінця циклу залежно від типу організації циклу. Часто для зображення на блок-схемі циклу замість цього символу використовують символ рішення, вказуючи в ньому умову, а одну з ліній виходу замикають вище в блок-схемі (перед операціями циклу) — прямокутник з горизонтальними та вертикальними сторонами, у якого згори відрізано рівнобедрені трикутники, і результат симетрії такого 6-кутника відносно горизонталі.
	З'єднувач — символ відображає вихід з частини схеми і вхід у іншу частину цієї схеми. Використовують для обриву лінії та продовження її в іншому місці для поділу блок-схеми, що не можливо розташувати на одній сторінці. Відповідні сполучні символи повинні мати одне (при тому унікальне) позначення — круг.
	Коментар — використовують для подання інформації про кроки, процесу або групи процесів. Опис розташовують з боку квадратної дужки, яка охоплює його по всій висоті. Пунктирна лінія йде до описуваного елементу, або групи елементів, яку виділяють замкнутою пунктирною лінією, — ліва квадратна дужка, з середини якої виходить пунктирна лінія ліворуч.

Стрілками блок-схемах вказують переходи між кроками виконання.

Блок-схема поданого алгоритму посадки дерева має такий вигляд.

4. Закріплення вивченого матеріалу

1. Подайте приклади речень, які є вказівками.
2. Подайте приклади речень, які не є вказівками.
3. Що таке алгоритм? Подайте приклади з лінійною структурою.
4. Що таке виконавець?
5. Що таке система вказівок виконавця?
6. Що таке середовище виконання?
7. Назвіть властивості алгоритму. Поясніть кожну з них.
8. Подайте приклад послідовності вказівок, яка не є виконуваною.
9. Подайте приклад послідовності вказівок, яка не є результативною.
10. Поясніть відмінність між словесною та графічною формами подання алгоритму.
11. Назвіть елементи блок-схеми алгоритму та поясніть їх призначення.
12. Який алгоритм (фрагмент алгоритму) називають лінійним?
13. Подайте приклади з навколишнього життя:
    • виконавців;
    • алгоритмів;
    • систем вказівок.

5. Підбиття підсумків уроку
Виставлення оцінок.

6. Домашнє завдання
Повторити вивчений матеріал. У зошиті накреслити кожний з трьох вивчених елементів блок-схем: 5 зображень — з лінійкою і 5 зображень — від руки. Виробити при цьому швидкість креслення при збереженні охайності.

Текст упорядкував Бабенко Павло Анатолійович, вчитель інформатики спеціалізованої школи № 298 Оболонського району.