Виконавці алгоритмів

Матеріал з Фізмат Вікіпедії
Перейти до: навігація, пошук

Мета уроку:

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

Тип уроку

Лекційний.

Хід уроку.

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

Фронтальне опитування

  1. Яке походження терміна «алгоритм»?
  2. Що ми розуміємо під поняттям «алгоритм»?
  3. Що таке допустимі команди виконавця?
  4. Які є способи опису алгоритмів?
  5. Які властивості повинен мати алгоритм?
  6. Що означає скінченність (дискретність) алгоритму?
  7. Що таке формальність алгоритму?
  8. Що означає масовість алгоритму?

ІІ. Викладання нового навчального матеріалу.

1. Виконавець алгоритму

Виконавцем алгоритму може бути людина, машина, комп’ютер, система людина-машина, верстат-автомат, робот тощо, яких «навчено» виконувати вказівки алгоритму.

Характеристики виконавця

Середовище – «місце проживання» виконавця.

Припустимі дії – обмежений набір дій, що вміє виконувати даний виконавець. Описати виконавця – значить вказати його припустимі дії. Досяжні цілі – результати, що виконавець може одержати за допомогою своїх припустимих дій. Система команд виконавця – суворо заданий список вказівок, як виконати визначені дії. Виконавця можна представити у виді пристрою з кнопками, де кожна кнопка відповідає одній команді. Натискання кнопки означає виклик команди.

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

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

Узагальнюючи сказане, можна сказати, що кінець кінцем кожну задачу можна вважати окремою командою виконавцю, якщо його навчено виконувати поставлене завдання. Якщо ж виконавець не знає, як розв'язувати запропоновану задачу, виникає потреба розкласти її на такі підзадачі, що являються "посильними" для виконання, тобто входять до системи команд виконавця. Продовжуючи цей процес, остаточно отримують алгоритм, що складається з простих команд, зрозумілих виконавцю, або остаточно переконуються, що дана задача непосильна для вибраного виконавця, тому що в його системі команд не існує необхідних для цього команд. Наприклад, як би ми не деталізували алгоритм побудови багатоповерхової будівлі для дитини, задача кінець кінцем являється для неї непосильною.

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

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

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

Візьмемо, наприклад, простий алгоритм "переходу через вулицю". Взагалі для кожної дитини можна вважати це командою, що входить до її "системи команд". Але кожен пам'ятає, як в дитинстві батьки та вихователі неодноразово повторювали: якщо в місті, де необхідно перейти вулицю, є підземний перехід, скористуйся ним, якщо немає, відшукай місце, де є світлофор, і перейди вулицю, користуючись правилами; якщо немає ні підземного переходу, ні світлофора... (далі діти самостійно продовжать це алгоритм). Однак, навіть в цьому алгоритмі є необхідність дещо деталізувати. Наприклад, що значить "перейди вулицю, користуючись правилами", при наявності світлофора? А якщо алгоритм складається для зовсім маленької дитини, то що таке світлофор і як його шукати? А якщо виконавець взагалі прибулець з інших світів? Що таке "зелений", "червоний", "жовтий"? Що таке підземний перехід? Перелік питань можна доповнити нескінченою послідовністю непорозумінь. Алгоритми, що складаються для розв'язування окремих підзадач основної задачі, називаються допоміжними.

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

Таким чином, можна вважати допоміжний алгоритм своєрідним "чорним ящиком", на вхід якого подаються деякі вхідні дані, а на виході ми отримуємо очікуваний результат. Головне чітко домовитись про правила оформлення вхідних даних та вигляд результату. Невиконання домовленостей може привести до збою у виконанні допоміжного алгоритму або до отримання неочікуваного результату. Описаний метод послідовної деталізації лежить в основі технології структурного програмування і широко застосовується при використанні таких мов програмування, як Паскаль, С, С++ та інших. При описуванні програми для комп'ютера мовами високого рівня допоміжні алгоритми реалізовуються у вигляді підпрограм. Правила опису, звернення до них та повернення в точку виклику визначаються конкретною мовою програмування. Для зручності часто використовувані підпрограми можна об'єднувати в бібліотечні модулі і при необхідності підключати їх в свої програми.

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

Креслення різноманітних ліній із записом кроків в програмі «Кенгуру» («Сходинки») та «Лого-Миры»

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

Домашнє завдання:

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