Kurzus nemzetközi vendég- és részidős hallgatóknak
- Kar
- Természettudományi Kar
- Szervezet
- TTK Számítógéptudományi Tanszék
- Kód
- algelm1u0um17em
- Cím
- Algoritmuselmélet (ea)
- Tervezett félév
- Őszi
- Meghirdetve
- 2024/25/1
- ECTS
- 3
- Nyelv
- hu
- Oktatás célja
- Tudás: A terület alapvető fogalmainak, eredményeinek és módszereinek értő ismerete. Képesség: A terület ismereteinek alkalmazása, összefüggések átlátása, problémák megoldása. Attitűd: Igény a matematikai tudás gyarapítására és a tanultak minél alaposabb megismerésére, törekvés az ismeretek minél szélesebb körű alkalmazására Autonómia és felelősség: Matematikai kérdések megfogalmazása és elemzése önállóan, az alkalmazhatóságok korlátainak felelős értékelése.
- Tantárgy tartalma
- Rendezés és kiválasztás. Számolás nagy számokkal, Euklideszi algoritmus, RSA. Gyors Fourier-transzformáció és alkalmazásai. Dinamikus programozás alkalmazásai. Gráfalgoritmusok: a szélességi és mélységi keresés megvalósítása, alkalmazásai (legrövidebb utak, kétszínezhetőség, erősen összefüggővé irányítás, kettő-összefüggő blokkokra bontás, erősen összefüggő komponensek megtalálása). Dijkstra algoritmus alkalmazásai (legszélesebb út, legbiztonságosabb út, PERT módszer, legrövidebb utak közül legolcsóbb kiválasztása). Bellman-Ford-algoritmus, Johnson algoritmusa, Karp minimális átlagú kört kereső algoritmusa, Suurballe és Tarjan algoritmusa. Stabil párosítás. Hopcroft-Karp-algoritmus, Dinic-algoritmus, diszjunkt utak. Hálózati kódok. Közelítő algoritmus fogalma, példák (Ibarra-Kim, metrikus TSP, Steiner fa, lefogó csúcshalmaz). Fix paraméteresen megoldható feladatok. Párhuzamos algoritmusok (Brent tételei, minimum, összeadás, szorzás, rendezés, mátrix-szorzás alkalmazásai).
- Számonkérés és értékelés
- kollokvium
- Ajánlott irodalom
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Új algoritmusok. Scolar, 2003. Rónyai-Ivanyos-Szabó: Algoritmusok, TypoTeX, 1998.