Теорія алгоритмів - Life-Prog
Теорія алгоритмів (англ. Theory of computation) як окремий розділ математики, що вивчає загальні властивості алгоритмів, виникла в 30-х роках 20 століття. Алгоритми, проте, простежуються в математиці протягом усього її існування. Необхідність точного математичного уточнення інтуїтивного поняття алгоритму стала неминучою після усвідомлення неможливості існування алгоритмів вирішення багатьох масових проблем, в першу чергу пов'язаних з арифметикою та математичною логікою (проблеми істинності арифметичних формул і формул першопорядкового обчислення предикатів, 10-я проблема у .).. Для доказу неіснування алгоритму треба мати його точне математичне визначення, тому після сформування поняття алгоритму як нової та окремої сутності першочергової стала проблема знаходження адекватних формальних моделей алгоритму та дослідження їх властивостей. У цьому формальні моделі було запропоновано як початкового поняття алгоритму, так похідного поняття алгоритмічно обчислюваної функції.
Історія розвитку теорії алгоритмів
Вперше поняття алгоритму з'явилося у працях Є. Бореля (1912) та Г. Вейля (1921).
Першими формальними моделями алгоритмічно обчислюваних функцій були - функції ( Алонзо Черч, 1932) і загальнорекурсивні функції ( Курт Гедель, 1934). Зазначені класи визначалися як функції, графіки яких породжуються відповідно обчисленням-конверсій та обчисленням Ербрана-Геделя. В 1936 Стівен Коул Кліні поширив поняття загальнорекурсивної функції на випадок часткових функцій, ввівши поняття частково рекурсивної функції, і описав клас таких функцій в суто функціональних термінах. У 1943 році Еміль Постзапропонував модель обчислюваних функцій на основі введеного ним обчислення спеціального виду (канонічних систем).
Для формалізації самого поняття алгоритму було запропоновано точні математичні описи алгоритмічної машини та обчислюваності у ньому. Першою формальною моделлю алгоритмічної машини була машина Тьюринга (Алан Т'юрінг, Еміль Пост, 1936). З пізніших моделей відзначимо нормальні алгоритми (А. Марков, І952) та регістрові машини (Д. Шепердсон, Г. Стерджіс, 1963).
У 1936 р. А. Черч і С. Кліні довели збіг класів загальноосвітніх рекурсивних і -означених функцій. На основі цього факту та аналізу ідей, що призвели до зазначених понять, А. Черч висунув тезу про збіг класу АОФ із класом загальнорекурсивних функцій. С. Кліні узагальнив цю тезу для випадку часткових функцій. Доведено А. Т'юрінгом в 1937 р. збіг класів частково рекурсивних функцій і функцій, що обчислюються на машинах Т'юрінга, стало ще одним підтвердженням тези Черча. Пізніше такі збіги були встановлені всім відомих формальних моделей АОФ. Тому є підстави вважати, кожна з названих вище формальних моделей адекватно уточнює інтуїтивне поняття АОФ.
Теорія алгоритмів виникла як розділ математичної логіки, поняття алгоритму був із поняттям обчислення. Перші та найчисленніші застосування теорія алгоритмів має саме в математичній логіці. Теорія алгоритмів є теоретичним фундаментом програмування, має застосування скрізь, де зустрічаються алгоритмічні проблеми (основи математики, теорія інформації, теорія управління, конструктивний аналіз, обчислювальна математика, теорія ймовірності, лінгвістика, економіка та інших.).
Основні поняття теорії алгоритмів
Областюзастосовності алгоритму називається сукупність тих об'єктів, яких його можна застосувати, тобто у застосуванні яких він дає результат. Про алгоритм U говорять, що він: 1) « обчислює функцію f », коли його сфера застосування збігається з областю визначення f, і U перетворює будь-який х зі своєї області застосування в f (х), 2) « вирішує безліч A щодо множини X », коли він застосовується до будь-якого х з X, і перетворює будь-який х з X A на слово «так», а будь-яке х з Х \ А - на слово «ні», 3) «перераховує безліч B », коли його сфера застосування є натуральний ряд, а сукупність результатів є B. Функція зв. обчислюваної, якщо є алгоритм, її обчислює. Безліч називається розв'язною щодо X, якщо існує алгоритм, який вирішує її щодо X. Множина зв.перелічуваних, якщо або вона порожня, або існує перераховуючи її алгоритм.
Детальний аналіз поняття «алгоритм» виявляє, що (I) область можливих вихідних даних і область застосування будь-якого алгоритму є перелічуваними множинами. У свою чергу, (II) для будь-якої пари вкладених одна в одну множин, що перераховуються, можна підібрати алгоритм, у якого велика кількість служить областю можливих вихідних даних, а менше - областю застосовності. Мають місце такі основні теореми: (III) функція f обчислюється тоді і тільки тоді, коли перераховуються її графік, тобто безліч усіх пар виду . (IV) Підмножина А перелічуваних множини X тоді і тільки тоді можна розв'язати щодо X, коли А і X \ A перераховані. (V) Якщо А та В перераховані, то A об'єднати B і A B також перераховані. (VI) У кожному нескінченному перелічуваному множині X існує перелічуване підмножина з неперелічуваним доповненням (в силу (IV) ця перемножувана підмножина буденерозв'язним щодо X). (VII) Для кожної нескінченної перелічуваної множини X існує функція, що обчислюється, визначена на підмножині цієї множини і яка не триває до обчислюваної функції, визначеної на всій X. Твердження (VI) і (II) в сукупності дають приклад алгоритму з нерозв'язною областю застосовності.
Дозволені та перераховані множини складають найпростіші (і важливі) приклади множин, структура яких задається за допомогою тих чи інших алгоритмічних процедур. Систематичне вивчення множин конструктивних об'єктів з погляду таких властивостей цих множин, пов'язані з наявністю тих чи інших алгоритмів, утворює так звану алгоритмічну теорію множин.
Теорію алгоритмів можна розділити на дескриптивну (якісну) та метричну (кількісну). Перша досліджує алгоритми з погляду встановлюваної ними відповідності між вихідними даними та результатами; до неї відносяться, зокрема, проблеми побудови алгоритму, що притаманні ті чи інші властивості, - алгоритмічні проблеми. Друга досліджує алгоритми з погляду складності як самих алгоритмів, і обчислень, якими задаються, тобто. процесів послідовного перетворення конструктивних об'єктів (див. складності алгоритму). Важливо підкреслити, що складність алгоритмів, і складність обчислень можуть визначатися різними способами. Розробка методів оцінки складності алгоритмів та обчислень має важливе теоретичне та практичне значення.
Застосування теорії алгоритмів
У всіх галузях математики, у яких трапляються алгоритмічні проблеми. Такі проблеми виникають практично у всіх розділах математики. У математичній логіці для кожної теорії формулюється проблема розв'язання безлічі всіх істиннихабо довідкові твердження цієї теорії щодо безлічі всіх її пропозицій (теорії поділяються на розв'язні та нерозв'язні залежно від розв'язності або нерозв'язності зазначеної проблеми); в 1936 А. Черч встановив нерозв'язність проблеми розв'язності для безлічі всіх справжніх пропозицій логіки предикатів, подальші важливі результати в цьому напрямку належать А.Тарському, А. І. Мальцеву та ін. зокрема, для груп: перші приклади напівгруп з нерозв'язною проблемою тотожності були винайдені в 1947 р. незалежно А. А. Марковим та Е. Постом, а приклад групи з нерозв'язною проблемою тотожності - у 1952 р. П. С. Новіковим); у топології (проблема гомеоморфії, нерозв'язність якої для важливого класу випадків була доведена у 1958 р. А. А. Марковим); у теорії чисел (проблема розв'язання діофантових рівнянь, нерозв'язність якого була встановлена в 1970 р. Ю. В. Матіясевичем) та в ін. розділах математики.
Теорія алгоритмів тісно пов'язана: 1) з математичною логікою, оскільки в термінах алгоритмів може бути викладено одне з центральних понять математичної логіки - поняття обчислення (і тому, напр., Геделя теорема про неповноту формальних систем може бути отримана як наслідок теорем А. т.) 2) з основами математики, в яких одне з центральних місць займає проблема співвідношення конструктивного та неконструктивного (зокрема, А. т. дає апарат, необхідний для розробки конструктивного спрямування в математиці) ; в 1965 р. А. Н. Колмогоров запропонував використовувати А. т. для обґрунтування теорії інформації, 3) з кібернетикою, в якій важливе місце займає вивчення алгоритмів управління. А. т. утворює теоретичнийфундамент для низки питань обчислювальної математики