Algorytmy i struktury danych

RSS

Cel przedmiotu

Przegląd podstawowych algorytmów i struktur danych. Projektowanie i analiza algorytmów.

Program wykładu

Wprowadzenie do złożoności: złożoność obliczeniowa pamięciowa i czasowa (pesymistyczna, optymistyczna, oczekiwana) . Sortowania: proste, QuickSort, MergeSort, HeapSprt, pozycyjne. Selekcja: algorytm Hoare’a, magiczne piątki. Elementarne struktury danych (stos, kopiec, kolejka, kolejka priorytetowa, listy, lista z przeskokami). Drzewa binarne: AVL, czerwono-czarne, drzewa typu splay. Drzewa słownikowe, B-drzewa. Tablice z haszowaniem. Metody konstruowania i analizowania algorytmów: metoda dziel i zwyciężaj, programowanie dynamiczne, metoda zachłanna. Algorytmy grafowe: DFS, BFS, minimalne drzewo rozpinające, najkrótsze ścieżki.

Charakterystyka pozostałych zajęć

W przedmiocie prowadzone są ćwiczenia audytoryjne. Treści tych zajęć ugruntowują i rozszerzają wiedzę przekazywaną podczas wykładów.

Bibliografia

1. Wprowadzenie do algorytmów, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.
2. Algorytmy + struktury danych = programy, Niklaus Wirth, Wydawnictwa Naukowo - Techniczne, 2004.
3. Projektowanie i analiza algorytmów komputerowych, A. Aho, J. Hopcroft, J. Ullman, Helion Wydawnictwo, 2003.

Wszelkie prawa zastrzeżone © 2010 Katedra Informatyki   |   Akademia Górniczno-Hutnicza   |   Realizacja Creative Bastards