Теорія алгоритмів () — окремий розділ математики, що вивчає загальні властивості алгоритмів. Виникла в 30-х роках XX століття.
Алгоритми, проте, простежуються в математиці протягом усього часу її існування. Необхідність точного математичного уточнення інтуїтивного поняття алгоритму стала неминучою після усвідомлення неможливості існування алгоритмів розв'язку багатьох масових проблем, в першу чергу пов'язаних з арифметикою та математичною логікою (проблеми істинності арифметичних формул та формул першопорядкового числення предикатів, 10-та проблема Гільберта про розв'язність діофантових рівнянь та ін.). Для доведення неіснування алгоритму треба мати його точне математичне визначення, тому після сформування поняття алгоритму як нової та окремої сутності першочерговою стала проблема знаходження адекватних формальних моделей алгоритму та дослідження їх властивостей. При цьому формальні моделі були запропоновані як для первісного поняття алгоритму, так і для похідного поняття алгоритмічно обчислюваної функції.
Історія розвитку Вперше поняття алгоритму з'явилося в працях Е. Бореля (1912) та Г. Вейля (1921).
Першими формальними моделями алгоритмічно обчислюваних функцій були λ-означувані функції (Алонзо Черч, 1932) та загальнорекурсивні функції (Курт Гедель, 1934). Вказані класи визначались як функції, графіки яких породжуються відповідно численням λ-конверсій та численням Ербрана-Геделя. В 1936 році Стівен Коул Кліні поширив поняття загальнорекурсивної функції на випадок часткових функцій, ввівши поняття частково рекурсивної функції, та описав клас таких функцій в чисто функціональних термінах. В 1943 році Еміль Пост запропонував модель обчислюваних функцій на основі введеного ним числення спеціального вигляду (канонічних систем).
Для формалізації самого поняття алгоритму були запропоновані точні математичні описи алгоритмічної машини та обчислюваності на ній. Першою формальною моделлю алгоритмічної машини була машина Тюрінга (Алан Тюрінг, Еміль Пост, 1936). З пізніших моделей відзначимо нормальні алгоритми (А. Марков, 1952) та регістрові машини (Д. Шепердсон, Г. Стерджіс, 1963).
В 1936 р. А. Черч та С. Кліні довели збіг класів загально-рекурсивних та λ-означуваних функцій. На основі цього факту й аналізу ідей, які привели до вказаних понять, А. Черч висунув тезу про збіг класу АОФ з класом загальнорекурсивних функцій. С. Кліні узагальнив цю тезу для випадку часткових функцій. Доведений А. Тюрінгом в 1937 р. збіг класів частково рекурсивних функцій та функцій, обчислюваних на машинах Тюрінга, став ще одним підтвердженням тези Черча. Пізніше такі збіги були встановлені для всіх відомих формальних моделей АОФ. Тому є всі підстави вважати, що кожна із названих вище формальних моделей адекватно уточнює інтуїтивне поняття АОФ.
Теорія алгоритмів виникла як розділ математичної логіки, поняття алгоритму тісно пов'язане з поняттям числення. Перші та найчисельніші застосування теорія алгоритмів має саме в математичній логіці. Теорія алгоритмів є теоретичним фундаментом програмування, вона має застосування всюди, де зустрічаються алгоритмічні проблеми (основи математики, теорія інформації, теорія керування, конструктивний аналіз, обчислювальна математика, теорія ймовірності, лінгвістика, економіка та ін.).
Основні поняття теорії алгоритмів
Областю застосовності алгоритму називається сукупність тих об'єктів, до яких його можна застосувати, тобто в застосуванні до яких він дає результат. Про алгоритм U кажуть, що він: 1) «обчислює функцію f», коли його область застосування збігається з областю визначення f, і U перетворює будь-який х зі своєї області застосування в f(х); 2) «розв'язує множину A відносно множини X», коли він застосовується до будь-якого х з X, і перетворює будь-який х з X∩A на слово «так», а будь-який х з Х\А — на слово «ні»; 3) «перераховує множину B», коли його область застосування є натуральний ряд, а сукупність результатів є B. Функція наз. обчислюваною, якщо існує алгоритм, що її обчислює. Множина називається розв'язною відносно X, якщо існує алгоритм, що розв'язує її відносно X. Множина наз. перераховуваною, якщо або вона порожня, або існує перераховуючий її алгоритм.
Детальний аналіз поняття «алгоритм» виявляє, що (I) область можливих вихідних даних і область застосовності будь-якого алгоритму є перераховуваними множинами. Своєю чергою, (II) для будь-якої пари вкладених одна в одну перераховуваних множин можна підібрати алгоритм, у якого більша множина слугує областю можливих вихідних даних, а менша — областю застосовності. Мають місце такі основні теореми: (III) функція f обчислювана тоді й тільки тоді, коли перераховуваний її графік, тобто множина всіх пар вигляду <х, f(x)>. (IV) Підмножина А перераховуваної множини X тоді і тільки тоді розв'язна відносно X, коли А і X\A перераховувані. (V) Якщо А і В перераховувані, то A об'єднати B і A∩B також перераховувані. (VI) У кожній нескінченній перераховуваній множині X існує перераховувана підмножина з неперераховуваним доповненням (в силу (IV) ця перераховувана підмножина буде нерозв'язною відносно X). (VII) Для кожної нескінченної перераховуваної множини X існує обчислювана функція, визначена на підмножині цієї множини і яка не продовжувана до обчислюваної функції, визначеної на всій X. Твердження (VI) і (II) в сукупності дають приклад алгоритму з нерозв'язною областю застосовуваності.
Розв'язні і перераховувані множини складають найпростіші (і найважливіші) приклади множин, структура яких задається за допомогою тих чи тих алгоритмічних процедур. Систематичне вивчення множин конструктивних об'єктів з точки зору таких властивостей цих множин, які зв'язані з наявністю тих чи інших алгоритмів, утворює так звану алгоритмічну теорію множин.
Теорію алгоритмів можна розділити на дескриптивну (якісну) і метричну (кількісну). Перша досліджує алгоритми з точки зору встановлюваної ними відповідності між вихідними даними та результатами; до неї належать, зокрема, проблеми побудови алгоритму, що йому властиві ті чи інші властивості,— алгоритмічні проблеми. Друга досліджує алгоритми з точки зору складності як самих алгоритмів, так і обчислень, що ними задаються, тобто процесів послідовного перетворення конструктивних об'єктів (див. Складність алгоритму). Важливо підкреслити, що як складність алгоритмів, так і складність обчислень можуть визначатися різними способами. Розробка методів оцінки складності алгоритмів і обчислень має важливе теоретичне і практичне значення.
Формалізація поняття алгоритму
Серед інших поширених математичних моделей алгоритмів можна назвати:
Мережі Петрі описані Карлом Петрі в 1962 роціPetri, C. (1962). Kommunikation mit Automaten, Ph.D. Dissertation, University of Bonn, Bonn, Germany., як і машини Тюрінга, мають різні форми — звичайні та з обмеженнями, регулярні, вільні, розфарбованіZervos, C. (1977). Colored Petri Nets: Their Properties and Applications, Technical Report 107, System Engineering Laboratory, University of Michigan, Ann Arbor, Michigan., само-змінювані, тощоValk, R. (1978). Self-Modifying Nets — A Natural Extension of Petri Nets, in Automata, Languages, and Programming, Lecture Notes in Computer Science, 62, Springer-Verlag, New York, Berlin. Векторні машини, запропоновані Праттом, Рабіном, Стокмаєром в 1974 роціV. Pratt, M. Rabin, L. Stockmeyer, A charaterization of the power of vector machines, Proc. SToC 74, pp. 122—134. Нейронні мережі, найпростіші моделі з'явились в 1943 р. з появою статті нейрофізіолога Уоррена Маккалоха і математика Волтера Піттса. Подібно до машини Тюрінга існує кілька різновидів: зі сталими вагами, з керованим та некерованим навчанням, з прямим поширенням або рекурентніMcCulloch, W.S. and Pitts, E. (1943). A logical calculus of the ideas immanent in nervous activity, Bulletin of Mathematical Biophysics, v. 5, pp. 115—133. Автомат фон Неймана та загальні клітинні автоматиvon Neumann, J. (1966). Theory of Self-Reproducing Automata, 1949 University of Illinois Lectures on the Theory and Organization of Complicated Automata, edited and completed by Arthur W. Burks. Urbana, University of Illinois Press.. Запропоноване Колмогоровим визначення алгоритму в 1953 роціKolmogorov, A.N. (1953). On the concept of algorithm, Russian Mathematical Surveys, v. 8, no. 4, pp. 175—176.1958 г. июль—август т. XIII, вып. 4 (82) УСПЕХИ МАТЕМАТИЧЕСКИХ НАУК. К ОПРЕДЕЛЕНИЮ АЛГОРИТМА А. Н. Колмогоров и В. А. Успенский http://lpcs.math.msu.su/~uspensky/bib/Uspensky_1958_UMN_Kolmogorov_Opredelenie_algoritma.pdf Скінченні автомати, перші праці про які зазвичай приписують Маккалоху і Піттсу, праці з формальним описом структури були написані МіліMealy, G.H. (1953). A method for synthesizing sequential circuits, Bell System Techn. J., v. 34, pp. 1045—1079., Стівеном КлініKleene, S.C. (1956). Representation of events in nerve nets, Automata Studies, Princeton University Press, Princeton, NJ, pp. 3–41. та МуромMoore, E.F. (1956). Gedanken-experiments on sequential machines, in Automata Studies, Princeton University Press, Princeton, NJ, pp. 129—153.. Подібно до машин Тюрінга скінченні автомати також мають низку різновидів: без пам'яті, автономні, без виведення або приймальні автомати, детерміновані та недетермінованіRabin, M.O. and Scott, D. (1959). Finite automata and their decision problems, IBM Journal of Research and Development, v. 3, pp. 114—125., стохастичні автомати, тощо. Машина Мінського запропонована Марвіном Мінським в 1967 році. зі змінюваною пам'яттю, або так звані «машини Шенхаге», запропоновані в 1980 роціShönhage, A. (1980). Storage modification machines, SIAM Journal on Computing, v. o 9, pp. 490—508. . рівнодоступна адресна машина (РАМ), запропоновані Шефердсоном та Старгісом в 1963 роціShepherdson, J.C. and Sturgis, H.E. (1963). Computability of recursive functions, Journal of the ACM, v. 10, no. 2, pp. 217—255. з варіантами — рівнодоступна адресна машина з програмою, що зберігається (РАСП), запропоновані Елготом і Робінсоном в 1964 роціElgot, C.C. and Robinson, A. (1964). Random-access stored-program machines, an approach to programming languages, J. Assoc. Comput. Mach., 11, pp. 365—399.; паралельні рівнодоступні машини (ПРАМ); Машини обробки масивів описані Льовеном та Відерманом в 1985 роціVan Leeuwen, J. and Wiedermann, J. (1985). Array Processing Machines, in Fundamentals of Computation Theory, Lecture Notes in Computer Science, 199, Springer-Verlag, New York, Berlin, pp. 99–113. ; Багатовимірна модель обчислень та обчислювальних систем розроблена М. С. Бургіним та А. Ю. КарасікомБургин М.С, А. Ю. Карасик. Исследование одной абстрактной модели вычислительных систем // Программирование. — 1975. — № 1. — С. 72–82. http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=at&paperid=8035&option_lang=rus Burgin, M. and Karasik, A. (1976). Operators of multidimensional structured model of parallel computations, Automation and Remote Control, v. 37, no. 8, pp. 1295—1300.. Систолічний масив запропонований Кунгом та Лейсерсоном в 1978 роціKung, H.T. and Leiserson, C.E. (1979). Systolic arrays (for VLSI), in Sparse Matrix Proc. (Society for Industrial and Applied Mathematics), pp. 256—282.. Машини, що змінюють апаратне забезпечення, описані Даймондом та Куком в 1989 роціDymond, P.W. and Cook, S.A. (1989). Complexity theory of parallel time and hardware, Information and Computation, v. 80, pp. 205—226. Числення Поста запропоноване Емілем Постом в 1943 роціEmil Post, «Formal Reductions of the General Combinatorial Decision Problem» American Journal of Mathematics 65 (2): 197—215, 1943.. Нормальні алгоритми Маркова, запропоновані А. Марковим в 1954 роціА. А. Марков, «Теория алгорифмов», Тр. МИАН СССР, 42, Изд-во АН СССР, М.–Л., 1954, 3–375 http://mi.mathnet.ru/tm1178