До цих пір наше обговорення алгоритмів носило досить загальний характер, і, ймовірно, "математично налаштований" читач утвердився в думці, що всі попередні коментарі представляють собою дуже хиткий фундамент для побудови будь-якої теорії алгоритмів.Тому давайте підіб'ємо підсумок даного розділу, коротко описавши метод, за допомогою якого поняття алгоритму можна строго обгрунтувати в термінах математичної теорії множин.
Д. Кнут, Мистецтво програмування
Книга 1. Основні алгоритми
1.1. АЛГОРИТМИ
Попередня публікація
...
До цих пір наше обговорення алгоритмів носило досить загальний характер, і, ймовірно, "математично налаштований" читач утвердився в думці, що всі попередні коментарі представляють собою дуже хиткий фундамент для побудови будь-якої теорії алгоритмів.Тому давайте підіб'ємо підсумок даного розділу, коротко описавши метод, за допомогою якого поняття алгоритму можна строго обгрунтувати в термінах математичної теорії множин.Формально визначимо метод обчислень як четвірку (Q, I, Ω, f), де Q - це множина, що містить підмножини I і Ω, а f - функція, що переводить множину Q в себе. Крім того, f залишає нерухомими точки множини Ω, тобто f(q) дорівнює q для всіх елементів q з множини Ω. Ці чотири елемента, Q, Ι, Ω, f, представляють відповідно стан обчислення, ввід, вивід і правило обчислень. Кожне вхідне значення x з множини I визначає обчислювану послідовність χ0, x1, x2, ... наступним чином:
х0 = x і xk +1 = f (xk) для k >= 0 (1)
Кажуть, що обчислювана послідовність закінчується через k кроків, якщо k - це найменше ціле число, для якого хk належить Ω, і що вона дає вихідне значення xk для заданого х.(Зауважимо, що якщо xk належить Ω, то й xk+1 належить Ω, оскільки в цьому випадку xk+1 = xk) Деякі обчислювані послідовності можуть ніколи не закінчуватися, але алгоритм - це метод обчислень, який закінчується через кінцеве число кроків для всіх x з I.
Наприклад, алгоритм Ε в цих термінах можна формалізувати наступним чином. Нехай елементами множини Q будуть всі величини (n), всі впорядковані пари (m, n) і всі впорядковані четвірки (m, n, r, 1), (m, n, r, 2) та (m, n, p, 3), де m, n і p - це цілі позитивні числа, а r - невід'ємне ціле число. Нехай I - це підмножина всіх пар (m, n), а Ω - підмножина всіх величин (n). Визначимо функцію f наступним чином:
f ((m, n)) = (m, n, 0, l);
f ((n)) = (n);
f ((m, n, r, 1)) = (m, n, залишок від ділення m на n, 2);
f ((m, n, r, 2)) = (n), якщо r = 0, (m, n, r, 3) в протилежному випадку;
f ((m, n, p, 3)) = (n, p, p, 1).
Відповідність між даною записом і алгоритмом Ε очевидна.
У цьому формулюванні поняття "алгоритм" не міститься обмеження, що стосується ефективності, про який згадувалося раніше. Наприклад, Q може бути множиною нескінченних послідовностей, які не можна обчислити за допомогою олівця та паперу, а f може включати операції, які простий смертний зможе виконати не завжди.
Продовження далі..
До цих пір наше обговорення алгоритмів носило досить загальний характер, і, ймовірно, "математично налаштований" читач утвердився в думці, що всі попередні коментарі представляють собою дуже хиткий фундамент для побудови будь-якої теорії алгоритмів.Тому давайте підіб'ємо підсумок даного розділу, коротко описавши метод, за допомогою якого поняття алгоритму можна строго обгрунтувати в термінах математичної теорії множин.
На практиці нам потрібні не просто алгоритми, а хороші алгоритми в широкому сенсі цього слова. Одним з критеріїв якості алгоритму є час, необхідний для його виконання; дану характеристику можна оцінити по тому, скільки разів виконується кожен крок. Іншими критеріями є адаптованість алгоритму до різних комп'ютерів, його простота, витонченість і т. д.
Досі ми говорили про форму запису алгоритмів, а тепер давайте спробуємо виконати один з них. Хочу відразу зауважити, що читачеві не слід розраховувати на те, що алгоритми можна читати, як роман.Таке читання приведе до того, що вам буде важко зрозуміти, що ж насправді відбувається при виконанні алгоритму. Для перевірки алгоритму, в ньому треба розібратися, і кращий спосіб зрозуміти, як він працює, - випробувати його.
ПОНЯТТЯ алгоритм є основним для всієї галузі комп'ютерного програмування, тому розпочати ми повинні з ретельного аналізу цього терміну.
Фундаментальна монографія відомого американського математика і фахівця в галузі комп'ютерних наук Дональда Кнута, присвячена розгляду та аналізу найважливіших алгоритмів, що використовуються в інформатиці. У 1999 році книга була визнана однією з дванадцяти кращих фізико-математичних монографій століття