Складність алгоритмів

3. Складність алгоритмів

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

Машини Тьюринга дозволяють обчислювати тільки рекурсивні функції.

Частково рекурсивні функції – визначена не при всіх значеннях аргумента.

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

Теза Чорча: клас частково рекурсивних функцій збігається з класом частково обчислюваних функцій.

Теза Чорча еквівалентна тезі Тьюринга.

Моделі РАМ і РАСП

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

Модель РАМ – довільний доступ до пам’яті, одна стрічка – для читання, друга – для запису.

РАСП – програма перебуває в регістрах і може сама себе змінювати.

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

Апріорний аналіз алгоритму – теоретично, тестування – практична перевірка.

Розмірність задачі (вхідних даних) – це число (ціле), яке характеризує розмір вхідних даних задачі (розмірність одномірних, двомірних масивів, ...).

Часова складність алгоритму – час вирішення проблеми у залежності від розмірності задачі.

Асимптотична часова складність – поведінка часової складності при збільшенні розмірності задачі.

Задачі з великої часової складністю неможливі для реальних комп’ютерів (млрд. років).

При аналізі алгоритмів використовують такі позначення.

Запис f(n)=O(g(n)) означає: функція має порядок g(n) тоді, існують дві додатні константи с i n₀, що f(n)<=c[g(n)] для всіх n>n₀.

Звичайно f(n)=O(g(n)) визначає час обчислень;

.

Теорема. Якщо

A(n)=a_mn^m + … a₁n + a₀

є поліномом ступеня m, тоді

A(n)=O(n^m).

Нехай є два алгоритми з часовою оцінкою обчислень O(n) і O(n²). Час виконання першого алгоритму - c₁n, а другого - c₂n² (с - константи). Тоді при n<c₁/c₂ перевагу має перший алгоритм, а при n>c₁/c₂ – другий.

При великих n значення констант несуттєві.

Найбільш типові часові оцінки алгоритмів: O(1) - константна, O(log n) - логарифмічна, O(n) - лінійна, O(n^m) - поліноміальна, O(2ⁿ) - експоненційна. Для досить великих n:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ)

Ω(g(n)) - мінінімальна часова оцінка.

Задачі класу P I NP

Якщо розмірність задачі n, то P задача може бути розв’язана за поліноміальний час O(n^m).

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

Більшість дискретних і комбінаторних задач можна вирішити шляхом перебору. Проте перебірні методи мають експоненційну складність.

Проблема: знайти метод вирішення експоненційних задач за поліноміальний час.

3.1 Планування в просторі станів. Основні поняття теорії графів

Граф – сукупність вершин і дуг. Для комп’ютерного опису графу використовуються: матриця інцидентності, матриця суміжності та списки суміжності.

Поширена структура даних в програмуванні – лінійні списки.

Лінійний список – скінченна послідовність однотипних елементів (певної довжини). Списки бувають однозв’язні (лінійні), двозв’язні (циклічні) і т.п. Лінійний список L, що складається з l₁, l₂,.. l_n елементів , записується у вигляді L=< l₁, l₂,.. l_n >

Рис..1. Графічне зображення списку

Існує два основних методи задання списків: послідовний (масиви) і зв’язний (динамічні змінні).

Стек – список, в якому занесення і видалення елементів можна проводити тільки через один початковий елемент (вершину стеку). Стек працює за принципом: останній зайшов – перший вийшов (Last In First Out - LIFO)

Чергою називають список, в якому всі вставки здійснюються в кінець списку (змінна rear), а всі видалення відбуваються з голови (початку) списку (змінна front).

Черга працює за принципом : перший зайшов – перший вийшов (First In First Out - FIFO).

Поняття граф ввів у 1736 році Ейлер. Граф G містить дві множини G=(V,E), де V - множина вершин (вузлів 1...n), E - множина ребер. Коли пари вершин впорядковані - то граф орієнтований, інакше - неорієнтований. Впорядкована пара позначається <i,j>, невпорядкована – (i,j). У зважених графах кожне ребро має вагу.

Ступенем вершини називається число суміжних вершин. В орієнтованому графі виділяють півстепінь входу (число вхідних ребер) та півстепінь виходу (число вихідних ребер).

Шляхом називається послідовність вершин між двома вершинами p і q.

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

а) б)

Рис.2. Зображення орієнтованого (а) і неорієнтованого (б) графів.