Алгоритм побудови бінарного дерева згортання

Міністерство освіти та науки України
національний університет “Львівська Політехніка”
Кафедра програмного забезпечення














Звіт
про виконання лабораторної роботи №12
з дисципліни “Алгоритми та структури даних”












Підготував:




Прийняв:






Львів – 2009
    Тема роботи: Алгоритм побудови бінарного дерева згортання
    Мета роботи: Вивчити та дослідити методи обробки даних. Ознайомитись із алгоритмом побудови бінарного дерева згортання. Виконати лабораторну роботу використавши здобуті знання з методів обробки даних, зокрема алгоритму побудови бінарного дерева згортання.


    ТЕОРЕТИЧНІ ВІДОМОСТІ
      Необхідно побудувати дерево згортання Т(Х, F) графу. Множина вершин Х графу належатимуть до 1-го рівня дерева згортання, приймемо Х1 = Х. На першому кроці в множині Х2   маємо групи з двох елементів, для яких функція критерію F приймає екстремальне значення. Утворені групи належать до множини 2-го рівня дерева згортання. На другому кроці формується множина Х3 3-го рівня з елементів множини Х1 і Х2 . Процес продовжується до утворення множини Хk   , яка складається з одного елемента – кореня дерева згортання.
      Алгоритм А
      А1. Для всіх   хi, хj є Х1   визначити функцію критеріюF(хi, хj);
      А2. Об‘єднати пари елементів хk, хt з найкращим значенням функції критерію F і виключити їх зі списку елементів – кандидатів на об‘єднання.


Програма:


#include
#include
#include

using namespace std;

template
class