1. АЛГОРИТМИ
1.1. Змістовне поняття алгоритму
Уявіть собі, що Вам необхідно пояснити учневі 6-го класу, як додавати дроби. Оскільки викладати математичну теорію питання не хочеться, Ви вирішуєте представити метод розв’язання задачі у виді послідовності дій над числами, які він повинен виконувати, не вникаючи в суть справи. Це і є алгоритм рішення задачі.
Термін «алгоритм» уперше був використаний середньовічними вченими, що переводили на латинь твори узбецького вченого Аль Хорезми. Алгоритмами вони називали правила арифметичних дій над багаторозрядними числами.
Такий метод викладення способу рішення задач широко розповсюджений. У виді алгоритмів викладають кулінарні рецепти, правила користування побутовими приладами, службові інструкції і т.д. В інформатиці алгоритми використовуються для опису способу рішення задач по перетворенню інформації.
Точне математичне визначення алгоритму і вивчення цього поняття - предмет спеціальної математичної дисципліни - теорії алгоритмів, що, у свою чергу, спирається на апарат математичної логіки.
Зараз ми розглянемо на змістовному (неформальному) рівні характерні основні риси цього поняття.
Алгоритм – це деяке правило перетворення інформації, застосування якого до заданої (вихідної) інформації приводить до результату – нової інформації.
Так, наприклад, застосування правила додавання дробів до 1/2 і 2/3 приводить до результату 7/6.
Особливу увагу в теорії і практиці алгоритмізації приділяють методам завдання (опису, конструювання) алгоритмів. Один з основних підходів до опису алгоритмів – так званий імперативний підхід полягає в уточненні способу опису алгоритму як послідовності кроків, на кожному з яких виконується одна з команд (інструкцій, операторів).
Алгоритм – це скінчена послідовність інструкцій (команд), виконання яких приводить до результату. Кожна команда алгоритму містить точний опис деякої елементарної дії (операції), а також, у явному або неявному виді, вказівку на команду, яку необхідно виконати наступною.
На рис. 1.2 зображена послідовність команд C1, C2, …, Ck по перетворенню інформації, з яких складено алгоритм.
Згадаємо стародавню задачу-головоломку про вовка, козу і капусту, які на чолі з людиною вийшли до річки і мають переправитися на інший берег. У розпорядженні цієї веселої компанії є човен, що вміщує разом з людиною ще тільки одного її члена – або вовка, або козу, або капусту. Якщо вовк виявиться наодинці з козою, він її з'їсть. Якщо коза виявиться наодинці з капустою, вона її (капусту) з'їсть. Потрібно скласти такий план перевезень, при якому наша компанія перебереться на інший берег у цілості і схоронності. Цей план і є алгоритм. Опишемо його:
Алгоритм Перевезення:
