Algoritmusok és bonyolultságelmélet

2015 Tavasz

Előadások

2015. február 5.: Kiszámíthatóság, Turing-gép, alapfogalmak
- Az előadás jegyzete pdf 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
2015. február 12.: 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
  - Scott Aaronson - The Complexity Zoo pdf file
  - Greg Kuperberg (Mathematics Department at UC Davis) próbálkozása.
2015. február 19.: Nem-determinizmus, Bonyolultsági osztályok közötti egyszerű viszonyok
- Az előadás jegyzete: pdf file
- Az előadáson túlmutató segédanyagok:
  - Wikipedia oldala a nem-determinizmusról
  - 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
2015. február 26.: Példák.
- Az előadás jegyzete: pdf file
- Az előadáson túlmutató segédanyagok:
  - A Wikipedia listája eldönthetetlen problémákról
  - Richard Lipton blogja a Savitch-tételről
2015. március 5.: Redukciók. Teljes nyelvek. NL és az ELÉRHETŐSÉG nyelv. Savitch tétel.
- Az előadás jegyzete: pdf file
- Az előadáson túlmutató segédanyagok:
  - A redukció fogalma a wikipedia szerint
2015. március 12.: Immermann-Szelepcsenyi-tétel
- Az előadás jegyzete: pdf 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
2015. március 19.: P-teljes és NP-teljes problémák, Cook-Levin tétel
- Az előadás jegyzete: 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
  - 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.
2015. március 26.: Gráfelméleti NP-teljes problémák, További NP-teljes problémák
- Az előadás jegyzete: pdf file
- Az előadáson túlmutató segédanyagok:
  - 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
2015. április 2.: P és PSPACE között: QBF egy PSPACE-teljes probléma, Polinomiális hierarchia
- Az előadás jegyzete: pdf 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
2015. április 9.: Tavaszi szünet
2015. április 16.: Véletlen számítások, bonyolultsági osztályok
2015. április 23.: BPP, Nem-uniform P és a hierarhia
2015. április 30.: Véletlen algoritmusok
2015. május 7.: Összeszámlálási problémák bonyolultsága
- Az előadás jegyzete: pdf 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
2015. május 14.: Kitekintés
- Az előadás jegyzete: pdf 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