АЛГОРИТМ - система правил, сформульована на зрозумілому виконавцеві мові, яка визначає процес переходу від допустимих вихідних даних до деякого результату і має властивості масовості, кінцівки, визначеності, детермінованості.
Слово «алгоритм» знову стало вживаним з появою електронних обчислювальних машин для позначення сукупності дій, що становлять певний процес. Тут мається на увазі не тільки процес вирішення деякої математичної задачі, але і кулінарний рецепт і інструкція по використанню пральної машини, і багато інших послідовні правила, які не мають відношення до математики, - всі ці правила є алгоритмами. Слово «алгоритм» в наші дні відомо кожному, воно настільки впевнено зробило крок в розмовну мову, що зараз нерідко на сторінках газет, у виступах політиків зустрічаються вирази «алгоритм поведінки», «алгоритм успіху» і т.д.
Проблема визначення поняття «алгоритм».
Протягом багатьох століть поняття алгоритму пов'язувалося з числами і відносно простими діями над ними, та й сама математика була, по більшій частині, наукою про обчисленнях, наукою прикладної. Найчастіше алгоритми представлялися у вигляді математичних формул. Порядок елементарних кроків алгоритму задавався розстановкою дужок, а самі кроки полягали у виконанні арифметичних операцій і операцій відносини (перевірки рівності, нерівності і т.д.). Часто обчислення були громіздкими, а обчислення вручну - трудомісткими, але суть самого обчислювального процесу залишалася очевидною. У математиків не виникало потреба в усвідомленні і строгому визначенні поняття алгоритму, в його узагальненні. Але з розвитком математики з'являлися нові об'єкти, якими доводилося оперувати: вектори, графи, матриці, безлічі і ін. Як визначити для них однозначність або як встановити кінцівку алгоритму, які кроки вважати елементарними? У 1920-х завдання точного визначення поняття алгоритму стала однією з центральних проблем математики. У той час існувало дві точки зору на математичні проблеми:
Всі проблеми алгоритмічно розв'язні, але для деяких алгоритм ще не знайдений, оскільки ще не розвинені відповідні розділи математики.
Є проблеми, для яких алгоритм взагалі не може існувати.
Ідея про існування алгоритмічно нерозв'язних проблем виявилася вірною, але для того, щоб її обґрунтувати, необхідно було дати точне визначення алгоритму. Спроби виробити таке визначення привели до виникнення теорії алгоритмів, до якої ввійшли праці багатьох відомих математиків - К.Гедель. К.Черч, С.Кліні, А. Тьюрінг. Е.Пост, А.Марков, А.Колмогоров і багато інших.
Точне визначення поняття алгоритму дало можливість довести алгоритмічну нерозв'язність багатьох математичних проблем.
Поява перших проектів обчислювальних машин стимулювало дослідження можливостей практичного застосування алгоритмів, використання яких, з огляду на їх трудомісткості, було раніше недоступне. Подальший процес розвитку обчислювальної техніки визначив розвиток теоретичних і прикладних аспектів вивчення алгоритмів.
Поняття «алгоритму».
У повсякденному житті кожна людина стикається з необхідністю вирішення завдань самої різної складності. Деякі з них важкі і вимагають тривалих роздумів для пошуку рішень (а іноді його так і не вдається знайти), інші ж, навпаки, настільки прості і звичні, що вирішуються автоматично. При цьому виконання навіть найпростішої завдання здійснюється в кілька послідовних етапів (кроків). У вигляді послідовності кроків можна описати процес вирішення багатьох завдань, відомих зі шкільного курсу математики: приведення дробів до спільного знаменника, рішення системи лінійних рівнянь шляхом послідовного виключення невідомих, побудова трикутника за трьома сторонами за допомогою циркуля і лінійки і т.д. Така послідовність кроків у вирішенні завдання називається алгоритмом. Кожне окреме дію - це крок алгоритму. Послідовність кроків алгоритму строго фіксована, тобто кроки повинні бути впорядкованими. Правда, існують паралельні алгоритми, для яких ця вимога не дотримується.
Поняття алгоритму близько до інших понять, таким, як метод (метод Гаусса рішення систем лінійних рівнянь), спосіб (спосіб побудови трикутника за трьома сторонами за допомогою циркуля і лінійки). Можна сформулювати основні особливості саме алгоритмів.
Наявність вихідних даних і деякого результату.
Алгоритм - це точно певна інструкція, послідовно застосовуючи яку до вихідних даних, можна отримати рішення задачі. Для кожного алгоритму є деякий безліч об'єктів, допустимих в якості вихідних даних. Наприклад, в алгоритмі розподілу дійсних чисел ділене може бути будь-яким, а дільник не може бути дорівнює нулю.
Масовість, тобто можливість застосовувати багаторазово один і той же алгоритм. Алгоритм служить, як правило, для вирішення не однієї конкретної задачі, а деякого класу задач. Так алгоритм складання застосуємо до будь-якої парі натуральних чисел.
Детермінованість.
При застосуванні алгоритму до одних і тих же вихідних даних повинен виходити завжди один і той же результат, тому, наприклад, процес перетворення інформації, в якому бере участь кидання монети, не є детермінованим і не може бути названий алгоритмом.
Результативність.
Виконання алгоритму повинно обов'язково приводити до його завершення. У той же час можна навести приклади формально нескінченних алгоритмів, широко застосовуваних на практиці. Наприклад, алгоритм роботи системи збору метеорологічних даних складається в безперервному повторенні послідовності дій ( «виміряти температуру повітря», «визначити атмосферний тиск»), які виконуються з певною частотою (через хвилину, годину) в усі час існування даної системи.
Визначеність.
На кожному кроці алгоритму у виконавця має бути достатньо інформації, щоб його виконати. Крім того, виконавцю потрібно чітко знати, яким чином він виконується. Кроки інструкції повинні бути досить простими, елементарними, а виконавець повинен однозначно розуміти сенс кожного кроку послідовності дій, що становлять алгоритм (при обчисленні площі прямокутника будь-якому виконавцеві потрібно вміти множити і трактувати знак «x» саме як множення). Тому питання про вибір форми подання алгоритму дуже важливий. Фактично мова йде про те, якою мовою записаний алгоритм.
Форми подання алгоритмів.
Для запису алгоритмів необхідний деякий мову, при цьому дуже важливо, яка саме мова обраний. Записувати алгоритми російською мовою (або будь-якому іншому природному мовою) громіздко і незручно.
Наприклад, опис алгоритму Евкліда знаходження НСД (найбільшого загального дільника) двох цілих позитивних чисел може бути представлено у вигляді трьох кроків. Крок 1: Розділити m на n. Нехай p - залишок від ділення.
Крок 2: Якщо p дорівнює нулю, то n і є вихідний НСД.
Крок 3: Якщо p не дорівнює нулю, то зробимо m рівним n. а n рівним p. Повернутися до кроку 1.