- Nazwa przedmiotu:
- Algorytmy i struktury danych 2
- Koordynator przedmiotu:
- Dr inż. Jan Bródka
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia I stopnia
- Program:
- Informatyka i Systemy Informacyjne
- Grupa przedmiotów:
- Wspólne
- Kod przedmiotu:
- 1120-IN000-ISP-0241
- Semestr nominalny:
- 4 / rok ak. 2022/2023
- Liczba punktów ECTS:
- 4
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- 1. godziny kontaktowe – 68 h; w tym
a) obecność na wykładach – 15 h
b) obecność na ćwiczeniach – 15 h
c) obecność na laboratoriach – 30 h
d) konsultacje – 5 h
e) obecność na egzaminie – 3 h
2. praca własna studenta – 47 h; w tym
a) przygotowanie do ćwiczeń – 7 h
b) przygotowanie do zajęć laboratoryjnych – 20 h
c) przygotowanie do kolokwium i egzaminu – 20 h
Razem 115 h, co odpowiada 4 pkt. ECTS
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- 1. obecność na wykładach – 15 h
2. obecność na ćwiczeniach – 15 h
3. obecność na laboratoriach – 30 h
4. konsultacje – 5 h
5. obecność na egzaminie – 3 h
Razem 68 h, co odpowiada 3 pkt. ECTS
- Język prowadzenia zajęć:
- polski
- Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- 1. obecność na laboratoriach – 30 h
2. przygotowanie do zajęć laboratoryjnych – 20 h
Razem 50 h, co odpowiada 2 pkt. ECTS
- Formy zajęć i ich wymiar w semestrze:
-
- Wykład15h
- Ćwiczenia15h
- Laboratorium30h
- Projekt0h
- Lekcje komputerowe0h
- Wymagania wstępne:
- Podstawowa wiedza na temat grafów, znajomość podstawowych struktur danych (stos, kolejka, kolejka priorytetowa, drzewa zrównoważone), znajomość pojęcia złożoności obliczeniowej, biegła umiejętność programowania w językach wysokiego poziomu (najlepiej C#).
Przedmioty poprzedzające: Algorytmy i struktury danych 1, Matematyka dyskretna 2, Programowanie 3 – zaawansowane
- Limit liczby studentów:
- Ćwiczenia – 30 os. /grupa Laboratoria (ćwiczenia komputerowe) – 12-15 os. / grupa
- Cel przedmiotu:
- Celem przedmiotu jest zdobycie umiejętności konstruowania wydajnych algorytmów i dobierania właściwych struktur danych dla rozpatrywanych zagadnień, a także zapoznanie się z takimi technikami konstruowania algorytmów jak programowanie dynamiczne, algorytmy z nawrotami, algorytmy zachłanne, zasada "dziel i zwyciężaj". Celem przedmiotu jest również zapoznanie się z wydajnymi algorytmami dotyczącymi grafów i innych przykładowych dziedzin.
Po ukończeniu kursu studenci powinni:
- znać i rozumieć pojęcie złożoności obliczeniowej, umieć oceniać klasę złożoności algorytmów
- umieć konstruować wydajne algorytmy wykorzystując takie techniki jak programowanie dynamiczne, algorytmy z nawrotami, algorytmy zachłanne, zasada "dziel i zwyciężaj"
- umieć dobrać struktury danych odpowiednie dla rozwiązywanego problemu
- znać najważniejsze algorytmy grafowe i metody reprezentacji grafów, a w szczególności algorytmy wyznaczania najkrótszych dróg w grafach, algorytmy dla problemu komiwojażera, algorytmy obliczania maksymalnego przepływu w sieciach
- znać algorytmy wyszukiwania wzorca w tekście
- znać podstawowe algorytmy geometryczne, np. wyznaczania otoczki wypukłej
- Treści kształcenia:
- Wykład:
Grafy. Metody reprezentacji grafów (macierz sąsiedztwa i listy incydencji). Przeszukiwanie grafów (w głąb, wszerz, ogólne). Wyznaczanie najkrótszych dróg w grafie: algorytm Forda-Bellmana, algorytm Dijkstry, algorytm A*, algorytm dla grafu acyklicznego, odległości pomiędzy wszystkimi parami wierzchołków grafu (algorytm Floyda-Warshalla, algorytm Johnsona). Algorytmy dla zagadnienia komiwojażera (dokładne i przybliżone). Przepływy w sieciach (algorytmy Forda-Fulkersona, Dinica, „push-relabel”).
Algorytmy geometryczne. Wyznaczanie otoczki wypukłej (algorytmy Grahama, Jarvisa, QuickHull). Problem przynależności punktu do wielokąta. Znajdywanie par przecinających się odcinków (metoda zamiatania).
Wyszukiwanie wzorca w tekście. Algorytm naiwny i jego usprawnienia (algorytmy Knutha-Morrisa-Pratta i Boyera-Moore'a). Algorytm Karpa-Rabina. Zagadnienia pokrewne (wzorzec ze znakami nieznaczącymi, wzorzec dwuwymiarowy).
Laboratorium:
Na każdych (dwugodzinnych) zajęciach odrębne zadanie ilustrujące zagadnienia z wykładu, przewidywane są również zadania związane z tematyką wykładów Algorytmy i struktury danych 1 oraz Matematyka dyskretna 2 (do których nie ma laboratoriów).
- Metody oceny:
- 50% - laboratorium (suma punktów za poszczególne zadania, obecność obowiązkowa, nie ma możliwości poprawiania zadań);
20% - kolokwium pisemne;
30% - egzamin końcowy; dodatkowe punkty za dużą aktywność na ćwiczeniach oraz za nieobowiązkowe zadania (programy) domowe.
Dla uzyskania oceny pozytywnej zarówno laboratorium jak i egzamin końcowy traktowane oddzielnie również muszą być zaliczone.
- Egzamin:
- tak
- Literatura:
- 1. R. Sedgewick, Algorytmy w C++. Grafy, Read Me, 2003.
2. T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT, 2007.
3. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, 2006.
4. A. V. Aho, J. E. Hopcroft, J. D. Ullman, Algorytmy i struktury danych, Helion, 2003.
5. Materiały z wykładów na stronie internetowej http://www.mini.pw.edu.pl/~brodka.
- Witryna www przedmiotu:
- Uwagi:
Efekty uczenia się
Profil ogólnoakademicki - wiedza
- Charakterystyka W01
- Ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie algorytmów i ich złożoności obliczeniowej
Weryfikacja: egzamin
Powiązane charakterystyki kierunkowe:
K_W04
Powiązane charakterystyki obszarowe:
- Charakterystyka W02
- Ma szczegółową wiedzę nt. algorytmiki oraz projektowania i programowania obiektowego
Weryfikacja: egzamin, ocena zadań wykonywanych w ramach laboratoriów
Powiązane charakterystyki kierunkowe:
K_W08
Powiązane charakterystyki obszarowe:
- Charakterystyka W03
- Zna podstawowe metody i techniki stosowane przy rozwiązywaniu prostych zadań informatycznych z zakresu analizy złożoności obliczeniowej algorytmów
Weryfikacja: egzamin, kolokwium, ocena zadań wykonywanych w ramach laboratoriów
Powiązane charakterystyki kierunkowe:
K_W10
Powiązane charakterystyki obszarowe:
Profil ogólnoakademicki - umiejętności
- Charakterystyka U01
- Potrafi wykorzystać wiedzę z teorii grafów do tworzenia, analizowania i stosowania modeli matematycznych służących do rozwiązywania problemów z różnych dziedzin
Weryfikacja: kolokwium, ocena zadań wykonywanych w ramach laboratoriów
Powiązane charakterystyki kierunkowe:
K_U03
Powiązane charakterystyki obszarowe:
- Charakterystyka U02
- Ma umiejętność formułowania algorytmów i ich programowania z użyciem przynajmniej jednego z popularnych narzędzi
Weryfikacja: ocena zadań wykonywanych w ramach laboratoriów
Powiązane charakterystyki kierunkowe:
K_U14
Powiązane charakterystyki obszarowe:
- Charakterystyka U03
- Potrafi ocenić złożoność obliczeniową algorytmów i problemów
Weryfikacja: kolokwium, ocena zadań wykonywanych w ramach laboratoriów
Powiązane charakterystyki kierunkowe:
K_U14
Powiązane charakterystyki obszarowe:
Profil ogólnoakademicki - kompetencje społeczne
- Charakterystyka K01
- Rozumie znaczenie wiedzy matematycznej w opisie procesów, tworzeniu modeli, zapisie algorytmów i innych działaniach w obszarze informatyki
Weryfikacja: egzamin, kolokwium, ocena zadań wykonywanych w ramach laboratoriów
Powiązane charakterystyki kierunkowe:
K_K02
Powiązane charakterystyki obszarowe: