І Скляр - Я готуюсь до курсу інформатики. Алгоритмізація та програмування

Примітка: на даному етапі уроку можна дати учням завдання придумати задачу, яка б була непосильною для вибраного виконавця (виконавцем може бути людина, комп’ютер, якийсь пристрій тощо). Наприклад, спробуйте створити алгоритм виконання ремонту кімнати, розрахований на виконавця «екскаватор».

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

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

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

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

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

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

• Вивчити означення, що були прочитані на лекції;

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

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