Моделі і методи прийняття рішень (стр. 2 из 3)
| # | 0 | 1 | ← |
| q0 | q1 | q2 | q5 |
| q1 | q1 | q1 | q1 |
| q2 | q1 | q4 | q3 |
| q3 | q1 | q5 | q2 |
| q4 | q1 | q2 | q5 |
| q5 | q1 | q3 | q4 |
Рис.1. Табличне задання автомата
Рядки таблиці позначаються станами множини Q, а стовпці – символами вхідного алфавіту. Символ ←позначає заключні допустимі стани.
Графічний опис автомата полягає у побудові графа, де вершини qiі qjз’єднуються дугою a якщо виконується команда qia→qj. Заключні допустимі вершини позначаються подвійним колом.
Рис.2. Графічне задання автомата
Спеціальним типом автомата є машина Тьюринга. Універсальна машина Тьюринга може обчислити будь-який інтуїтивний алгоритм.
3. Складність алгоритмів
Універсальним обчислювальним пристроєм називатимемо пристрій, на якому можна промоделювати роботу машини Тьюринга.
Машини Тьюринга дозволяють обчислювати тільки рекурсивні функції.
Частково рекурсивні функції – визначена не при всіх значеннях аргумента.
Теза Тьюринга: Клас функцій, частково обчислюваних за Тьюрингом, збігається з класом частково рекурсивних функцій.
Теза Чорча: клас частково рекурсивних функцій збігається з класом частково обчислюваних функцій.
Теза Чорча еквівалентна тезі Тьюринга.
Моделі РАМ і РАСП
Машина Тьюринга дуже незручна для програмування через послідовний доступ до комірок пам’яті (стрічка), неструктурованість записів на стрічці (потрібно використовувати розподільники), відсутні основні арифметичні операції та ін.
Модель РАМ – довільний доступ до пам’яті, одна стрічка – для читання, друга – для запису.
РАСП – програма перебуває в регістрах і може сама себе змінювати.
Під складністю алгоритму розуміється часова оцінка його роботи або ємність необхідної пам’яті.
Апріорний аналіз алгоритму – теоретично, тестування – практична перевірка.
Розмірність задачі (вхідних даних) – це число (ціле), яке характеризує розмір вхідних даних задачі (розмірність одномірних, двомірних масивів, ...).
Часова складність алгоритму – час вирішення проблеми у залежності від розмірності задачі.
Асимптотична часова складність – поведінка часової складності при збільшенні розмірності задачі.
Задачі з великої часової складністю неможливі для реальних комп’ютерів (млрд. років).
При аналізі алгоритмів використовують такі позначення.
Запис f(n)=O(g(n)) означає: функція має порядок g(n) тоді, існують дві додатні константи с in0, що f(n)<=c[g(n)] для всіх n>n0.
Звичайно f(n)=O(g(n))визначає час обчислень;
.Теорема. Якщо
A(n)=amnm + … a1n + a0
є поліномом ступеня m, тоді
A(n)=O(nm).
Нехай є два алгоритми з часовою оцінкою обчислень O(n) і O(n2). Час виконання першого алгоритму - c1n, а другого - c2n2 (с - константи). Тоді при n<c1/c2перевагу має перший алгоритм, а приn>c1/c2 – другий.
При великих n значення констант несуттєві.
Найбільш типові часові оцінки алгоритмів: O(1) - константна, O(log n) - логарифмічна, O(n) - лінійна, O(nm) - поліноміальна, O(2n) - експоненційна. Для досить великих n:
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n)
Ω(g(n)) - мінінімальна часова оцінка.
Задачі класу PINP
Якщо розмірність задачіn, тоP задача може бути розв’язана за поліноміальний час O(nm).
Задача NPможе бути вирішена за поліноміальний час для недетермінованої машини Тьюринга (така машина породжує на кожному кроці певну кількість нових машин).
Більшість дискретних і комбінаторних задач можна вирішити шляхом перебору. Проте перебірні методи мають експоненційну складність.
Проблема: знайти метод вирішення експоненційних задач за поліноміальний час.
3.1 Планування в просторі станів. Основні поняття теорії графів
Граф – сукупність вершин і дуг. Для комп’ютерного опису графу використовуються: матриця інцидентності, матриця суміжності та списки суміжності.
Поширена структура даних в програмуванні – лінійні списки.
Лінійний список – скінченна послідовність однотипних елементів (певної довжини). Списки бувають однозв’язні (лінійні), двозв’язні (циклічні) і т.п. Лінійний список L, що складається з l1, l2,.. lnелементів , записується у вигляді L=< l1, l2,.. ln >
Рис..1. Графічне зображення списку
Існує два основних методи задання списків: послідовний (масиви) і зв’язний (динамічні змінні).
Стек – список, в якому занесення і видалення елементів можна проводити тільки через один початковий елемент (вершину стеку). Стек працює за принципом: останній зайшов – перший вийшов (LastInFirstOut - LIFO)
Чергою називають список, в якому всі вставки здійснюються в кінець списку (змінна rear), а всі видалення відбуваються з голови (початку) списку (змінна front).
Черга працює за принципом : перший зайшов – перший вийшов (FirstInFirstOut - FIFO).
Поняття граф ввів у 1736 році Ейлер. Граф Gмістить дві множиниG=(V,E), де V - множина вершин (вузлів 1...n), E - множина ребер. Коли пари вершин впорядковані - то граф орієнтований, інакше - неорієнтований. Впорядкована пара позначається <i,j>, невпорядкована – (i,j). У зважених графах кожне ребро має вагу.
Ступенем вершини називається число суміжних вершин. В орієнтованому графі виділяють півстепінь входу (число вхідних ребер) та півстепінь виходу (число вихідних ребер).
Шляхом називається послідовність вершин між двома вершинамиp і q.
Циклом називається шлях, у якого початкова і кінцева вершини збігаються. Граф називається зв’язним, якщо для довільної пари вершин існує між ними шлях.
 |
 |
