BSc Matematika Alapszak
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ő
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.
  • Király Zoltán: Gráfok és Algoritmusok elmélete. http://www.cs.elte.hu/~kiraly/Grafalg.pdf
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.