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, dr inż. Michał Dębski
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. 2020/2021
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 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 laboratorium 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:
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_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: