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