Serwisy internetowe Uniwersytetu Warszawskiego | USOSownia - uniwersyteckie forum USOSoweNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Algorytmy dynamiczne

Informacje ogólne

Kod przedmiotu: 1000-2M14AD Kod Erasmus / ISCED: 11.3 / (0612) Database and network design and administration
Nazwa przedmiotu: Algorytmy dynamiczne
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Punkty ECTS i inne: (brak)
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 kształcenia:

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.