Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритм побудови бінарного дерева згортання.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2008
Тип роботи:
Методичні вказівки
Предмет:
Алгоритми і структури даних
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти України
Національний університет «Львівська політехніка»
Методичні вказівки
До лабораторної роботи № 12
На тему: «Алгоритм побудови бінарного дерева згортання»
з дисципліни
«Алгоритми і структури даних»
Для базового напрямку 6.0804 «Комп’ютерні науки»
ЗАТВЕРДЖЕНО
на засіданні кафедри
програмного забезпечення
протокол № від 2008 року
місто Львів
2008 рік
Методичні вказівки до лабораторної роботи з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки»
Укладачі: Семчишин Ю. Б.
Коротєєва Т. О.
Вовчак І. Г.
Відповідальний за випуск:
Рецензенти:
Тема роботи: Алгоритм побудови бінарного дерева згортання
Мета роботи: Вивчити та дослідити методи обробки даних. Ознайомитись із алгоритмом побудови бінарного дерева згортання. Виконати лабораторну роботу використавши здобуті знання з методів обробки даних, зокрема алгоритму побудови бінарного дерева згортання.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Необхідно побудувати дерево згортання Т(Х, F) графу. Множина вершин Х графу належатимуть до 1-го рівня дерева згортання, приймемо Х1 = Х. На першому кроці в множині Х2 маємо групи з двох елементів, для яких функція критерію F приймає екстремальне значення. Утворені групи належать до множини 2-го рівня дерева згортання. На другому кроці формується множина Х3 3-го рівня з елементів множини Х1 і Х2 . Процес продовжується до утворення множини Хk , яка складається з одного елемента – кореня дерева згортання.
Алгоритм А
А1. Для всіх хi, хj є Х1 визначити функцію критеріюF(хi, хj);
А2. Об‘єднати пари елементів хk, хt з найкращим значенням функції критерію F і виключити їх зі списку елементів – кандидатів на об‘єднання.
Приклад роботи алгоритму побудови бінарного дерева згортання представлено на рис. 1.
SHAPE \* MERGEFORMAT
d a b a a a
e e c c b b
f f e d c d
adef
abcde
abcdef
abcd
abcd
2
2
3
3
2
2
2
2
2
2
Рис. 1. Дерево згортання.
РЕКОМЕНДОВАНІ ДЖЕРЕЛА
http://studik.lviv.ua/index.php?option=com_content&task=view&id=47.
Базилевич Р. П., Гудз І. Б., Ждан А. Р. Ієрархічна кластеризація складних схем // Вісник НУ «Львівська політехніка», № 546, «Комп'ютерні системи та мережі», НУЛП, 2005. — С. 3–7.
2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ
При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм побудови бінарного дерева згортання.
Використовувати мову програмування C/C++.
Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи.
3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ
Отримати індивідуальне завдання у викладача;
Уточнити завдання (можливі різні трактування завдання);
Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу (алгоритму) на даній лабораторній роботі;
Протестувати на наявність логічних помилок програми;
Оформити звіт відповідно до стандарту;
Захистити виконану роботу.
4. КОНТРОЛЬНІ ПИТАННЯ
Які ви знаєте методи обробки даних?
Який метод обробки даних був розглянений на даній лабораторній роботі?
Від чого прямо – залежним являється швидкість побудови бінарного дерева згортання?
Опишіть характеристики даного методу.
Наскільки являється ефективним даний метод обробки даних?
Чи використовують даний метод на практиці, і наскільки часто?
Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах?
Чим оригінальним виділяється даний метод від інших?
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора