zakres do kol2

KOLOKWIUM II (tips&tricks)

Na kolokwium obowiązuje materiał z działów kolejno:

1.    abstrakcyjne struktury danych (operacje, weryfikacja poprawności formuł zdaniowych wyrażonych w języku operacji danej struktury):

a)    stosy,

b)    kolejki,

c)    słowniki,

d)    kolejki priorytetowe,

2.    implementacje abstrakcyjnych struktur danych:

a)    stos, kolejka - tablica, lista (realizacja operacji stosowych/kolejkowych)

b)    słowniki - drzewa BST, drzewa AVL (realizacja operacji słownikowych),

c)    kolejki priorytetowe - kopiec-drzewo, kopiec-tablica (realizacja operacji kolejki priorytetowej),

3.    metody przechodzenia drzew binarnych,

4.    metody przechodzenia grafów,

5.    kodowanie:

a)    kod stałej długości,

b)    optymalny kod zmiennej długości,

6.    problemy grafowe:

a)    drzewo najkrótszych ścieżek z wierzchołka źródłowego,

b)    minimalne drzewo rozpinające,

7.    geometria obliczeniowa - problem otoczki wypukłej.

Proszę powtórzyć (ze zrozumieniem) ideę działania następujących metod oraz algorytmów (wraz z oszacowaniem złożoności czasowej):

•    wyliczanie wartości wyrażeń arytmetyczny przy użyciu stosów,

•    rotacja w drzewach AVL,

•    budowa kopca w drzewie binamym/tablicy,

•    sortowanie przez kopcowanie (HeapSort),

•    przechodzenie drzewa binarnego w kolejności PreOrder, InOreder, PostOrder,

•    przechodzenie grafów w kolejności DFS, BFS,

•    budowa drzewa kodowego Huffmana,

•    algorytm Dijkstry,

•    algorytm Kruskala,

•    algorytm Prima,

•    algorytm Grahama,

•    algorytm Jarvisa.

Obowiązkowa jest umiejętność zastosowania w/w algorytmów dla przykładowych danych (tak jak było to zaprezentowana na ćwiczeniach).

Ponadto zalecane jest zapoznanie się z następującymi zadaniami (i co oczywiste ich rozwiązaniami) z książki „Algorytmy i struktury danych - zadania”, Dańko, Lan Le, Mirkowska, Rembelski, Smyk, Sydow, PJWSTK 2006:

1.    5, 8, 9, 12 - str. 56-59,

2.    1,3, 5, 6, 7, 13, 16,17,22,31 - str. 60-67,

3.    4-str. 70,

4.    1,2, 3, 5,6, 7, 9-str. 73-77,

5.    3,4, 5 - str. 84-85.