Sylabus przedmiotu

• ćwiczenia laboratoryjne

1. Podstawowe zasady analizy algorytmów (poprawność, złożoność obliczeniowa algorytmu, koszt zamortyzowany).

2. Dane, struktury danych, relacyjne struktury danych, rekurencyjne struktury danych. Miary złożoności struktur danych.

3. Listy liniowe, kolejki, stosy i ich zastosowanie. Algorytm łączenia kolejek posortowanych, zastosowanie do aktualizacji kartotek. Algorytm sortowania przez łączenie.

4. Grafy i drzewa, metody ich reprezentacji w komputerach. Przegląd wybranych algorytmów grafowych (badanie spójności, poszukiwanie drzewa rozpinającego, poszukiwanie fundamentalnego zbioru cykli, problem najkrótszych dróg).

5. Drzewa k-arne, algorytmy trawersowania.

6. Binarne drzewa poszukiwań, algorytmy wyszukiwania, wstawiania i usuwania kluczy. Drzewa AVL i czerwono-czarne.

7. B-drzewa, algorytmy wyszukiwania, wstawiania i usuwania kluczy. Zastosowanie do organizacji indeksów.

8. Stogi i ich zastosowanie do implementacji kolejek priorytetowych.

9. Tablice z laszowaniem; funkcje haszujące.

10. Tablice i drzewa sufiksowe.

11. Algorytmy geometrii obliczeniowej.

• obecność na zajęciach
• ocena ciągła (bieżące przygotowanie do zajęć i aktywność)
• śródsemestralne pisemne testy kontrolne

1. A. Aho, J. Hopcroft, J. Ullman, Projektowanie i analiza algorytmów komputerowych.

2. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT 1996.

3. E, Koffman, P. Wolfgang, Struktury danych i techniki obiektowe na przykładzie Javy 5.0.

4. W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa 1982.

5. N. Wirth, Algorytmy + struktury danych = programy, WNT, Warszawa 1980.

6. T. Cormen, Ch. leiserson, R. Rivest, Wprowadzenie do algorytmów, Warszawa 2001.