Kurzus nemzetközi vendég- és részidős hallgatóknak
- Kar
- Természettudományi Kar
- Szervezet
- TTK Operációkutatási Tanszék
- Kód
- appalg1u0um17em
- Cím
- Approximációs algoritmusok (ea)
- Tervezett félév
- Tavaszi
- ECTS
- 3
- Nyelv
- hu
- Oktatás célja
- Tudás: az approximációs algoritmusok fő eredményeinek elsajátítása Képesség: approximációs algoritmusok megértése, használata Attitűd: igény az alkalmazott matematikai tudás gyarapítására, új alkalmazott matematikai ismeretek megszerzésére, kompetenciák elsajátítására, kifejlesztésére. Törekvés a matematikai ismereteinek minél szélesebb körű alkalmazására Autonómia és felelősség: az approximációs algoritmusok témakörében elsajátított alapvető ismeretei felhasználásával képes önállóan megválasztani az alkalmazási problémák megoldására alkalmazható módszereket
- Tantárgy tartalma
- Halmazfedés, lefogó ponthalmaz, utazóügynök feladat, Steiner fa. LP-relaxációk, primál-duál algoritmusok, körlefogó ponthalmaz, bin packing, forráselhelyezés. Ütemezési feladatok, k-központ, k-vágás, multivágás, többutas vágás. Többtermékes folyamok. Minimális k-összefüggő részgráf. Minimális maxfokú feszítőfa.
- Számonkérés és értékelés
- kollokvium
- Ajánlott irodalom
- Jordán Tibor – Recski András – Szeszlér Dávid: Rendszeroptimalizálás, Typotex Kiadó, Budapest, 2004. V. Vazirani: Approximation algorithms. Springer, 2001.