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)
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License