Алгоритм. Слово алгоритм походить від algorithmi - латинської форми написання імені великого математика IX ст

Слово алгоритм походить від algorithmi - латинської форми написання імені великого математика IX ст. Аль-Хорезмі, який сформулював правила виконання арифметичних дій.

Розглянемо, наприклад, відому задачу про людину з човном (Л), вовком (В), козою (Кз) і капустою (Кп). Алгоритм її розв’язку можна представити таким чином:

початковий стан, { Л, В, Кз, Кп -> }

- 1-ий крок, пливуть Л, Кз, Кп { В -> Л, Кз, Кп }

- 2-ий крок, пливуть Л, Кз { В, Л, Кз <- Кп }

- 3-ій крок, пливуть Л, В { Кз -> Л, В, Кп }

-4-ий крок пливуть Л { Л, Кз <- В, Кп }

- кінцевий стан пливуть Л, Кз { -> Д, В, Кз, Кп }.

Таким чином, алгоритм - це абстрактний математичний об'єкт, тому він вимагає абстрактного виконавця. Визначення цього виконавця по суті дає операційну семантику алгоритмічної мови. Модифікація алгоритмічної мови, очевидно, вимагає відповідної зміни іншого математичного об'єкта - виконавця.

Виконавцем ми будемо називати пристрій, здатний виконувати дії із заданого набору дій. Команду на виконання окремої дії звичайно називають оператором або інструкцією. Приклади виконавців: пральна машина, телефон, мікрокалькулятор, магнітофон, комп'ютер тощо. Приклади інструкцій: перемотати плівку, встановити з'єднання із заданим номером, виконати прання бавовняної білизни, зіграти партію у реверсі і т.д.

Відмітимо особливості виконавців.

По-перше, людина далеко не єдиний виконавець алгоритмів.

По-друге, будь-який виконавець складається з пристрою управління і " робочого інструмента ".

По-третє, кожний виконавець алгоритмів володіє обмеженим набором допустимих дій (описати виконавця - значить указати його допустимі дії). Кожний виконавець може розуміти і виконувати якесь порівняно невелике число різних елементарних команд. З цих команд складаються алгоритми. З цього невеликого числа команд можна скласти невелику учбову програму, а можна і складну програму з тисяч команд.

По-четверте, для рішення одних і тих же задач виконавці з більш "бідним" набором допустимих дій вимагають більш складних і докладних алгоритмів. По-п'яте, різні класи задач вимагають різних наборів допустимих дій, різних виконавців.

Розглянемо приклади найпростіших виконавців.

Виконавець "Обчислювач ". Він вміє: множити число на 2 (*2); збільшувати число на 1 (+1). Потрібно скласти алгоритм отримання числа 100 з одиниці. Скільки дій в самому короткому з таких алгоритмів?

Розглянемо більш просту задачу отримання з одиниці числа 4. Для її рішення можна використати алгоритм вигляду 1 (+1) (+1) (+1) або +1 (*2) (*2). Очевидно, що другий алгоритм більш короткий. Повернемося до нашої задачі. Для отримання найкоротшого алгоритму перетворюємо число 100 у 1 використовуючи ділення на 2 і віднімання 1. Маємо

100 -> 50 -> 25 -> 24 -> 12 -> 6 -> 3 -> 2 -> 1.

Отже, для нашого виконавця алгоритм 1 (*2) (+1) (*2) (*2) (*2) (+1) (*2) (*2) буде найбільш коротким і містить 8 дій.

І нарешті складання програми для ЕОМ - це заключний етап рішення задачі.

Як влучно помітив А.П.Єршов, " програміст повинен володіти здатністю першокласного математика до абстракції і логічного мислення в поєднанні з едісонівським талантом до створення чого-небудь з нуля і одиниці " (А.П.Єршов "Людський чинник у програмуванні").

Якщо алгоритмічну мову вибирають, виходячи з власних бажань, то вибір мови програмування можуть диктувати певна реальність: замовник, комп'ютер, попередній досвід. Основною, навчальною мовою програмування вважається мова Паскаль, названа в пошану великого французького вченого, який першим в світі у 1642 році виготував автоматичний пристрій для додавання чисел. Мова Паскаль була створена у 1969 році Ніклаусом Віртом в Швейцарському технічному інституті у Цюріху спеціально для вивчення програмування. Сьогодні існує декілька варіантів мови Паскаль.