Користувач:Тарас Огар

Теорія алгоритмів

Теорія алгоритмів - наука, яка знаходиться на стику математики та інформатики, що вивчає загальні властивості та закономірності алгоритмів і різноманітні формальні моделі їх подання. До завдань теорії алгоритмів відносяться формальний доказ алгоритмічної нерозв'язності завдань, асимптотичний аналіз складності алгоритмів, класифікація алгоритмів відповідно до класів складності, розробка критеріїв порівняльної оцінки якості алгоритмів і т. П. Разом з математичною логікою теорія алгоритмів утворює теоретичну основу обчислювальних наук.

Виникнення теорії алгоритмів

Розвиток теорії алгоритмів починається з доказу К. Геделем теорем про неповноту формальних систем, що включають арифметику, перша з яких була доведена в 1931 р. Виникненні у зв'язку з цими теоремами припущення про неможливість алгоритмічного розв'язання багатьох математичних проблем (зокрема, проблеми виводимості в численні предикатів ) викликало необхідність стандартизації поняття алгоритму. Перші стандартизовані варіанти цього поняття були розроблені в 30-х роках XX століття в роботах А. Тьюринга, А. Черча і Е. Посту. Запропоновані ними: машина Тьюринга, машина Посту і лямбда-числення Черча виявилися еквівалентними один одному. Грунтуючись на роботах Геделя, С. Кліні ввів поняття рекурсивної функції, також виявилося еквівалентним вище переліченим.

Одним з найбільш вдалих стандартизованих варіантів алгоритму є введене А. А. Марковим поняття нормального алгоритму. Воно було розроблено десятьма роками пізніше робіт Тьюринга, Посту, Черча і Кліні в зв'язку з доказом алгоритмічної нерозв'язності низки алгебраїчних проблем.

Слід зазначити також чималий внесок в теорію алгоритмів, зроблений Д. Кнутом, A. Ахо і Дж. Ульманом. Однією з кращих робіт на цю тему є книга «Алгоритми: побудова й аналіз» Томаса Х. Кормена, Чарльза І. Лейзерсон, Рональда Л. Ривеста, Кліффорда Штайна.

Моделі обчислень

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

Теза Черча - Тьюринга і алгоритмічно нерозв'язні проблеми

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

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

Сучасний стан теорії алгоритмів

В даний час теорія алгоритмів розвивається, головним чином, за трьома напрямками.

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

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

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

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

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

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

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

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

$f(n)={\boldsymbol {\Theta }}(g(n))$

якщо при g > 0 при n > 0 існують додатні с₁, с₂, n₀, такі, що:

$c_{1}g(n)\leq \;f(n)\leq \;c_{2}g(n)$

при n > n₀, інакше кажучи, можна знайти такі с₁ і c₂, що при достатньо великих n f(n) буде знаходитьсь між

${\boldsymbol {c_{1}\;g(n)}}$ і ${\boldsymbol {c_{2}\;g(n)}}$.

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

$f(n)={\boldsymbol {\Theta }}(n\log n)$ то є $g(n)=n\log n$

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

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

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

$\exists \;c>0,n_{0}>0:0\leq \;f(n)\leq \;cg(n),\forall \;n>n_{0}$

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

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

$\exists \;c>0,n_{0}>0:0\leq \;cg(n)\leq \;f(n),\forall \;n>n_{0}$

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

Асимптотичний аналіз алгоритмів має не тільки практичне, але і теоретичне значення. Так, наприклад, доведено, що всі алгоритми сортування, засновані на попарному порівнянні елементів, відсортують n елементів за час, не менше ${\boldsymbol {\Omega }}(n\log 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-повної задачі є задача про кон'юнктивні форми.

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

Математичні додатки теорії алгоритмів

1. Дослідження масових проблем.
2. Додатки до підстав математики: конструктивна семантика.
3. Додатки до математичної логіки: аналіз формалізованих мов логіки і арифметики.
4. Обчислюваності аналіз.
5. Нумеровані структури.
6. Додатки до теорії ймовірностей: визначення випадкової послідовності.
7. Додатки до теорії інформації: алгоритмічний підхід до поняття кількості інформації.
8. Оцінки складнощів рішення окремих завдань.
9. Вплив теорії алгоритмів на алгоритмічну практику.

Література

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М. : Вильямс, 2006. — С. 1296. — ISBN 0-07-013151-1.
• Дональд Кнут. Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М. : Вильямс, 2006. — С. 720. — ISBN 0-201-89683-4.
• Колмогоров А. Н. Теория информации и теория алгоритмов. — М. : Наука, 1987. — 304 с.
• Марков А. А., Нагорный Н. М. Теория алгорифмов. — 2-е изд.. — М. : ФАЗИС, 1996.