Лінійні алгоритми: теоретичний аспект
1. Загальні поняття алгоритмів
Поняття алгоритму виникло в математиці. Здавна при виконанні обчислювальних робіт використовувалися різноманітні інструкції, правила. За допомогою правил обчислювач міг, не вникаючи в суть задачі, одержати правильний розв'язок. Такі правила виконання математичних дій отримали назву алгоритмів. Велика роль у введенні поняття алгоритмів належить видатному узбецькому математику ІX століття Мухаммеду ібн Муса ал-Хорезмі, який сформулював правила виконання чотирьох арифметичних дій надчислами. Головна його праця з арифметики була перекладена в Європі на латинь. На латині ім'я математика писали Аlgorіthmі, звідки утворилося слово «алгоритм»1.
Приклади математичних задач, алгоритми розв’язання яких усім знайомі зі шкільного курсу математики:
додавання двох багатоцифрових чисел;
ділення відрізка навпіл за допомогою циркуля і лінійки;
квадратного рівняння тощо.
У житті людини трапляються алгоритми не тільки як правила математичних обчислень, а й у вигляді інших послідовностей дій. дій, для виконання яких можна скласти алгоритми, можуть бути:
як перейти регульоване перехрестя двох вулиць;
як зварити картоплю;
як розкласти багаття.
Алгоритм «Користування телефоном»:
1. зняти трубку; 2. почувши гудок, набрати номер; 3. якщо з'єднання відбулось — говорити; 4. якщо з'єднання не відбулось — покласти трубку і перейти до п.1.
Алгоритм «Відгадай число»:
1. Задумай будь-яке число. 2. Додай до нього 12. 3. Від результату відніми 7. 4. Відніми від результату задумане число. 5. Одержано число 5.
Останній алгоритм — це приклад числового алгоритму.
Числовий алгоритм описує послідовність математичних дій над числами.
Наведемо приклади алгоритмів, за допомогою яких обробляється не числова інформація, а літерна:
алгоритм запису прізвищ учнів класу в алфавітному порядку;
алгоритм вибору із даного списку осіб жіночої статі;
алгоритм-рецепт приготування салату з крабів тощо.
Нечисловий алгоритм описує послідовність дій, не пов'язаних з обробкою числової інформації.
Існує багато визначень поняття «алгоритм». На погляд багатьох авторів, під алгоритмом слід розуміти наступне:
Алгоритм — це зрозумілий, точний та повний опис послідовності простих дій для розв'язування конкретної задачі1.
Алгоритм знаходження найбільшого спільного дільника (НСД) двох натуральних чисел вперше описав Евклід:
1. Порівняй числа а і b.
2. Якщо а = b, то а найбільший спільний дільник.
3. Якщо а > b, то замінити а на a – b.
4. Якщо а < b, то замінити b на b – a.
5. Перейти до п. 1.
Алгоритми застосовується не тільки в математиці, але й у багатьох сферах людської діяльності.
Виконавцем алгоритмів може бути людина або машина.
Для людини це звичайні правила, рецепти, інструкції (як перейти вулицю, як спекти торт, як користуватися магнітофоном). Ці правила передаються усно або записуються на папері у вигляді тексту,креслень і малюнків. Машині для роботи потрібен опис дій на її «машинній» мові, який записується на магнітну стрічку або диск, лазерний диск тощо. До розробки алгоритмів звертаються тоді, коли потрібно «доручити» автоматичному приладу роботу,яку виконувала людина. Саме тут виникає необхідність точного опису послідовності простих дій для виконання певної роботи. Машині не скажеш: «Візьми ту штуку і стукай по цій штуці!»Саме після розробки відповідних алгоритмів створювалися пральні і швейні машини, м'ясорубки,трактори, газові плити, авторучки, екскаватори, друкарські машини тощо. В інформатиці використовують більш спеціалізоване поняття «алгоритму», яке ґрунтується на поняттях «команда» і «виконавець»1.
Алгоритм — це послідовність команд, що визначають дії виконавця з урахуванням його можливостей.
Програмісти вчаться розробляти алгоритми для того, щоб за їх допомогою писати програми для комп'ютера. За програмою-алгоритмом комп'ютер буде дуже швидко розв'язувати складні задачі, на які людина потратила б багато часу і зусиль.