Алгоритми та їх властивості
Кожна людина щодня вирішує багато задач: від найпростіших до дуже складних. Існують визначені правила (інструкції, команди) для пояснення виконавцю, як розв'язувати дану проблему. Ці правила людина може вивчити або сформулювати сама в процесі розв'язування задачі. Чим точніше описані правила, тим швидше людина опанує ними і буде ефективніше їх застосовувати. У житті ми постійно складаємо опис деякої послідовності дій для досягнення бажаного результату, тому поняття алгоритму не є для нас чимось новим і незвичайним. Так, ранком мама сину-школяру дає вказівки: «Коли прийдеш зі школи, відразу пообідай і вимий посуд. Сходи на заняття у музичну школу, а потім можеш трохи погуляти й відразу за уроки!». Ця інструкція складається з послідовності окремих вказівок, які визначають поведінку школяра після повернення зі школи. Кожен із нас щодня використовує сотні різних алгоритмів: можна згадати деякі з них (алгоритми виконання арифметичних дій під час розв'язування задач; алгоритми проведення хімічних дослідів у лабора-торії; алгоритм приготування кулінарних виробів тощо).
Отже, алгоритмом можна назвати скінчений набір інструкцій (пра¬вил), що дає змогу розв'язувати будь-яку конкретну задачу з певного класу однотипних задач. Поняття алгоритму в інформатиці є фунда¬ментальним, тобто таким, яке не визначається через інші більш простіші поняття (для порівняння: у фізиці фундаментальними є поняття простору і часу, в математиці — поняття точки і т.д.).
Для виконання алгоритму завжди потрібен виконавець. Виконавцем алгоритму може бути людина, автомат або комп'ютер (тобто той, хто спроможний виконати цей алгоритм). Наприклад: складання телевізорів (виконавцем може бути або людина або автоматизована поточна лінія); прокладання курсу літака (виконавцем може бути або людина-штурман або бортовий комп'ютер) тощо. Будь-який виконавець може виконувати тільки обмежений набір операцій (наприклад, рука-маніпулятор переміщує деталі; провізор виготовляє ліки; банкомат видає гроші, комп'ютер виконує арифметичні дії тощо). Тому алгоритми мають характеризуватися такими властивостями:
1. Зрозумілість. Щоб виконавець міг досягти поставленої мети, використовуючи даний алгоритм, виконавцю необхідно уміти виконувати кожну вказівку, що входять до алгоритму. Наприклад: мама доручила купити в магазині продукти. Виконавцем цього алгоритму може бути хтось із родини: батько, син, бабуся, донька. Зрозуміло, що батькові достатньо сказати, які купити продукти, а далі деталізувати алгоритм не потрібно. Сину-підлітку слід детальніше пояснити де саме можна придбати потрібний товар, що можна купити замість відсутнього товару. Маленькій доньці алгоритм слід деталізувати ще більше: де взяти сумку, яку решту грошей потрібно принести з магазину, як дійти до магазину і як там себе поводити.
Зрозумілість — це властивість алгоритму, яка полягає в тому, що кожен алгоритм має бути написаний у командах, які розуміє та може виконати даний конкретний виконавець.
2. Визначеність (однозначність). Зрозумілий алгоритм не повинен містити вказівок, зміст яких може сприйматися неоднозначне. Наприклад, «купи щось смачненьке», «посоли за смаком», «прибери в квартирі» тощо є неоднозначними, тому що в різних випадках можуть привести до різних результатів. Окрім того, в алгоритмах неприпустимі такі ситуації, коли після виконання чергового розпорядження алгоритму виконавцю не зро¬зуміло, що потрібно робити потім. Наприклад, невдаху-учня тато попере¬джає: «отримаєш двійку до дому не повертайся». А що йому робити?
Визначеність — це властивість алгоритму, яка полягає в тому, що алгоритм має бути однозначно витлумачений і на кожному кроці вико¬навець повинен знати, що йому робити далі.
3. Дискретність. Як було згадано вище, алгоритм задає певну послі-довність дій, які дають змогу виконати розв'язання задачі. Отже, весь алгоритм розбивають у визначеній послідовності на прості вказівки: виконати дії наступної вказівки можна лише виконавши дії попередньої. Ця розбивка алгоритму на окремі елементарні дії (команди), що може виконати даний виконавець, і називається дискретністю.
4. Масовість. Дуже важливо, щоб складений алгоритм забезпечував розв'язання не однієї окремої задачі, а виконував розв'язання певного класу задач даного типу. Наприклад, алгоритм розв'язування системи лінійних рівнянь буде завжди однаковий, незалежно від значень коефіцієнтів. Або алгоритм приготування пиріжка не залежить від компонентів начинки. Отож, під масовістю алгоритму розуміють можливість застосування цього алгоритму для вирішення великої кількості однотипних завдань.
5. Результативність. Виконання будь-якого алгоритму має завер-шуватися одержанням кінцевих результатів. Тобто ситуацій, коли можуть виникнути так звані «зациклення», слід уникати ще при написанні алгоритму. Наприклад, розглянемо таку ситуацію: роботу дано вказівку залишити кімнату (замкнутий простір), не виконуючи руйнівних дій. У цьому випадку, якщо йому не дати команди «відкрити двері» (які, можливо, можуть бути закритими), то спроби робота залишити кімнату будуть марними.
Примітка: Учням можна запропонувати навести приклади інструкцій, що не мають властивостей алгоритму, а, отже, такі набори інструкції не можна вважати алгоритмами.
Яким чином можна подати алгоритм виконавцю? Існує кілька способів, вибір способу залежить від виконавця та того, хто подає алгоритм.
Першій спосіб — це словесний опис алгоритму. На цьому уроці ми вже розібрали кілька алгоритмів і всі вони подавалися виконавцю за допомогою словесного опису.
Другий спосіб — це подача алгоритму у вигляді таблиць, формул, схем, малюнків тощо. Наприклад, під час вивчення правил поведінки на дорозі, учням пропонують багато схем, дорожніх знаків (адже у такому разі інформація у вигляді схем ефективніше сприймається). Аналізуючи їх, учень відпрацьовує ту лінію поведінки, що пропонується. Аналогічно можна навести приклади алгоритмів, записаних у вигляді умовних позначок на упаковці товару щодо його використання (наприклад, заварювання чаю, кави тощо). В математиці за допомогою формул можна розв'язати задачу.
Третій спосіб — запис алгоритмів за допомогою блок-схеми. Цей ме¬тод був запропонований в інформатиці для наочності представлення алго¬ритму за допомогою набору спеціальних блоків.
Основні з цих блоків такі:
Четвертий спосіб — навчальні алгоритмічні мови (псевдокоди). Ці мови мають чітко визначений синтаксис. Але створені вони з навчальною метою, тому мають зрозумілий для людей вигляд. Таких навчальних алгоритмічних мов нині існує багато: починаючи з графічних середовищ «Алторитміка», «Роботландія», «Лого-світи», «Черепашка» тощо і закінчу¬ючи текстовими «національними» реалізаціями алгоритмічних мов, подібних до мови Паскаль. Всі вони широко застосовуються на етапі нав¬чання основам програмування.
П'ятий спосіб — запис алгоритму мовою програмування. На практиці найчастіше виконавцем створеного людиною алгоритму е комп'ютер і тому алгоритм має бути написаний мовою, зрозумілою для комп'ютера, тобто .мовою програмування.
Запитання для перевірки засвоєння знань
1. Поясніть що таке зрозумілість алгоритму?
2. Назвіть властивості алгоритму.
3. Для чого використовуються блок-схеми?
4. Що таке масовість алгоритму?
5. Що таке дискретність алгоритму? Базові структури алгоритмів
Навіть ще не маючи досвіду в створенні алгоритмів, ми інтуїтивно розуміємо, що вони розрізняються за своєю структурою.
Існує три базових структури алгоритмів: лінійні; розгалужені; циклічні. Найпростіша в написанні та виконанні перша з цих структур — лінійна. Алгоритм лінійної структури складається з послідовності простих команд.
Простими можна назвати ті команди, що виконуються безумовно, тобто після першої команди виконується друга, потім третя і т.д. Загальний вигляд лінійного алгоритму, поданий мовою блок-схем, такий:
На відміну від людини-виконавця, виконавець-комп'ютер не може відмовитися від виконання команди (він не може подібно недбалому учню сказати «не хочу», «не буду», «в мене болить голова і поганий настрій»). Команду, записану в алгоритмі, потрібно виконувати, тому, якщо знехтувати суто людськими якостями («не хочу», «не можу» і т.д.), лінійним можна назвати алгоритм ранкового збирання учня до школи:
Прокинутися /зробити ранковий туалет / одягнутися / поснідати / зібрати речі / одягнути верхній одяг, взутися / вийти до школи.
Та навіть у такому простому алгоритмі можна легко знайти недоліки. Наприклад, що робити, якщо: «я себе погано почуваю», а «я вже зібрав речі звечора», а «я не встиг напередодні вивчити всі уроки і мені необхідно щось повторити», а що значить «одягнути верхній одяг» (залежить від пори року, погоди тощо). Коли простежити за поведінкою будь-якої людини протягом дня, то з'ясується, що майже ніколи людина не діє за лінійним алгоритмом: адже людині доводиться весь час аналізувати ситуацію, змінювати свою поведінку та свої плани, залежно від обставин. Тому набагато частіше доводиться мати справу з іншим типом алгоритму — розгалуженим. Цей алгоритм обов'язково містить у собі умову і виконується залежно від цієї умови.
Умова — це елемент структури алгоритму, де відбувається перевірка деякої альтернативи і залежно від результату перевірки обирається по-слідовність подальших дій з двох варіантів
Мовою блок-схем розгалужений алгоритм подається таким чином:
Блок-схема розгалуженого алгоритму
Аналізуючи наведену схему можна дійти висновку, що коли умова істинна (так), то виконуватимуться команди серії 1, якщо умова хибна (ні), то — серія 2. Тепер розглянемо, що ж таке умова з точки зору виконавця. Умовою можна вважати висловлювання на яке можна дати відповідь так (істина) або ні (хибність). Виходячи з цього, висловлювання «Якого кольору твій піджак?» не можна вважати умовою, а висловлю¬вання «Твоє волосся русяве?» — можна.
Примітка: Тут можна запропонувати учням пограти і придумати вирази, які можна вважати умовами, а потім перефразувати їх таким чином, щоб ці вирази стали помилковими, і запропонувати знайти помилки.
Дуже часто в житті ми змушені враховувати велику кількість най-різноманітніших умов. Наприклад, дівчинка йде на прогулянку, якщо «мама відпустила» та «гарна погода», а ще якщо «подруга покликала». Уроки дехто з учнів робить, якщо знов таки «тато примусив», або «вчителька дуже сувора». Такі умови називаються складеними. Вони містять кілька простих умов і об'єднуються між собою словами «або» чи «та». Перше з цих слів («або») використовується тоді, коли необхідне виконання хоча б однієї з умов, тобто хоча б одна з умов є істинною. Наприклад, діти залишаються вдома (не йдуть до школи), якщо «сьогодні вихідний», або «сьогодні канікули», або «сьогодні свято», або «захворів». зрозуміло, що зовсім не обов'язково, щоб сьогодні були одночасно і кані¬кули, і свято, і вихідний, та ще й хвороба, щоб не піти до школи.
Друге слово («та»), навпаки, використовується лише тоді, коли необ¬хідне тільки одночасне виконання всіх умов. Наприклад, тільки у випадку наявності закордонного паспорту та наявності квітка на певний рейс літака та своєчасного прибуття в аеропорт пасажир має можливість літаком подорожувати за кордон.
Однак, застосовуючи лише команду розгалуження, важко реалізувати алгоритми, де потрібне багаторазове повторення деякої послідовності певних дій. У такому разі виручає циклічний алгоритм. Дуже часто доводиться мати справу з алгоритмами з повтореннями, причому чітко розрізняють два типи повторень: в одному випадку точно відомо, скільки разів слід повторити задану послідовність команд, а в іншому — ні. На¬приклад, у першому класі вчителька дає завдання дітям: «Діти, напишіть, будь ласка, в зошитах десять цифр «1», а потім рядочок цифр «2». Чим відрізняються ці два завдання? У першому випадку дитина отримала чітку вказівку написати десять одиниць, а в другому — ця вказівка була неточною (рядочок двійок). Чому другий випадок не такий точний? Тому що кількість написаних кожним учнем цифр буде залежати від почерку.
Залежно від того, чи відомо скільки разів слід повторювати якусь по-слідовність команд, розрізняють цикли з лічильникам (кількість повторень відома заздалегідь) та цикли з умовою (цикл повторюється доти, доки не виконається (або буде виконуватися) якась умова). Крім того, в циклах з умовою теж можна виділити два різних варіанти:
• цикл з передумовою — коли виконавець спочатку перевіряє умову, а потім виконує деяку послідовність;
• цикл з післяумовою — спочатку виконавець виконує хоча б один раз певну послідовність дій, а потім перевіряє, чи не досягнуто бажаного результату (коли ми хочемо пити, то спочатку робимо хоча б ковток води, а потім починаємо контролювати, чи не вгамували свою спрагу).
Мовою блок-схем обидва типи циклів виглядають таким чином:
Найчастіше у житті доводиться виконувати завдання, для розв'язання яких слід використати елементи різних типів алгоритмів. Отже, найпо-ширенішими є алгоритми, де поєднуються елементи лінійних, розгалу¬жених та циклічних структур.
Під час складання алгоритмів іноді виникає ситуація, коли необхідно виконати повторювану послідовність дій, але не зовсім ідентичну. Напри¬клад, потрібно приготувати торт, пиріжки. Алгоритми приготу¬вання загалом схожі, але є в них певні відмінності. Щоб не переписувати алгоритми, які суттєво не розрізняються, використовують так звані допоміжні алгоритми, які слід викликати і виконувати тільки тоді, коли в них є потреба. Перевага використання допоміжних алгоритмів полягає в тому, що склавши їх один раз, можна потім використовувати їх при написанні інших алгоритмів. У цьому випадку такі алгоритми об'єднують у так звані бібліотеки і використовують їх так само, як в реальному житті ми користуємося традиційними бібліотеками.
Запитання для перевірки засвоєння знань
1. Наведіть приклад алгоритму з 4-5 простих команд,
2. Наведіть приклад алгоритму з умовами. Зробіть висновки,
3. Чим складені умови зі словом «та» відрізняються від умов зі словом «або»? Наведіть приклади.
4. Які циклічні алгоритми ви знаєте?
5. Наведіть приклад алгоритму з повтореннями. Побудова алгоритмів
Під час побудови алгоритму часто виникає необхідність пояснити виконавцю деякі складні дії, виконання яких не входить у систему команд виконавця. Наприклад, перший раз даючи дитині завдання пришити ґудзик до сорочки, їй необхідно пояснити, як слід добирати нитки для шиття, як протягнути нитку в голку, як тримати голку та ґудзик під час роботи, чим відрізняється пришивання ґудзика до тоненької сорочки та товстої куртки (у другому випадку беруть ґудзик на «ніжці»). У подальшому такі докладні пояснення будуть зайвими, оскільки алгоритм «пришивання ґудзика» стає вже командою в системі команд виконавця «дитина».
Наприклад, кожна дія людини (якщо вона може її виконати) може вважатися командою її «системи команд», хоча колись, на етапі навчання, їй ретельно пояснювали, які саме дії та в якій послідовності потрібно виконати, щоб досягти поставленої мети. Отже, кожну дію можна вважати окремою командою виконавцю. Якщо виконавець не знає, як розв'язувати запропоновану задачу, потрібно розкласти її на такі підзадачі, які входять до системи команд виконавця. Таким чином отримують алгоритм, що складається з простих команд, зрозумілих даному виконавцю, або остаточно переконуються, що таку задачу даний виконавець виконати не зможе, оскільки в його системі команд не існує команд, необхідних для розв'язання цієї задачі. Наприклад, як би ми не деталізували дошколярику алгоритм керування літаком, таке завдання, дитина виконати неспроможна.
Запропонований підхід до конструювання алгоритмів називається методам покрокової деталізації зверху донизу. За такого підходу кожну операцію можна подати у вигляді лише одного а трьох типів базових структур алгоритмів —лінійної (слідування), розгалуження та повторення (циклу). Ступінь деталізації алгоритму при цьому залежить від того, на якого виконавця орієнтовано виконання даного алгоритму.
Набір команд із системи команд обраного виконавця суттєво впливає на ступінь деталізації алгоритму та на його структуру. Розглянемо, наприклад, алгоритм «переходу через вулицю». Взагалі для кожної людини можна вважати це командою, що входить до її «системи команд». Але кожний пам'ятає, як його навчали: «якщо там, де потрібно перейти вулицю, є ї підземний перехід, то скористайся ним, якщо немає — відшукай місце, де є світлофор, і перейди вулицю за правилами дорожнього руху»; «якщо немає ані підземного переходу, ані світлофора...». Однак, навіть у такому алгоритмі є необхідність дещо деталізувати. Наприклад, що значить «перейди вулицю за правилами при наявності світлофора»? А якщо виконавець — маленька дитина, то що таке світлофор і як його шукати? А якщо виконавець — взагалі прибулець з інших світів? Що таке «зелене», «червоне», «жовте»? Що таке підземний перехід? Запитання можна продовжувати.
Алгоритми, що складаються для розв'язування окремих підзадач основної задачі, називаються допоміжними. Їх створюють при поділі складної задачі на прості або за необхідності багаторазового використання того ж самого набору дій в одному або різних алгоритмах. Допоміжний алгоритм (як і будь-який інший алгоритм) повинен мати тільки один вхід та один вихід, причому того, хто користується таким алгоритмом, зовсім не цікавить, як реалізований цей алгоритм. Головне, щоб усі команди, які входять до складу допоміжного алгоритму, входили до системи команд обраного виконавця. Зверніть увагу й на те, що в реальному житті допоміжні алгоритми можуть виконувати навіть інші виконавці. Наприклад, якщо майстер виконує ремонт квартири, то це не означає, що він повинен власноруч зробити шпалери, інструменти, фарбу та клей. Алгоритми виробництва матеріалів існують, і їх хтось виконує, а він тільки використовує результати такої роботи. Таким чином, можна вважати допоміжний алгоритм деякою «чорною скринькою», на вхід якої виконавець подає деякі вхідні дані, а на виході — отримує очікуваний результат. Головне — чітко домовитись про правила оформлення вхідних даних та результату. Невиконання домовленостей може призвести до збою у виконанні допоміжного алгоритму або до отримання неочікуваного результату. Описаний метод послідовної деталізації покладено в основу технології структурного програмування і е широко застосовуваним у таких мовах програмування, як Паскаль, С, С++.
Запитання для перевірки засвоєння знань
1. Що таке система команд виконавця?
2. Які типи базових структур алгоритмів ви знаєте?
3. Від чого залежить ступінь деталізації алгоритму?
4. Які алгоритми називають допоміжними?
5. Схарактеризуйте особливості допоміжних алгоритмів.
|