Algoritmusok és bonyolultságelmélet

2012-13 Tavasz

Előadások

2013. február 7.: Kiszámíthatóság, Turing-gép, alapfogalmak
- Az előadás jegyzete pdf file ps file
- Az előadáson túlmutató segédanyagok:
  - Egy Java szimuláció Turing-gép programozásra
  - Egy másik Java szimuláció
  - A Wikipedia Turing-gépről szóló oldala
  - Alan Turing életéről és munkájáról szóló lap
  - Egy másik Alan Turingról szóló lap
2013. február 14.: Bonyolultsági osztályok. Turing-gép fogalmának változatai. PALINDROM nyelv bonyolultsága.
- Az előadás jegyzete: pdf file
- Az előadáson túlmutató segédanyagok:
  - Nemcsak azok az osztályok léteznek, amiket bevezettünk. Egy egész zoo (állatkert) létezik
  - Egy másik (közelről sem teljes) lista
  - Egy harmadik próbálkozás.
2013. február 21.: Bonyolultsági osztályok közötti egyszerű viszonyok. Nem-determinizmus.
- Az előadás jegyzete: pdf file ps file
- Az előadáson túlmutató segédanyagok:
  - A Milleneumi problémák egyike P?NP kérdés, amelyről Stephen Cook írt egy összefoglalót
  - Egy összefoglaló cikk (Allender-Loui-Regan) a bonyolultsági osztályokról és viszonyukról
  - Wikipedia oldala a nem-determinizmusról
2013. február 28.: Példák.
- Az előadás jegyzete: pdf file ps file
- Az előadáson túlmutató segédanyagok:
  - A Wikipedia listája eldönthetetlen problémákról
2013. március 7.: Redukciók. Teljes nyelvek. NL és az ELÉRHETŐSÉG nyelv. Savitch algoritmus/tétel.
- Az előadás jegyzete: pdf file ps file
- Az előadáson túlmutató segédanyagok:
  - A redukció fogalma a wikipedia szerint
  - Richard Lipton blogja a Savitch-tételről
2013. március 14.: Immermann-Szelepcsényi-tétel. Teljes probléma P-re és NP-re.
- Az előadás jegyzete: pdf file ps file
- Az előadáson túlmutató segédanyagok:
  - Az 1995-ös Gödel-díj indoklása
  - Jerrum Sinclair egy előadás jegyzete az Immerman-Szelepcsényi tételről
  - Lance Fortnow blogjának Immerman-Szelepcsényi bejegyzése
2013. március 21.: Cook-Levin-tétel, NP-teljesség
- Az előadás jegyzete: pdf file ps file
- Az előadáson túlmutató segédanyagok:
  - Cook eredeti cikke.
  - Cook méltatása mint a Turing-díj nyertese (1982).
  - Leonid Levin wikipedia oldala
  - A Knuth-díj 2012. évi nyertesének - Leonid Levin-nek - méltatása.
  - Egy Caltech előadás jegyzet a Cook-Levin-tételről
  - Két Harvard jegyzet: első, második NP-teljességről.
  - A wikipedia listája NP-teljes problémákról
  - Karp eredeti cikke, amely az NP-teljes problémák sorát elindította.
  - Egy Pierluigi Crescenzi és Viggo Kann által gondozott online lista NP-teljes problémákról.
  - Jeff Erickson az University of Illinois at Urbana-Champaign algoritmuselméleti kurzusának NP-teljességi órájához adott anyaga
2013. március 28.: Egy PSPACE-teljes probléma, a polinomiális hierarchia
- Az előadás jegyzete: pdf file ps file
- Az előadáson túlmutató segédanyagok:
  - Schaefer-Umans egy listája a polinomiális hierarchia egyes szintjeire teljes problémákról
2013. április 4.: Tavaszi/Húsvéti szünet
2013. április 11.: Hálózatok és SAT
- Az előadás jegyzete: pdf file ps file
2013. április 18.: OTDK
2013. április 25. Véletlen számokat használó Turing-gépek és bonyolultsági osztályaik
- Az előadás jegyzete: pdf file ps file
2011. május 16.: Összeszámlálási problémák és a velük kapcsolatos bonyolultsági osztályok.
- Az előadás jegyzete: pdf file ps file
- Az előadáson túlmutató segédanyagok:
  - A VisualWikipedia oldala Valiant tételéről
  - Ben-Dor és Halevi eredeti cikke Valiant tételéről
  - Toda-tétel egy új bizonyítása
  - Egy hálózatos megközelítése Toda tételének
  - Az 1998-as Gödel-díj indoklása
2013. május 9.: Véletlen algoritmusok
- Az előadás jegyzete: pdf file ps file
2013. május 16.: Kitekintés (olvasnivaló, nem vizsgaanyag)
- Az előadás jegyzete: pdf file ps file
- A kitekintésen túlmutató segédanyagok:
  - Avi Wigderson egy előadásának anyaga
  - Az 1993-as Gödel-díj indoklása
  - Az 2001-es Gödel-díj indoklása