| Literatura: |
Literatura podstawowa:
T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, „Wprowadzenie do algorytmów”, WNT, 1997
P. Wróblewski, „Algorytmy, struktury danych i techniki programowania”, Helion, 2003
L. Banachowski, A. Kreczmar, W.Rytter, „Algorytmy i struktury danych”, WNT, Warszawa,1985
Literatura uzupełniająca:
A. Acho, J. Hopcroft, J. Ullman, „Projektowanie i analiza algorytmów komputerowych”, PWN, Warszawa,1982
N. Wirth, „Algorytmy+Struktury danych=Programy, WNT
|
| Efekty uczenia się: |
Zna podstawowe pojęcia i techniki dotyczące projektowania i analizy algorytmów . K_W03
Zna podstawowe struktury danych oraz wybrane algorytmy na nich działających . K_W03
Rozumie potrzebę ustawicznego dokształcania się. K_K02
Weryfikacja: egzamin pisemny; zaliczenie - od 51% punktów
|
| 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). Tablice z haszowaniem. 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). Problemy obliczeniowo trudne: NP-zupełność, nierozstrzygalność. Problem P=NP.
|
