Algorytmy dynamiczne

Informacje ogólne

Kod przedmiotu:	1000-2M14AD
Kod Erasmus / ISCED:	11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu:	Algorytmy dynamiczne
Jednostka:	Wydział Matematyki, Informatyki i Mechaniki
Grupy:	Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne:	(brak) Podstawowe informacje o zasadach przyporządkowania punktów ECTS: roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS; tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h; 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się; tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS; nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta. zobacz reguły punktacji
Język prowadzenia:	angielski
Rodzaj przedmiotu:	monograficzne
Wymagania (lista przedmiotów):	Algorytmika 1000-2D97AL
Skrócony opis:	W wielu zastosowaniach musimy wykonywać pewne obliczenia wielokrotnie dla niewiele zmienionych danych. Stawia nas to przed problemem wyznaczenia wartości pewnej funkcji bez obliczania wszystkiego od zera. W ramach wykładu przedstawię znane wyniki dla problemów dynamicznych, takich jak: FFT, spójność grafu, domknięcie przechodnie, wyszukiwanie wzorca w tekście.
Pełny opis:	1.Omówienie problemów oraz definicje 2.Dynamiczne drzewa 3.Dynamiczne problemy algebraiczne (FFT i inne) 4.Dynamiczne wyszukiwanie wzorca w tekście 5.Dynamiczna spójność grafu 6.Dynamiczne domknięcie przechodnie oraz dynamiczne macierze 7.Dynamiczne najkrótsze ścieżki w grafach 8.Dynamiczne najkrótsze ścieżki w grafach planarnych 9.Dynamiczne algorytmy aproksymacyjne dla najkrótszych ścieżek w grafach
Literatura:	Prace konferencyjne i czasopismowe z ostatnich kilku lat.
Efekty uczenia się:	Wiedza: Student zna dobrze algorytmy dynamiczne, takie jak: algorytmy algebraiczne, czy grafowe. Umiejętności: Student umie zastosować poznane techniki w różnych problemach, oraz ma wiedzie o tym w jaki sposób wybrać najlepszy algorytm do danego zastosowania.
Metody i kryteria oceniania:	Ocena na podstawie zadań domowych. Zaliczenie w drugim terminie na podstawie egzaminu ustnego.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.