Algorytmy aproksymacyjne, teoria złożoności
Opis zajęć
Niektóre problemy algorytmiczne okazują się trudniejsze od innych - np. potrafimy w czasie wielomianowym znaleźć cykl Eulera w grafie, a cyklu Hamiltona - już nie (i - o ile $P \neq NP$, jak się powszechnie uważa - nigdy nie będziemy tego umieć) Często jednak możemy uzyskać przybliżone rozwiązanie problemu, korzystając z tzw. algorytmu aproksymacyjnego.
Podczas warsztatów poznamy różne klasy złożoności problemów i zbadamy związki pomiędzy nimi - co krok będziemy napotykać na fascynujące wyniki. Dokonamy też przeglądu różnych technik pojawiających się w algorytmach aproksymacyjnych.
Wbrew temu, co mógłby sugerować powyższy opis, rodem z książek popularnonaukowych - warsztaty będą jak najbardziej konkretne, trudne, i ciekawe :)
Program
- szczegóły programu ukażą się wkrótce
Wymagania
- ogólne obycie algorytmiczne
- znajomość pojęcia klasy złożoności oraz redukcji (a bardziej intuicji związanych z tymi pojęciami - sformalizujemy je na warsztatach)
Literatura
- Cormen, Leiserson, Rivest[, Stein] - Wprowadzenie do algorytmów (rozdziały o NP-zupełności i algorytmach aproksymacyjnych)
- Wikipedia
Kwalifikacja
- zadania kwalifikacyjne ukażą 5 czerwca (przepraszam za opóźnienie)
wersja strony: 4, ostatnia edycja: 24 May 2009 21:03