Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

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


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

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

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

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


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

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

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

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

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


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

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

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

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

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

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

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

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

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

якщо при g> 0 при n> 0 існують позитивні з 1, с 2, n 0, такі, що:

c_1 g (n) \ le \; f (n) \ le \; c_2 g (n)

при n> n 0, інакше кажучи, можна знайти такі з 1 і c 2, що при достатньо великих nf (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 \ le \; f (n) \ le \; 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 \ le \; cg (n) \ le \; 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.Ахо, Дж. Ульман, Дж. Хопкрофта.


4.2. Класи складності

У рамках класичної теорії здійснюється класифікація завдань за класами складності ( 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-повної задачі є задача про кон'юнктівной формі

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


Література

  • Томас Х. Кормен, Чарльз І. Лейзерсон, Рональд Л. Ривест, Кліффорд Штайн Алгоритми: побудова й аналіз = 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.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Алгебра алгоритмів
Розробка алгоритмів
Список алгоритмів
Псевдокод (мова опису алгоритмів)
Перелік основних розділів теорії алгоритмів
М-теорія
Теорія 4P
Теорія
© Усі права захищені
написати до нас
Рейтинг@Mail.ru