а) б)
Рис.2. Зображення орієнтованого (а) і неорієнтованого (б) графів.
3.2 Способи задання графів
Існує послідовний і зв’язний спосіб задання графів.
Послідовна форма використовує квадратну таблицю (Graf(n,n), n- вершин), яку називають матрицею суміжності. Якщо є зв’язок між вершинами, то Graf(I,j)=1, інакше Graf(I,j)=0.
а)
б) 
Рис.3. Матриці суміжності графів з рис.2.: а – неорієнтованого, б – орієнтованого
Матриця інцидентності відображає зв’язок n вершин за допомогою m дуг, розмір матриці інцидентності (n*m), але вона менш зручна, ніж матриця суміжності.
Інша форма задання графу – список зв’язності. Граф зnвершинами буде задаватися списками – по одному для кожної вершини. Список для вершини і містить вершини, суміжні з і.
3.3 Дерева
Дерево – це орієнтований ациклічний граф, для якого виконуються такі умови:
1) існує одна вершина, в яка не входить жодне ребро (корінь);
2) у будь-яку вершину, крім кореня, входить лише одне ребро;
3) з кореня можна знайти унікальний шлях до кожної вершини дерева.
Орієнтований граф з кількох вершин – ліс. Бінарне дерево – кожна вершина має два нащадки. При пошуку певного вузла у дереві використовують пряме і зворотне проходження вузлів.
Способи зберігання дерев
Послідовне зберігання ділиться на рівневі і діжкове.
Рівневе: для кожного рівня дерева послідовно вказаються його вузли.
Дужкове: дужками вказуються нащадки даного вузла.
Зв’язне зберігання – списки, кожен список містить вказівними на нащадків.
Пошук у глибину і ширину
Пошук в глибину – послідовно відвідуються всі нові вершини –нащадки (якщо вершина була відвідана, то вона перестає бути новою).
Пошук у ширину – перевіряються суміжні вершини одного рівня, потім – перехід на нижчий рівень.
Остові дерева
Довільне дерево <V, T> неорієнтованого графу G=<V, E> називається остовим.
Ейлерові шляхи
Для вирішення багатьох прикладних проблем використовуються ейлерові шляхи. Ейлеревими називають шляхи, які проходять через кожне ребро графу один раз. Якщо початковий вузол є кінцевим, то такий граф називається ейлеревим циклом.
Задача про Кенігсбергські мости.
Теорема. У графі існує ейлерів шлях тільки тоді, коли граф зв’язний і містить не більше двох вершин непарного ступеня.
Знаходження найкоротших шляхів у графі
Потрібно знайти мінімальний шлях (контур) у навантаженому графі, де d(u,v) - відстань між вершинами u і v, якщо не існує шляху, то d(u,v)=
.4. Загальна схема алгоритму Харта, Нельсона і Рафаеля
Узагальненням алгоритмів пошуку найкоротшого шляху на графах є алгоритм Харта, Нельсона і Рафаеля.
Введемо такі позначення:
s - початкова вершина;
q - цільова вершина;
c(i,j) - довжина ребра між вершинами і та j;
d(i, j) - довжина найкоротшого шляху між і-ю та j-ю вершинами;
g(n) - довжина найкоротшого шляху між від початкової вершини до n-ї;
h(n) - довжина найкоротшого шляху між від n-ї вершини до цільової;
f(n) - довжина найкоротшого шляху між від початкової вершини до цільової, які проходять через вершину n, при цьому f(n)=g(n)+h(n);