Tantárgy neve:  Gráfok és algoritmusok elmélete (elemző szakirány)

 

Tantárgy heti óraszáma: 2 óra előadás, 2 óra gyakorlat

kreditértéke: 2+3

 

            tantárgyfelelős neve:  Király Zoltán

                        tanszéke:  Számítógép-tudományi

            számonkérés rendje:  kollokvium + gyakorlati jegy

 

Az elsajátítandó ismeretanyag rövid (néhány soros) leírása:  Rendezések, mediáns keresése,

összefésülő, kupacos, gyorsrendezés és leszámláló rendezés. Tömbök, listák, sorok, kupacok, keresőfák.

Számolás maradékosztályokkal, Euklideszi algoritmus, prímszámgenerálás, RSA. Gráfok tárolása. Szélességi és mélységi keresés megvalósításai, alkalmazásai. Dinamikus programozás. Feszítőfa és legrövidebb út algoritmusok megvalósítása és alkalmazásai. Párosítások. Folyamalgoritmusok, Menger tételei. Huffman –kód, Lempel-Ziv-Welch tömörítési eljárása.

A bonyolultságelmélet alapjai: Turing-gépek, P és NP fogalma, NP-teljesség.

 

Kötelező irodalom:

Cormen, Leiserson, Rivest, Stein: Új algoritmusok, Scolar Kiadó, 2003

Ajánlott irodalom:

Rónyai L., Ivanyos G., Szabó R.: Algoritmusok, Typotex 1998

Katona Gy., Recski A., Szabó Cs.: A számítástudomány alapjai, Typotex, 2002