Algoritmusok elemzése és bonyolultsága (algbonym22ea)
Előadás: hétfő 9:30-12:00, 1-820
Gyakorlat 1 (Pálvölgyi Dömötör): péntek 8:30-10, 3-306
Gyakorlat 2 (Zólomy Kristóf): kedd 4-5:30, 5-501
Gyakorlat 3 (Damásdi Gábor): csütörtök 10:15-11:45, 3-316
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
További jó algoritmusos gyakorlófeladatok: Nemes Tihamér progverseny
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 .pdf, Thomas Watson: Complexity in Computer Science .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. feladatsor: 0.pdf
1. hét (febr. 9): Barkochba, rendezés, median of medians. Feladatsor: 1.pdf
2. hét (febr. 16): Determinisztikus döntési fák. Feladatsor: 2.pdf
3. hét (febr. 23): Nemdeterminisztikus döntési fák, Aritmetikai műveletek. Feladatsor: 3.pdf
4. hét (márc. 2): Dinamikus programozás, Tömbök. Feladatsor: 4.pdf
5. hét (márc. 9): Kupacok, Bináris keresőfák, Hashelés. Feladatsor: 5.pdf
6. hét (márc. 16): Véges automaták, Turing-gép. Feladatsor: 6.pdf
1. ZH (márc 23) ZH1.pdf Gyakorlatra feladatsor: 7.pdf
8. hét (márc. 30): Univerzális Turing-gép, RAM-gép, hálózatok.
9. hét (ápr. 13): Eldönthetetlenség. Feladatsor: 8.pdf
10. hét (ápr. 20): Információelmélet, Huffman-kód, Kolmogorov-bonyolultság. Feladatsor: 9.pdf
11. hét (ápr. 27): NP, polinomiális visszavezetés, SAT NP-teljes kimondva, biz jövő héten. Feladatsor: 10.pdf
12. hét (máj. 4): NP-teljes nyelvek. Feladatsor: 11.pdf
2. ZH (máj 11) ZH2.pdf
UV/pótZH (máj 18)
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 hétfőn, az előadás időpontjában kerül sor, 9:55-11:55-ig. Ezeken maximálisan 70+70 pontot lehet szerezni. Aki nem éri el mindkét ZH-n legalább a 15 pontot, annak lesz lehetősége javítani, 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 beugró feladatok, aztán, kapsz két 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).