6 клас Урок 28

 

Тема уроку. Розв'язування задачі методом поділу на підзадачі 

Актуалізація опорних знань
Дати означення понять, виділені жирним шрифтом.
Алгоритм — це запис скінченої послідовності вказівок, виконання яких призводить до розв'язання певної задачі.
Вказівка (алгоритму) — це спонукальне речення, що вказує, яку дію має виконати виконавець алгоритму.
Виконавець (алгоритму) — це жива істота (людина або тварина) або автоматичний пристрій (робот, електронна обчислювальна машина тощо), спроможна діяти відповідно з алгоритмом.
Система вказівок виконавця — це множина (сукупність) всіх вказівок, які може виконувати даний виконавець.
Середовище виконання алгоритму — об'єкти, з якими працює виконавець у процесі виконання алгоритму.
Властивості алгоритму: дискретність, визначеність, виконуваність, скінченність, результативність, масовість, ефективність.
Дискретність (латинською discretus — розділений, розривний) алгоритму означає, що виконання алгоритму зводиться до виконання окремих дій (кроків) у певній послідовності. Причому, кожну вказівку алгоритму виконують за скінченний проміжок часу.
Визначеність (однозначність) означає, що алгоритм однозначно визначає порядок дій виконавця, результат цих дій і не потребує додаткового тлумачення..
Виконуваність означає, що алгоритм, призначений для певного виконавця, може містити лише вказівки, які входять до системи вказівок цього виконавця.
Скінченність означає, що виконання алгоритму закінчиться після скінченної (можливо, досить великої) кількості кроків і за скінченний час для довільних вхідних даних.
Результативність алгоритму означає, що після закінчення виконання алгоритму обов’язково:

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

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

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

Допоміжний алгоритм призначений для досягнення проміжної мети.

Великі алгоритми зазвичай проектують так. Спочатку аналізують умову задачі. Складають загальний план її розв'язування. Якщо задача складна, то її розбивають на декілька простіших підзадач. Проектують модульну структуру алгоритму: описують призначення головного та допоміжних алгоритмів, дають їм назви. Потім деталізують (створюють, уточнюють) необхідні допоміжні алгоритми для розв'язування підзадач. Маючи допоміжні алгоритми, записують головний алгоритм, який складатиметься з команд викликів допоміжних. Отже, великі алгоритми утворюють з готових модулів (блоків) подібно до того, як будинки будують з готових блоків, а машини збирають з окремих деталей. 

Створіть проєкт Будинок мовою програмування Скретч

Якщо на Вашому комп'ютері не установлена мова прогрпмування Скретч, створіть Ваш проєкт онлайн за посиланням 

https://scratch.mit.edu/projects/editor/?tutorial=home

Задача .

Скласти алгоритм дій на тиждень. Тиждень складається з п'яти робочих днів, для кожного з яких підходить алгоритм День, а також суботи та неділі. Модульну структуру алгоритму Тиждень подано на рисунку нижче.

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

Алгоритм Тиждень

1. Доки не настала субота, виконати алгоритм День.
2. Виконати алгоритм Субота.
3. Виконати алгоритм Неділя.

Цей алгоритм стане визначеним, якщо будуть складені допоміжні алгоритми Субота, Неділя. Для розв'язання задачі потрібно два кроки (рівні, етапи) деталізації. На першому кроці деталізують алгоритми День, Субота, Неділя, а на другому деталізують або використовують алгоритми Ранок, Школа, Вечір.

Описаний метод називають проектуванням алгоритму «зверху-вниз» з покроковою деталізацією (уточненням) допоміжних алгоритмів.
Метод покрокової деталізації конструювання алгоритмів не враховує явно конкретні особливості поставленої задачі та вибір певного виконавця. Але сукупність вказівок вибраного виконавця істотно впливає на ступінь деталізації алгоритму та на його структуру. Допоміжний алгоритм (як і будь-який інший алгоритм) повинен мати лише один вхід і один вихід. Потрібно щоб усі вказівки допоміжного алгоритму входили до системи вказівок обраного виконавця. У реальному житті допоміжні алгоритми можуть виконувати навіть інші виконавці.

Процес роботи комп’ютера полягає у виконанні програм, тобто наборів вказівок у визначеному порядку. Писати такі програми – складна справа. Раніше для цього програміст повинен був пам’ятати не лише всі комбінації нулів та одиниць двійкового коду кожної вказівки, але й двійкові коди адрес даних, використаних під час виконання програми. Щоб полегшити роботу програмістів, було розроблено багато мов програмування високого рівня, які в наочнішому (для людини) вигляді подавали послідовність дій комп’ютера. Такі алгоритмічні мови опису побудованих алгоритмів, призначених для виконання комп’ютерами, називаються мовами програмування. Легше написати програму такою мовою програмування, яка наближена до людської, а перекладання з цієї мови мовою машинних кодів доручити комп’ютеру. Допоміжні алгоритми, що природнім чином виникають при використанні методу покрокової деталізації, записують за допомогою функцій. Ці можливості було передбачено вже у перших мовах програмування високого рівня.
Закріплення вивченого матеріалу

Підсумок уроку

Розгадай ребуси

Домашня робота

Опрацювати матеріал уроку