Teoria obliczeń i złożoności obliczeniowej 2

RSS

Cel przedmiotu

Celem przedmiotu jest zapoznanie studentów z metodami rozwiązywania problemów o wysokiej złożoności obliczeniowej (zarówno pod względem teoretycznym jak i praktycznym) oraz przedstawienie zaawansowanych metod analizy złożoności czasowej i pamięciowej.

Program wykładu

Dokładne, wykładnicze algorytmy dla problemów NP-zupełnych. Algorytmy aproksymacyjne dla problemów NP-zupełnych (w tym w pełni wielomianowe schematy aproksymacji). Obliczenia z wyrocznią oraz hierarchia wielomianowa. Klasa PSPACE i jej relacja do hierarchii wielomianowej. Obliczenia z pamięcią logarytmiczną. Problem L versus NL oraz NL versus coNL. Granice aproksymacji. Twierdzenie o probablistycznie weryfikowalnych dowodach (PCP).

Charakterystyka pozostałych zajęć

Prowadzony są zajęcia projektowe, których celem jest zapoznanie studentów z praktycznymi aspektami rozwiązywania trudnych obliczeniowo problemów (np. NP-zupełnych) oraz przedstawienie praktycznego znaczenia wysokiej złożoności obliczeniowej. W ramach projektu studenci otrzymują problem dla którego nie jest znany algorytm wielomianowy i ich zadanie polega na napisaniu programu, który efektywnie znajduje rozwiązania dla możliwie jak najszerszej gamy instancji tego problemu. Studenci pracują indywidualnie. Wszyscy studenci zajmują się tym samym problemem.

Bibliografia

1. Sipser M.: Wprowadzenie do teorii obliczeń. WNT, Warszawa 2009
2. Papadimitriou C.H.: Złożoność obliczeniowa. WNT, Warszawa 2002
3. Bovet D.P, Crescenzi P.: Introduction to the theory of complexity. Prentice Hall, 1994
4. Wegener I.: Complexity Theory, Springer, 2005
5. Kościelski A.: Teoria obliczeń. Wydawnictwo Uniwersytetu Wrocławskiego, Wrocław 1997

Wszelkie prawa zastrzeżone © 2010 Katedra Informatyki   |   Akademia Górniczno-Hutnicza   |   Realizacja Creative Bastards