Literatura: |
Aho A. V., Hopcroft J. E., Ullman J. D.: Algorytmy i struktury danych, Helion, Gliwice 2003
L. Banachowski, A. Kreczmar, W.Rytter, „Algorytmy i struktury danych”, WNT, Warszawa,1985
T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, „Wprowadzenie do algorytmów”, WNT, 1997
Homenda W.: Algorytmy, złożoność obliczeniowa, granice obliczalności, Centrum Studiów Zaawansowanych Politechniki Warszawskiej, 2009
Sysło M.M.: Algorytmy, WSiP, Warszawa 2002
Wirth N.: Algorytmy + struktury danych = programy, WNT, Warszawa 2002
P. Wróblewski, „Algorytmy, struktury danych i techniki programowania”, Helion, 2003
|
Efekty uczenia się: |
- Zna podstawowe pojęcia i techniki dotyczące projektowania i analizy algorytmów
- Zna podstawowe struktury danych oraz wybrane algorytmy na nich działających
- Umie oszacować złoźoność prostego algortmu
- Umie zastosować i przeanalizować wybrane algorytmy oparte o metodę "dziel i zwyciężaj" w zakresie problemu sortowania i wyszukiwania
- Potrafi wykonać podstawowe operacje słownikowe na wybranych strukturach danych
- Umie zastosować wybrany algorytm wyszukiwania wzorca
Rozumie potrzebę ustawicznego dokształcania się
|
Zakres tematów: |
- Poprawność i złożoność algorytmu.
- Koszty algorytmu.
- Techniki projektowania algorytmów. Technika „dziel i zwyciężaj”.
- Metody zachłanne a programowanie dynamiczne.
- Problem wyszukiwania i sortowania.
- Struktury danych: listy, stosy, kolejki, kolejki priorytetowe.
- Struktury do reprezentacji grafów (macierze sąsiedztwa, macierze incydencji, listy incydencji). Struktury drzewiaste: BST, AVL. Grafy bez wag oraz ich podstawowe operacje i algorytmy (przeszukiwanie w szerz, przeszukiwanie w głąb). Grafy z wagami oraz ich podstawowe operacje i algorytmy (algorytm Bellmana-Forda, algorytm Dijkstry - wyznaczenie złożoności).
Problem wyszukiwania wzorca (algorytm naiwnego, algorytm Rabina-Karpa, Knutha-Morrisa-Pratta i Boyera-Moore'a).
|