Spis Treści
Warianty
Należy zaimplementować jeden z niżej wymienionych algorytmów znajdujących minimalne drzewo rozpinające oraz opanować (ze zrozumieniem) dotyczącą go teorię. Ocena zależy od wybranego wariantu.
Algorytm Prima używający zwykłej tablicy (na ocenę 3.5)
Algorytm Prima używający jako kolejki priorytetowej tablicy indeksowanej wierzchołkami albo kopca binarnego z bibliotek języka.
Algorytm Prima używający kopca binarnego (na ocenę 4.5)
Algorytm Prima używający samodzielnie zaimplementowanego kopca binarnego jako kolejki priorytetowej.
Algorytm Kruskala z dowolną strukturą find-union (na ocenę 3)
Algorytm Kruskala z efektywną strukturą find-union (na ocenę 4)
Implementacja używająca drzewiastych, samodzielnie zaimplementowanych struktur do operacji na zbiorach rozłącznych.
Uwaga: Implementacja algorytmu Kruskala może używać sortowania z biblioteki języka. Należy jednak przeczytać w dokumentacji jaka jest złożoność tej operacji.
Budowanie labiryntu - opcjonalne rozszerzenie podwyższające ocenę o 1
Program używa zaimplementowano algorytmu do wygenerowania labiryntu.
Labirynt można narysować za pomocą ascii-art albo zapisać do pliku SVG. SVG to XMLowy format kodujący grafikę wektorową, który można otworzyć przeglądarką internetową. Do narysowania labiryntu wystarczy wiedza zawarta w tym przykładzie.
Przykładowe pytania sprawdzające
Dla wszystkich wariantów
- Zilustrować działanie zaimplementowanego algorytmu na zadanym grafie. Które krawędzie zostaną dodane do budowanego drzewa i w jakiej kolejności?
- Jaka jest złożoność czasowa zaimplementowanego algorytmu? Wskazać miejsca w kodzie (pętle, rekurencje), które za to opowiadają.
- Jaka jest złożoność pamięciowa zaimplementowanego algorytmu? Wskazać miejsca w kodzie gdzie alokowana jest pamięć (w jakiej ilości?).
- Co to jest minimalne drzewo rozpinające? Co to jest drzewo? Co to znaczy, że jest ono minimalne? I co oznacza, że jest rozpinające?
- Zaimplementowany algorytm (Prima lub Kruskala) jest przykładem algorytmu zachłannego. Co to jest algorytm zachłanny? Na jakiej zasadzie działa?
Dla wariantu używającego kopca binarnego z bibliotek języka
- Jaka jest złożoność wykorzystanych operacji kopca?
Dla wariantu używającego własnej implementacji kopca binarnego
- Co to jest kopiec binarny? Opisać tzw. warunek kopca, czyli zależność zachodzącą pomiędzy każdym węzłem i jego synami.
- Dla zadanego kopca, zilustrować działanie wskazanej operacji: dodawania nowego elementu, usuwania korzenia, zmiany priorytetu.
- Jaka jest czasowa złożoność poszczególnych operacji działających na kopcu?
Dla wariantu używającego efektywnej (drzewiastej) implementacji find-union
- Jak reprezentowane są zbiory rozłączne?
- Zilustrować działanie wskazanej operacji na zbiorach rozłącznych: znajdywania korzenia/reprezentanta (z kompresją ścieżki), sprawdzenia czy dwa elementy należą do tego samego zbioru, złączenia dwóch zbiorów (z zaimplementowaną w programie heurystyką podpinania: niższego drzewa do wyższego albo mniejszego do większego).
- Jaka jest czasowa złożoność poszczególnych operacji działających na zbiorach rozłącznych?