Перегляд вихідного коду сторінки Теорія алгоритмів

{{вичитати}}
'''Теорія алгоритмів''' ({{lang-en|Theory of computation}})&nbsp;— окремий розділ [[Математика|математики]], що вивчає загальні властивості [[алгоритм]]ів. Виникла в 30-х роках ХХ століття.

Алгоритми, проте, простежуються в [[Математика|математиці]] протягом всього часу її існування. Необхідність точного математичного уточнення інтуїтивного поняття алгоритму стала неминучою після усвідомлення неможливості існування алгоритмів розв'язку багатьох масових проблем, в першу чергу пов'язаних з [[арифметика|арифметикою]] та [[математична логіка|математичною логікою]] (проблеми істинності арифметичних формул та формул першопорядкового числення предикатів, 10-та проблема Гільберта про розв'язність [[діофантове рівняння|діофантових рівнянь]] та ін.). Для доведення неіснування алгоритму треба мати його точне математичне визначення, тому після сформування поняття алгоритму як нової та окремої сутності першочерговою стала проблема знаходження адекватних формальних моделей алгоритму та дослідження їх властивостей. При цьому формальні моделі були запропоновані як для первісного поняття алгоритму, так і для похідного поняття алгоритмічно обчислюваної функції.

== Історія розвитку ==
Вперше поняття алгоритму з'явилося в працях [[Борель Еміль|Е. Бореля]] (1912) та [[Вейль Герман|Г. Вейля]] (1921).

Першими формальними моделями алгоритмічно обчислюваних функцій були ''λ-означувані функції'' ([[Алонзо Черч]], 1932) та ''загальнорекурсивні функції'' ([[Курт Гедель]], 1934). Вказані класи визначались як функції, графіки яких породжуються відповідно численням λ-конверсій та численням Ербрана-Геделя. В 1936 році [[Стівен Коул Кліні]] поширив поняття загальнорекурсивної функції на випадок часткових функцій, ввівши поняття частково рекурсивної функції, та описав клас таких функцій в чисто функціональних термінах. В 1943 році [[Еміль Пост]] запропонував модель обчислюваних функцій на основі введеного ним числення спеціального вигляду (''канонічних систем'').

Для формалізації самого поняття алгоритму були запропоновані точні математичні описи алгоритмічної машини та обчислюваності на ній. Першою формальною моделлю алгоритмічної машини була [[машина Тюрінга]] ([[Алан Тюрінг]], [[Еміль Пост]], 1936). Із пізніших моделей відзначимо нормальні алгоритми ([[Андрій Марков|А. Марков]], 1952) та регістрові машини ([[Д. Шепердсон]], [[Г. Стерджіс]], 1963).

В 1936&nbsp;р. [[Алонзо Черч|А. Черч]] та [[Стівен Коул Кліні|С. Кліні]] довели збіг класів загально-рекурсивних та λ-означуваних функцій. На основі цього факту та аналізу ідей, які привели до вказаних понять, А. Черч висунув тезу про збіг класу АОФ з класом загальнорекурсивних функцій. С. Кліні узагальнив цю тезу для випадку часткових функцій. Доведений А. Тьюрінгом в 1937&nbsp;р. збіг класів частково рекурсивних функцій та функцій, обчислюваних на машинах Тюрінга, став ще одним підтвердженням тези Черча. Пізніше такі збіги були встановлені для всіх відомих формальних моделей АОФ. Тому є всі підстави вважати, що кожна із названих вище формальних моделей адекватно уточнює інтуїтивне поняття АОФ.

Теорія алгоритмів виникла як розділ математичної логіки, поняття алгоритму тісно пов'язане з поняттям числення. Перші та найчисельніші застосування теорія алгоритмів має саме в математичній логіці. Теорія алгоритмів є теоретичним фундаментом [[програмування]], вона має застосування всюди, де зустрічаються алгоритмічні проблеми (основи математики, [[теорія інформації]], [[теорія керування]], [[конструктивний аналіз]], [[обчислювальна математика]], [[теорія ймовірності]], [[лінгвістика]], [[Економіка (наука)|економіка]] та ін.).

== Основні поняття теорії алгоритмів ==

Областю застосовності [[алгоритм]]у називається сукупність тих об'єктів, до яких його можна застосувати, тобто в застосуванні до яких він дає результат. Про алгоритм ''U'' кажуть, що він: 1) «''обчислює функцію'' ''f''», коли його область застосування збігається з областю визначення ''f'', і ''U'' перетворює будь-який ''х'' зі своєї області застосування в ''f(х)''; 2) «''розв'язує множину A відносно множини X''», коли він застосовується до будь-якого ''х'' з ''X'', і перетворює будь-який ''х'' з'' X∩A'' на слово «так», а будь-який ''х'' з ''Х\А''&nbsp;— на слово «ні»; 3) «''перераховує множину B''», коли його область застосування є натуральний ряд, а сукупність результатів є ''B''. Функція наз. обчислюваною, якщо існує алгоритм, що її обчислює. [[Множина]] називається ''розв'язною'' відносно ''X'', якщо існує [[алгоритм]], що розв'язує її відносно ''X''. Множина наз. перераховуваною, якщо або вона порожня, або існує перераховуючий її алгоритм.

