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:
Minden órához lesz egy ilyen jegyzet: 0.pdf Ha hibát találsz benne, lécci írd meg!
Jegyzet 1. fejezet (döntési fák): jegyzet1fej.pdf
Jegyzet 2. fejezet (véges automaták): jegyzet2fej.pdf
Jegyzet 3. fejezet (univerzális számítási modellek): jegyzet3fej.pdf
Jegyzet 4. fejezet (eldönthetetlenség): jegyzet4fej.pdf
Jegyzet 5. fejezet (információelmélet): jegyzet5fej.pdf
Jegyzet 6. fejezet (adatstruktúrák): jegyzet6fej.pdf
Jegyzet 7. fejezet (aritmetikai műveletek): jegyzet7fej.pdf
Jegyzet 8. fejezet (dinamikus programozás): jegyzet8fej.pdf
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
maradék (ápr. 19, 24, 26, máj. 3): NP előadás jegyzet.pdf Gyakorlat feladatsor: gyak10.pdf
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.
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.