Алгоритм — це чітка послідовність дій, яка перетворює вхідні дані у результат. Це не набір випадкових команд, а продумана інструкція, яку можна виконати крок за кроком — людиною, машиною або механізмом. Простіше кажучи: алгоритм показує, як із даних отримати відповідь, і виконує це за суворими правилами.
Що таке алгоритм?
Алгоритм описує покрокову процедуру: бере вхід, обробляє і видає вихід. Він може бути записаний на природній мові, у вигляді псевдокоду або реалізований у програмі, але у будь-якому випадку залишається структурованим способом розв'язання задачі. Рецепт приготування, інструкція з збирання меблів та програма сортування — все це приклади алгоритмів.
Ключові властивості алгоритму:
- дискретність — алгоритм розбитий на окремі кроки, кожен з яких виконується за кінцевий час;
- детермінованість — за однакових вхідних даних алгоритм дає однаковий результат;
- зрозумілість — інструкції сформульовані так, щоб виконавець міг їх однозначно виконати;
- завершуваність — алгоритм повинен завершуватися за кінцеву кількість кроків;
- масовість — алгоритм застосовний до цілого класу однотипних задач;
- результативність — після виконання роботи алгоритм видає визначений результат.
Історія виникнення терміна "алгоритм"
Ідея покрокових обчислень існувала задовго до появи комп’ютерів: люди вміли виконувати арифметичні операції та знаходити найпоширеніші спільні дільники ще в давнину. Сам термін пов’язаний із ім’ям математика Мухаммада ибн Муси аль-Хорезмі. Близько 825 року він писав трактат, у якому систематично описав позиційну десяткову систему та використання нуля. Латинський переклад його праці у XII столітті отримав назву "Algoritmi de numero Indorum", і від латинітизованого імені автора походить слово "алгоритм".
У наступні століття поняття розширювалося: Лейбніц та Ейлер застосовували ідеї алгоритмічності до різних галузей математики, а з розвитком обчислювальної техніки у ХХ столітті алгоритми стали центральною темою інформатики.
Формалізація поняття алгоритму
У ХХ столітті математики сформували строгі моделі обчислень, які дозволили точно описати, що таке алгоритм і які функції обчислювані.
Машина Тюринга
Машина Тюрінга, запропонована у 1936 році, — абстрактна модель з безмежною стрічкою, головкою для читання та запису й набором правил переходу. На кожному кроці машина читає символ, змінює стан, записує символ і здвигає головку. Тезис Чорча–Тюринга стверджує, що все, що може бути обчислено алгоритмічно, можна реалізувати на машині Тюринга.
Рекурсивні функції
У 1930‑х роках вчені розробили теорію рекурсивних функцій: складні функції збудовуються з простих за допомогою обмеженого набору операцій. Тезис Чорча пов'язує цей підхід з обчислюваністю: частково рекурсивні функції збігаються з тими, що обчислюються машиною Тюринга.
Нормальні алгоритми Маркова
У 1950‑х Андрій Марков запропонував нормальні алгоритми — систему послідовних підстановок для перетворення символьних рядків. Вони показують, що алгоритми можна звести до правил заміни символів, що ще раз підтверджує універсальність формалізації.
Стохастичні алгоритми
Стохастичні алгоритми використовують випадковість: це корисно, коли детермінований шлях надто складний. Існують алгоритми типу Лас-Вегас, які завжди дають правильну відповідь, але час роботи варіюється, і алгоритми типу Монте‑Карло, які працюють швидше, але допускають невелику ймовірність помилки. На практиці найчастіше застосовуються псевдовипадкові числа, генеровані алгоритмічно.
Інші підходи до формалізації
Крім класичних моделей розвивалися багатоленточні та недетерміновані машини Тюрінга, регістрні машини, кінцеві та клітинні автомати — кожна модель підкреслює різні аспекти обчислюваності та складності.
Класифікація алгоритмів
Алгоритми розділяють за різними ознаками, що допомагає обрати відповідний метод для задачі:
- механічні алгоритми — кожен крок суворо визначений;
- гнучкі алгоритми — використовуються елементи випадковості або евристики;
- лінійні алгоритми — послідовність без розгалужень та повторень;
- розгалужені алгоритми — виконання залежить від умов;
- циклічні алгоритми — повторення дій до виконання умови;
- допоміжні алгоритми — модулі, що використовуються всередині більш обширних процедур.
.jpg)
Аналіз та ефективність алгоритмів
Коректність важлива, але без ефективності алгоритм практично не придатний до використання. Аналіз алгоритмів допомагає оцінити витрати часу й пам’яті та обрати оптимальний підхід для конкретних обсягів даних.
Час виконання та складність
Часова складність показує, як зростає час виконання при збільшенні обсягу вхідних даних n. Для опису асимптотичної поведінки використовується нотація O-велике. Вона не залежить від конкретної машини або реалізації, а відображає масштабованість алгоритму: O(n²) зростає квадратично, O(log n) — дуже повільно тощо.
| Складність | Коментар | Приклади |
|---|---|---|
| O(1) | Постійний час виконання не залежить від розміру задачі. | Очікуваний час пошуку в хеш‑таблиці. |
| O(log log n) | Дуже повільне зростання потрібного часу. | Очікуваний час роботи інтерпольованого пошуку по n елементів. |
| O(log n) | Логарифмічне зростання — збільшення розміру задачі вдвічі збільшує час роботи на постійну величину. | Обчислення x^n; двійковий пошук у масиві з n елементів. |
| O(n) | Лінійний ріст — збільшення розміру задачі вдвічі збільшить і необхідний час. | Додавання/віднімання чисел із n цифр; лінійний пошук у масиві з n елементів. |
| O(n log n) | Лінійно‑логарифмічне зростання — збільшення розміру задачі вдвічі збільшує час виконання трохи більш ніж удвічі. | Сортування злиттям або за допомогою купи n елементів; нижня межа сортування порівнянням n елементів. |
| O(n²) | Квадратичне зростання — збільшення розміру задачі вдвічі збільшує час у чотири рази. | Елементарні алгоритми сортування. |
| O(n³) | Кубічне зростання — збільшення розміру задачі вдвічі збільшує час у вісім разів. | Звичайне множення матриць. |
| O(c^n) | Експоненційне зростання — збільшення розміру задачі на 1 призводить до c‑кратного збільшення часу. | Деякі задачі теорії наборів, повний перебір. |
Алгоритмічно нерозв’язані задачі
Формалізація обчислень дозволила довести, що деякі завдання принципово нерозв’язні за алгоритмами. Класичний приклад — задача зупинки, сформульована Тюрінгом: неможливо побудувати універсальну процедуру, яка для будь-якої програми та її вхідних даних визначає, чи завершиться програма. Це обмеження лежить в основі теоретичної інформатики.
Представлення алгоритмів
Алгоритми зручніше й зрозуміліше представляти різними способами залежно від цілей та аудиторії:
- словесний опис — для швидкого переказу ідеї;
- алгоритмічні мови та псевдокод — для точного опису перед кодуванням;
- машинний код — низькоуровневий спосіб представлення для процесора;
- математична нотація — компактна для чисельних методів;
- схеми та блок‑схеми — наочне візуальне представлення логіки.
Алгоритм Євкліда
Алгоритм Євкліда — один із найдавніших та найпростіших способів знайти найбільший спільний дільник двох цілих чисел. Ідея проста: замінити більшу число на різницю з меншою та повторювати, доки одне з чисел не стане нулем. Доцільніше використовувати ділення із залишком.
Рекурсивний варіант у псевдокоді:
алг нод(a, b) початок якщо b = 0 повернути a інакше повернути нод(b, a mod b) кінець
Приклад обчислення НСД для 1599 та 650 за кроками:
- Крок 1 — 1599 = 650 * 2 + 299.
- Крок 2 — 650 = 299 * 2 + 52.
- Крок 3 — 299 = 52 * 5 + 39.
- Крок 4 — 52 = 39 * 1 + 13.
- Крок 5 — 39 = 13 * 3 + 0.
Коли залишок стає нулем, НСД дорівнює останньому ненульовому залишку, тобто 13. Цей приклад наочно демонструє кінцевість та результативність алгоритму.
