Algorytmy i struktury danych 0600-IS1-2ASD
Ćwiczenia (CW) Rok akademicki 2017/18

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

Umie oszacować złożoność prostego algoyrtmu . K_U06

Umie zastosować i przeanalizować wybrane algorytmy oparte o metodę 'dziel i zwyciężaj' w zakresie problemu sortowania i wyszukiwania . K_U06, K_U08

Potrafi wykonać podstawowe operacje słownikowe na wybranych strukturach danych . K_U06

Umie zastosować wybrany algorytm wyszukiwania wzorca. K_U06, K_U08

Rozumie potrzebę ustawicznego dokształcania się. K_K02

Weryfikacja efektów kształcenia na podstawie kolokwiów oraz aktywności w trakcie zajęć.

Warunkiem zaliczenia przedmiotu jest uzyskanie minimum 60% punktów z kolokwiów oraz obecność na zajęciach. Dopuszczalny limit zajęć nieusprawiedliwionych: 4 godziny (2 ćwiczenia).

Poprawność i złożoność algorytmu. Koszty algorytmu. Technika „dziel i zwyciężaj”. Problem wyszukiwania i sortowania. Struktury danych: listy, stosy, kolejki, kolejki priorytetowe. Tablice z haszowaniem. Struktury drzewiaste: BST, AVL. Struktury do reprezentacji grafów (macierze sąsiedztwa, macierze incydencji, listy incydencji). 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.

Ćwiczenia: 30 godz.