algorytmyisd4pu

AWiip_Algorytmy i Struktury Danych - semestr IV_

EGZAMIN 1    14. 06. 2006

Grupa A    Nazwisko i Imię - czytelnie

TEMAT 1

Przedstawić równania rekurencyjne stosowane w analizie złożoności.

Podać przebieg rozwiązania tych równań.

Podać przykłady algorytmów, których czasy działania spełniają te równania.

TEMAT 2

Wyjaśnić pojęcia: cykl Eulera, cykl Hamiltona w grafach i podać stosowne przykłady. Omówić algorytm przeszukiwania grafu wszerz BFS i zilustrować go na przykładzie grafu spójnego o parametrach: 8 węzłów i 12 krawędzi.

Wyjaśnić praktyczny aspekt metody BFS. Przeanalizować złożoność obliczeniową.

TEMAT 3

Omówić wszystkie poznane algorytmy sortowania klasy O(n).

Dowieść, że rzeczywiście posiadają złożoność O(n).

TEMAT 4

Omówić algorytm (2 etapy) wyszukiwania wzorca metodą Knutha-Morrisa-Pratta i

zilustrować jego działanie przykładem. Przedyskutować złożoność obliczeniową.

TEMAT 5

Omówić B-drzewa.

Przedstawić poznane algorytmy z nimi związane i zilustrować je przykładami.