AAL260 - ćw - temat B1
Zadanie 20 "algorytm Prima"
Zaimplementuj algorytm Prima znajdujący MST używający "prymitywnej"
kolejki priorytetowej.
Opis algorytmu Prima oraz rozmaite wskazówki znajdziesz tutaj - patrz Zadanie 29.
Oszacuj czas działania tego algorytmu jako funkcję n i m (+pisemne uzasadnienie); n to
liczba wierz, m to liczba kraw.
Wykonaj wizualizację efektów działania tego algorytmu! (proc do
wizual.: mst_wizual.txt, przykładowy obraz).
Co do reprezentacji grafu w pamięci - patrz zadanie 24 poniżej.
Zadanie 21 "algorytm Prima + kolejka
priorytetowa z kopca binarnego"
Zaimplementuj ponownie algorytm Prima, tym razem używając kolejki
priorytetowej zbudowanej z kopca binarnego.
Opis kopców binarnych
znajdziesz tutaj (asd220) (rozdz "Kopce;
algorytm HeapSort")
i tutaj (asd120) (chyba lepszy
opis!).
Oszacuj czas działania tego algorytmu (+pisemne uzasadnienie); kiedy
ten algorytm jest lepszy od wersji z zadania 20?
Wykonaj wizualizację efektów działania ...
Zadanie 22 "algorytm Kruskala"
Zaimplementuj algorytm Kruskala znajdujący MST.
Opis algorytmu Kruskala znajdziesz tutaj
(Zadanie 19);
reprezentuj zbiory rozłączne tak jak to jest opisane w tym zadaniu.
Oszacuj czas działania tego algorytmu (+pisemne uzasadnienie).
Wykonaj wizualizację efektów działania ...
Porównaj wyniki działania z tymi produkowanymi w zadaniach 20 lub 21
dla tego samego grafu wejściowego.
Zadanie 23
Zaimplementuj algorytm znajdujący drugie "co do ciężaru" drzewo
MST.
Zadanie 23.1
Zaimplementuj algorytm wypisujący wszystkie możliwe drzewa MST. Ile ich
może być i od czego to zależy?
......................................................................
Zadanie 24
Wymyśl sposób reprezentacji grafu z wagami na krawędziach, który to
sposób
jest efektywny pamięciowo (każda waga krawedzi jest przechowywana
dokładnie raz)
oraz efektywny czasowo (dostęp do wierzchołków, sąsiadów, wag jest
szybki).
Szybkie mają być także operacje budowanie czy modyfikowania grafu.
Uwaga: mówimy tu o
rozwiązaniu, w którym każdy wierzchołek ma szybki dostęp do swoich
sąsiadów
(co eliminuje reprezentacje, w której jest tablica z elementami (v1,
v2, waga), gdy {v1,v2} należy do E(G)).
Zadanie 25 "szybkie wyszukiwanie
wzorca"
Napisz algorytm wyszukiwania "wzorca" w "tekscie" który działa szybciej
niż rozwiązanie trywialne...
(Rozwiązanie trywialne polega na tym ze po tekscie przesuwa się "okno"
rozmiaru takiego jak wzorzec,
i za każdym razem porównuje się okno i wzorzec).
Wskazówka: użyj funkcji
haszującej h() mającej własność, że mając obliczone h(a1,a2...ak)
można szybko obliczyć h(a2,a3...ak+1).
Porównaj fizyczny czas działania Twojego rozwiązania i trywialnego na
jakimś dlugim tekście.