ПОНЯТТЯ алгоритм є основним для всієї галузі комп'ютерного програмування, тому розпочати ми повинні з ретельного аналізу цього терміну.
Д. Кнут, Мистецтво програмування
Книга 1. Основні алгоритми
1.1. АЛГОРИТМИ
ПОНЯТТЯ алгоритм є основним для всієї галузі комп'ютерного програмування, тому розпочати ми повинні з ретельного аналізу цього терміну. Слово "алгоритм" (algorithm) (іноді використовується застаріле слово "алгорифм" .- Прим. Перекл.) вже саме по собі представляє великий інтерес. На перший погляд може здатися, ніби хтось збирався написати слово "логарифм" (logarithm), але випадково переставив перші чотири літери. Цього слова ще не було у виданні словника Webster's New World Dictionary, що вийшов у 1957 році. Ми знаходимо там тільки застарілу форму "algorism" - старовинне слово, яке означає "виконання арифметичних дій за допомогою арабських цифр". В середньовіччя абакісти рахували на абаках (лічильних дошках), а алгоритміки використовували "algorism". В епоху Відродження походження цього слова виявилося забутим.
...
Поступово форма і значення слова algorism спотворилася; як пояснюється в словнику Oxford English Dictionary, це слово "зазнало безліч псевдоетімологіческіх спотворень, включаючи останній варіант algorithm, де сталася плутанина" з коренем слова грецького походження arithmetic. Цей перехід від "algorism" до "algorithm" здається цілком закономірним з огляду на те, що походження розглянутого слова було повністю забуте. У старовинному німецькому математичному словнику Vollständiges mathematisches Lexicon (Leipzig, 1747) дається таке визначення слова algorithmus: "Цей термін містить у собі поняття про чотири типи арифметичних операцій, а саме: про складання, множення, віднімання і ділення". Латинський вираз algorithmus infinitesimalis у той час використовувався для визначення "способів виконання дій з нескінченно малими величинами, відкритих Лейбніцем (Leibniz)".
Упритул до 1950 року слово "алгоритм" найчастіше асоціювалося з алгоритмом Евкліда, який являє собою процес знаходження найбільшого загального дільника двох чисел. Цей алгоритм наведений у книзі Евкліда (Euclid) “Початки” (книга 7, речення 1 і 2). Думаю, має сенс навести тут опис цього алгоритму.
Алгоритм Е (Алгоритм Евкліда). Дано два цілих позитивних числа m і n. Потрібно знайти їх найбільший спільний дільник, тобто найбільше ціле позитивне число, яке без остачі ділить обидва числа m і n.
E1. [Знаходження залишку.] Поділимо m на n, і нехай залишок від ділення буде
дорівнює р (де 0 <= р < n).
Е2. [Порівняння з нулем.] Якщо р = 0, то виконання алгоритму припиняється; n -
шукане значення.
ЕЗ. [Заміщення.] Присвоїти m ← n, n ← r і повернутися до кроку E1.
Звісно, у Евкліда цей алгоритм сформульовано не зовсім так. Наведене вище формулювання ілюструє стиль, в якому алгоритми будуть представлені протягом всієї цієї книги.
кожному розглянутого алгоритму присвоюється літера-ідентифікатор (у попередньому прикладі використовувалася літера Е), а крокам алгоритму — ця сама буква в поєднанні з числом (El, E2, ЕЗ).
Продовження
До цих пір наше обговорення алгоритмів носило досить загальний характер, і, ймовірно, "математично налаштований" читач утвердився в думці, що всі попередні коментарі представляють собою дуже хиткий фундамент для побудови будь-якої теорії алгоритмів.Тому давайте підіб'ємо підсумок даного розділу, коротко описавши метод, за допомогою якого поняття алгоритму можна строго обгрунтувати в термінах математичної теорії множин.
На практиці нам потрібні не просто алгоритми, а хороші алгоритми в широкому сенсі цього слова. Одним з критеріїв якості алгоритму є час, необхідний для його виконання; дану характеристику можна оцінити по тому, скільки разів виконується кожен крок. Іншими критеріями є адаптованість алгоритму до різних комп'ютерів, його простота, витонченість і т. д.
Досі ми говорили про форму запису алгоритмів, а тепер давайте спробуємо виконати один з них. Хочу відразу зауважити, що читачеві не слід розраховувати на те, що алгоритми можна читати, як роман.Таке читання приведе до того, що вам буде важко зрозуміти, що ж насправді відбувається при виконанні алгоритму. Для перевірки алгоритму, в ньому треба розібратися, і кращий спосіб зрозуміти, як він працює, - випробувати його.
ПОНЯТТЯ алгоритм є основним для всієї галузі комп'ютерного програмування, тому розпочати ми повинні з ретельного аналізу цього терміну.
Фундаментальна монографія відомого американського математика і фахівця в галузі комп'ютерних наук Дональда Кнута, присвячена розгляду та аналізу найважливіших алгоритмів, що використовуються в інформатиці. У 1999 році книга була визнана однією з дванадцяти кращих фізико-математичних монографій століття