Algoritmusok elemzése és bonyolultsága (algbonym22ea)
Előadás: szerda 9:30-12:00, 00-623 (vigyázat, nem arra kell menni, mint amerre mennél!)
Gyakorlat 1 (Pálvölgyi Dömötör): kedd 2-3:30, 5-501
Gyakorlat 2 (Zólomy Kristóf): csüt 2:15-3:45, 4-202
Gyakorlat 3 (Ködmön Lili): kedd 12:15-13:45, 3-719
Hasznos linkek:
Tavalyi óra honlapja: .html
Idei óra honlapja: .html
Jövő évi óra honlapja: .html
Kurzus a tantervi hálón: .html
Király algoritmus jegyzet: .pdf
Lovász bonyelm jegyzet: .pdf
Alapvető bonyolultsági osztályok: .html
Turing-gép szimulátorok: .html és .html
RAM-gép szimulátor helyett Human Resource Machine
Ajánlott olvasmányok: Rónyai-Ivanyos-Szabó: Algoritmusok, Cormen-Leiserson-Rivest-Stein: Új Algoritmusok, Christos H. Papadimitriou: Számítási bonyolultság, Sanjeev Arora és Boaz Barak: Computational Complexity: A Modern Approach .html
Egyéb kapcsolódó ismeretterjesztő könyvek: Raymond Smullyan könyvek, pl.: To Mock a Mockingbird, Roger Penrose: A császár új elméje, Douglas L. Hofstadter: Gödel, Escher, Bach
Turing eredeti cikke: .html
Turing társasjáték: .html
Turing Film: .html
Órák témái:
Néha frissülő előadásjegyzet jegyzet.pdf Ha hibát találsz benne, lécci írd meg!
0. hét feladatsor (febr. 11): 0.pdf
1. hét (febr. 12): Barkochba, rendezés, döntési fák (1.34. tétel kimondásáig)
Gyakorlat feladatsor: 1.pdf
2. hét (febr. 19): Zárkózottság, nemdeterminizmus (1. fejezet végig)
Gyakorlat feladatsor: 2.pdf
3. hét (febr. 26): Aritmetikai műveletek, Dinamikus programozás (3.1-3.3)
Gyakorlat feladatsor: 3.pdf
4. hét (márc. 5): Dinamikus programozós gráfalgoritmusok, Tömb, Kupac
Gyakorlat feladatsor: 4.pdf
5. hét (márc. 12): Bináris Keresőfa, Hashelés, Véges automaták
Gyakorlat feladatsor: 5.pdf
6. hét (márc. 19): Turing-gépek, RAM-gépek Gyakorlat feladatsor: 6.pdf
1. ZH (márc. 26): ZH1.pdf
7. hét (ápr. 2): Hálózatok, Eldönthetetlenség Dominós tétel kimondásáig Gyakorlat feladatsor: 7.pdf
8. hét (ápr. 9): Dominós tétel bize, Gödel-tétel, Huffman-kódolás, Kolmogorov-bonyolultság Gyakorlat feladatsor: 8.pdf
9. hét (ápr. 23): NP és Cook-tétel Gyakorlat feladatsor: 9.pdf
10. hét (ápr. 30): NP-teljes nyelvek Gyakorlat feladatsor: 10.pdf
11. hét (máj. 7): Hamilton-kör, időhierarchia, PCP, RSA
2. ZH (máj. 14): ZH2.pdf
Tematika röviden:
Barkochba, rendezés, döntési fák.
Dinamikus programozás.
Adatstruktúrák.
Véges automaták.
Turing- és RAM-gépek, hálózatok.
Eldönthetetlenség.
Információelmélet.
Bonyolultsági osztályok.
NP-teljesség és visszavezetések.
Gyakorlatjegy: Hagyományos módon két ZH lesz, melyekre szerdán, az előadás időpontjában kerül sor, március 26-án és május 14-én az Északi Tömb 0.81-ben 10-12-ig. Ezeken maximálisan 70+70 pontot lehet szerezni. Aki nem éri el mindkét ZH-n legalább a 15 pontot, annak május 21-én lesz lehetősége javítani a szokásos 00-623-ban 9:30-12-ig, illetve aki elérte a 15 pontokat, az is eljöhet megírni, hogy leronthassa a korábban megszerzett jegyét. Az így szerzett pontszámhoz jön hozzá a félév közbeni munkával szerezhető max 20 pont, ami tipikusan heti házifeladatok megoldását jelenti 2 pontért. Jegyek: 100-tól 5-ös, 80-tól 4-es, 60-tól 3-as, 40-től 2-es.
Javító ZH (ami a megbukottaknak UV) szabályai: Akinek meglett a jegye, az tud javítani. Új jegy: (régi jegy + javZH)/2 felfele kerekítve. Figyelem, lehet rontani is, tehát ha egy feladatot sem oldasz meg, akár meg is bukhatsz! De nem kötelező beadni a javító ZH-t. UV-sok: Akinek egy ZH-n nem lett meg a 15 pont, az olyan, mintha a régi jegye 1-es lenne. Akinek 2 ZH-n nem lett meg, annak olyan, mintha a régi jegye 0-s lenne, tehát legalább 25 pontot kell szereznie a javítón!
A vizsga menete: Először két beugró feladat, egyszerű fogalmat/algoritmust elmondani/elvégezni (lásd jegyzet hátulját), vagy egy nyelvrol meg kell mondani, hogy reguláris-e, vagy bonyolultsági osztályok defjét/viszonyát. Ha egyik sem megy, egyes. Ha csak az egyik megy, a másik helyett adok újat, ha az sem megy, egyes. Ha megy, kapsz egy tételt a tételsorról (kivéve azt a 3-at, amit felírtál), amit ki kell dolgozni, de persze többiből is kérdezhetek ezt-azt (felírtból is, csak a bizonyításokat nem).