- 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
- Grupa przedmiotów:
- Wspólne
- Kod przedmiotu:
- 1120-IN000-ISP-0023
- Semestr nominalny:
- 4 / rok ak. 2015/2016
- Liczba punktów ECTS:
- 4
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- 1. godziny kontaktowe – 60 h; w tym
a) obecność na wykładach – 15 h
b) obecność na ćwiczeniach – 15 h
c) obecność na laboratoriach – 30 h
2. praca własna studenta – 60 h; w tym
a) przygotowanie do ćwiczeń i zajęć laboratoryjnych – 30 h
b) przygotowanie do kolokwium i egzaminu – 30 h
Razem 120 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
Razem 60 h, co odpowiada 2 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. część przygotowania 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 algo-rytmów jak programowanie dynamiczne, algorytmy z powrotami, 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 powrotami, 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, algo-rytmy 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:
- Program wykładu:
Grafy. Metody reprezentacji grafów (macierz sąsiedztwa i listy incydencji). 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). Algorytmy dla zagadnienia komiwojażera (dokładne i przybliżone). Przepływy w sieciach.
Wyszukiwanie wzorca w tekście. Algorytm naiwny i jego usprawnienia (algorytmy Knutha-Morrisa-Pratta i Boyera-Moore'a). Inne algorytmy (Karpa-Rabina i Karpa-Millera-Rosenberga). Zagadnienia pokrewne (wzorzec ze znakami nieznaczącymi, wzorzec dwuwymiarowy)
Algorytmy geometryczne. Wyznaczanie otoczki wypukłej (algorytmy Gra-hama i Jarvisa). Problem przynależności punktu do wielokąta (przypadek ogólny i wielokąta wypukłego). Znajdywanie par przecinających się odcinków (metoda zamiatania)
Program laboratorium:
Na każdych (dwugodzinnych) zajęciach odrębne zadanie ilustrujące zagad-nienia 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 ćwicze-niach 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. W. Lipski, Kombinatoryka dla programistów, WNT, 2004
3. T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT, 2007
4. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, 2006
5. A. V. Aho, J. E. Hopcroft, J. D. Ullman, Algorytmy i struktury danych, Helion, 2003
- Witryna www przedmiotu:
- e.mini.pw.edu.pl
- Uwagi:
Efekty uczenia się
Profil ogólnoakademicki - wiedza
- Efekt W01
- Ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie algorytmów i ich złożoności obliczeniowej
Weryfikacja: egzamin
Powiązane efekty kierunkowe:
K_W04
Powiązane efekty obszarowe:
T1A_W03
- Efekt W02
- Ma szczegółową wiedzę nt. algorytmiki oraz projektowania i programowania obiektowego
Weryfikacja: egzamin, ocena zadań wykonywanych w ramach laboratoriów
Powiązane efekty kierunkowe:
K_W08
Powiązane efekty obszarowe:
T1A_W04
- Efekt 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 efekty kierunkowe:
K_W10
Powiązane efekty obszarowe:
T1A_W07
Profil ogólnoakademicki - umiejętności
- Efekt 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 efekty kierunkowe:
K_U03
Powiązane efekty obszarowe:
T1A_U09
- Efekt 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 efekty kierunkowe:
K_U11
Powiązane efekty obszarowe:
T1A_U09, T1A_U14, T1A_U15
- Efekt U03
- Potrafi ocenić złożoność obliczeniową algorytmów i problemów
Weryfikacja: kolokwium, ocena zadań wykonywanych w ramach laboratoriów
Powiązane efekty kierunkowe:
K_U14
Powiązane efekty obszarowe:
T1A_U09, T1A_U15