Temat 7

Question 1

Jak wygląda struktura kopca Fibonacciego oraz jaką metodę amortyzacji kosztów najlepiej użyć?

Answer 1

Kopiec Fibonacciego ma formę lasu złożonego z kopców, gdzie stopień każdego węzła wynosi co najwyżej log n.
Metoda potencjału do analizy złożoności.

Question 1

Jakie mamy metody dla kosztu zamortyzowanego?

Answer 1

Metoda Ksiegowania:
- Operacja ma koszt rzeczywisty oraz kredyt
- Koszt zamortyzowany operacji może być większy od rzeczywistego, co generuje kredyt

Metoda potencjału:
- Przypisuje się strukturze potencjał, który jest funkcją od stanu struktury
- Koszt zamortyzowany operacji to koszt rzeczywisty plus różnica potencjałów

Question 2

Dlaczego zważając na stopień trudności i skomplikowania implementujemy kopiec Fibonacciego?

Answer 2

Ze względu na jego złożoność obliczeniową przy decrease-key(), przydaje sie to bardzo do algorytmu Dijkstry.

Question 3

Gdzie stosujemy najczęściej strukturę zbiorów rozłącznych?

Answer 3

Algorytm Kruskala

Question 4

Czym Disjont Set Data Structure/ Union Find?

Answer 4

Struktura do zarządzania zbiorami, które nie mają wspólnych elementów. Służy do śledzenia i zarządzania zbiorami elementów, które zmieniają się w wyniku łączenia (union)

Question 5

Techniki optymalizacji dla struktur zbiorów rozłącznych

Answer 5

Kompresja Ścieżki;
Łączenie według Rangi;
Łączenie według Wielkości;

Question 6

Główna różnica między kompresją ścieżki a łączeniem według rangi lub wielkości?

Answer 6

Przy kompresji ścieżki skracamy wysokość drzew, a dla łączenia minimalizujemy wzrost wysokości drzew, łącząc drzewa w określony sposób.

Question 7

Na czym polega zasada konsolidacji dla kopca Fibonacciego?

Answer 7

Wszystkie drzewa o tym samym stopniu są scalane poprzez ich połączenie, dopóki nie pozostaną drzewa o unikalnych stopniach.