Prowadzony w cyklach: 2023/24L, 2024/25L

Punkty ECTS: 6

Język: polski

Organizowany przez: Wydział Matematyki i Informatyki

Algorytmy i struktury danych II 1000-I1ASD-2

Wykład (tematy):

1. Struktury danych
a) Struktury dla uporządkowanego multizbioru
b) Drzewa licznikowe, potęgowe (Fenwicka)
c) Drzewa przedziałowe (punkt-przedział, przedział-punkt, przedział-przedział) d) Kolejka minimów i dla dowolnej operacji łącznej

2. Przepływy w sieciach
a) algorytm Forda-Fulkersona
b) algorytm Edmondsa-Karpa

3. Algorytmy geometryczne
a) Położenie punktu względem odcinka
b) Przynależność punktu do wielokąta wypukłego, dowolnego
c) Otoczka wypukła - algorytm Jarvisa
d) Otoczka wypukła - sortowanie biegunowe i algorytm Grahama
e) Metoda zamiatania - przecinanie odcinków

4. Algorytmy tekstowe
a) Problem wyszukiwania wzorca, algorytm naiwny
b) Słownik podsłów bazowych
c) Haszowanie i algorytm Rabina-Karpa
d) Prefiksy, sufiksy i algorytm KMP
e) Algorytm Boyera-Moore'a
f) Algorytm Aho-Corasick wyszukiwania wzorca w tekście
g) Wyszukiwanie wzorca z wykorzystaniem automatów skończonych
h) Algorytm Huffmana
i) Drzewa palindromów, podpalindromy, algorytm Manachera

5. Algorytmy aproksymacyjne
a) Pokrycie wierzchołkowe
b) Pokrycie zbioru
c) Problem sumy podzbioru

W trakcie laboratorium studenci będą:

1. analizować oraz implementować omawiane algorytmy
2. tworzyć projekty zespołowe wykorzystując poznane algorytmy
3. w trakcie tworzenia projektów zespołowych wykorzystywany będzie GiT

Całkowity nakład pracy studenta

30 godz. – wykład; 30 godz. – laboratorium 50 godz. – praca własna - bieżące przygotowanie do zajęć, przygotowanie referatów, przygotowanie programów komputerowych, studiowanie literatury, konsultacje z prowadzącymi zajęcia 35 godz. – praca własna: przygotowanie do egzaminu 5 godz. – zaliczenie laboratorium i egzamin RAZEM: 150 godz. 6 pkt. ECTS

Efekty uczenia się - wiedza

W1: zna zaawansowane struktury danych, m.in. dla uporządkowanego multizbioru, drzewa licznikowe, potęgowe (Fenwicka), drzewa przedziałowe, kolejka minimów (K_W05) W2: zna podstawowe pojęcia teorii sieci oraz podstawowe algorytmy wyznaczające maksymalny przepływ w sieci (K_W02, K_W03, K_W05) W3: zna podstawowe algorytmy geometryczne, m.in. położenie punktu względem odcinka, przynależność punktu do wielokąta, znajdowanie otoczki wypukłej, metoda zamiatania (K_W02, K_W03) W4: zna podstawowe algorytmy tekstowe, m.in. algorytmy wyszukiwania wzorca, algorytm Rabina-Karpa, algorytm Huffmana, algorytm Manachera (K_W02, K_W03) W5: zna algorytmy aproksymacyjne wyznaczające: pokrycie wierzchołkowe, pokrycie zbioru, rozwiązujący problem sumy podzbioru (K_W02, K_W03) W6: zna przykłady zastosowań omawianych algorytmów (K_W02, K_W03)

Efekty uczenia się - umiejętności

U1: umie zastosować poznane algorytmy na przykładach (K_U07) U2: potrafi samodzielnie wyszukać (w internecie lub literaturze) oraz zastosować na odpowiednich przykładach algorytmy rozwiązujące zadane problemy (K_U02) U3: potrafi zaimplementować poznane algorytmy (K_U07) U4: potrafi pracować indywidualnie i w zespole informatyków, w tym także potrafi zarządzać swoim czasem oraz podejmować zobowiązania i dotrzymywać terminów (K_U03)

Efekty uczenia się - kompetencje społeczne

K1: przekazuje innym swoją wiedzę i przemyślenia w zrozumiały sposób; właściwie rozumie sformułowania pytań i problemów, poprawnie posługuje się terminologią fachową (K_K02) K2: rozumie potrzebę ciągłego uczenia się (K_K03)

