1. SylabUZ
2. Faculty of Mathematics, Computer Science and Econometrics
3. winter term 2022/2023
4. Mathematics - First-cycle studies leading to Bachelor's degree
5. Algorithms and Data Structures

Generate PDF for this page

Algorithms and Data Structures - course description

Aim of the course

Zdobycie wiedzy i umiejętności w zakresie analizy algorytmów. Znajomość i umiejętność implementacji algorytmów sortowania i selekcji, algorytmów wyszukiwania, podstawowych algorytmów grafowych.

Prerequisites

Save changes

Znajomość podstawowego kursu z analizy i algebry liniowej. Umiejętność programowania komputerów w zakresie programowania strukturalnego.

Scope

Wykład

1. Wprowadzenie. Algorytmy i ich złożoność obliczeniowa i pamięciowa. Semantyczna poprawność algorytmu. Badanie poprawności algorytmów. (2 godz.)
2. Asymptotyka. Rzędy wielkości funkcji. Szacowanie sum. (2 godz.)
3. Metody projektowania efektywnych algorytmów. Rekurencja, zasada „dziel i zwyciężaj”, algorytmy zachłanne, programowanie dynamiczne. (2 godz.)
4. Algorytmy sortowania i selekcji. Algorytmy sortowania wewnętrznego i zewnętrznego. Algorytm szybkiej selekcji. (4 godz.)
5. Algorytmy wyszukiwania. Wyszukiwanie: liniowe, binarne, interpolacyjne. (2 godz.)
6. Struktury danych dla słownika. Wektor charakterystyczny, haszowanie, drzewa poszukiwań binarnych. (4 godz.)
7. Wyszukiwanie zewnętrzne. B – drzewa. (2 godz.)
8. Algorytmy grafowe. Reprezentacje komputerowe grafów. Przechodzenie drzew, przechodzenie grafów, wyznaczanie minimalnego drzewa rozpinającego. Najkrótsze ścieżki. (4 godz.)
9. Algorytmy tekstowe: problem wyszukiwania wzorca, drzewa sufiksowe i grafy podsłów. (4 godz.)
10. Algorytmy geometryczne: problem przynależności, wypukła otoczka, metoda zamiatania. (4 godz.)

Laboratorium

1. Wyznaczanie złożoności obliczeniowej i pamięciowej algorytmów. (4 godz.)
2. Badanie poprawności algorytmów. (4 godz.)
3. Algorytmy sortowania i selekcji. (4 godz.)
4. Struktury danych dla zbiorów. (6 godz.)
5. Algorytmy grafowe. (6 godz.)
6. Algorytmy tekstowe i algorytmy geometryczne. (6 godz.)

Teaching methods

Wykład: wykład problemowy.

Laboratorium: ćwiczenia laboratoryjne w pracowni komputerowej – implementacja i testowanie wybranych algorytmów. Każdy student w trakcie semestru musi zrealizować cztery projekty. Każdy z projektów polegać będzie na zaimplementowaniu wskazanego przez prowadzącego algorytmu do rozwiązania konkretnego praktycznego zadania, napisaniu do tego programu, przetestowaniu go oraz przedstawieniu dokumentacji zgodnie z zadaną specyfikacją. Nad dwoma z tych czterech projektów studenci będą pracowali w grupach 2-3 osobowych. Ponadto studenci na zajęcia będą pisali programy implementujące różne inne algorytmy.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Wykład. Egzamin weryfikujący efekty kształcenia w zakresie wiedzy i umiejętności. Egzamin składa się z dwóch części, pisemnej i ustnej. Warunkiem przystąpienia do części ustnej jest uzyskanie 30% punktów z części pisemnej. Uzyskanie 50% punktów z części pisemnej gwarantuje uzyskanie pozytywnej oceny.

Laboratorium. Ocena końcowa jest wystawiana na podstawie punktów uzyskanych na zajęciach. Punkty uzyskuje się za: napisane na zajęciach sprawdziany, zrealizowane na zajęciach projekty, aktywność na zajęciach.

Na ocenę z przedmiotu składa się ocena z laboratorium (50%) oraz ocena z egzaminu (50%). Warunkiem przystąpienia do egzaminu jest pozytywna ocena z laboratorium. Warunkiem zaliczenia przedmiotu jest pozytywna ocena z egzaminu.

Recommended reading

1. Aho A., Hopcroft J.E., Ullman J.D.,: Projektowanie i analiza  algorytmów komputerowych, PWN, Warszawa 1983.
2. Banachowski L., Diks K.,  Rytter W., Algorytmy i struktury danych, WNT, Warszawa 1996.
3. Cormen T.H., Leiserson C.E., Rivest R.L., Wprowadzenie do algorytmów, WNT, Warszawa 1997.

Further reading

1. Lipski W.: Kombinatoryka dla programistów, WNT, 2007.
2. Knuth D. : Sztuka programowania, t. 1-3, WNT, Warszawa 2001.
3. Wróblewski P.: Algorytmy, struktury danych i techniki programowania, wyd. II popr., Helion, 2001.

Notes

Modified by dr Alina Szelecka (last modification: 19-05-2022 21:46)