Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Algorytmy i struktury danych II
Koordynator przedmiotu:
Dr Jan Bródka
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
4 / rok ak. 2012/2013
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. przygotowanie do ćwiczeń i zajęć laboratoryjnych – 30 h 3. przygotowanie do egzaminu – 30 h Razem nakład pracy studenta 120 h = 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 I, Matematyka Dyskretna II, Programowanie Obiektowe  
Limit liczby studentów:
Bez limitu
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 1. 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. 2. 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) 3. Algorytmy geometryczne • wyznaczanie otoczki wypukłej (algorytmy Grahama 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 zagadnienia z wykładu, przewidywane są również zadania związane z tematyką wykładów Algorytmy i Struktury Danych I oraz Matematyka Dyskretna II (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ń) • 50% - egzamin końcowy • dodatkowe punkty za dużą aktywność na ćwiczeniach oraz za nieobowiązkowe zadania (programy) domowe   Z dodatkowym warunkiem, że dla uzyskania oceny pozytywnej zarówno laboratorium jak i egzamin końcowy traktowane oddzielnie również muszą być zaliczone  
Egzamin:
tak
Literatura:
• Robert Sedgewick – „Algorytmy w C++. Grafy”, Read Me, 2003 • Witold Lipski – „Kombinatoryka dla programistów”, WNT, 2004 • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein – „Wprowadzenie do algorytmów”, WNT, 2007 • Lech Banachowski, Krzysztof Diks, Wojciech Rytter – „Algorytmy i struktury danych”, WNT, 2006 • Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman – „Algorytmy i struktury danych”, Helion, 2003  
Witryna www przedmiotu:
brak
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 na laboratoriach
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, ocena na laboratoriach
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: ocena na ćwiczeniach i laboratoriach
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 na laboratoriach
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: sprawozdania z zadań laboratoryjnych
Powiązane efekty kierunkowe: K_U14
Powiązane efekty obszarowe: T1A_U09, T1A_U15