AAL260
- analiza algorytmów
Prowadzący: Michał Hanćkowiak
oceny ze sprawozdan i egzaminu
oraz końcowa!!!
Wykład - slajdy.
(Wyłącznie do użytku wewnętrznego !)
- wykład 1: aal260_01.ps, aal260_01.pdf; wstęp, słowniki, drzewa BST i
RB
- wykład 2: aal260_02.ps, aal260_02.pdf; MST/ algorytm Prima,
kolejka priorytetowa, kopce dwumianowe
- wykład 3: analiza kosztu zamortyzowanego, kopce Fibonacciego
- wykład 4: algorytmy rozproszone/ synchroniczne: kolorowanie
wierzchołkowe
w drzewie ukorzenionym (algorytm CV) i w grafie stałego stopnia
- wykład 5: najkrótsze ścieżki z 1 źródłem (algorytm Dijkstry),
aproksymacja rozproszona: MWIS, MM, MDS w grafach planarnych
Egzamin.
Egzamin wyłącznie pisemny.
Ocena końcowa z egzaminu to średnia arytmetyczna oceny ze sprawozdań
oraz z egzaminu pisemnego.
Przykładowe zadania:
- wykonać operacje rotacji w lewo na konkretnym przykładzie drzewa RB
- wykonać pewną operacje na konkretnym kopcu dwumianowym
- jaki kopiec dwumianowy powstanie po wykonaniu operacji Insert dla
konkretnego ciągu liczb
- opisać jak działa alg. rozproszony aproksymujący MWIS w grafie
planarnym
- przeprowadzić kilka kroków algorytmu rozproszonego CV na podanym
drzewie ukorzenionym
- uzasadnić dlaczego kopiec dwumianowy na n-wierz. składa sie z
podłoga(log n)+1 drzew dwumianowych
- oszacować czas działania alg Prima przy podanej implementacji kolejki
priorytetowej
- dla podanego (małego) kopca Fib, wykonać operację konsolidacji
- wykonać relaksacje dla podanego ciągu krawędzi w alg. najkrótszych
ścieżek z 1 źródłem
- opisać algorytm rozproszony, który w grafie planarnym znajduje
orientacje krawędzi
z max stopniem wyjściowym <=6
- napisz procedurę, która wypisuje wszystkie permutacje ciągu {1,2, ..,
n} dla dowolnego n
Ćwiczenia.
- temat A: narzędzia prog.; słowniki:
drzewa BST i RB
- temat B1: problem MST, kolejka
priorytetowa (15.11.2008 - zakończenie tematu)
- temat B2: kopce dwumianowe i
Fibonacciego; szybka kolejka priorytetowa (24.01.2009 - zakończenie
tematu)
- temat C1: najkrótsze scieżki,
algorytmy rozproszone
- temat C2: algorytmy rozproszone
synch. i asynch.
Literatura.
- Cormen, Leiserson, Rivest "Wprowadzenie do algorytmów";
są tu opisane wszystkie algorytmy z 1 procesorem, o których wspomniano
na wykładzie ...
- algorytmy rozproszone/ synchroniczne dla problemow grafowych:
3-kolorowanie-wierzcholkowe w drzewie ukorzenionym tree.ps
(str 3-8)
MIS i (Delta+1)-kolorowanie-wierzcholkowe w grafie malego stopnia simplemis.ps (od 6 str)
MWIS w grafie planarnym ch05.pdf (od 12 str)
MDS i MCDS w grafie planarnym ch06.pdf (od 8
str)