bigpo.ru
добавить свой файл
1
/*


Реферат з ПЗІС


На тему:


Складність алгоритмів. Методи аналізу алгоритмів. Рекурентніспіввідношення: методи пістановки, ітераціј. Основна теорема про
рекурентні співввідношення.


Виконав студент ФІН-5

Науменко Тарас


Київ – 2008



  1. Вступ.


Теорія алгоритмів (англ. Theory of computation) як окремий розділ математики, що вивчає загальні властивості алгоритмів, виникла в 30-х роках 20 століття. Алгоритми, проте, простежуються в математиці протягом всього часу її існування. Необхідність точного математичного уточнення інтуїтивного поняття алгоритму стала неминучою після усвідомлення неможливості існування алгоритмів розв’язку багатьох масових проблем, в першу чергу пов'язаних з арифметикою та математичною логікою (проблеми істинності арифметичних формул та формул першопорядкового числення предикатів, 10-та проблема Гільберта про розв'язність діофантових рівнянь та ін.). Для доведення неіснування алгоритму треба мати його точне математичне визначення, тому після сформування поняття алгоритму як нової та окремої сутності першочерговою стала проблема знаходження адекватних формальних моделей алгоритму та дослідження їх властивостей. При цьому формальні моделі були запропоновані як для первісного поняття алгоритму, так і для похідного поняття алгоритмічно обчислюваної функції. Вперше поняття алгоритму з’явилося в працях Е. Бореля (1912) та Г. Вейля (1921).

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

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

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

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


^

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


Областю застосовності алгоритму називається сукупність тих об’єктів, до яких його можна застосувати, тобто в застосуванні до яких він дає результат. Про алгоритм 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) в сукупності дають приклад алгоритму з нерозв’язною областю застосовуваності.

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

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

  1. Поняття складності алгоритму.



Основними мірами обчислювальної складності алгоритму є:

1. Часова складність, яка характеризує час, необхідний для

виконання алгоритму на даному комп’ютері. Цей час визначається кількістю

операцій, які потрібно виконати для реалізації алгоритму.

2. Ємнісна складність, яка характеризує обсяг пам’яті, необхідної

для виконання алгоритму.

Обидві складності є функціями від кількості вхідних даних. Як

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

Складність буває взалежності від функції:

1) Логарифмічною f(n)=0(n):

2) Лінійною

3) Поліноміальною

4) Експоненціальною

В теорії алгоритмів відрізняють три головні напрями побудови

теоретичних моделей алгоритмів. Перший напрям пов’язаний з тим, що будь-

які дані можуть бути закодовані числами, тоді кожне перетворення даних

може бути зведене до арифметичного обчислення, тобто кожен алгоритм

буде знаходити значення деякої числової функції. Послідовність

елементарних кроків в таких моделях визначається за допомогою

суперпозиції функції чи рекурсії.

Суперпозиція – це підстановка одних функцій в інші. Суперпозиція

породжує математичні формули.

X=Y+Z

X=U-T

Z=V*W

(U-T)*Y+V*W…

Рекурсія – це обчислення наступного значення функції з

використанням отриманого раніше її значення.

n!=1,2,3,…n

f(0)=1

f(n+1)=(n+1)f(n)

1 …

2

3

4

5



n

Другий напрям побудови теоретичних моделей алгоритмів

пов’язаний з допущенням, що будь-який алгоритм може бути представлений,

як послідовне перетворення вхідних слів, що складені із символами

скінченого алфавіту. Це так звані нормальні алгоритми.

В третьому напрямі побудови теоретичних моделей алгоритмів

передбачається, що кожен крок алгоритму може бути виконаний нескладним

пристроєм (машиною, бажано універсальною) , тобто здатним виконати

будь-який алгоритм. Такий пристрій вперше запропонував у 1936 році Еміль

Пост, у цьому ж році схожу машину представив і Тьюринг.

^

4.Аналіз алгоритмів та методи аналізу


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

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

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

Основной оценкой функции сложности алгоритма 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 оцінка трудомісткості складаєто есть g(n) = nlogn

Из следует, что .

Важно понимать, что представляет собой не функцию, а множество функций, описывающих рост с точностью до постоянного множителя.

дает одновременно верхнюю и нижнюю оценки роста функции. Часто бывает необходимо рассматривать эти оценки по отдельности. Оценка представляет собой верхнюю асимптотическую оценку трудоемкости алгоритма. Мы говорим, что если



Иначе говоря, запись означает, что f(n) принадлежит классу функций, которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя.

Оценка задает нижнюю асимптотическую оценку роста функции f(n) и определяет класс функций, которые растут не медленнее, чем g(n) с точностью до постоянного множителя. если



Например, запись обозначает класс функций, которые растут не медленнее, чем , в этот класс попадают все полиномы со степенью большей единицы, равно как и все степенные функции с основанием большим единицы. Равенство выполняется тогда и только тогда, когда и .

Асимптотичний аналіз алгоритмів має не тільки практичне, але і теоретичне значення. Так, наприклад, доведено, що всі алгоритми сортування, засновані на попарному порівнянні елементів, відсортують n елементів за час, не менший .
^

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


В рамках класичної теорії здійснюється класифікація завдань по класах складності (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. Рекурентні співвідношення: методи пістановки, ітерації
^

Рекурентні співвідношення


При рішенні багатьох комбінаторних задач користуються методом зведення даного завдання до завдання, що стосується меншого числа предметів. Метод зведення до аналогічного завдання для меншого числа предметів називається методом рекурентних співвідношень (від латинського "recurrere" - "повертатися").

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

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

Пусть - число пар кроликов в популяции по прошествии месяцев, и пусть эта популяция состоит из пар приплода и "старых" пар, то есть . Таким образом, в очередном месяце произойдут следующие события: . Старая популяция в -й момент увеличится на число родившихся в момент времени . . Каждая старая пара в момент времени производит пару приплода в момент времени . В последующий месяц эта картина повторяется:





Объединяя эти равенства, получим следующее рекуррентное соотношение:



frame1Выбор начальных условий для последовательности чисел Фибоначчи не важен; существенное свойство этой последовательности определяется рекуррентным соотношением. Будем предполагать (иногда ).

Розглянемо це завдання небагато інакше.

Пара кроликів приносить раз на місяць приплід з двох крольчат (самки і самця), причому новонароджені крольчата через два місяці після народження вже приносять приплід. Скільки кроликів з'явиться через рік, якщо на початку року була одна пара кроликів?

З умови завдання виходить, що через місяць буде дві пари кроликів. Через два місяці приплід дасть тільки перша пара кроликів, і вийде 3 пари. А ще через місяць приплід дадуть і початкова пара кроликів, і пара кроликів, що з'явилася два місяці тому.Поэтому всего будет 5 пар кроликов. Обозначим через количество пар кроликов по истечении месяцев с начала года. Ясно, что через месяцев будут эти пар и еще столько новорожденных пар кроликов, сколько было в конце месяца , то есть еще пар кроликов. Иными словами, имеет место рекуррентное соотношение

frame2Так как, по условию, и , то последовательно находим



и т.д.

В частности, .

Числа называются числами Фибоначчи. Они обладают целым рядом замечательных свойств.

Метод ітерацій.

Це спосіб чисельного рішення математичних задач. Його суть – знаходження алгоритму пошуку по відомому наближенню (наближеному значенню) шуканої величини наступного, точнішого наближення. Застосовується у разі, коли послідовність наближень по вказаному алгоритму сходиться.

Даний метод називають також методом послідовних наближень, методом повторних підстановок, методом простих ітерацій і т.п.

Пояснимо суть методу на прикладі рішення рівняння
f(x) = 0. (1)

Будем вместо уравнения (1) рассматривать равносильное ему уравнение
х = F(x),   (2)
где F(x) = f(x) + х.

Пусть х0 – произвольное число (начальное приближение искомого корня уравнения (1)). Рассмотрим последовательность
х1 = F(x0), x2 = F(x1), …, xn= F(xn-1), …
Если эта последовательность имеет предел, то он и есть решение (корень) уравнения (2), а значит, и уравнения (1).



Процес складання послідовних наближень наочно показаний на мал., де крива – графік функції у = F(x), а пряма – бісектриса першого і третього координатних кутів (її рівняння у = х).

Последовательность {xn} сходится, например, если выполнены оба условия:
F(x) > x; ,
где ε > 0 – достаточно малое положительное число (в этом случае как раз и будет ситуация, изображенная на рис.).

Метод ітерації (підстановки).

Суть метода состоит в последовательной подстановке – итерации рекурсивного определения, с последующим выявлением общих закономерностей:

Пусть f(n)=3*f(n/4)+n, тогда:

f(n)=n+3*f(n/4)=n+3*[n/4+3*f(n/16)]=n+3*[n/4+3{n/16+3*f(n/64) }],

и раскрывая скобки, получаем:

f(n)=n+3*n/4+9*n/16+27*n/64+…+ *n/

Остановка рекурсии произойдет при , в этом случае последнее слагаемое не больше, чем

, то окончательно:




  1. ^

    Основная теорема о рекуррентных соотношениях


Следующая теорема принадлежит Дж. Бентли, Д. Хакен и Дж. Саксу (1980 г.).

Теорема.Пусть a >= 1, b > 1 - константы, g(n) - функция, пусть далее:

f(n)=a*f(n/b)+g(n)

Тогда:

    1. Если g(n)=O(), >0, то f(n)=Q()
      Пример:f(n) = 8f(n/2)+, тогда f(n) = Q()

    2. ) Если g(n)=Q(), то f(n)=Q(*log n)
      Пример: fA(n)= 2 * fA( n/2 )+ Q (n), тогда f(n) = Q(n*log n)

    3. Если g(n) = (), e > 0, то f(n)=Q(g(n))
      Пример: f(n)=2*f(n/2)+, имеем:

= , и следовательно: f(n) = Q()

Данная теорема является мощным средством анализа асимптотической сложности рекурсивных алгоритмов, к сожалению, она не дает возможности получить полный вид функции трудоемкости.