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 i może być podwyższona o 0,5 stopnia za oddanie programu w pierwszym terminie, z bezbłędną odpowiedzią.
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?