Geometriai algoritmusok (VISZD304) adatlapja, előadó: Tóth Géza A tantárgy angol neve: Computational Geometry Adatlap utolsó módosítása: 2009. szeptember 5 Budapesti Műszaki és Gazdaságtudományi Egyetem, Villamosmérnöki és Informatikai Kar 3. A tantárgyfelelős személy és tanszék Tóth Géza, docens, Számítástudományi és Információelméleti Tanszék 4. A tantárgy előadója Tóth Géza 5. A tantárgy az alábbi témakörök ismeretére épít Lineáris algebra, gráfok, algoritmusok elmélete 7. A tantárgy célkitűzése A tárgy bemutatja a legfontosabb, legalapvetőbb problémákat, fogalmakat, módszereket, amelyek a geometriai algoritmusok elméletében szerepelnek. 8. A tantárgy részletes tematikája Bevezetés: Konvex burok számítása a síkon, degenerált esetek, számítási hibák, alkalmazások Szakaszok metszéspontjainak a kiszámítása, tárolás, több térkép (szakasz elrendezés) egyesítése Sokszögek háromszögelése, a teremőr probléma, sokszögek felosztása monoton részekre, monoton részek háromszögelése Lineáris programozás a síkon illetve alacsony dimenzióban, félsíkok metszetének kiszámítása, véletlent használó algoritmus Pont helyének meghatározása, trapéz felosztás, véletlen algoritmus, degenerált esetek Voronoi diagram tulajdonságai és hatékony kiszámítása Egyenes elrendezések, dualitás, diszkrepancia kiszámítása, a k-halmaz illetve k-szint probléma, alsó és felső korlátok Delaunay háromszögelés tulajdonságai és hatékony kiszámítása, ponthalmaz háromszögelései Konvex burok a térben Gráfok metszési számai, alsó és felső korlátok, elméleti és gyakorlati alkalmazások, metszési szám viszonya más gráf paraméterekhez, véletlen gráf metszési száma 9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) Előadás 10. Követelmények a.       A szorgalmi időszakban: házi feladat (?) b.       A vizsgaidőszakban: szóbeli vizsga          c.              Elővizsga: lehetséges 11. Pótlási lehetőségek A tanulmányi és vizsgaszabályzatnak megfelelően. 12. Konzultációs lehetőségek Fogadó órákon, illetve személyes egyeztetés alapján 13. Jegyzet, tankönyv, felhasználható irodalom de Berg, van Kreveld, Overmars, Cheong (Schwarzkopf): Computational Geometry, Springer, 2000. 14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka: Előadás 28, Készülés 22, Vizsga felkészülés 40, összesen 90. 15. A tantárgy tematikáját kidolgozta: Tóth Géza ? 2005-2008. BME VIK ------------------------------------------------------------------- Matematikus doktoranduszoknak kötelezően választható tárgy. Felsőbbéves matematikus hallgatók is nyugodtan felvehetik, a tárgy megértéséhez lineáris algebra, gráfelmélet, illetve algoritmuselméleti alapismeretek szükségesek. Főleg a geometriai ötletekre, módszerekre koncentrálunk, nem a konkrét megvalósításra, illetve az algoritmus részleteire. A tematika igazából túl sok egy félévre, az előadások a hallgatók érdeklődésének megfelelően fognak alakulni.