Algoritmusok elemzése és bonyolultsága (algbonym22ea)
Eloadás: szerda 8:30-10:00 és péntek 10:15-11:00, 2-502.
Gyakorlat 1 (Pálvölgyi Dömötör): szerda 4-5:30, 4-206.
Gyakorlat 2 (Damásdi Gábor): szerda 2-3:30, 3-110.
Hasznos linkek:
Kurzus a tantervi hálón: .html
Király algoritmus jegyzet: .pdf
Lovász bonyelm jegyzet: .pdf
Major Algoritmusok I. óra honlapja: .html
Major Számítástudomány óra honlapja: .html
Alapveto bonyolultsági osztályok: .html
Turing-gép szimulátorok: .html és .html
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ó ismeretterjeszto 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:
Előadásjegyzet (néha még frissül) jegyzet.pdf Ha hibát találsz benne, lécci írd meg!
1. hét (febr. 14): Barkochba, rendezés, döntési fák
Gyakorlat feladatsor: gyak1.pdf
2. hét (febr. 16, 21, 23): Egyszerű döntési fák
Gyakorlat feladatsor: gyak2.pdf
3. hét (febr. 28): Véges automaták
Gyakorlat feladatsor: gyak3.pdf
4. hét (márc. 1, 6): Univerzális számítási modellek
Gyakorlat feladatsor: gyak4.pdf
5. hét (márc. 13): Eldönthetetlenség
Gyakorlat feladatsor: gyak5.pdf
6. hét (márc. 20): Gödel-tétel, Információelmélet Gyakorlat feladatsor: gyak6.pdf
7. hét (márc. 22, ápr. 3, 5): Adatstruktúrák Gyakorlat feladatsor: gyak7.pdf
8. hét (ápr. 10): Aritmetikai műveletek Gyakorlat feladatsor: gyak8.pdf
9. hét (ápr. 17): Dinamikus programozás Gyakorlat feladatsor: gyak9.pdf
10. hét (ápr. 19, 24): NP Gyakorlat feladatsor: gyak10.pdf
11. hét (ápr. 26, máj. 3, 8): NP-teljesség Gyakorlat feladatsor: gyak11.pdf
máj. 15, 8:15-10:00: NagyZH: nagyZH.pdf
máj. 24, 8:30-11:00, a 0-803-as teremben: JavZH/UV
Tematika röviden: Barkochba, rendezés, döntési fák.
Véges automaták.
Turing- és RAM-gépek, hálózatok.
Eldönthetetlenség.
Bonyolultsági osztályok.
NP-teljesség és visszavezetések.
Adatstruktúrák és rendezések.
Dinamikus programozás.
Gráfok tárolása és bejárása
(szélességi és mélységi keresés).
Minimális költségu feszítofák.
Legrövidebb út.
Gyakorlatjegy: Két miniZH a 45 perces eloadás alatt (márc 8 és ápr 12), 3-3 feladattal. Ekkor van az elso beadandó határideje is, tehát 3+1 pontot lehet szerezni. Félév végén nagy ZH 7 feladattal (május 15). Összesen 6-tól 2-es, 8-tól 3-as, 10-től 4-es, 12-től 5-ös, de mind a három körben legalább 2 pontot kell szerezni. Elso vizsgahéten lesz UV és javító ZH egyben. Akinek meglett a jegye, az tud javítani. Új jegy: (régi jegy + javZH)/2 felfele kerekítve. Figyelem, lehet rontani is! De nem kötelező beadni a javZH-t. Akinek egy ZH-n nem lett meg a 20 pont, az olyan, mintha a régi jegye 1-es lenne. Akinek 2 ZH-n nem lett meg, annak olyan, mintha 0-s. Akinek egyszer sem lett meg, annak olyan, mintha -1-es lenne, tehát legalább 4-est kell írni a javZH-n a 2-eshez.
A vizsga menete: Eloször két beugró feladat, egyszeru algoritmust elmondani/elvégezni, 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, amit ki kell dolgozni, de persze többibol is kérdezhetek ezt-azt.