Drukuj Eksport do pliku (MS Word)
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 i Systemy Informacyjne
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-IN000-ISP-0023
Semestr nominalny:
4 / rok ak. 2019/2020
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

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_U11
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: