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. 2011/2012
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
  • Laboratorium0h
  • 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:
Cel przedmiotu:
• Znajomość omawianych algorytmów • Ogólna umiejętność konstruowania wydajnych algorytmów i dobierania właściwych struktur danych dla rozpatrywanych zagadnień.  
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:
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:
Uwagi:

Efekty uczenia się