- •Зміст дисципліни.
- •Найменування тем, їхній зміст, обсяг у годинах лекційних занять
- •Вказівки з використанНя літературних джерел
- •Алгоритми й структури даних
- •Стеки, списки
- •Дерева пошуку Бінарні дерева
- •Двійкові дерева
- •Червоно- чорні дерева
- •Частково впорядковані дерева Статья I.При створенні чуд елементи вводилися в наступному порядку: (13, 6, 15, 5, 10, 6, 3, 13, 5, 6, 35, 8). Пояснити побудова (переформування) дерева.
- •Рекурсія
- •Перебір з поверненням
- •Машина Тьюрінга
- •Приклади Послідовний пошук
- •Структури даних. Масиви Решето Ератосфена
- •Обчислення найближчої точки
- •Структури даних. Списки Приклад циклічного списку (задача Йосипа)
- •Сортування методом вставки в список
- •Звертання порядку проходження елементів списку
- •Структури даних. Рядки Сортування масиву рядків
- •Абстрактні типи даних (атд) Інтерфейс абстрактного типу даних стека
- •Реалізація черги fifo на базі масиву
- •Реалізація черги fifo на базі зв'язного списку
- •Перетворення з інфіксної форми в постфіксну
- •Рекурсія Алгоритм Евклида
- •Рекурсивна програма для оцінки префіксних виразів
- •Розв’язання
- •Приклад 2 Завдання
- •Розв’язання
- •Приклад 3 Завдання
- •Розв’язання
- •Приклад 4 Завдання
- •Розв’язання
- •Приклад 5 Завдання
- •Розв’язання
- •Приклад 6 Завдання
- •Розв’язання
- •Приклад 7 Завдання
- •Розв’язання
- •Алгоритм роботи машини т’юринга
- •Дослідження функції на рекурсивність
- •Нормальні алгоритми Маркова
- •Алгоритм роботи програми.
- •Приклад роботи програми.
- •Варіанти курсових робіт
- •Варіанти виконання Алгоритм виконання курсової роботи:
- •Приклад1.
- •Побудова моделі.
- •Розроблення алгоритму.
- •Правильність алгоритму.
- •Реалізація алгоритму.
- •Перевірка програми.
- •Приклад2
- •Постановка задачі
- •Перший варіант розв’язку
- •Другий варіант розв’язку.
- •Приклад3
- •Опукла оболонка
- •Метод обходу Грехема
- •Метод обходу Джарвіса
- •Алгоритм апроксимації опуклої оболонки
- •Швидкі методи побудови опуклої оболонки
- •Алгоритм типу розділяй та пануй
- •Побудова опуклої оболонки простого многокутника
- •Динамічні алгоритми побудови опуклої оболонки
- •Порівняльний аналіз алгоритмів побудови опуклої оболонки
- •Висновки
Метод обходу Грехема
Знайдемо внутрішню точку O множини точок S та перетворимо координати інших точок так, щоб знайдена внутрішня точка стала початком координат. Впорядкуємо лексикографічно N точок у відповідності зі значеннями полярного кута та відстані від початку координат (при цьому переводити координати точок до полярної системи координат не треба).
Алгоритм Грехема полягає в однократному перегляді впорядкованої послідовності точок, в процесі якої видаляються внутрішні точки. Перегляд починається з точки p0, в якості якої можна взяти саму праву (з максимальною абсцисою) з найменшою ординатою (вона точно належить опуклій оболонці). Послідовно перевіряються трійки точок p1p2p3, при чому
1. Якщо трійка p1p2p3 утворює правий поворот, то видалити вершину p2 та перевірити трійку p0p1p3.
2. Якщо трійка p1p2p3 утворює лівий поворот, то продовжувати перегляд, перейшовши дотрійки p2p3p4.
Оболонка Грехема
1. Знайти внутрішню точку q.
2. Використовуючи q як початок координат, впорядкувати лексикографічно точки множини S у відповідності з полярним кутом та відстанню від q. Організувати точки множини у вигляді кільцевого списку із вказівниками NEXT, PREV та вказівником ПОЧАТОК на першу вершину. Значення TRUE логічної змінної f вказує на те, що вершина ПОЧАТОК досягнута при прямому русі по оболонці, а не в результаті повертання.
3. Обхід
begin
v ПОЧАТОК; w NEXT[v]; f FALSE;
while (NEXT[v] ПОЧАТОК or f = FALSE) do
begin
if NEXT[v] = w then f TRUE;
if (три точки v, NEXT[v], NEXT[NEXT[v]] утворюють лівий поворот) then v NEXT[v];
else
begin
ВИДАЛИТИ NEXT[v];
v PREV[v];
end;
end;
end.
Теорема. Опукла оболонка N точок на площині може бути знайдена за час O(N * logN) при витратах пам’яті O(N).
Метод обходу Джарвіса
Теорема. Відрізок l є ребром опуклої оболонки тоді і тільки тоді, коли всі інші точки заданої множини лежать на l або з одної сторони від нього.
N точок
множини S визначають
прямих. Для кожної цієї прямої можна
визначити за лінійний час розташування
інших N-2 точок відносно цієї прямої,
тим самим перевіривши чи задовольняє
пряма умові теореми. За час O(N3)
можна знайти всі пари точок, що визначають
ребра опуклої оболонки та розташувати
ці точки у вигляді списку послідовних
вершин оболонки.
Джарвіс покращив цей алгоритм помітивши, що якщо відрізок pq є ребром оболонки, то повинно існувати інше ребро оболонки з кінцем в точці q. Нехай знайдено точку p1, яка належить опуклій оболонці (яка, наприклад, має максимальну х координату; а якщо таких точок декілька – то серед них взяти точку з мінімальною у координатою). Наступна точка p2 опуклої оболонки – це точка, яка має найменший додатний полярний кут відносно точки p1 як початку координат. І так далі шукаються наступні точки шляхом проходу вкругову опуклої оболонки, породжуючи у потрібному порядку послідовність крайніх точок, по одній на кожному кроці.
Обхід Джарвіса
p[1] точка з найменшою y координатою;
p[2] точка з множини S, для якої кут між прямою p[2] - p[1] та віссю Ox найменший;
print (p[1], p[2]);
i 2;
while (p[i] p[1]) do
begin
p[i + 1] точка з множини S, для якої кут p[i - 1] p[i] p[i + 1] є найбільшим;
i i + 1;
print (p[i]);
end.
Теорема. Часова оцінка обходу Джарвіса дорівнює O(N2).
Оскільки всі N точок можуть лежати на опуклій оболонці, а алгоритм Джарвіса вимагає лінійний час для знаходження кожної наступної точки оболонки, то в найгіршому випадку часова оцінка дорівнює O(N2). Обхід Джарвіса є ефективним, якщо кількість вершин опуклої оболонки h є малою у порівнянні зі значенням N – часова оцінка у цьому випадку дорівнюватиме O(N * h).
