Uniwersytet w Białymstoku - Centralny System Uwierzytelniania
Strona główna

Algorytmy i struktury danych I 400-IS1-1ASD
Wykład (WYK) Rok akademicki 2020/21

Informacje o zajęciach (wspólne dla wszystkich grup)

Liczba godzin: 15
Limit miejsc: (brak limitu)
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ę

Metody i kryteria oceniania:

egzamin pisemny, egzamin ustny, kolokwium + aktywność na zajęciach

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).

Metody dydaktyczne:

Prezentacja i analiza najważniejszych struktur danych oraz wybranych algorytmów. Prezentacja metod wyznaczania złożoności obliczeniowej. Prezentacja przykładowych zastosowań struktur danych i algorytmów.

Grupy zajęciowe

zobacz na planie zajęć

Grupa Termin(y) Prowadzący Miejsca Liczba osób w grupie / limit miejsc Akcje
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet w Białymstoku.
ul. Świerkowa 20B, 15-328 Białystok tel: +48 85 745 70 00 (Centrala) https://uwb.edu.pl kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)