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
- 2026/27/1
- ECTS
- 3
- Nyelv
- hu
- Oktatás célja
- Az Algoritmuselmélet néhány fő területének megismerése az algoritmusok alapjaira építve. Hangsúlyos a minél több különböző témába történő bevezetés, valamint a tervezési, elemzési és implementálási módszerek megismerése. 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
- Polinomok szorzása, diszkrét és gyors Fourier-transzformáció. Nagy számok gyors szorzása. Dijkstra algoritmusa, absztrakt Dijsktra, alkalmazások. Idő-függő legrövidebb út. Karp algoritmusa minimális átlagú körre. Suurballe és Tarjan algoritmusa: legrövidebb útpár egy forrásból minden célcsúcsra. Dinic algoritmusa, diszjunk utak keresése. Többtermékes folyamok, Japán-tétel, Hu és Rothschild-Whinston tételei. Stabil párosítás alkalmazása a magyar egyetemi felvételi rendszerben, teljes stabil párosítás keresése nem páros gráfban. Hálózati kódolás, lineáris hálózati kódok. A lineáris hálózati kódok alaptétele. Közelítő algoritmusok, APX osztály, PTAS, EPTAS és FPTAS. Ibarra-Kim, halmazfedés, legnagyobb stabil párosítás, Beck-Fiala-tétel. FPT problémák és algoritmusok. Lefogó csúcshalmaz, kernel. Párhuzamos algoritmusok. Szükséges előismeretek: Rendezés és kiválasztás. Számolás nagy számokkal, modulo m számítások. Szótárak, bináris keresőfák. Gráfok tárolása, szélességi és mélységi keresés (bejárás). Kupacok, d-edfokú kupacok, alkalmazásuk a Dijkstra- és a Prim-algoritmusban. Leghosszabb út keresése aciklikus gráfban. Bellmann és Ford algoritmusa. Legnagyobb ill. stabil párosítás keresése páros gráfban.
- Számonkérés és értékelés
- kollokvium
- Irodalomjegyzék
- https://zkiraly.web.elte.hu/Algoritmusok.pdf
- Ajánlott irodalom
- Cormen, Leiserson, Rivest, Stein: Új Algoritmusok, Scolar Kiadó, 2003 Cikkgyűjtemény