Algoritmusok és bonyolultságelmélet

2013-14 Tavasz

• Amit a kurzusról tudni kell

---

Előadások

• 2014. február 13.: 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
• 2014. február 20.: 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 próbálkozás.
• 2014. február 27.: Nem-determinizmus, 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
    • Wikipedia oldala a nem-determinizmusról
• 2014. március 6.: 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
    • Richard Lipton blogja a Savitch-tételről
• 2014. március 13.: 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
• 2014. március 20.: 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
• 2014. március 27.: 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
• 2014. április 3.: 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
• 2014. április 10.: Véletlen számokat használó Turing-gépek és bonyolultsági osztályaik
  • Az előadás jegyzete:    pdf file  ps file