BSc Matematika Alapszak
Tantárgyleírás
2013.
Tantárgyleírás
2013.
Gráfok és algoritmusok elmélete
Óraszám ea/gy |
Kredit ea/gy |
Számonkérés | Szakirány | Tárgykód ea/gy |
Ajánlott félév |
Státusz |
---|---|---|---|---|---|---|
2 + 2 | 2 + 3 | kollokvium + gyak. jegy |
elemző | mm1c1ga3e mm1c2ga3e |
3 | kötelező |
Tantárgyfelelős
Erős | Gyenge | előfeltételek | |
---|---|---|---|
Gyakorlat | |||
Erős:
Véges matematika2E
(mm1c1vm2)
| |||
Előadás | |||
Gyenge:
a gyakorlat
|
Megjegyzések
- Követelmény: A gyakorlati jegy megszerzéséhez beadandó program készítése is tartozik.
- Pótlási lehetőség: A félév végén, indokolt esetben, a gyakorlatvezető döntése alapján egy javító zárthelyi dolgozat írására van lehetőség.
A tematikát kidolgozta:
Szükséges előismeretek
Elemi számelmélet, elemi gráfelmélet.
A tantárgy célkitűzése
A tárgy bevezetés az algoritmusok tervezésébe és elemzésébe, az alapvető algoritmusok és adatszerkezetek ismertetésével együtt.
Irodalom
- Rónyai L., Ivanyos G., Szabó R.: Algoritmusok. TypoTeX, 1998.
- Cormen, Leiserson, Rivest, Stein: Új algoritmusok. Scolar Kiadó, 2003.
Tematika
- 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, hasítás.
- 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.