Algoritmusok és bonyolultságelmélet

2011 Tavasz

Előadások

2011. február 1.: Kiszámíthatóság, Turing-gép, alapfogalmak
- Az uv hét és a szorgalmi időszak egymásba lógása miatt az első előadás nincs megtartva. Az alábbi jegyzet ELOLVASÁSA AJÁNLOTT: 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
2011. február 8.: Turing-gép fogalmának változatai. PALINDROM nyelv bonyolultsága.
- Az előadás jegyzete (Csenkei Anita): pdf file ps file
2011. február 15.: Turing-gépek kódolása, Univerzális Turing-gép, MEGÁLLÁS nyelv. Bonyolultsági osztályok. Nem-determinizmus.
- Az előadás jegyzete (Sallai Gyöngyi): pdf file ps file
- Az előadáson túlmutató segédanyagok:
  - Wikipedia oldala a nem-determinizmusról
  - 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.
2011. február 22.: Bonyolultsági osztályok közötti egyszerű viszonyok. Redukciók. ELÉRHETŐSÉG nyelv és kapcsolata a tárbonyolultsággal.
- Az előadás jegyzete (Nemes Anna): 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
  - A redukció fogalma a wikipedia szerint
2011. március 1.: Példák. Savitch-algoritmus.
- Az előadás jegyzete (Szőri András): pdf file ps file
2011. március 8.: További példák. Teljes problémák fogalma. Teljes probléma P-re.
- Az előadás jegyzete (Szarvák Gábor): pdf file ps file
2011. március 15.: Nemzeti ünnepünk
2011. március 22.: Cook-Levin-tétel, NP-teljesség, QBF, PSPACE-teljesség, 3-SAT
- Az előadás jegyzete (Karsai Dávid): pdf file ps file
- Az előadáson túlmutató segédanyagok:
  - Egy Stanford előadás jegyzet a Cook-Levin-tételről
2011. március 29.: További NP-teljes problémák
- Az előadás jegyzete (Győrffy Lajos): 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
2011. április 5.: Tavaszi szünet
2011. április 12.: Immerman-Szelepcsényi-tétel. Polinomiális hierarchia.
- Az előadás jegyzete (Bogya Norbert): 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
- Schaefer-Umans egy listája a polinomialis hierarchia egyes szintjeire teljes problémákról
2011. április 19.: Hálózatok és SAT
- Az előadás jegyzete (Kovácsházi Anna): pdf file ps file
2011. április 26.: Mahaney-tétel. 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 3.: Véletlen algoritmusok
- Az előadás jegyzete: pdf file ps file
2011. május 10.: Ö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áson 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