Детальний аналіз поняття «[[алгоритм]]» виявляє, що (I) область можливих вихідних даних і область застосовності будь-якого алгоритму є перераховуваними множинами. Своєю чергою, (II) для будь-якої пари вкладених одна в другу перераховуваних множин можна підібрати алгоритм, у якого більша множина слугує областю можливих вихідних даних, а менша&nbsp;— областю застосовності. Мають місце такі основні теореми: (III) функція ''f'' обчислювана тоді і тільки тоді, коли перераховуваний її графік, тобто множина всіх пар вигляду ''<х, f(x)>''. (IV) Підмножина ''А'' перераховуваної множини ''X'' тоді і тільки тоді розв'язна відносно'' X'', коли ''А'' і ''X\A'' перераховувані. (V) Якщо ''А'' і ''В'' перераховувані, то ''A об'єднати B'' і ''A∩B'' також перераховувані. (VI) В кожній нескінченній перераховуваній множині ''X'' існує перераховувана підмножина з неперераховуваним доповненням (в силу (IV) ця перераховувана підмножина буде нерозв'язною відносно ''X''). (VII) Для кожної нескінченної перераховуваної множини'' X'' існує обчислювана функція, визначена на підмножині цієї множини і яка не продовжувана до обчислюваної функції, визначеної на всій ''X''. Твердження (VI) і (II) в сукупності дають приклад алгоритму з нерозв'язною областю застосовуваності.

Розв'язні і перераховувані множини складають найпростіші (і найважливіші) приклади множин, структура яких задається за допомогою тих чи тих алгоритмічних процедур. Систематичне вивчення множин конструктивних об'єктів з точки зору таких властивостей цих множин, які зв'язані з наявністю тих чи інших алгоритмів, утворює так звану [[Алгоритмічна теорія множин|алгоритмічну теорію множин]].

Теорію алгоритмів можна розділити на ''дескриптивну'' (якісну) і ''метричну'' (кількісну). Перша досліджує алгоритми з точки зору встановлюваної ними відповідності між вихідними даними і результатами; до неї належать, зокрема, проблеми побудови алгоритму, що йому властиві ті чи інші властивості,— алгоритмічні проблеми. Друга досліджує алгоритми з точки зору складності як самих алгоритмів, так і обчислень, що ними задаються, тобто процесів послідовного перетворення конструктивних об'єктів (див. [[Складність алгоритму]]). Важливо підкреслити, що як складність алгоритмів, так і складність обчислень можуть визначатися різними способами. Розробка методів оцінки складності алгоритмів і обчислень має важливе теоретичне і практичне значення.

=== Формалізація поняття алгоритму ===

Серед інших поширених математичних моделей алгоритмів можна назвати<ref>{{Cite book| publisher = Springer| isbn = 978-0-387-95569-8| last = Burgin| first = M. S.| title = Super-recursive algorithms| url = https://archive.org/details/superrecursiveal0000burg| location = New York, NY| series = Monographs in computer science| date = 2005 | chapter = 2.2 Mathematical models of algorithms and why we need them }}</ref>:

* [[Мережа Петрі|Мережі Петрі]] описані [[Карл Адам Петрі|Карлом Петрі]] в 1962 році<ref>Petri, C. (1962). Kommunikation mit Automaten, Ph.D. Dissertation, University of Bonn, Bonn, Germany.</ref>, як і машини Тюрінга, мають різні форми&nbsp;— звичайні та з обмеженнями, регулярні, вільні, розфарбовані<ref>Zervos, C. (1977). Colored Petri Nets: Their Properties and Applications, Technical Report 107, System Engineering Laboratory, University of Michigan, Ann Arbor, Michigan.</ref>, само-змінювані, тощо<ref>Valk, R. (1978). Self-Modifying Nets&nbsp;— A Natural Extension of Petri Nets, in Automata, Languages, and Programming, Lecture Notes in Computer Science, 62, Springer-Verlag, New York, Berlin. </ref>
* Векторні машини, запропоновані Праттом, Рабіном, Стокмаєром в 1974 році<ref>V. Pratt, M. Rabin, L. Stockmeyer, A charaterization of the power of vector machines, Proc. SToC 74, pp. 122—134</ref>.
* [[Штучна нейронна мережа|Нейронні мережі]], найпростіші моделі з'явились в [[1943]]&nbsp;р. з появою статті нейрофізіолога [[Маккалох Воррен|Уоррена Маккалоха]] і математика [[Піттс Волтер|Волтера Піттса]]. Подібно до машини Тюрінга існує кілька різновидів: зі сталими вагами, з [[Кероване навчання|керованим]] та [[Некероване навчання|некерованим навчанням]], з [[Нейронна мережа прямого поширення|прямим поширенням]] або [[Рекурентні нейронні мережі|рекурентні]]<ref name="mc-pc.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.</ref>
* [[Автомат фон Неймана]] та загальні [[Клітинний автомат|клітинні автомати]]<ref>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.</ref>.
* Запропоноване [[Колмогоров Андрій Миколайович|Колмогоровим]] визначення алгоритму в 1953 році<ref>Kolmogorov, A.N. (1953). On the concept of algorithm, Russian Mathematical Surveys, v. 8, no. 4, pp. 175—176.</ref><ref>1958 г. июль—август т. XIII, вып. 4 (82) УСПЕХИ МАТЕМАТИЧЕСКИХ НАУК. К ОПРЕДЕЛЕНИЮ АЛГОРИТМА А.&nbsp;Н.&nbsp;Колмогоров и В.&nbsp;А.&nbsp;Успенский http://lpcs.math.msu.su/~uspensky/bib/Uspensky_1958_UMN_Kolmogorov_Opredelenie_algoritma.pdf {{Webarchive|url=https://web.archive.org/web/20160513074755/http://lpcs.math.msu.su/~uspensky/bib/Uspensky_1958_UMN_Kolmogorov_Opredelenie_algoritma.pdf |date=13 травня 2016 }}</ref>
* [[Скінченний автомат|скінченні автомати]], перші праці про які зазвичай приписують [[Маккалох Воррен|Маккалоху]] і [[Піттс Волтер|Піттсу]]<ref name="mc-pc.1943"/>, праці з формальним описом структури були написані [[Джордж Мілі|Мілі]]<ref>Mealy, G.H. (1953). A method for synthesizing sequential circuits, Bell System Techn. J., v. 34, pp. 1045—1079.</ref>, [[Стівен Коул Кліні|Стівеном Кліні]]<ref>Kleene, S.C. (1956). Representation of events in nerve nets, Automata Studies, Princeton University Press, Princeton, NJ, pp. 3–41.</ref> та Муром<ref>Moore, E.F. (1956). Gedanken-experiments on sequential machines, in Automata Studies, Princeton University Press, Princeton, NJ, pp. 129—153.</ref>. Подібно до машин Тюрінга скінченні автомати також мають низку різновидів: [[Автомат без пам'яті|без пам'яті]], автономні, без виведення або приймальні автомати, [[Детермінований скінченний автомат|детерміновані]] та [[Недетермінований скінченний автомат|недетерміновані]]<ref>Rabin, M.O. and Scott, D. (1959). Finite automata and their decision problems, IBM Journal of Research and Development, v. 3, pp. 114—125.</ref>, стохастичні автомати, тощо.
* [[Лічильна машина (автомат)|Машина Мінського]]<!-- counter machine --> запропонована [[Марвін Мінський|Марвіном Мінським]] в 1967 році<ref>{{Cite book| publisher = Prentice-Hall| isbn = 978-0-13-165563-8| last = Minsky| first = Marvin| title = Computation: finite and infinite machines| url = https://archive.org/details/computationfinit0000mins| location = Englewood Cliffs, NJ| date = 1967}}</ref>.
* зі змінюваною пам'яттю, або так звані «[[Машина Шенхаге|машини Шенхаге]]», запропоновані в 1980 році<ref>Shönhage, A. (1980). Storage modification machines, SIAM Journal on Computing, v. o 9, pp. 490—508. </ref>.
* [[рівнодоступна адресна машина]] (РАМ), запропоновані Шефердсоном та Старгісом в 1963 році<ref>Shepherdson, J.C. and Sturgis, H.E. (1963). Computability of recursive functions, Journal of the ACM, v. 10, no. 2, pp. 217—255. </ref> з варіантами&nbsp;— [[рівнодоступна адресна машина з програмою, що зберігається]] (РАСП), запропоновані Елготом і Робінсоном в 1964 році<ref>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.</ref>; паралельні рівнодоступні машини (ПРАМ);
* Машини обробки масивів описані Льовеном та Відерманом в 1985 році<ref>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. </ref>;
* Багатовимірна модель обчислень та обчислювальних систем розроблена М.&nbsp;С.&nbsp;Бургіним та А.&nbsp;Ю.&nbsp;Карасіком<ref>Бургин М.С, А.&nbsp;Ю.&nbsp;Карасик. Исследование одной абстрактной модели вычислительных систем // Программирование.&nbsp;— 1975.&nbsp;— №&nbsp;1.&nbsp;— С. 72–82. http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=at&paperid=8035&option_lang=rus {{Webarchive|url=https://web.archive.org/web/20160514002622/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=at&paperid=8035&option_lang=rus |date=14 травня 2016 }}</ref><ref>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.</ref>.
* [[Систолічний масив]] запропонований Кунгом та Лейсерсоном в 1978 році<ref>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.</ref>.
* Машини, що змінюють апаратне забезпечення, описані Даймондом та Куком в 1989 році<ref>Dymond, P.W. and Cook, S.A. (1989). Complexity theory of parallel time and hardware, Information and Computation, v. 80, pp. 205—226. </ref>
* [[Числення Поста]] запропоноване [[Еміль Пост|Емілем Постом]] в 1943 році<ref>[[Emil Post]], «Formal Reductions of the General Combinatorial Decision Problem» ''[[American Journal of Mathematics]]'' '''65''' (2): 197—215, 1943.</ref>.
* [[Нормальні алгоритми|Нормальні алгоритми Маркова]], запропоновані [[Марков Андрій Андрійович|А. Марковим]] в 1954 році<ref>А.&nbsp;А.&nbsp;Марков, «Теория алгорифмов», Тр. МИАН СССР, 42, Изд-во АН СССР, М.–Л., 1954, 3–375 http://mi.mathnet.ru/tm1178</ref>
* [[Формальна граматика|Формальні граматики]], які подібно до машин Тюрінга мають низку різновидів: регулярні, контекстно-вільні, контекстно-залежні, тощо<ref>Chomsky, N. (1956). Three models for the description of language, IRE Trans. On Information Theory, v. 2, no. 3, pp. 113—124. </ref><ref>Backus, J.W. (1959). The Syntax and Semantics of the Proposed International Algebraic Language of the Zurich ACM-GAMM Conference, Proc. Internat. Conf on Information Processing, UNESCO, pp. 125—132.</ref><ref>Naur, P., et al. (1960). Report on the algorithmic language ALGOL 60, Communications of the ACM, v. 3, no. 5, pp. 299—314.</ref>.

== Моделі обчислень ==
* Машина Тьюринга&nbsp;— абстрактний виконавець (абстрактна обчислювальна машина). Була запропонована Аланом Тьюрингом в 1936 році для формалізації поняття алгоритму. Машина Тьюринга є розширенням кінцевого автомата і, згідно з тезою Черча&nbsp;— Тьюринга, здатна імітувати всіх інших виконавців (за допомогою завдання правил переходу), будь-яким чином реалізує процес покрокового обчислення, в якому кожен крок обчислення досить елементарний.
* Лямбда-числення&nbsp;— розглядається пара&nbsp;— λ-вираз і його аргумент,&nbsp;— а обчисленням вважається застосування, або аппліцирування, першого члена пари до другого. Це дозволяє відокремити функцію і те, до чого вона застосовується. У більш загальному випадку обчисленням вважаються ланцюжки, що починаються з вихідного λ-виразу, за яким слідує кінцева послідовність λ-виразів, кожен з яких виходить з попереднього застосування β-редукції, тобто правила підстановки.
* Комбінаторна логіка&nbsp;— трактування обчислення схоже до λ-обчислень, але є і важливі відмінності (наприклад, комбінатор нерухомої точки '''Y''' має нормальну форму в комбінаторній логіці, а в λ-численні&nbsp;— не має). Комбінаторна логіка була спочатку розроблена для вивчення природи парадоксів і для побудови концептуально ясних підстав математики, причому уявлення про змінну виключалося зовсім, що допомагало прояснити роль і місце змінних в математиці.
* RAM-машина&nbsp;— абстрактна обчислювальна машина, що моделює комп'ютер з довільним доступом до пам'яті. Саме ця модель обчислень найбільш часто використовується при аналізі алгоритмів.

== Теза Черча&nbsp;— Тьюринга і алгоритмічно нерозв'язні проблеми ==

Алан Т'юринг висловив припущення (відоме як Теза Черча&nbsp;— Тьюринга), що будь-який алгоритм в інтуїтивному сенсі цього слова може бути представлений еквівалентною машиною Тьюринга. Уточнення уявлення про обчислюваності на основі поняття машини Тьюринга (і інших аналогічних їй понять) відкрило можливості для сурового доказу алгоритмічної нерозв'язності різних масових проблем. А саме проблем про знаходження єдиного методу рішення деякого класу задач, умови яких можуть змінюватися в певних межах. Найпростішим прикладом алгоритмічно нерозв'язної масової проблеми є так звана проблема застосовності алгоритму (звана також проблемою зупинки). Вона полягає в наступному: потрібно знайти спільний метод, який дозволяв би для довільної машини Тьюринга (заданої за допомогою своєї програми) і довільного початкового стану стрічки цієї машини визначити, чи завершиться робота машини за кінцеве число кроків, або ж буде тривати необмежено довго.

Протягом першого десятиліття історії теорії алгоритмів нерозв'язні масові проблеми були виявлені лише всередині самої цієї теорії (сюди відноситься описана вище проблема застосовності).  Також всередині математичної логіки (проблема виводу в класичному численні предикатів). Тому вважалося, що теорія алгоритмів є узбіччям математики, що не грає важливої ролі для таких її класичних розділів, як [[абстрактна алгебра]] або математичний аналіз. Положення змінилося після того, як А.&nbsp;А.&nbsp;Марков і Е.&nbsp;Л.&nbsp;Пост в 1947 році встановили алгоритмічну нерозв'язність відомої в алгебрі проблеми рівності для кінцево-створених і кінцево-визначених напівгруп (т. з. [[Проблеми ТУЕ]]). Згодом було встановлено алгоритмічна нерозв'язність і багатьох інших «чисто математичних» масових проблем. Одним з найбільш відомих результатів в цій області є доведена Ю.&nbsp;В.&nbsp;Матіясевич алгоритмічна нерозв'язність десятої [[проблеми Гільберта]].

== Застосування теорії алгоритмів ==
У всіх галузях математики, в яких зустрічаються алгоритмічні проблеми. Такі проблеми виникають практично в усіх розділах математики. В математичній логіці для кожної теорії формулюється проблема розв'язування множини всіх істинних або довідних тверджень цієї теорії відносно множини всіх її пропозиції (теорії поділяються на розв'язні і нерозв'язні в залежності від розв'язності або нерозв'язності вказаної проблеми). У 1936&nbsp;р. [[Алонзо Черч|А. Черч]] встановив нерозв'язність проблеми розв'язності для множини всіх істинних пропозицій [[логіка предикатів|логіки предикатів]], подальші важливі результати в цьому напрямі належать [[Тарський Альфред|А. Тарському]], [[Мальцев Анатолій Іванович|А.&nbsp;І.&nbsp;Мальцеву]] та іншим. Нерозв'язні алгоритмічні проблеми зустрічаються в [[алгебра|алгебрі]] (проблема тотожності для напівгруп і, зокрема, для [[Група (математика)|груп]]. Перші приклади [[Напівгрупа|напівгруп]] з нерозв'язною проблемою тотожності були винайдені в [[1947]]&nbsp;р. незалежно [[Марков Андрій Андрійович|А.&nbsp;А.&nbsp;Марковим]] і [[Пост Еміль|Е. Постом]], а приклад групи з нерозв'язною проблемою тотожності&nbsp;— в 1952&nbsp;р. [[Новіков Петро Сергійович|П.&nbsp;С.&nbsp;Новіковим]]). В [[топологія|топології]] (проблема гомеоморфії, нерозв'язність якої для важливого класу випадків була доведена в [[1958]]&nbsp;р. [[Марков Андрій Андрійович|А.&nbsp;А.&nbsp;Марковим]]); в [[теорія чисел|теорії чисел]] (проблема розв'язності [[діофантові рівняння|діофантових рівнянь]], нерозв'язність якої була встановлена в [[1970]]&nbsp;р. [[Матіясевич Юрій Володимирович|Ю.&nbsp;В.&nbsp;Матіясевичем]]) та в інших розділах [[математика|математики]].

Теорія алгоритмів тісно зв'язана:
* з [[математична логіка|математичною логікою]], оскільки в термінах алгоритмів може бути викладено одне з центральних понять математичної логіки&nbsp;— поняття числення. І тому, наприклад, [[теорема Геделя про неповноту]] [[Формальна система|формальних систем]] може бути одержана як наслідок теорем теорії алгоритмів;
* з [[основи математики|основами математики]], в яких одне з центральних місць займає проблема співвідношення [[Конструктивне доведення|конструктивного]] і [[Неконструктивне доведення|неконструктивного]] (зокрема, теорія алгоритмів надає апарат, необхідний для розробки конструктивного напряму в математиці). В [[1965]]&nbsp;р. [[Колмогоров Андрій Миколайович|А.&nbsp;М.&nbsp;Колмогоров]] запропонував використовувати теорію алгоритмів для обґрунтування [[Алгоритмічна теорія інформації|теорії інформації]];
* з [[кібернетика|кібернетикою]], в якій важливе місце займає вивчення [[алгоритми керування|алгоритмів керування]]. Теорія алгоритмів утворює теоретичний фундамент для низки питань [[обчислювальна математика|обчислювальної математики]].

== Сучасний стан теорії алгоритмів ==
На даний час теорія алгоритмів розвивається, головним чином, за трьома напрямками:

* Класична теорія алгоритмів. Вивчає проблеми формулювання завдань в термінах формальних мов, вводить поняття завдання дозволу, проводить класифікацію задач за класами складності (P, NP і ін.).

* Теорія асимптотичного аналізу алгоритмів. Розглядає методи отримання асимптотичних оцінок ємності або часу виконання алгоритмів, зокрема, для рекурсивних алгоритмів. Асимптотичний аналіз дозволяє оцінити зростання потреби алгоритму в ресурсах (наприклад, часу виконання) зі збільшенням обсягу вхідних даних.

* Теорія практичного аналізу обчислювальних алгоритмів. Вирішує завдання отримання явних функції трудомісткості, інтервального аналізу функцій, пошуку практичних критеріїв якості алгоритмів, розробки методики вибору раціональних алгоритмів.

=== Аналіз трудомісткості алгоритмів ===

Метою аналізу трудомісткості алгоритмів є знаходження оптимального алгоритму для вирішення даного завдання. Як критерій оптимальності алгоритму вибирається трудомісткість алгоритму, що розуміється як кількість елементарних операцій, які необхідно виконати для вирішення задачі за допомогою даного алгоритму. Функцією трудомісткості називається відношення, що зв'язують вхідні дані алгоритму з кількістю елементарних операцій.

Трудомісткість алгоритмів по-різному залежить від вхідних даних. Для деяких алгоритмів трудомісткість залежить тільки від обсягу даних, для інших алгоритмів&nbsp;— від значень даних. В деяких випадках порядок надходження даних може впливати на трудомісткість. Трудомісткість багатьох алгоритмів може в тій чи іншій мірі залежати від всіх перерахованих вище факторів.

Одним зі спрощених видів аналізу, що використовуються на практиці, є асимптотичний аналіз алгоритмів. Метою асимптотичного аналізу є порівняння витрат часу та інших ресурсів різними алгоритмами, призначеними для вирішення однієї і тієї ж задачі, при великих обсягах вхідних даних. Використовувана в асимптотичному аналізі оцінка функції трудомісткості, звана '''складністю алгоритму''', дозволяє визначити, як швидко зростає трудомісткість алгоритму зі збільшенням обсягу даних. У асимптотичному аналізі алгоритмів використовуються позначення, прийняті в математичному асимптотичному аналізі. Нижче перераховані основні оцінки складності.

Основною оцінкою функції складності алгоритму f(n) є оцінка <math>\boldsymbol{\Theta}</math>. Тут n&nbsp;— величина обсягу даних або довжина входу. Ми говоримо, що оцінка складності алгоритму

<math>f(n) = \boldsymbol{\Theta}(g(n))</math>

якщо при g > 0  та при n > 0 існують додатні с<sub>1</sub>, с<sub>2</sub>, n<sub>0</sub>, такі, що:

<math>c_1 g(n)\le \; f(n) \le \; c_2 g(n)</math>

при n > n<sub>0</sub>, інакше кажучи, можна знайти такі с<sub>1</sub> і c<sub>2</sub>, що при достатньо великих n f(n) буде знаходитись між

<math>\boldsymbol{c_1\;g(n)}</math> і <math>\boldsymbol{c_2\;g(n)}</math>.

У такому випадку говорять також, що функція g(n) є асимптотично точною оцінкою функції f(n), так як за визначенням функція f(n) не відрізняється від функції g(n) з точністю до постійного множника. Наприклад, для методу сортування купою оцінка трудомісткості становить

<math>f(n) = \boldsymbol{\Theta}(n\log n)</math> то є <math>g(n) = n \log n</math>

Із <math>f(n) = \boldsymbol{\Theta}(g(n))</math> випливає, що <math>g(n) = \boldsymbol{\Theta}(f(n))</math>.

Важливо розуміти, що <math>\boldsymbol{\Theta}(g(n))</math> це не функція, а безліч функцій, що описують зростання <math>\boldsymbol{f(n)}</math> з точністю до постійного множника.

<math>\boldsymbol{\Theta}</math> дає одночасно верхню і нижню оцінки зростання функції. Часто буває необхідно розглядати ці оцінки окремо. Оцінка <math>\boldsymbol{O}</math> це верхня асимптотична оцінка трудомісткості алгоритму.
Ми говоримо, що <math> f(n) = \boldsymbol{O}(g(n))</math> якщо

<math>\exists \; c > 0, n_0 > 0 : 0 \le \; f(n) \le \; c g(n), \forall \; n > n_0 </math>

Інакше кажучи, запис <math>f(n) = \boldsymbol{O}(g(n))</math> означає, що f(n) належить класу функцій, що ростуть не швидше, ніж функція g(n) з точністю до постійного множника.

Оцінка <math>\boldsymbol{\Omega}</math> задає нижню асимптотичну оцінку зростання функції f(n) і визначає клас функцій, які ростуть не повільніше, ніж g(n) з точністю до постійного множника. <math> f(n) = \boldsymbol{\Omega}(g(n))</math> якщо

<math> \exists \; c > 0, n_0 > 0 : 0 \le \; c g(n) \le \; f(n), \forall \; n > n_0 </math>

Наприклад, запис <math> f(n) = \boldsymbol{\Omega}(n\log\;n)</math> позначає клас функцій, які ростуть не повільніше, ніж <math>\boldsymbol{g(n) = n\log\;n}</math>. В цей клас потрапляють всі поліноми зі ступенем більшої одиниці, так само як і всі статичні функції з повним правом великої одиниці.
Рівність <math> f(n) = \boldsymbol{\Theta}(g(n))</math> виконується тоді і тільки тоді, коли <math> f(n) = \boldsymbol{O}(g(n))</math> і <math> f(n) = \boldsymbol{\Omega}(g(n))</math>.

Асимптотичний аналіз алгоритмів має не тільки практичне, але і теоретичне значення. Наприклад, доведено, що всі алгоритми сортування, засновані на попарному порівнянні елементів, відсортують n елементів за час, не менше <math>\boldsymbol{\Omega}(n\log n)</math>.

Важливу роль у розвитку асимптотичного аналізу алгоритмів зіграли A. Ахо, Дж. Ульман, Дж. Гопкрофта.

=== Класи складності ===

В рамках класичної теорії здійснюється класифікація завдань за класами складності (''P-''складні, ''NP-''складні, експоненціально складні і ін.). До класу P відносяться завдання, які можуть бути вирішені за час, залежний від обсягу вихідних даних, за допомогою детермінованої обчислювальної машини (наприклад, машини Тьюринга). До класу ''NP''&nbsp;— завдання, які можуть бути вирішені за виражений час за допомогою недетермінованої обчислювальної машини, тобто машини, наступний стан якої не завжди однозначно визначається попередніми. Роботу такої машини можна уявити як розгалужується на кожній неоднозначності процесу: завдання вважається вирішеним, якщо хоча б одна гілка процесу прийшла до відповіді. Інше визначення класу NP: до класу NP відносяться завдання, вирішення яких за допомогою додаткової інформації довжини, даної нам згори, ми можемо перевірити за поліноміальний час. Зокрема, до класу ''NP'' відносяться всі завдання, вирішення яких можна ''перевірити'' за поліноміального часу. Клас P міститься в класі NP. Класичним прикладом NP-задачі є задача про комівояжера.

Оскільки клас P міститься в класі ''NP'', приналежність того чи іншого завдання до класу ''NP'' часто відображає наше поточне уявлення про способи вирішення даного завдання і носить неостаточний характер. У загальному випадку немає підстав вважати, що для того чи іншого NP-завдання не може бути знайдено P-рішення. Питання про можливість еквівалентності класів P і NP (тобто про можливість знаходження P-рішення для будь-якої ''NP-''задачі) вважається одним з основних питань сучасної теорії складності алгоритмів. Відповідь на це питання не знайдена досі. Сама постановка питання про еквівалентність класів P і NP можлива завдяки введенню поняття ''NP-''повних задач. ''NP-''повні задачі складають підмножина ''NP-''задач і відрізняються тією властивістю, що всі ''NP-''завдання можуть бути тим чи іншим способом зведені до них. З цього випливає, що якщо для NP-повної задачі буде знайдено ''P-''рішення, то ''P-''рішення буде знайдено для всіх завдань класу ''NP''. Прикладом ''NP-''повної задачі є задача про кон'юнктивні форми.

Дослідження складності алгоритмів дозволили по-новому поглянути на вирішення багатьох класичних математичних задач. А також знайти для ряду таких завдань (множення многочленів і матриць, рішення лінійних систем рівнянь і ін.) рішення, які вимагають менше ресурсів, ніж традиційні.

== Примітки ==
{{reflist|2}}

== Посилання ==
* ''Бондарчук Ю. В.'' [http://www.ukma.edu.ua/~yubod/teach/logica/Mathemtics/algtheory.pdf Лекції з теорії алгоритмів] {{Webarchive|url=https://web.archive.org/web/20160927215222/http://www.ukma.edu.ua/~yubod/teach/logica/Mathemtics/algtheory.pdf |date=27 вересня 2016 }}, Києво-Могилянська Академія. {{ref-uk}}

== Література ==
;Українською
* {{книга
 |автор          = Л.&nbsp;М.&nbsp;Клакович, С.&nbsp;М.&nbsp;Левицька
 |частина        = 
 |заголовок      = Теорія алгоритмів: Навчальний посібник
 |посилання      = 
 |видання        = Друге видання, доповнене
 |відповідальний = 
 |місце          = Львів
 |видавництво    = Видавничий центр ЛНУ ім. Івана Франка
 |рік            = 2015
 |том            = 
 |сторінки       = 
 |сторінок       = 161
 |isbn           =  9786171002302
 |ref            =
}} {{ref-uk}}
* «[[Енциклопедія кібернетики]]», відповідальний ред. [[Глушков Віктор Михайлович|В. Глушков]], 2 тт., [[1973]]. {{ref-uk}}
;Іншими мовами
* {{книга |автор                   = Michael Sipser
 |частина               = 
 |заголовок           = Introduction to the Theory of Computation
 |посилання           = 
 |видання               = 
 |відповідальний = 
 |місце                   = Boston
 |видавництво       = PWS Publishing Company
 |рік                       = 1997
 |том                       = 
 |сторінки             = 
 |сторінок             = 387
 |isbn                         = 0-534-94728-X
 |ref                          = 
 |url-access                   = registration
 |url                          = https://archive.org/details/introductiontoth00sips
}} {{ref-en}}
* ''Вейль Г.,'' О философии математики, пер. с нем., М.— Л., 1934;
* ''Марков А. А., Нагорный Н. М.,'' Теория алгоритмов, М., 1984;
* ''Мальцев А. И.,'' Алгоритмы и рекурсивные функции, М., 1965;
* ''Роджерс X.,'' Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972;
* ''Успенский В. А.,'' Машина Поста, М., 1979; его же, Теорема Гёделя о неполноте, М., 1982;
* Проблемы математической логики. Сложность алгоритмов и классы вычислимых функций. Сб. переводов, М., 1970;
* ''Колмогоров А. Н.,'' «Проблемы передачи информации», 1965, т. 1, №&nbsp;1, с. 3—11;
* Алгоритмы в современной математике и ее приложениях, ч. 1—2, Новосиб., 1982;
* ''Успенский В. А., Семенов А. Л.,'' «Квант», 1985, №&nbsp;7, с. 9—15.

== Див. також ==
* [[Список алгоритмів]]
* [[Теорія складності обчислень]]
* [[Асоціативне числення]]
{{Refimprove|дата=грудень 2015}}
{{Algorithm-stub}}
{{Класи складності}}
{{Інформатика}}
{{Розділи математики|state=collapsed}}

[[Категорія:Теорія алгоритмів|*]]
[[Категорія:Програмування]]
[[Категорія:Теоретична інформатика]]