Алгоритмів теорія

Алгори́тмів тео́рія — розділ математики, що вивчає загальні властивості алгоритмів методом визначення та дослідження формальних моделей алгоритмів і алгоритмічно обчислюваних функцій. Теорія алгоритмів є теоретичним фундаментом програмування та інформатики. До завдань класичної алгоритмів теорії належать встановлення розв’язності чи нерозв’язності масових проблем, класифікація алгоритмів відповідно до їхньої складності, асимптотичний аналіз (див. Асимптота) складності алгоритмів та розробка критеріїв порівняльної оцінки їхньої якості.

Історична довідка

Обчислювальні процеси алгоритмічного характеру (арифметичні дії над цілими числами, знаходження найбільшого спільного дільника двох чисел тощо) відомі людству з глибокої давнини, проте в явному вигляді поняття алгоритму сформувалося лише на початку 20 ст. Необхідність уточнення поняття алгоритму постала після усвідомлення неможливості знайти єдиний спосіб розв’язання для низки проблем, пов’язаних, передовсім, з арифметикою та математичною логікою (проблеми істинності для арифметичних формул, для формул числення предикатів 1-го порядку, 10-а проблема Гільберта (див. Гільберта проблеми) про розв’язність діофантових рівнянь). Для доведення неіснування алгоритму потрібно мати його точне математичне визначення, тому після сформування поняття алгоритму як нової та окремої сутності першочерговим стало завдання створення адекватних формальних моделей алгоритму та дослідження їхніх властивостей. Це привело до виникнення теорії алгоритмів як окремого розділу математики.

