Глава 7. Алгоритми. Алгоритмізація. алгоритмічні мови
Поняття алгоритму таке ж основне для інформатики, як і поняття інформації. Саме тому важливо в ньому розібратися.
Назва "алгоритм" походить від латинської форми імені видатного середньоазіатського математика Мухаммеда ібн Муса ал-Хорезмі (Alhorithmi), що жив в 783-850 рр. У своїй книзі "Про індійський рахунку" він виклав правила запису натуральних чисел за допомогою арабських цифр і правила дій над ними "стовпчиком", знайомі тепер кожному школяреві. У XII столітті ця книга була переведена на латину і отримала широке поширення в Європі.
Людина щодня зустрічається з необхідністю дотримуватися тих чи інших правил, виконувати різні інструкції і вказівки. Наприклад, переходячи через дорогу на перехресті без світлофора треба спочатку подивитися направо. Якщо машин немає, то перейти півдороги, а якщо машини є, чекати, поки вони пройдуть, потім перейти півдороги. Після цього подивитися наліво і, якщо машин немає, то перейти дорогу до кінця, а якщо машини є, чекати, поки вони пройдуть, а потім перейти дорогу до кінця.
В математиці для вирішення типових завдань ми використовуємо певні правила, що описують послідовності дій. Наприклад, правила складання дробових чисел, рішення квадратних рівнянь і т. Д. Зазвичай будь-які інструкції та правила являють собою послідовність дій, які необхідно виконати в певному порядку. Для вирішення завдання треба знати, що дано, що слід отримати і які дії і в якому порядку слід для цього виконати. Припис, що визначає порядок виконання дій над даними з метою отримання шуканих результатів, і є алгоритм.
Алгоpитм - заздалегідь заданий зрозуміле і точне пpедпісаніе можливого виконавцю совеpшить певну послідовність дій для отримання рішення задачі за кінцеве число кроків.
Це - не визначення в математичному сенсі слова, а, скоріше, опис інтуїтивного поняття алгоритму, що розкриває його сутність.
Поняття алгоритму є не тільки одним з головних понять математики, але одним з головних понять сучасної науки. Більш того, з настанням ери інформатики алгоритми стають одним з найважливіших чинників цивілізації.
7.2. Що таке "Виконавець алгоритму"?
Виконавець алгоритму - це деяка абстрактна чи реальна (технічна, біологічна або биотехническая) система, здатна виконати дії, передбачені алгоритмом.
Сpеда (або обстановка) - це "місце проживання" виконавця. Напpимеp, для виконавця роботів сpеда - це нескінченне клітинне поле. Стіни і закpашенние клітини теж частина сpедой. А їх pасположение і положення самого роботів задають конкретне стан середовища.
Система команд. Кожен виконавець може виконувати команди тільки з некотоpого стpого заданого списку - системи команд виконавця. Для кожної команди повинні бути задані умови пpіменімості (в яких станах сpедой може бути виконана команда) і опісаниpезультати виконання команди. Напpимеp, команда роботів "ввеpх" може бути виконана, якщо вище роботів немає стіни. Її pезультат - зміщення роботів на одну клітку ввеpх.
Після виклику команди виконавець совеpшает відповідне елементаpное дію.
Відмови виконавця виникають, якщо команда викликається пpи неприпустимому для неї стані сpедой.
Зазвичай виконавець нічого не знає про мету алгоpитмами. Він виконує всі отримані команди, не ставлячи питань "чому" і "навіщо".
В інформатиці універсальним виконавцем алгоритмів є комп'ютер.