Metody dydaktyczne podające

- wykład problemowy
- wykład informacyjny (konwencjonalny)

Metody dydaktyczne poszukujące

- projektu
- doświadczeń
- referatu
- klasyczna metoda problemowa
- laboratoryjna
- ćwiczeniowa

Wymagania wstępne

Algorytmy i struktury danych, Podstawy programowania, Algorytmika i programowanie w języku Python, Programowanie I, Programowanie II

Koordynatorzy przedmiotu

Justyna Kosakowska

Kryteria oceniania

Zaliczenie laboratorium na podstawie przygotowanych projektów (indywidualnych oraz zespołowych z wykorzystaniem GIT) w postaci programów komputerowych będących implementacja poznanych algorytmów. Weryfikacja efektów: U1, U2, U3, U4, K1, K2

Egzamin pisemny lub ustny z tematyki zajęć - wykazanie się znajomością poznanego materiału. Dopuszcza się połączenie egzaminu z prezentacją projektów przygotowanych w ramach laboratorium. Weryfikacja efektów: W1, W2, W3, W3, W4, W5, W6

Kryteria oceny:

- bardzo dobra – student bardzo dobrze przedstawia, omawia oraz implementuje algorytmy prezentowane na zajęciach; potrafi zastosować algorytmy do przykładów, które nie były omawiane na zajęciach; potrafi zmodyfikować znane algorytmy i uzasadnić poprawność swojego rozumowania

- dobra – student prawidłowo przestawia, omawia oraz implementuje algorytmy prezentowane na zajęciach; potrafi zastosować algorytmy do przykładów, które nie były omawiane na zajęciach;

- dostateczna – student prawidłowo przestawia, omawia oraz implementuje proste algorytmy prezentowane na zajęciach; potrafi zastosować algorytmy do przykładów, które były omawiane na zajęciach;

- niedostateczna – student nie potrafi w dostatecznym stopniu przedstawić ani zaimplementować algorytmów prezentowanych na zajęciach, nie potrafi zastosować ich do prostych przykładów omawianych na zajęciach

Praktyki zawodowe

Nie dotyczy

Literatura

Literatura podstawowa:

• L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, 2018
• T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT PWN, 2012
• D. Harel, Rzecz o istocie informatyki. Algorytmika, WNT, 1992.
• M.M. Syslo, N. Deo, J.S. Kowalik, Algorytmy optymalizacji dyskretnej z programami w języku Pascal, WN PWN, 1997
• M.M. Sysło, Algorytmy, Helion, 2016
• M.M. Sysło, Piramidy, szyszki i inne konstrukcje programistyczne, Helion, 2015
• J. Tomasiewicz, Zaprzyjaźnij się z algorytmami, Przewodnik dla początkujących i średnio zaawansowanych, PWN, 2016

Literatura uzupełniająca:

• A.V. Aho, J.E. Hopcroft, J.D. Ullman, Algorytmy i struktury danych, Helion, 2003.
• R.J. Wilson, Wprowadzenie do teorii grafów, PWN 2016 r.
• P. Stańczyk, Algorytmika praktyczna. Nie tylko dla mistrzów, PWN, 2009.
• P. Mikołajczyk, Wprowadzenie do STL, UMCS, Lublin 2012.

Uwagi

W cyklu 2023/24L:

Zaliczenie przedmiotu:

1) Zaliczenie na podstawie projektu

2) Studenci zostaną podzieleni na grupy i w grupach będą tworzyć wspólny projekt

3) Wyniki pracy (dokumentacja, pliki programów, opis poprawności rozwiązania i raporty przeprowadzonych testów) będą zapisywane z wykorzystaniem systemu Git

4) Oceniane będzie: poprawność rozwiązania, systematyczność pracy, sposób prezentacji, kompletność i przejrzystość dokumentacji

5) Oceniane będzie również indywidualne zaangażowanie studenta w realizację projektu

6) Zaliczenie laboratorium (ocena): oceniane będą programy komputerowe i ich poprawność

7) Zaliczenie wykładu (ocena/egzamin): obecność na wykładzie; prezentacja projektów (oceniana będzie dokumentacja oraz opis poprawności rozwiązania); dodatkowo oceniana będzie znajomość algorytmów prezentowanych na wykładzie.

W cyklu 2024/25L: