Belépés címtáras azonosítással
magyar nyelvű adatlap
Théorie d'algorithme
A tantárgy angol neve: Theory of Algorithms (In French)
Adatlap utolsó módosítása: 2006. július 1.
Tantárgy lejárati dátuma: 2015. január 31.
Műszaki Informatika Szak
Név:
Beosztás:
Tanszék, Int.:
Csima Judit
egy.tanársegéd
Számítástudományi és Információelméleti Tanszék
Diszkrét matematika elemei, alapvető programozási ismeretek.
A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.
A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.
Diszkrét matematika I. kredit
Programozás alapjai I, II. kredit
Számítógép labor I, II. kredit
Az algoritmusok tervezésével, elemzésével kapcsolatos alapvető módszerek, készségek elsajátítása.
Turing gépek (TG): definíció; egyszerű példák; idő- és tárkorlátos TG; univerzális TG; többszalagos TG szimulációja 1 szalagossal, TG-k konstrukciója.
A kiszámíthatóság elméletének alapjai: Rekurzíve felsorolható és rekurzív nyelvek, parciális rekurzív és rekurzív függvények, kapcsolatuk egymással; R a RE és coRE osztályok metszete; RE-n kívüli nyelvek létezése; a megállási feladat eldönthetetlensége, nyelv-tulajdonságok eldönthetetlensége; Hilbert 10. problémája; dominóprobléma; Post feladat; Church-Turing tézis.
A RAM gép: definíció; logaritmikus költség és uniform költség
RAM-TG és TG-RAM szimulációk.
Kolgomorov bonyolultság: invariancia tétel: összenyomhatatlan szavak létezése, alkalmazások; a Kolgomorov bonyolultság kiszámíthatatlansága.
Nevezetes bonyolultsági osztályok: idő és tár kapcsolata; lineáris idő, P, FP, PSPACE, EXPTIME példákkal.
Az NP nyelvosztály: Nemdeterminisztikus Turing gépek (NTG); NP definíciója NTG-vel illetve tanúkkal; példák NP-beli nyelvekre (gráftulajdonságok: összefüggőség, színezhetőség, független ponthalmazok, Hamilton-kör stb.; lieáris egyenlőtlenség-rendszerek, összetett illetve prímszámok); jó karakterizáció (NP és coNP metszete), Pratt, Kuratowski.
NP-teljesség: Karp redukció, NP-teljesség, Cook-Levin tétel; nevezetes NP-teljes nyelvek (3-SAT, 3-színezés, független ponthalmaz, 3DM, hátizsák probléma, ládapakolás stb.).
Randomizált algoritmusok: plinomazonosság tesztelés (Schwartz lemmája); Rabin-Miller prímteszt, véletlen prímszám generálása, a nyilvános kulcsú kriptográfia elemei; az RP és Las Vegas nyelvosztályok.
Algoritmus-tervezési technikák: mohó módszer (pl. minimális költségű feszítőfa), oszd meg és uralkodj, dinamikus programozás (pl. hátizsák), korlátozás és elágazás (pl. maximális független ponthalmaz gráfban), közelítő módszerek (pl. ládapakolási heurisztikák).
Adatrendezési módszerek: rendezés összehasonlításokkal (beszúrásos, összefésülő, gyorsrendezés); kupac fogalma, kupacos rendezés; kulcsmanipulációs rendezések (láda- és radixrendezés); külső tárak tartalmának rendezése.
Alapvető adatszerkezetek: tömb, lista, verem, sor; kereső fák (bináris keresőfák, 2-3 fák, B-fák, AVL fák, szófák); hashelés (cél, alkalmazhatóság, kezelendő problémák), ütközések feloldása (láncolás, nyitott címzés), jó hash-függvények; szekvenciális keresés. Információ tömörítés.
Alapvető gráf-algoritmusok: gráfok tárolására szolgáló adatszerkezetek; legrövidebb utak keresése (Dijkstra, Floyd, Warshall módszerei); mélységi keresés és aklkalmazásai (DAG tulajdonság tesztelése, erős komponensek); topologikus rendezés; szélességi keresés; minimális költségű feszítőfa keresése (piros-kék algoritmus, Boruvka, Prim és Kruskal módszerei); az UNIÓ-HOLVAN adatszerkezet; maximális párosítás kétrészes gráfokban, folyamok hálózatokban.
Alapvető aritmetikai algoritmusok: euklideszi algoritmus, gyors hatványozás.
Előadás, gyakorlat
a. A szorgalmi időszakban:
- a félév lezárásának módja: aláírás
- a félév lezárásához szükséges követelmény: sikeres zárthelyi vagy beszámoló a gyak.vezetőnél.
b. A vizsgaidőszakban:
- írásbeli vizsga
c. Elővizsga: Igény esetén biztosítunk lehetőséget.
Tankönyv: Ivanyos, Rónyai, Szabó: Algoritmusok, Typotex Kiadó, 1998, ISBN 963 9132 16 0
Az anyaghoz részben használható további szakkönyvek:
Aho, Hopcroft, Ullman: Számítógép-algoritmusok tervezése és elemzése;
Műszaki Könyvkiadó 1982.
Demetrovics, Denev, Pavlov: A számítástudomány matematikai alapjai;
Tankönyvkiadó 1987.
Lovász: Algoritmusok bonyolultsága; ELTE TTK jegyzet,
Tankönvkiadó 1989.
Knuth: A számítógép-programozás művészete, I-II-III. kötet;
Műszaki Könyvkiadó 1985.
Cormen Leiserson, Rivest: Algoritmusok, Műszaki Könyvkiadó, 1997
Feladatgyűjtemény elérhető: http://www.math.bme.hu/~ig/algel
Dr. Rónyai Lajos
egy. tanár
vimaF509.doc