Реферат: Моделі і методи прийняття рішень

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

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

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

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

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

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

.

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

A(n)=a_m n^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)) - мінінімальна часова оцінка.

Задачі класу PINP

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

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

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

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

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

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

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

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

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

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

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

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