Tantárgyleírás
2020.
Gráfok és algoritmusok elmélete
- Óraszám (ea+gy): 2 + 2
- Specializáció: elemző
- Kredit (ea+gy): 3 + 2
- Számonkérés: kollokvium + gyak. jegy
- Tárgykód (ea, gy): grafal1e0_m17ea, grafal1e0_m17ga
- Ajánlott félév: 3
- Státusz: kötelező
| Óraszám
ea(+k) + gy(+k) |
Kredit
ea + gy |
Számonkérés | Specializáció | Tárgykód
ea/gy |
Ajánlott
félév |
Státusz |
|---|---|---|---|---|---|---|
| 2 + 2 | 3 + 2 | kollokvium + gyak. jegy |
elemző | grafal1e0_m17ea grafal1e0_m17ga |
3 | kötelező |
Tantárgyfelelős
| Erős | Gyenge | előfeltételek |
|---|---|---|
| Gyakorlat | ||
|
Erős:
Véges matematika2E
(vegmat2*0_m17ea)
| ||
| Előadás | ||
|
Gyenge:
a gyakorlat
| ||
Megjegyzések
- A Gráfok és algoritmusok és az Algoritmusok tervezése és elemzése1 tárgyak közül csak az egyikre kapható kredit, utóbbi a nehezebb változat.
- Ennél a tárgynál a gyakorlaton is legalább 50%-ban az elméleti anyag elmélyítése történik.
- 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.