- •Зміст дисципліни.
- •Найменування тем, їхній зміст, обсяг у годинах лекційних занять
- •Вказівки з використанНя літературних джерел
- •Алгоритми й структури даних
- •Стеки, списки
- •Дерева пошуку Бінарні дерева
- •Двійкові дерева
- •Червоно- чорні дерева
- •Частково впорядковані дерева Статья I.При створенні чуд елементи вводилися в наступному порядку: (13, 6, 15, 5, 10, 6, 3, 13, 5, 6, 35, 8). Пояснити побудова (переформування) дерева.
- •Рекурсія
- •Перебір з поверненням
- •Машина Тьюрінга
- •Приклади Послідовний пошук
- •Структури даних. Масиви Решето Ератосфена
- •Обчислення найближчої точки
- •Структури даних. Списки Приклад циклічного списку (задача Йосипа)
- •Сортування методом вставки в список
- •Звертання порядку проходження елементів списку
- •Структури даних. Рядки Сортування масиву рядків
- •Абстрактні типи даних (атд) Інтерфейс абстрактного типу даних стека
- •Реалізація черги fifo на базі масиву
- •Реалізація черги fifo на базі зв'язного списку
- •Перетворення з інфіксної форми в постфіксну
- •Рекурсія Алгоритм Евклида
- •Рекурсивна програма для оцінки префіксних виразів
- •Розв’язання
- •Приклад 2 Завдання
- •Розв’язання
- •Приклад 3 Завдання
- •Розв’язання
- •Приклад 4 Завдання
- •Розв’язання
- •Приклад 5 Завдання
- •Розв’язання
- •Приклад 6 Завдання
- •Розв’язання
- •Приклад 7 Завдання
- •Розв’язання
- •Алгоритм роботи машини т’юринга
- •Дослідження функції на рекурсивність
- •Нормальні алгоритми Маркова
- •Алгоритм роботи програми.
- •Приклад роботи програми.
- •Варіанти курсових робіт
- •Варіанти виконання Алгоритм виконання курсової роботи:
- •Приклад1.
- •Побудова моделі.
- •Розроблення алгоритму.
- •Правильність алгоритму.
- •Реалізація алгоритму.
- •Перевірка програми.
- •Приклад2
- •Постановка задачі
- •Перший варіант розв’язку
- •Другий варіант розв’язку.
- •Приклад3
- •Опукла оболонка
- •Метод обходу Грехема
- •Метод обходу Джарвіса
- •Алгоритм апроксимації опуклої оболонки
- •Швидкі методи побудови опуклої оболонки
- •Алгоритм типу розділяй та пануй
- •Побудова опуклої оболонки простого многокутника
- •Динамічні алгоритми побудови опуклої оболонки
- •Порівняльний аналіз алгоритмів побудови опуклої оболонки
- •Висновки
Алгоритм апроксимації опуклої оболонки
При знаходженні наближеної опуклої оболонки ми розмінюємо точність на простоту та ефективність алгоритму.
Знайдемо мінімальне та максимальне значення х координати точок множини S та розіб’ємо вертикальну смугу між ними на k смуг рівної ширини. В кожній із цих k смуг шукаються дві точки, які мають мінімальну та максимальну у координату (обирається 2k точок). Обираються також точки з екстремальними значеннями х координати; якщо їх декілька, то обираються дві точки з екстремальними значеннями у координати (максимум обирається 4 точки). Обрана множина містить не більш ніж 2k + 4 точок і позначимо її через S*. Далі можна застосувати алгоритм Грехема побудови опуклої оболонки для множини точок S*.
Приклад. Множину точок S розбито на k = 4 смуги. В кожній з смуг обрано дві точки. Для утвореної множини S* побудовано опуклу оболонку.
Теорема. Довільна точка p S, яка не попала всередину наближеної опуклої оболонки, знаходиться на відстані, не більшої за значення (xmax - xmin) / k.
Швидкі методи побудови опуклої оболонки
Розіб’ємо множину S з N точок на дві підмножини, кожна з яких буде містити одну з двох ламаних, об’єднання яких дає многокутник опуклої оболонки. Початкове розбиття множини точок визначається прямою, що проходить через дві точки l та r, які мають відповідно найменшу та найбільшу абсцису. Позначимо через S1 підмножину точок, яка розташована вище або на прямій, а через S2 – підмножину точок, яка розташована нижче або на прямій. Якщо бути точним, то {S1, S2} не є розбиттям множини S, оскільки {l, r} S1 S2. Далі множини S1 та S2 обробляються наступним чином (розглянемо на прикладі множини S1).
Знайдемо точку h, для якої трикутник lhr має максимальну площу серед усіх інших трикутників (якщо таких точок декілька, то обираємо ту, в якій кут hlr більший). Точка h гарантовано належить опуклій оболонці. Якщо провести через h пряму, паралельну lr, то над ній не буде жодної точки множини S. Якщо на цій прямій лежать декілька точок, то згідно з припущенням точка h буде самою лівою з них.
Будуємо дві прямі: L1 (сполучає точки l та h) та L2 (проходить через точки h та r). Для кожної точки множини S1 визначаємо її положення відносно цих прямих. Точки, які попали в трикутник lhr, можуть бути вилучені з подальшої обробки. Жодна з точок не знаходиться зліва від L1 та зліва від L2 (напрямки прямих вказано на рисунку). Точки, розташовані зліва від L1 чи на ній, утворюють множину S11. Аналогічно утворюється множина S12. Утворені множини S11 та S12 передаються далі на наступний рівень рекурсивної обробки.
Вибір початкових значень {l0, r0} точок l та r можна спростити. В якості l візьмемо точку (x0, y0), яка має найменшу абсцису, а в якості r візьмемо точку (x0, y0 - e), де e – мале додатне число. Вертикальна пряма, що проходить через l, буде першою прямою, яка розбиває множину точок S. Другою прямою буде пряма, що проходить через точки з екстремальними абсцисами.
Через * далі позначено операцію конкатенації списків.
Швидка опукла оболонка (S, l, r)
if (S = {l, r}) then return (l, r) /* опукла оболонка складається з єдиного орієнтованого ребра */
else
begin
h сама дальня точка(S, l, r);
S1 точки множини S, розташовані зліва від прямої lh чи на ній;
S2 точки множини S, розташовані зліва від прямої hr чи на ній;
return Швидка опукла оболонка (S1, l, r) * (Швидка опукла оболонка (S2, h, r) - h);
end;
begin
l0 (x0, y0) точка множини S з найменшою абсцисою;
r0 (x0, y0 - e);
Швидка опукла оболонка (S, l0, r0);
видалити точку r0 /* це еквівалентно тому, якщо покласти e = 0 */
end.
