Algoritmusok és bonyolultságelmélet

2010 Tavasz

• Amit a kurzusról tudni kell
• Amit a vizsgáról tudni kell

---

Előadások

• 2010. február 1.: 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
• 2010. február 8.: Bonyolultsági osztályok. Turing-gép fogalmának változatai. PALINDROM nyelv bonyolultsága. Turing-gépek kódolása, Univerzális Turing-gép, MEGÁLLÁS nyelv.
  • Az előadás jegyzete (Bittner Emese):   pdf file  ps 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
• 2010. február 15.: Nemdeterminizmus. Bonyolultsági osztályok közötti egyszerű viszonyok. ELÉRHETŐSÉG nyelv és kapcsolata a tárbonyolultsággal.
  • Az előadás jegyzete (Pék Máté):   pdf file  ps 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
• 2010. február 22.: Példák.
  • Az előadás jegyzete:   pdf file  ps file
• 2010. március 1.: További példák. Redukció fogalma. Teljes problémák fogalma.
  • Az előadás jegyzete (Domanovszki Bettina):   pdf file
  • Az előadáson túlmutató segédanyagok:
    • A redukció fogalma a wikipedia szerint
• 2010. március 8.: Teljes problémák P-re, NP-re
  • Az előadás jegyzete (Krizsan Lívia):   pdf file
  • Az előadáson túlmutató segédanyagok:
    • Egy Stanford előadás jegyzet a Cook-Levin-tételről
• 2010. március 15.: Nemzeti ünnepünk.
• 2010. március 22.: További NP-teljes problémák (Nagy-György Judit előadása).
  • 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ították.
    • 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
• 2010. március 29.: Immerman-Szelepcsényi-tétel. Polinomiális hierarchia.
  • Az előadás jegyzete (Körmendi Kristóf):   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
• 2010. április 5.: Húsvét hétfő
• 2010. április 12.: Hálózatok és SAT, Alternáló polinomiális idő
  • Az előadás jegyzete:   pdf file 
• 2010. április 19.: Véletlen számokat használó Turing-gépek és bonyolultsági osztályaik
  • Az előadás jegyzete (Udvari Balázs):   pdf file 
• 2010. április 26.: Véletlen algoritmusok
  • Az előadás jegyzete:   pdf file  ps file
• 2010. május 3.: Összeszámlálási problémák és a velük kapcsolatos bonyolultsági osztályok
  • Az előadás jegyzete (Dombi Péter):   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
• 2010. május 10.: Kitekintés
  • Az előadás jegyzete:   pdf file  ps file
  • 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