Nazwa przedmiotu:
Algorytmy i struktury danych 2
Koordynator przedmiotu:
Dr inż. Jan Bródka, Mgr inż. Jan Karwowski, Mgr inż. Małgorzata Śleszyńska-Nowak
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. 2016/2017
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
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 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, 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:
Program wykładu: 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). Program 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 laboratorium i egzamin końcowy traktowane oddzielnie również muszą być zaliczone (kolokwium nie musi).
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. A. V. Aho, J. E. Hopcroft, J. D. Ullman, Algorytmy i struktury danych, Helion, 2003. 4. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, 2006. 5. Materiały z wykładów na stronie internetowej http://www.mini.pw.edu.pl/~brodka.
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