Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. |
Теорія алгоритмів (англ. Theory of computation) — окремий розділ математики, що вивчає загальні властивості алгоритмів. Виникла в 30-х роках 20 століття.
Алгоритми, проте, простежуються в математиці протягом всього часу її існування. Необхідність точного математичного уточнення інтуїтивного поняття алгоритму стала неминучою після усвідомлення неможливості існування алгоритмів розв'язку багатьох масових проблем, в першу чергу пов'язаних з арифметикою та математичною логікою (проблеми істинності арифметичних формул та формул першопорядкового числення предикатів, 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 році, як і машини Тюрінга, мають різні форми — звичайні та з обмеженнями, регулярні, вільні, розфарбовані, само-змінювані, тощо
- Векторні машини, запропоновані Праттом, Рабіном, Стокмаєром в 1974 році.
- Нейронні мережі, найпростіші моделі з'явились в 1943 р. з появою статті нейрофізіолога Уоррена Маккалоха і математика . Подібно до машини Тюрінга існує кілька різновидів: зі сталими вагами, з керованим та некерованим навчанням, з прямим поширенням або рекурентні
- Автомат фон Неймана та загальні клітинні автомати.
- Запропоноване Колмогоровим визначення алгоритму в 1953 році
- скінченні автомати, перші праці про які зазвичай приписують Маккалоху і , праці з формальним описом структури були написані , Стівеном Кліні та Муром. Подібно до машин Тюрінга скінченні автомати також мають низку різновидів: без пам'яті, автономні, без виведення або приймальні автомати, детерміновані та недетерміновані, стохастичні автомати, тощо.
- запропонована Марвіном Мінським в 1967 році.
- зі змінюваною пам'яттю, або так звані , запропоновані в 1980 році.
- (РАМ), запропоновані Шефердсоном та Старгісом в 1963 році з варіантами — (РАСП), запропоновані Елготом і Робінсоном в 1964 році; паралельні рівнодоступні машини (ПРАМ);
- Машини обробки масивів описані Льовеном та Відерманом в 1985 році;
- Багатовимірна модель обчислень та обчисльвальних систем розроблена М. С. Бургіним та А. Ю. Карасіком.
- Систолічний масив запропоновані Кунгом та Лейсерсоном в 1978 році.
- Машини, що змінюють апаратне забезпечення, описані Даймондом та Куком в 1989 році
- Числення Поста запропоноване Емілем Постом в 1943 році.
- Нормальні алгоритми Маркова, запропоновані А. Марковим в 1954 році
- Формальні граматики, які подібно до машин Тюрінга мають низку різновидів: регулярні, контекстно-вільні, контекстно-залежні, тощо.
Моделі обчислень
- Машина Тьюринга — абстрактний виконавець (абстрактна обчислювальна машина). Була запропонована Аланом Тьюрингом в 1936 році для формалізації поняття алгоритму. Машина Тьюринга є розширенням кінцевого автомата і, згідно з тезою Черча — Тьюринга, здатна імітувати всі інші виконавці (за допомогою завдання правил переходу), будь-яким чином реалізують процес покрокового обчислення, в якому кожен крок обчислення досить елементарний.
- Лямбда-числення — розглядається пара — λ-вираз і його аргумент, — а обчисленням вважається застосування, або аппліцирування, першого члена пари до другого. Це дозволяє відокремити функцію і те, до чого вона застосовується. У більш загальному випадку обчисленням вважаються ланцюжки, що починаються з вихідного λ-виразу, за яким слідує кінцева послідовність λ-виразів, кожне з яких виходить з попереднього застосування β-редукції, тобто правила підстановки.
- Комбінаторна логіка — трактування обчислення подібне до λ-обчислень, але є і важливі відмінності (наприклад, комбінатор нерухомої точки Y має нормальну форму в комбінаторній логіці, а в λ-численні — не має). Комбінаторна логіка була спочатку розроблена для вивчення природи парадоксів і для побудови концептуально ясних підстав математики, причому уявлення про змінну виключалося зовсім, що допомагало прояснити роль і місце змінних в математиці.
- RAM-машина — абстрактна обчислювальна машина, що моделює комп'ютер з довільним доступом до пам'яті. Саме ця модель обчислень найбільш часто використовується при аналізі алгоритмів.
Теза Черча — Тьюринга і алгоритмічно нерозв'язні проблеми
Алан Тьюринг висловив припущення (відоме як Теза Черча — Тьюринга), що будь-який алгоритм в інтуїтивному сенсі цього слова може бути представлений еквівалентною машиною Тьюринга. Уточнення уявлення про обчислюваності на основі поняття машини Тьюринга (і інших аналогічних їй понять) відкрило можливості для суворого доказу алгоритмічної нерозв'язності різних масових проблем (тобто проблем про знаходження єдиного методу рішення деякого класу задач, умови яких можуть змінюватися в певних межах). Найпростішим прикладом алгоритмічно нерозв'язної масової проблеми є так звана проблема застосовності алгоритму (звана також проблемою зупинки). Вона полягає в наступному: потрібно знайти спільний метод, який дозволяв би для довільної машини Тьюринга (заданої за допомогою своєї програми) і довільного початкового стану стрічки цієї машини визначити, чи завершиться робота машини за кінцеве число кроків, або ж буде тривати необмежено довго.
Протягом першого десятиліття історії теорії алгоритмів нерозв'язні масові проблеми були виявлені лише всередині самої цієї теорії (сюди відноситься описана вище проблема застосовності), а також всередині математичної логіки (проблема виводу в класичному численні предикатів). Тому вважалося, що теорія алгоритмів є узбіччя математики, що не має значення для таких її класичних розділів, як абстрактна алгебра або математичний аналіз. Положення змінилося після того, як А. А. Марков і Е. Л. Пост в 1947 році встановили алгоритмічну нерозв'язність відомої в алгебрі проблеми рівності для кінцево-створених і кінцево-визначених напівгруп (т. з. ). Згодом було встановлено алгоритмічна нерозв'язність і багатьох інших «чисто математичних» масових проблем. Одним з найбільш відомих результатів в цій області є доведена Ю. В. Матіясевіч алгоритмічна нерозв'язність десятої проблеми Гільберта.
Застосування теорії алгоритмів
У всіх галузях математики, в яких зустрічаються алгоритмічні проблеми. Такі проблеми виникають практично в усіх розділах математики. В математичній логіці для кожної теорії формулюється проблема розв'язування множини всіх істинних або довідних тверджень цієї теорії відносно множини всіх її пропозиції (теорії поділяються на розв'язні і нерозв'язні в залежності від розв'язності або нерозв'язності вказаної проблеми); у 1936 р. А. Черч встановив нерозв'язність проблеми розв'язності для множини всіх істинних пропозицій логіки предикатів, подальші важливі результати в цьому напрямі належать А. Тарському, А. І. Мальцеву та інші. Нерозв'язні алгоритмічні проблеми зустрічаються в алгебрі (проблема тотожності для напівгруп і, зокрема, для груп; перші приклади напівгруп з нерозв'язною проблемою тотожності були винайдені в 1947 р. незалежно А. А. Марковим і Е. Постом, а приклад групи з нерозв'язною проблемою тотожності — в 1952 р. ); в топології (проблема гомеоморфії, нерозв'язність якої для важливого класу випадків була доведена в 1958 р. А. А. Марковим); в теорії чисел (проблема розв'язності діофантових рівнянь, нерозв'язність якої була встановлена в 1970 р. Ю. В. Матіясевичем) та в інших розділах математики.
Теорія алгоритмів тісно зв'язана:
- з математичною логікою, оскільки в термінах алгоритмів може бути викладено одне з центральних понять математичної логіки — поняття числення (і тому, наприклад, теорема Геделя про неповноту формальних систем може бути одержана як наслідок теорем теорії алгоритмів);
- з основами математики, в яких одне з центральних місць займає проблема співвідношення конструктивного і неконструктивного (зокрема, теорія алгоритмів надає апарат, необхідний для розробки конструктивного напряму в математиці); в 1965 р. А. М. Колмогоров запропонував використовувати теорію алгоритмів для обґрунтування теорії інформації;
- з кібернетикою, в якій важливе місце займає вивчення . Теорія алгоритмів утворює теоретичний фундамент для низки питань обчислювальної математики.
Сучасний стан теорії алгоритмів
В даний час теорія алгоритмів розвивається, головним чином, за трьома напрямками.
- Класична теорія алгоритмів вивчає проблеми формулювання завдань в термінах формальних мов, вводить поняття завдання дозволу, проводить класифікацію задач за класами складності (P, NP і ін.).
- Теорія асимптотичного аналізу алгоритмів розглядає методи отримання асимптотичних оцінок ємності або часу виконання алгоритмів, зокрема, для рекурсивних алгоритмів. Асимптотичний аналіз дозволяє оцінити зростання потреби алгоритму в ресурсах (наприклад, часу виконання) зі збільшенням обсягу вхідних даних.
- Теорія практичного аналізу обчислювальних алгоритмів вирішує завдання отримання явних функції трудомісткості, інтервального аналізу функцій, пошуку практичних критеріїв якості алгоритмів, розробки методики вибору раціональних алгоритмів.
Аналіз трудомісткості алгоритмів
Метою аналізу трудомісткості алгоритмів є знаходження оптимального алгоритму для вирішення даного завдання. Як критерій оптимальності алгоритму вибирається трудомісткість алгоритму, що розуміється як кількість елементарних операцій, які необхідно виконати для вирішення задачі за допомогою даного алгоритму. Функцією трудомісткості називається відношення, що зв'язують вхідні дані алгоритму з кількістю елементарних операцій.
Трудомісткість алгоритмів по-різному залежить від вхідних даних. Для деяких алгоритмів трудомісткість залежить тільки від обсягу даних, для інших алгоритмів — від значень даних, в деяких випадках порядок надходження даних може впливати на трудомісткість. Трудомісткість багатьох алгоритмів може в тій чи іншій мірі залежати від всіх перерахованих вище факторів.
Одним з спрощених видів аналізу, що використовуються на практиці, є асимптотичний аналіз алгоритмів. Метою асимптотичного аналізу є порівняння витрат часу та інших ресурсів різними алгоритмами, призначеними для вирішення однієї і тієї ж задачі, при великих обсягах вхідних даних. Використовувана в асимптотичному аналізі оцінка функції трудомісткості, звана складністю алгоритму, дозволяє визначити, як швидко зростає трудомісткість алгоритму зі збільшенням обсягу даних. У асимптотичному аналізі алгоритмів використовуються позначення, прийняті в математичному асимптотичному аналізі. Нижче перераховані основні оцінки складності.
Основною оцінкою функції складності алгоритму f(n) є оцінка . Тут n — величина обсягу даних або довжина входу. Ми говоримо, що оцінка складності алгоритму
якщо при g > 0 при n > 0 існують додатні с1, с2, n0, такі, що:
при n > n0, інакше кажучи, можна знайти такі с1 і c2, що при достатньо великих n f(n) буде знаходитись між
і .
У такому випадку говорять ще, що функція g(n) є асимптотично точною оцінкою функції f(n), так як за визначенням функція f(n) не відрізняється від функції g(n) з точністю до постійного множника. Наприклад, для методу сортування heapsort оцінка трудомісткості становить
то є
Із випливає, що .
Важливо розуміти, що це не функція, а безліч функцій, що описують зростання з точністю до постійного множника.
дає одночасно верхню і нижню оцінки зростання функції. Часто буває необхідно розглядати ці оцінки окремо. Оцінка це верхня асимптотична оцінка трудомісткості алгоритму. Ми говоримо, що якщо
Інакше кажучи, запис означає, що f(n) належить класу функцій, що ростуть не швидше, ніж функція g(n) з точністю до постійного множника.
Оцінка задає нижню асимптотичну оцінку зростання функції f(n) і визначає клас функцій, які ростуть не повільніше, ніж g(n) з точністю до постійного множника. якщо
Наприклад, запис позначає клас функцій, які ростуть не повільніше, ніж , в цей клас потрапляють всі поліноми зі ступенем більшої одиниці, так само як і всі статичні функції з повним правом великої одиниці. Рівність виконується тоді і тільки тоді, коли і .
Асимптотичний аналіз алгоритмів має не тільки практичне, але і теоретичне значення. Наприклад, доведено, що всі алгоритми сортування, засновані на попарному порівнянні елементів, відсортують n елементів за час, не менше .
Важливу роль у розвитку асимптотичного аналізу алгоритмів зіграли A. Ахо, Дж. Ульман, Дж. Гопкрофта.
Класи складності
В рамках класичної теорії здійснюється класифікація завдань за класами складності (P-складні, NP-складні, експоненціально складні і ін.). До класу P відносяться завдання, які можуть бути вирішені за час, залежне від обсягу вихідних даних, за допомогою детермінованої обчислювальної машини (наприклад, машини Тьюринга), а до класу NP — завдання, які можуть бути вирішені за виражений час за допомогою недетермінованої обчислювальної машини, тобто машини, наступний стан якої не завжди однозначно визначається попередніми. Роботу такої машини можна уявити як розгалужується на кожній неоднозначності процесу: завдання вважається вирішеним, якщо хоча б одна гілка процесу прийшла до відповіді. Інше визначення класу 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-повної задачі є задача про кон'юнктивні форми.
Дослідження складності алгоритмів дозволили по-новому поглянути на вирішення багатьох класичних математичних задач і знайти для ряду таких завдань (множення многочленів і матриць, рішення лінійних систем рівнянь і ін.) Рішення, які вимагають менше ресурсів, ніж традиційні.
Математичні застосування теорії алгоритмів
- Дослідження масових проблем.
- Застосування в основах математики: конструктивна семантика.
- Застосування в математичній логіці: аналіз формалізованих мов логіки і арифметики.
- Аналіз обчислюваності.
- Нумеровані структури.
- Застосування в теорії ймовірностей: визначення випадкової послідовності.
- Застосування в теорії інформації: алгоритмічний підхід до поняття кількості інформації.
- Оцінення складності розв'язування окремих задач.
- Вплив теорії алгоритмів на алгоритмічну практику.
Примітки
- Burgin, M. S. (2005). 2.2 Mathematical models of algorithms and why we need them. Super-recursive algorithms. Monographs in computer science. New York, NY: Springer. ISBN .
- 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.
- V. Pratt, M. Rabin, L. Stockmeyer, A charaterization of the power of vector machines, Proc. SToC 74, pp. 122—134
- 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.
- 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 [ 13 травня 2016 у Wayback Machine.]
- 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.
- Minsky, Marvin (1967). Computation: finite and infinite machines. Englewood Cliffs, NJ: Prentice-Hall. ISBN .
- Shönhage, A. (1980). Storage modification machines, SIAM Journal on Computing, v. o 9, pp. 490—508.
- Shepherdson, J.C. and Sturgis, H.E. (1963). Computability of recursive functions, Journal of the ACM, v. 10, no. 2, pp. 217—255.
- 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.
- 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 [ 14 травня 2016 у Wayback Machine.]
- 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.
- 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.
- Dymond, P.W. and Cook, S.A. (1989). Complexity theory of parallel time and hardware, Information and Computation, v. 80, pp. 205—226.
- , «Formal Reductions of the General Combinatorial Decision Problem» American Journal of Mathematics 65 (2): 197—215, 1943.
- А. А. Марков, «Теория алгорифмов», Тр. МИАН СССР, 42, Изд-во АН СССР, М.–Л., 1954, 3–375 http://mi.mathnet.ru/tm1178
- Chomsky, N. (1956). Three models for the description of language, IRE Trans. On Information Theory, v. 2, no. 3, pp. 113—124.
- 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.
- Naur, P., et al. (1960). Report on the algorithmic language ALGOL 60, Communications of the ACM, v. 3, no. 5, pp. 299—314.
Посилання
- Бондарчук Ю. В. Лекції з теорії алгоритмів [ 27 вересня 2016 у Wayback Machine.], Києво-Могилянська Академія. (укр.)
Література
- Українською
- Л. М. Клакович, С. М. Левицька. Теорія алгоритмів: Навчальний посібник. — Друге видання, доповнене. — Львів : Видавничий центр ЛНУ ім. Івана Франка, 2015. — 161 с. — . (укр.)
- «Енциклопедія кібернетики», відповідальний ред. В. Глушков, 2 тт., 1973. (укр.)
- Іншими мовами
- Michael Sipser. Introduction to the Theory of Computation. — Boston : PWS Publishing Company, 1997. — 387 с. — . (англ.)
- Вейль Г., О философии математики, пер. с нем., М.— Л., 1934;
- Марков А. А., Нагорный Н. М., Теория алгоритмов, М., 1984;
- Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965;
- Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972;
- Успенский В. А., Машина Поста, М., 1979; его же, Теорема Гёделя о неполноте, М., 1982;
- Проблемы математической логики. Сложность алгоритмов и классы вычислимых функций. Сб. переводов, М., 1970;
- Колмогоров А. Н., «Проблемы передачи информации», 1965, т. 1, № 1, с. 3—11;
- Алгоритмы в современной математике и ее приложениях, ч. 1—2, Новосиб., 1982;
- Успенский В. А., Семенов А. Л., «Квант», 1985, № 7, с. 9—15.
Див. також
Ця стаття потребує додаткових для поліпшення її . (грудень 2015) |
Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cya stattya mistit pravopisni leksichni gramatichni stilistichni abo inshi movni pomilki yaki treba vipraviti Vi mozhete dopomogti vdoskonaliti cyu stattyu pogodivshi yiyi iz chinnimi movnimi standartami Teoriya algoritmiv angl Theory of computation okremij rozdil matematiki sho vivchaye zagalni vlastivosti algoritmiv Vinikla v 30 h rokah 20 stolittya Algoritmi prote prostezhuyutsya v matematici protyagom vsogo chasu yiyi isnuvannya Neobhidnist tochnogo matematichnogo utochnennya intuyitivnogo ponyattya algoritmu stala neminuchoyu pislya usvidomlennya nemozhlivosti isnuvannya algoritmiv rozv yazku bagatoh masovih problem v pershu chergu pov yazanih z arifmetikoyu ta matematichnoyu logikoyu problemi istinnosti arifmetichnih formul ta formul pershoporyadkovogo chislennya predikativ 10 ta problema Gilberta pro rozv yaznist diofantovih rivnyan ta in Dlya dovedennya neisnuvannya algoritmu treba mati jogo tochne matematichne viznachennya tomu pislya sformuvannya ponyattya algoritmu yak novoyi ta okremoyi sutnosti pershochergovoyu stala problema znahodzhennya adekvatnih formalnih modelej algoritmu ta doslidzhennya yih vlastivostej Pri comu formalni modeli buli zaproponovani yak dlya pervisnogo ponyattya algoritmu tak i dlya pohidnogo ponyattya algoritmichno obchislyuvanoyi funkciyi Istoriya rozvitkuVpershe ponyattya algoritmu z yavilosya v pracyah E Borelya 1912 ta G Vejlya 1921 Pershimi formalnimi modelyami algoritmichno obchislyuvanih funkcij buli l oznachuvani funkciyi Alonzo Cherch 1932 ta zagalnorekursivni funkciyi Kurt Gedel 1934 Vkazani klasi viznachalis yak funkciyi grafiki yakih porodzhuyutsya vidpovidno chislennyam l konversij ta chislennyam Erbrana Gedelya V 1936 roci Stiven Koul Klini poshiriv ponyattya zagalnorekursivnoyi funkciyi na vipadok chastkovih funkcij vvivshi ponyattya chastkovo rekursivnoyi funkciyi ta opisav klas takih funkcij v chisto funkcionalnih terminah V 1943 roci Emil Post zaproponuvav model obchislyuvanih funkcij na osnovi vvedenogo nim chislennya specialnogo viglyadu kanonichnih sistem Dlya formalizaciyi samogo ponyattya algoritmu buli zaproponovani tochni matematichni opisi algoritmichnoyi mashini ta obchislyuvanosti na nij Pershoyu formalnoyu modellyu algoritmichnoyi mashini bula mashina Tyuringa Alan Tyuring Emil Post 1936 Iz piznishih modelej vidznachimo normalni algoritmi A Markov 1952 ta registrovi mashini 1963 V 1936 r A Cherch ta S Klini doveli zbig klasiv zagalno rekursivnih ta l oznachuvanih funkcij Na osnovi cogo faktu ta analizu idej yaki priveli do vkazanih ponyat A Cherch visunuv tezu pro zbig klasu AOF z klasom zagalnorekursivnih funkcij S Klini uzagalniv cyu tezu dlya vipadku chastkovih funkcij Dovedenij A Tyuringom v 1937 r zbig klasiv chastkovo rekursivnih funkcij ta funkcij obchislyuvanih na mashinah Tyuringa stalo she odnim pidtverdzhennyam tezi Chercha Piznishe taki zbigi buli vstanovleni dlya vsih vidomih formalnih modelej AOF Tomu ye vsi pidstavi vvazhati sho kozhna iz nazvanih vishe formalnih modelej adekvatno utochnyuye intuyitivne ponyattya AOF Teoriya algoritmiv vinikla yak rozdil matematichnoyi logiki ponyattya algoritmu tisno pov yazane z ponyattyam chislennya Pershi ta najchiselnishi zastosuvannya teoriya algoritmiv maye same v matematichnij logici Teoriya algoritmiv ye teoretichnim fundamentom programuvannya vona maye zastosuvannya vsyudi de zustrichayutsya algoritmichni problemi osnovi matematiki teoriya informaciyi teoriya keruvannya obchislyuvalna matematika teoriya jmovirnosti lingvistika ekonomika ta in Osnovni ponyattya teoriyi algoritmivOblastyu zastosovnosti algoritmu nazivayetsya sukupnist tih ob yektiv do yakih jogo mozhna zastosuvati tobto v zastosuvanni do yakih vin daye rezultat Pro algoritm U kazhut sho vin 1 obchislyuye funkciyu f koli jogo oblast zastosuvannya zbigayetsya z oblastyu viznachennya f i U peretvoryuye bud yakij h zi svoyeyi oblasti zastosuvannya v f h 2 rozv yazuye mnozhinu A vidnosno mnozhini X koli vin zastosovuyetsya do bud yakogo h z X i peretvoryuye bud yakij h zX A na slovo tak a bud yakij h z H A na slovo ni 3 pererahovuye mnozhinu B koli jogo oblast zastosuvannya ye naturalnij ryad a sukupnist rezultativ ye B Funkciya naz obchislyuvanoyu yaksho isnuye algoritm sho yiyi obchislyuye Mnozhina nazivayetsya rozv yaznoyu vidnosno X yaksho isnuye algoritm sho rozv yazuye yiyi vidnosno X Mnozhina naz pererahovuvanoyu yaksho abo vona porozhnya abo isnuye pererahovuyuchij yiyi algoritm Detalnij analiz ponyattya algoritm viyavlyaye sho I oblast mozhlivih vihidnih danih i oblast zastosovnosti bud yakogo algoritmu ye pererahovuvanimi mnozhinami Svoyeyu chergoyu II dlya bud yakoyi pari vkladenih odna v drugu pererahovuvanih mnozhin mozhna pidibrati algoritm u yakogo bilsha mnozhina sluguye oblastyu mozhlivih vihidnih danih a mensha oblastyu zastosovnosti Mayut misce taki osnovni teoremi III funkciya f obchislyuvana todi i tilki todi koli pererahovuvanij yiyi grafik tobto mnozhina vsih par viglyadu lt h f x gt IV Pidmnozhina A pererahovuvanoyi mnozhini X todi i tilki todi rozv yazna vidnosnoX koli A i X A pererahovuvani V Yaksho A i V pererahovuvani to A ob yednati B i A B takozh pererahovuvani VI V kozhnij neskinchennij pererahovuvanij mnozhini X isnuye pererahovuvana pidmnozhina z nepererahovuvanim dopovnennyam v silu IV cya pererahovuvana pidmnozhina bude nerozv yaznoyu vidnosno X VII Dlya kozhnoyi neskinchennoyi pererahovuvanoyi mnozhiniX isnuye obchislyuvana funkciya viznachena na pidmnozhini ciyeyi mnozhini i yaka ne prodovzhuvana do obchislyuvanoyi funkciyi viznachenoyi na vsij X Tverdzhennya VI i II v sukupnosti dayut priklad algoritmu z nerozv yaznoyu oblastyu zastosovuvanosti Rozv yazni i pererahovuvani mnozhini skladayut najprostishi i najvazhlivishi prikladi mnozhin struktura yakih zadayetsya za dopomogoyu tih chi tih algoritmichnih procedur Sistematichne vivchennya mnozhin konstruktivnih ob yektiv z tochki zoru takih vlastivostej cih mnozhin yaki zv yazani z nayavnistyu tih chi tih algoritmiv utvoryuye tak zvanu Teoriyu algoritmiv mozhna rozdiliti na deskriptivnu yakisnu i metrichnu kilkisnu Persha doslidzhuye algoritmi z tochki zoru vstanovlyuvanoyi nimi vidpovidnosti mizh vihidnimi danimi i rezultatami do neyi nalezhat zokrema problemi pobudovi algoritmu sho jomu vlastivi ti chi ti vlastivosti algoritmichni problemi Druga doslidzhuye algoritmi z tochki zoru skladnosti yak samih algoritmiv tak i obchislen sho nimi zadayutsya tobto procesiv poslidovnogo peretvorennya konstruktivnih ob yektiv div Skladnist algoritmu Vazhlivo pidkresliti sho yak skladnist algoritmiv tak i skladnist obchislen mozhut viznachatisya riznimi sposobami Rozrobka metodiv ocinki skladnosti algoritmiv i obchislen maye vazhlive teoretichne i praktichne znachennya Formalizaciya ponyattya algoritmu Sered inshih poshirenih matematichnih modelej algoritmiv mozhna nazvati Merezhi Petri opisani Karlom Petri v 1962 roci yak i mashini Tyuringa mayut rizni formi zvichajni ta z obmezhennyami regulyarni vilni rozfarbovani samo zminyuvani tosho Vektorni mashini zaproponovani Prattom Rabinom Stokmayerom v 1974 roci Nejronni merezhi najprostishi modeli z yavilis v 1943 r z poyavoyu statti nejrofiziologa Uorrena Makkaloha i matematika Podibno do mashini Tyuringa isnuye kilka riznovidiv zi stalimi vagami z kerovanim ta nekerovanim navchannyam z pryamim poshirennyam abo rekurentni Avtomat fon Nejmana ta zagalni klitinni avtomati Zaproponovane Kolmogorovim viznachennya algoritmu v 1953 roci skinchenni avtomati pershi praci pro yaki zazvichaj pripisuyut Makkalohu i praci z formalnim opisom strukturi buli napisani Stivenom Klini ta Murom Podibno do mashin Tyuringa skinchenni avtomati takozh mayut nizku riznovidiv bez pam yati avtonomni bez vivedennya abo prijmalni avtomati determinovani ta nedeterminovani stohastichni avtomati tosho zaproponovana Marvinom Minskim v 1967 roci zi zminyuvanoyu pam yattyu abo tak zvani zaproponovani v 1980 roci RAM zaproponovani Sheferdsonom ta Stargisom v 1963 roci z variantami RASP zaproponovani Elgotom i Robinsonom v 1964 roci paralelni rivnodostupni mashini PRAM Mashini obrobki masiviv opisani Lovenom ta Vidermanom v 1985 roci Bagatovimirna model obchislen ta obchislvalnih sistem rozroblena M S Burginim ta A Yu Karasikom Sistolichnij masiv zaproponovani Kungom ta Lejsersonom v 1978 roci Mashini sho zminyuyut aparatne zabezpechennya opisani Dajmondom ta Kukom v 1989 roci Chislennya Posta zaproponovane Emilem Postom v 1943 roci Normalni algoritmi Markova zaproponovani A Markovim v 1954 roci Formalni gramatiki yaki podibno do mashin Tyuringa mayut nizku riznovidiv regulyarni kontekstno vilni kontekstno zalezhni tosho Modeli obchislenMashina Tyuringa abstraktnij vikonavec abstraktna obchislyuvalna mashina Bula zaproponovana Alanom Tyuringom v 1936 roci dlya formalizaciyi ponyattya algoritmu Mashina Tyuringa ye rozshirennyam kincevogo avtomata i zgidno z tezoyu Chercha Tyuringa zdatna imituvati vsi inshi vikonavci za dopomogoyu zavdannya pravil perehodu bud yakim chinom realizuyut proces pokrokovogo obchislennya v yakomu kozhen krok obchislennya dosit elementarnij Lyambda chislennya rozglyadayetsya para l viraz i jogo argument a obchislennyam vvazhayetsya zastosuvannya abo appliciruvannya pershogo chlena pari do drugogo Ce dozvolyaye vidokremiti funkciyu i te do chogo vona zastosovuyetsya U bilsh zagalnomu vipadku obchislennyam vvazhayutsya lancyuzhki sho pochinayutsya z vihidnogo l virazu za yakim sliduye kinceva poslidovnist l viraziv kozhne z yakih vihodit z poperednogo zastosuvannya b redukciyi tobto pravila pidstanovki Kombinatorna logika traktuvannya obchislennya podibne do l obchislen ale ye i vazhlivi vidminnosti napriklad kombinator neruhomoyi tochki Y maye normalnu formu v kombinatornij logici a v l chislenni ne maye Kombinatorna logika bula spochatku rozroblena dlya vivchennya prirodi paradoksiv i dlya pobudovi konceptualno yasnih pidstav matematiki prichomu uyavlennya pro zminnu viklyuchalosya zovsim sho dopomagalo proyasniti rol i misce zminnih v matematici RAM mashina abstraktna obchislyuvalna mashina sho modelyuye komp yuter z dovilnim dostupom do pam yati Same cya model obchislen najbilsh chasto vikoristovuyetsya pri analizi algoritmiv Teza Chercha Tyuringa i algoritmichno nerozv yazni problemiAlan Tyuring visloviv pripushennya vidome yak Teza Chercha Tyuringa sho bud yakij algoritm v intuyitivnomu sensi cogo slova mozhe buti predstavlenij ekvivalentnoyu mashinoyu Tyuringa Utochnennya uyavlennya pro obchislyuvanosti na osnovi ponyattya mashini Tyuringa i inshih analogichnih yij ponyat vidkrilo mozhlivosti dlya suvorogo dokazu algoritmichnoyi nerozv yaznosti riznih masovih problem tobto problem pro znahodzhennya yedinogo metodu rishennya deyakogo klasu zadach umovi yakih mozhut zminyuvatisya v pevnih mezhah Najprostishim prikladom algoritmichno nerozv yaznoyi masovoyi problemi ye tak zvana problema zastosovnosti algoritmu zvana takozh problemoyu zupinki Vona polyagaye v nastupnomu potribno znajti spilnij metod yakij dozvolyav bi dlya dovilnoyi mashini Tyuringa zadanoyi za dopomogoyu svoyeyi programi i dovilnogo pochatkovogo stanu strichki ciyeyi mashini viznachiti chi zavershitsya robota mashini za kinceve chislo krokiv abo zh bude trivati neobmezheno dovgo Protyagom pershogo desyatilittya istoriyi teoriyi algoritmiv nerozv yazni masovi problemi buli viyavleni lishe vseredini samoyi ciyeyi teoriyi syudi vidnositsya opisana vishe problema zastosovnosti a takozh vseredini matematichnoyi logiki problema vivodu v klasichnomu chislenni predikativ Tomu vvazhalosya sho teoriya algoritmiv ye uzbichchya matematiki sho ne maye znachennya dlya takih yiyi klasichnih rozdiliv yak abstraktna algebra abo matematichnij analiz Polozhennya zminilosya pislya togo yak A A Markov i E L Post v 1947 roci vstanovili algoritmichnu nerozv yaznist vidomoyi v algebri problemi rivnosti dlya kincevo stvorenih i kincevo viznachenih napivgrup t z Zgodom bulo vstanovleno algoritmichna nerozv yaznist i bagatoh inshih chisto matematichnih masovih problem Odnim z najbilsh vidomih rezultativ v cij oblasti ye dovedena Yu V Matiyasevich algoritmichna nerozv yaznist desyatoyi problemi Gilberta Zastosuvannya teoriyi algoritmivU vsih galuzyah matematiki v yakih zustrichayutsya algoritmichni problemi Taki problemi vinikayut praktichno v usih rozdilah matematiki V matematichnij logici dlya kozhnoyi teoriyi formulyuyetsya problema rozv yazuvannya mnozhini vsih istinnih abo dovidnih tverdzhen ciyeyi teoriyi vidnosno mnozhini vsih yiyi propoziciyi teoriyi podilyayutsya na rozv yazni i nerozv yazni v zalezhnosti vid rozv yaznosti abo nerozv yaznosti vkazanoyi problemi u 1936 r A Cherch vstanoviv nerozv yaznist problemi rozv yaznosti dlya mnozhini vsih istinnih propozicij logiki predikativ podalshi vazhlivi rezultati v comu napryami nalezhat A Tarskomu A I Malcevu ta inshi Nerozv yazni algoritmichni problemi zustrichayutsya v algebri problema totozhnosti dlya napivgrup i zokrema dlya grup pershi prikladi napivgrup z nerozv yaznoyu problemoyu totozhnosti buli vinajdeni v 1947 r nezalezhno A A Markovim i E Postom a priklad grupi z nerozv yaznoyu problemoyu totozhnosti v 1952 r v topologiyi problema gomeomorfiyi nerozv yaznist yakoyi dlya vazhlivogo klasu vipadkiv bula dovedena v 1958 r A A Markovim v teoriyi chisel problema rozv yaznosti diofantovih rivnyan nerozv yaznist yakoyi bula vstanovlena v 1970 r Yu V Matiyasevichem ta v inshih rozdilah matematiki Teoriya algoritmiv tisno zv yazana z matematichnoyu logikoyu oskilki v terminah algoritmiv mozhe buti vikladeno odne z centralnih ponyat matematichnoyi logiki ponyattya chislennya i tomu napriklad teorema Gedelya pro nepovnotu formalnih sistem mozhe buti oderzhana yak naslidok teorem teoriyi algoritmiv z osnovami matematiki v yakih odne z centralnih misc zajmaye problema spivvidnoshennya konstruktivnogo i nekonstruktivnogo zokrema teoriya algoritmiv nadaye aparat neobhidnij dlya rozrobki konstruktivnogo napryamu v matematici v 1965 r A M Kolmogorov zaproponuvav vikoristovuvati teoriyu algoritmiv dlya obgruntuvannya teoriyi informaciyi z kibernetikoyu v yakij vazhlive misce zajmaye vivchennya Teoriya algoritmiv utvoryuye teoretichnij fundament dlya nizki pitan obchislyuvalnoyi matematiki Suchasnij stan teoriyi algoritmivV danij chas teoriya algoritmiv rozvivayetsya golovnim chinom za troma napryamkami Klasichna teoriya algoritmiv vivchaye problemi formulyuvannya zavdan v terminah formalnih mov vvodit ponyattya zavdannya dozvolu provodit klasifikaciyu zadach za klasami skladnosti P NP i in Teoriya asimptotichnogo analizu algoritmiv rozglyadaye metodi otrimannya asimptotichnih ocinok yemnosti abo chasu vikonannya algoritmiv zokrema dlya rekursivnih algoritmiv Asimptotichnij analiz dozvolyaye ociniti zrostannya potrebi algoritmu v resursah napriklad chasu vikonannya zi zbilshennyam obsyagu vhidnih danih Teoriya praktichnogo analizu obchislyuvalnih algoritmiv virishuye zavdannya otrimannya yavnih funkciyi trudomistkosti intervalnogo analizu funkcij poshuku praktichnih kriteriyiv yakosti algoritmiv rozrobki metodiki viboru racionalnih algoritmiv Analiz trudomistkosti algoritmiv Metoyu analizu trudomistkosti algoritmiv ye znahodzhennya optimalnogo algoritmu dlya virishennya danogo zavdannya Yak kriterij optimalnosti algoritmu vibirayetsya trudomistkist algoritmu sho rozumiyetsya yak kilkist elementarnih operacij yaki neobhidno vikonati dlya virishennya zadachi za dopomogoyu danogo algoritmu Funkciyeyu trudomistkosti nazivayetsya vidnoshennya sho zv yazuyut vhidni dani algoritmu z kilkistyu elementarnih operacij Trudomistkist algoritmiv po riznomu zalezhit vid vhidnih danih Dlya deyakih algoritmiv trudomistkist zalezhit tilki vid obsyagu danih dlya inshih algoritmiv vid znachen danih v deyakih vipadkah poryadok nadhodzhennya danih mozhe vplivati na trudomistkist Trudomistkist bagatoh algoritmiv mozhe v tij chi inshij miri zalezhati vid vsih pererahovanih vishe faktoriv Odnim z sproshenih vidiv analizu sho vikoristovuyutsya na praktici ye asimptotichnij analiz algoritmiv Metoyu asimptotichnogo analizu ye porivnyannya vitrat chasu ta inshih resursiv riznimi algoritmami priznachenimi dlya virishennya odniyeyi i tiyeyi zh zadachi pri velikih obsyagah vhidnih danih Vikoristovuvana v asimptotichnomu analizi ocinka funkciyi trudomistkosti zvana skladnistyu algoritmu dozvolyaye viznachiti yak shvidko zrostaye trudomistkist algoritmu zi zbilshennyam obsyagu danih U asimptotichnomu analizi algoritmiv vikoristovuyutsya poznachennya prijnyati v matematichnomu asimptotichnomu analizi Nizhche pererahovani osnovni ocinki skladnosti Osnovnoyu ocinkoyu funkciyi skladnosti algoritmu f n ye ocinka 8 displaystyle boldsymbol Theta Tut n velichina obsyagu danih abo dovzhina vhodu Mi govorimo sho ocinka skladnosti algoritmu f n 8 g n displaystyle f n boldsymbol Theta g n yaksho pri g gt 0 pri n gt 0 isnuyut dodatni s1 s2 n0 taki sho c 1 g n f n c 2 g n displaystyle c 1 g n leq f n leq c 2 g n pri n gt n0 inakshe kazhuchi mozhna znajti taki s1 i c2 sho pri dostatno velikih n f n bude znahoditis mizh c 1 g n displaystyle boldsymbol c 1 g n i c 2 g n displaystyle boldsymbol c 2 g n U takomu vipadku govoryat she sho funkciya g n ye asimptotichno tochnoyu ocinkoyu funkciyi f n tak yak za viznachennyam funkciya f n ne vidriznyayetsya vid funkciyi g n z tochnistyu do postijnogo mnozhnika Napriklad dlya metodu sortuvannya heapsort ocinka trudomistkosti stanovit f n 8 n log n displaystyle f n boldsymbol Theta n log n to ye g n n log n displaystyle g n n log n Iz f n 8 g n displaystyle f n boldsymbol Theta g n viplivaye sho g n 8 f n displaystyle g n boldsymbol Theta f n Vazhlivo rozumiti sho 8 g n displaystyle boldsymbol Theta g n ce ne funkciya a bezlich funkcij sho opisuyut zrostannya f n displaystyle boldsymbol f n z tochnistyu do postijnogo mnozhnika 8 displaystyle boldsymbol Theta daye odnochasno verhnyu i nizhnyu ocinki zrostannya funkciyi Chasto buvaye neobhidno rozglyadati ci ocinki okremo Ocinka O displaystyle boldsymbol O ce verhnya asimptotichna ocinka trudomistkosti algoritmu Mi govorimo sho f n O g n displaystyle f n boldsymbol O g n yaksho c gt 0 n 0 gt 0 0 f n c g n n gt n 0 displaystyle exists c gt 0 n 0 gt 0 0 leq f n leq cg n forall n gt n 0 Inakshe kazhuchi zapis f n O g n displaystyle f n boldsymbol O g n oznachaye sho f n nalezhit klasu funkcij sho rostut ne shvidshe nizh funkciya g n z tochnistyu do postijnogo mnozhnika Ocinka W displaystyle boldsymbol Omega zadaye nizhnyu asimptotichnu ocinku zrostannya funkciyi f n i viznachaye klas funkcij yaki rostut ne povilnishe nizh g n z tochnistyu do postijnogo mnozhnika f n W g n displaystyle f n boldsymbol Omega g n yaksho c gt 0 n 0 gt 0 0 c g n f n n gt n 0 displaystyle exists c gt 0 n 0 gt 0 0 leq cg n leq f n forall n gt n 0 Napriklad zapis f n W n log n displaystyle f n boldsymbol Omega n log n poznachaye klas funkcij yaki rostut ne povilnishe nizh g n n log n displaystyle boldsymbol g n n log n v cej klas potraplyayut vsi polinomi zi stupenem bilshoyi odinici tak samo yak i vsi statichni funkciyi z povnim pravom velikoyi odinici Rivnist f n 8 g n displaystyle f n boldsymbol Theta g n vikonuyetsya todi i tilki todi koli f n O g n displaystyle f n boldsymbol O g n i f n W g n displaystyle f n boldsymbol Omega g n Asimptotichnij analiz algoritmiv maye ne tilki praktichne ale i teoretichne znachennya Napriklad dovedeno sho vsi algoritmi sortuvannya zasnovani na poparnomu porivnyanni elementiv vidsortuyut n elementiv za chas ne menshe W n log n displaystyle boldsymbol Omega n log n Vazhlivu rol u rozvitku asimptotichnogo analizu algoritmiv zigrali A Aho Dzh Ulman Dzh Gopkrofta Klasi skladnosti V ramkah klasichnoyi teoriyi zdijsnyuyetsya klasifikaciya zavdan za klasami skladnosti P skladni NP skladni eksponencialno skladni i in Do klasu P vidnosyatsya zavdannya yaki mozhut buti virisheni za chas zalezhne vid obsyagu vihidnih danih za dopomogoyu determinovanoyi obchislyuvalnoyi mashini napriklad mashini Tyuringa a do klasu NP zavdannya yaki mozhut buti virisheni za virazhenij chas za dopomogoyu nedeterminovanoyi obchislyuvalnoyi mashini tobto mashini nastupnij stan yakoyi ne zavzhdi odnoznachno viznachayetsya poperednimi Robotu takoyi mashini mozhna uyaviti yak rozgaluzhuyetsya na kozhnij neodnoznachnosti procesu zavdannya vvazhayetsya virishenim yaksho hocha b odna gilka procesu prijshla do vidpovidi Inshe viznachennya klasu NP do klasu NP vidnosyatsya zavdannya virishennya yakih za dopomogoyu dodatkovoyi informaciyi dovzhini danoyi nam zgori mi mozhemo pereviriti za polinomialnij chas Zokrema do klasu NP vidnosyatsya vsi zavdannya virishennya yakih mozhna pereviriti za polinomialnogo chasu Klas P mistitsya v klasi NP Klasichnim prikladom NP zadachi ye zadacha pro komivoyazhera Oskilki klas P mistitsya v klasi NP prinalezhnist togo chi inshogo zavdannya do klasu NP chasto vidobrazhaye nashe potochne uyavlennya pro sposobi virishennya danogo zavdannya i nosit neostatochnij harakter U zagalnomu vipadku nemaye pidstav vvazhati sho dlya togo chi inshogo NP zavdannya ne mozhe buti znajdeno P rishennya Pitannya pro mozhlivist ekvivalentnosti klasiv P i NP tobto pro mozhlivist znahodzhennya P rishennya dlya bud yakoyi NP zadachi vvazhayetsya odnim z osnovnih pitan suchasnoyi teoriyi skladnosti algoritmiv Vidpovid na ce pitannya ne znajdena dosi Sama postanovka pitannya pro ekvivalentnist klasiv P i NP mozhliva zavdyaki vvedennyu ponyattya NP povnih zadach NP povni zadachi skladayut pidmnozhina NP zadach i vidriznyayutsya tiyeyu vlastivistyu sho vse NP zavdannya mozhut buti tim chi inshim sposobom zvedeni do nih Z cogo viplivaye sho yaksho dlya NP povnoyi zadachi bude znajdeno P rishennya to P rishennya bude znajdeno dlya vsih zavdan klasu NP Prikladom NP povnoyi zadachi ye zadacha pro kon yunktivni formi Doslidzhennya skladnosti algoritmiv dozvolili po novomu poglyanuti na virishennya bagatoh klasichnih matematichnih zadach i znajti dlya ryadu takih zavdan mnozhennya mnogochleniv i matric rishennya linijnih sistem rivnyan i in Rishennya yaki vimagayut menshe resursiv nizh tradicijni Matematichni zastosuvannya teoriyi algoritmivDoslidzhennya masovih problem Zastosuvannya v osnovah matematiki konstruktivna semantika Zastosuvannya v matematichnij logici analiz formalizovanih mov logiki i arifmetiki Analiz obchislyuvanosti Numerovani strukturi Zastosuvannya v teoriyi jmovirnostej viznachennya vipadkovoyi poslidovnosti Zastosuvannya v teoriyi informaciyi algoritmichnij pidhid do ponyattya kilkosti informaciyi Ocinennya skladnosti rozv yazuvannya okremih zadach Vpliv teoriyi algoritmiv na algoritmichnu praktiku PrimitkiBurgin M S 2005 2 2 Mathematical models of algorithms and why we need them Super recursive algorithms Monographs in computer science New York NY Springer ISBN 978 0 387 95569 8 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 V Pratt M Rabin L Stockmeyer A charaterization of the power of vector machines Proc SToC 74 pp 122 134 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 Kolmogorov A N 1953 On the concept of algorithm Russian Mathematical Surveys v 8 no 4 pp 175 176 1958 g iyul avgust t XIII vyp 4 82 USPEHI MATEMATIChESKIH NAUK K OPREDELENIYu ALGORITMA A N Kolmogorov i V A Uspenskij http lpcs math msu su uspensky bib Uspensky 1958 UMN Kolmogorov Opredelenie algoritma pdf 13 travnya 2016 u Wayback Machine 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 Minsky Marvin 1967 Computation finite and infinite machines Englewood Cliffs NJ Prentice Hall ISBN 978 0 13 165563 8 Shonhage A 1980 Storage modification machines SIAM Journal on Computing v o 9 pp 490 508 Shepherdson J C and Sturgis H E 1963 Computability of recursive functions Journal of the ACM v 10 no 2 pp 217 255 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 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 Burgin M S A Yu Karasik Issledovanie odnoj abstraktnoj modeli vychislitelnyh sistem Programmirovanie 1975 1 S 72 82 http www mathnet ru php archive phtml wshow paper amp jrnid at amp paperid 8035 amp option lang rus 14 travnya 2016 u Wayback Machine 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 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 Dymond P W and Cook S A 1989 Complexity theory of parallel time and hardware Information and Computation v 80 pp 205 226 Formal Reductions of the General Combinatorial Decision Problem American Journal of Mathematics 65 2 197 215 1943 A A Markov Teoriya algorifmov Tr MIAN SSSR 42 Izd vo AN SSSR M L 1954 3 375 http mi mathnet ru tm1178 Chomsky N 1956 Three models for the description of language IRE Trans On Information Theory v 2 no 3 pp 113 124 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 Naur P et al 1960 Report on the algorithmic language ALGOL 60 Communications of the ACM v 3 no 5 pp 299 314 PosilannyaBondarchuk Yu V Lekciyi z teoriyi algoritmiv 27 veresnya 2016 u Wayback Machine Kiyevo Mogilyanska Akademiya ukr LiteraturaUkrayinskoyu L M Klakovich S M Levicka Teoriya algoritmiv Navchalnij posibnik Druge vidannya dopovnene Lviv Vidavnichij centr LNU im Ivana Franka 2015 161 s ISBN 9786171002302 ukr Enciklopediya kibernetiki vidpovidalnij red V Glushkov 2 tt 1973 ukr Inshimi movami Michael Sipser Introduction to the Theory of Computation Boston PWS Publishing Company 1997 387 s ISBN 0 534 94728 X angl Vejl G O filosofii matematiki per s nem M L 1934 Markov A A Nagornyj N M Teoriya algoritmov M 1984 Malcev A I Algoritmy i rekursivnye funkcii M 1965 Rodzhers X Teoriya rekursivnyh funkcij i effektivnaya vychislimost per s angl M 1972 Uspenskij V A Mashina Posta M 1979 ego zhe Teorema Gyodelya o nepolnote M 1982 Problemy matematicheskoj logiki Slozhnost algoritmov i klassy vychislimyh funkcij Sb perevodov M 1970 Kolmogorov A N Problemy peredachi informacii 1965 t 1 1 s 3 11 Algoritmy v sovremennoj matematike i ee prilozheniyah ch 1 2 Novosib 1982 Uspenskij V A Semenov A L Kvant 1985 7 s 9 15 Div takozhSpisok algoritmiv Teoriya skladnosti obchislen Asociativne chislennya Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno gruden 2015 Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi