Algoritmusok és bonyolultságelmélet

2012 Tavasz

Előadások

2012. február 8.: 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
2012. február 15.: Turing-gép fogalmának változatai. PALINDROM nyelv bonyolultsága. Bonyolultsági osztályok. Turing-gépek kódolása, Univerzális Turing-gép.
- Az előadás jegyzete (Görbe Tamás Ferenc): 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.
2012. február 22.: Nem eldönthető problémák. Nem-determinizmus.
- 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
  - Wikipedia oldala a nem-determinizmusról
2012. február 29.: Bonyolultsági osztályok közötti egyszerű viszonyok.
- 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
2012. 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
2012. március 14.: Immermann-Szelepcsényi-tétel. Teljes probléma P-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
2012. március 21.: Cook-Levin-tétel, NP-teljesség
- Az előadás jegyzete (Vizi Zsolt): pdf 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
  - Egy Caltech előadás jegyzet a Cook-Levin-tételről
  - Egy Harvard előadás jegyzet a Cook-Levin-tételről
2012. március 28.: További NP-teljes problémák
- Az előadás jegyzete: pdf file ps file
- Az előadáson túlmutató segédanyagok:
  - 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 anyag
2012. április 4.: Még további NP-teljes problémák, QBF, PSPACE-teljesség
- Az előadás jegyzete: pdf file ps file
2012. április 11.: Tavaszi/Húsvéti szünet
2012. április 18.: 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
2012. április 25.: Hálózatok és SAT
- Az előadás jegyzete (Vörös Anett): pdf file ps file
2012. május 2..: Véletlen számokat használó Turing-gépek és bonyolultsági osztályaik
- Az előadás jegyzete (Vass Mária): pdf file ps file
2011. május 9.: Véletlen algoritmusok
- Az előadás jegyzete (Virágh Zita): 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
Nem maradt rá idő: Kitekintés
- 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