Тема: Поняття алгоритму. Властивості алгоритмів. Форми подання алгоритму. Виконавець алгоритму
Матеріал для вивчення
Визначення алгоритму
Слово «алгоритм» походить від «algorithmi» — латинської форми написання імені великого математика аль-Хорезмі, який сформулював правила виконання арифметичних дій. Тому спочатку під алгоритмом розуміли тільки правила виконання чотирьох арифметичних дій над багатоцифровими числами в десятковій системі числення. Зараз він є одним із фундаментальних понять інформатики.
Алгоритм — це скінчена послідовність команд (вказівок), що визначає, які дії та у якому порядку потрібно виконати, щоб досягти поставленої мети.
Алгоритм складається із команд — окремих указівок виконавцеві виконати деякі конкретні дії. Команди алгоритму виконуються одна за одною, і на кожному кроці відомо, яка команда повинна виконуватися. Почергове виконання команд за кінцеве число кроків приводить до розв’язання задачі. Для того щоб виконавець міг розв’язати задачу за заданим алгоритмом, він повинен уміти виконувати кожну з дій, що вказується командами алгоритму.
Система команд виконавця — сукупність команд, які можуть бути виконані виконавцем; кожна команда алгоритму входить до системи команд виконавця.
В основі роботи автоматичних пристроїв лежить положення, що найпростіші операції, на які розпадається процес розв’язання задачі, може виконати машина, яка спеціально створена для виконання окремих команд алгоритму і виконує їх у послідовності, вказаній в алгоритмі.
Властивості алгоритму
Виконуючи алгоритм, виконавець може не вникати в зміст того, що він робить, і разом із тим отримати потрібний результат, тобто виконавець діє формально. Тому для правильної побудови алгоритму необхідно знати систему команд виконавця, бути впевненим, що виконання алгоритму завершиться за кінцеве число кроків. Тому кажуть про деякі загальні властивості алгоритмів.
Дискретність. Алгоритм розв’язання задачі повинен складатися з послідовності окремих кроків — відокремлених одна від одної команд (указівок), кожна з яких виконується за кінцевий час. Тільки закінчивши виконання однієї команди, виконавець переходить до виконання іншої.
Визначеність (однозначність). Кожна команда алгоритму однозначно визначає дії виконавця і не припускає подвійного тлумачення. Суворо визначеним є й порядок виконання команд.
Формальність. Будь-який виконавець, який володіє заданою системою команд, може виконати заданий алгоритм, не вникаючи в суть задачі.
Виконуваність. Алгоритм призначений для певного виконавця, може містити тільки команди, які входять до системи команд даного виконавця.
Результативність. Виконання алгоритму не може закінчуватися невизначеною ситуацією або зовсім не закінчуватися. Будь-який алгоритм передбачає, що його виконання при допустимих початкових даних за кінцеве число кроків приведе до очікуваного результату.
Масовість. Алгоритм має передбачати можливість зміни початкових (вхідних) даних у деяких допустимих межах і можливість використання його для розв’язання задач одного класу (універсальність алгоритму).
Саме через ці властивості часто дається визначення поняття алгоритму як скінченної однозначно визначеної послідовності операцій, формальне виконання якої приводить до розв’язання певної задачі за кінцеве число кроків.
Виконавець алгоритму
Виконавцем алгоритму може бути людина, тварина, ЕОМ, система людина-машина, верстат-автомат, робот тощо, тобто ті хто розуміє та може виконати команди алгоритму.
Точне визначення, що таке виконавець, дати дуже складно, та в цьому й немає потреби. Важливо зрозуміти основні характеристики виконавця: середовище, елементарні дії, систему команд, відмови. Середовище – це місце перебування виконавця. Кожен виконавець може виконувати команди лише з деякого строго заданого списку – системи команд виконавця. Для кожної команди повинні бути задані умови застосування, тобто в яких станах середовища може бути виконана команда, й описані результати її виконання.
Виконавця можна представити у вигляді деякого пристрою, керування яким спричиняє виконання тієї чи іншої команди. Після виклику команди виконавець здійснює відповідну елементарну дію. Важливо зазначити, що в цьому процесі нас більше цікавить результат, а не механізм виконання команди. Відмови виконавця виникають за умови виклику команди в неприпустимому для даної команди стані середовища. Ситуації, при яких виникає відмова, різні для різних команд виконавця (наприклад, ділення на нуль, відсутність принтера при виведенні інформації на друк). При виконанні деяких команд відмови ніколи не виникають (наприклад, обчислення виразу 2 + 2).
У деяких випадках виконавцем алгоритмів є людина. Наприклад, якщо йдеться про правила, інструкції, функціональні та посадові обов’язки тощо. Але людина далеко не єдиний виконавець алгоритмів. Роботи-маніпулятори, верстати з програмним управлінням, жива клітина і навіть тварини в цирку виконують різноманітні алгоритми, в тому числі й ті алгоритми, які людина не може виконати.
Що ж таке виконавець? Спрощено виконавця можна уявити собі як деякий пристрій керування, з’єднаний з набором інструментів. Пристрій керування розуміє алгоритми і організовує їх виконання, користуючись при цьому відповідними інструментами. А інструменти, сприймаючи команди керуючого пристрою, виконують дії. Якщо людину розглядати як виконавця, то можна провести таку аналогію: мозок – пристрій керування, руки, ноги, очі, ніс тощо – інструменти. У роботів-маніпуляторів, верстатів з програмним управлінням, комп’ютерів пристроєм керування є процесор, а набір інструментів залежить від того, для розв’язування яких задач призначений той чи інший виконавець.
Формальне виконання алгоритму
Під формальним виконанням алгоритму розуміється таке його виконання, коли сам виконавець не знає ні постановки задачі, ні змісту отриманих результатів, але, чітко виконуючи усі дії, записані в алгоритмі, досягає результату.
Найчастіше алгоритми виконуються саме формальним чином. Формальними виконавцями є користувачі різноманітних побутових електричних приладів, учасники спортивних ігор, які дотримуються правил цих ігор, учні, що застосовують у своїх творчих роботах мовні правила, виконують завдання з математики чи фізики, використовуючи відомі формули, закони та методи розв’язування різних типів задач. Продовжуючи цю думку, комп’ютер також слід вважати формальним виконавцем алгоритмів при виконанні ним програм.
Способи представлення алгоритму
- Словесні.
- Словесно-формульні.
- Графічні.
- Скінчений набір кодів.
При складанні алгоритмів можна поєднувати різні форми подання алгоритмів.
Процес алгоритмізації — це визначення елементарних дій та порядку їх виконання для розв’язання поставленого завдання. Існують різні способи запису алгоритмів (словесний, формульно-словесний, метод блок-схем, програмний та ін.), які застосовуються для представлення алгоритму у вигляді, що однозначно розуміється і розробником, і виконавцем алгоритму.
Для опису алгоритмів людина часто користується природною мовою, але для запису багатьох алгоритмів природна мова виявилась незручною, тому виникла необхідність у створенні штучних мов, наприклад мови математичних формул, хімічних процесів тощо. Існує спеціальна навчальна алгоритмічна мова, яка була створена для запису алгоритмів на папері; вона використовує слова природної мови, але має більш жорстку структуру. Найбільше поширення для запису логічної структури алгоритмів отримали графічні (структурні) схеми, які спрощують складання та аналіз алгоритму, полегшують перехід від запису алгоритму до написання програми.
Графічна схема (блок-схема) алгоритму — це графічне зображення алгоритму у вигляді спеціальних блоків з необхідними словесними поясненнями. Кожний етап алгоритму представляється у вигляді геометричної фігури (блоку), що має певну форму в залежності від характеру операції. Блоки на схемі з’єднуються стрілками (лініями зв’язку), які визначають послідовність виконання операцій та утворюють логічну структуру алгоритму.
Важливою особливістю базових структур алгоритмів є те, що вони мають один вхід і один вихід, що дозволяє при відносній незалежності конструювати окремі блоки алгоритмів, а потім окремо розроблені структури з’єднувати між собою (вихід однієї базової структури сполучається із входом іншої). Весь алгоритм представляє лінійну послідовність базових структур.
Аргументи, результати, проміжні величини
Для роботи багатьох алгоритмів треба задавати початкові значення. Ці значення передаються в алгоритм за допомогою аргументів.
Аргумент – це величина, значення якої необхідно задати для виконання алгоритму.
Проте є алгоритми, що не потребують жодних початкових значень для свого виконання. Пізніше ми ознайомимося з такими алгоритмами. Однак немає жодного алгоритму, що не дає ніякого результату. Справді, яка ж потреба в такому алгоритмі? Прикладом різноманітності результатів роботи програм є ігрові комп’ютерні програми. У цих програмах дані обробляються та певним чином перетворюються у графічні і звукові образи.
Результат – це величина, значення якої отримується внаслідок виконання алгоритму.
Під час складання багатьох алгоритмів виникає необхідність крім аргументів і результатів використовувати ще й додаткові величини. Введення в алгоритм таких величин задає автор алгоритму.
Проміжна величина – це величина, яка додатково вводиться в процесі розробки алгоритму.
Ми вже достатньо наочно уявили собі алгоритм. Але як він виглядає з погляду звичайного користувача цього алгоритму? Найчастіше користувач не знає, яким чином цей алгоритм записаний, за допомогою яких команд, які методи були застосовані для його реалізації, якою мовою програмування. У даному випадку йдеться про виконання алгоритму на комп’ютері у вигляді готової програми. Виконавець алгоритму бачить лише його зовнішню сторону: які початкові дані необхідно задати і в якому вигляді отримується результат. Кожний, мабуть, може пригадати номер фокусника, коли той у чорну скриньку закладає одні предмети, а витягує зовсім інші. Від глядачів прихований вміст цієї чорної скриньки, і залишається таємницею, яким чином у ній відбувається «перетворення» предметів. Саме такою «чорною скринькою» для користувача і є програма, якою він користується на комп’ютері. Це можна зобразити у такому вигляді
Домашнє завдання
Інформатика 11 клас рівень стандарту (Ривкінд, Лисенко, Чернікова, Шакотько)
Опрацювати параграф підручника п.1.2
Завдання № 8, 9, 10, 11 на с. 15-16 підручника