Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Geometriai algoritmusok

    A tantárgy angol neve: Algorithms in Geometry

    Adatlap utolsó módosítása: 2017. január 27.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar

    PhD  képzés

    szabadon vagy kötelezően választható tantárgy

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZD304   2/0/0/v 3  
    3. A tantárgyfelelős személy és tanszék Dr. Tóth Géza, Számítástudományi és Információelméleti Tanszék
    A tantárgy tanszéki weboldala www.vik.bme.hu
    4. A tantárgy előadója
    Név:

     

     

     

    Beosztás:

     

     

     

    Tanszék, Int.:

     

     

     

    Dr. Tóth Géza

     

     

     docens

     

     

     

    SZIT

     

     

     

    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, k-halmaz ill. 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, Schwarzkopf:  Computational Geometry, Springer, 2000.
    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra28
    Félévközi készülés órákra22
    Felkészülés zárthelyire 
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés40
    Összesen90
    15. A tantárgy tematikáját kidolgozta Dr.Tóth Géza