Пошук формальних уточнень поняття алгоритму проводили в таких напрямах: • опис точного математичного поняття алгоритмічної машини та обчислюваності на ній (машини Тюрінґа, нормальні алгоритми Маркова (див. Марков, Андрій Андрійович (молодший), регістрові машини тощо); • опис певних класів функцій, для яких існує алгоритм знаходження значення функції за значеннями її аргументів, тобто уточнюється не первісне поняття алгоритму, а похідне поняття алгоритмічно обчислюваної функції (АОФ) (-означувані функції, рекурсивні та частково рекурсивні функції, програмовані функції; • ці класи часто визначали як функції, графіки яких породжені певним численням — численням Ербрана — Геделя (див. Ж. Ербран), системою Поста тощо).

У 1936 А. Чорч висунув тезу про збіг класу тотальних АОФ з класом рекурсивних функцій, а С. Кліні узагальнив її для випадку часткових функцій. Різним уточненням поняття алгоритму відповідає своє формулювання тези Чорча. Наприклад, теза Тюрінга стверджує збіжність класу АОФ з класом функцій, обчислюваних машинами Тюрінґа. Підтвердженням тези Чорча є збіг (з точністю до кодувань) класів функцій для всіх відомих формальних моделей алгоритму. Це означає, що кожна з таких моделей дає строге математичне уточнення інтуїтивного поняття АОФ.

Проблему побудови алгоритму, що має певні властивості, називають алгоритмічною проблемою. Це проблеми обчислюваності функції, розв’язності чи перелічності множини, алгоритмічної звідності. Прикладом нерозв’язної є проблема зупинки програми (машини Тюрінга): для довільних програми та вхідного даного встановити, зупиниться чи не зупиниться програма, під час роботи над цим даним. Доведення нерозв’язності проблеми істинності для формул числення предикатів (А. Чорч, 1936) було першим досягненням теорії алгоритмів. Подальші важливі результати в цьому напрямі належать А. Тарському, О. Мальцеву, С. Кліні. Установлено нерозв’язність проблем тотожності для напівгруп (Е. Пост, А. Марков, 1947) та груп (П. Новіков, 1952), 10-ї проблеми Гільберта про розв’язність діофантових рівнянь (Ю. Матіясевич, 1970). Проблеми алгоритмічної звідності вивчали, зокрема, А. Тюрінг, Е. Пост, С. Кліні, Х. Роджерс (США). Ефективні (обчислювані) операції (оператори (у математиці)) на функціях та множинах досліджували А. Тарський та С. Кліні. Фундаментальним твердженням щодо таких операторів є теорема Кліні про нерухому точку. Вона дає змогу задавати обчислювані функції через обчислювані оператори: опис оператора трактують як фінішне задання функції, яка є його нерухомою точкою. Це дало імпульс роботам Дж. Маккарті й Д. Скотта з математичної теорії обчислюваності. Спеціальними способами подання обчислюваних операторів є схеми програм (Ю. Янов (РФ), А. Єршов, Д. Скотт, В. Глушков). Роботи В. Глушкова зі структурованих схем програм започаткували теорію систем алгоритмічних алгебр. Важливим розділом теорії алгоритмів є автоматів теорія, фундаментальний унесок у її розвиток зробила вітчизняна наукова школа на чолі з В. Глушковим. Загальні властивості класів об’єктів, занумерованих певними конструктивними об’єктами (зазвичай натуральними числами) вивчає розділ теорії автоматів — теорія нумерацій. Ідея нумерації та дослідження властивостей нечислових об’єктів через властивості їхніх номерів запропонована К. Геделем і використана ним у доведенні теореми про неповноту. Далі теорію нумерацій розвивали С. Кліні, Е. Пост, О. Мальцев, Ю. Єршов. До класичних розділів теорії автоматів також додано дослідження недетермінованих, стохастичних і паралельних алгоритмів та обчислень. Узагальненням традиційної обчислюванoсті на натуральних числах є теорія обчислюваності на нескінченних ординалах (порядкових числах). На основі теорії алгоритмів уточнено (А. Колмогоров) поняття випадкової послідовності та кількості інформації.

Характеристика

Теорію алгоритмів поділяють на дескриптивну (якісну) і метричну (кількісну). Дескриптивна теорія алгоритмів досліджує алгоритми з погляду встановлюваної ними відповідності між вхідними і вихідними даними. Метрична теорія алгоритмів досліджує алгоритми з погляду складності як самих алгоритмів, так і заданих ними обчислень. Для дослідження складності обчислень найчастіше використовують багатострічкові машини Тюрінґа. З погляду обчислюваності важливими класами АОФ є P та NP. До класу P (класу NP) належать функції, обчислювані на детермінованій (недетермінованій) машині Тюрінга за поліноміально обмежений (від довжини вхідного даного) час. Задачі, пов’язані з функціями класу P, можна трактувати як практично розв’язні. Водночас багато задач у різних галузях математики й інформатики належать до класу NP. Значна увага приділяється вивченню методів отримання асимптотичних оцінок обсягу пам’яті чи часу виконання алгоритмів та розробці критеріїв порівняльної оцінки їхньої якості. Властивості оцінок складності, які не залежать від конкретних алгоритмічних моделей, досліджує інваріантна (машинно-незалежна) теорія складності обчислень (М. Блюм та ін.).

Застосування

Розвиток інформаційних технологій і програмування веде до розширення сфери застосування теорії алгоритмів. Методи й поняття теорії алгоритмів успішно використовують у всіх галузях науки, де трапляються алгоритмічні проблеми (основи математики, теорія інформації, теорія керування, обчислювальна математика, конструктивний аналіз, ймовірностей теорія, економіка, лінгвістика тощо). Стосовно практичних аспектів теорії алгоритмів важливою є тріада: розробник алгоритму, його виконавець та користувач. Вона є теоретичним підґрунтям для програмної інженерії, основним досягненням якої має бути максимальна автоматизація всіх процесів життєвого циклу програмного забезпечення.

Література

Мальцев А. И. Алгоритмы и рекурсивные функции. Москва : Наука, 1965. 394 с.
Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. Москва : Мир, 1972. 624 с.
Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра, языки, программирование. Киев : Наукова думка, 1974. 327 с.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. Москва : Мир, 1979. 536 с.
Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. Москва : Мир, 1983. 195 с.
Колмогоров А. Н. Теория информации и теория алгоритмов. Москва : Наука, 1987. 304 с.
Успенский В. А., Семенов А. Л. Теория алгоритмов: основные открытия и приложения. Москва : Наука, 1987. 288 с.
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. Москва : Вильямс, 2005. 1296 с.

Автор ВУЕ

М. С. Нікітченко

Покликання на цю статтю: Нікітченко М. С. Алгоритмів теорія // Велика українська енциклопедія. URL: https://vue.gov.ua/Алгоритмів теорія (дата звернення: 7.05.2024).