M7130 Geometrické algoritmy

Přírodovědecká fakulta
podzim 2008
Rozsah
2/0/0. 2 kr. (plus 2 za zk). Doporučované ukončení: zk. Jiná možná ukončení: k.
Vyučující
doc. RNDr. Martin Čadek, CSc. (přednášející)
Garance
prof. RNDr. Jan Slovák, DrSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Rozvrh
Po 12:00–13:50 A107
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
Přehled tzv. "Computational Geometry". Hlavním cílem kurzu je seznámit studenty s různými paradigmaty při návrhu algoritmů (jednoprůchodové, rekurzivní "rozděl a panuj", pročesávací, náhodnostní, geometrické transformace problémů), s vhodnými datovými strukturami, s odhady nejhorších i očekávaných parametrů algoritmů. Na konci kurzu by studenti měli být schopni implementaci probíraných algoritmů.
Osnova
  • 1. Konvexní obaly 2. Průsečíky úseček 3. Triangulace mnohoúhelníků 4. Lineární programování v rovině 5. Ortogonální vyhledávání 6. Lokalizace bodu 7. Diagramy Voronoia 8. Dualita 9. Delauneyovy triangulace 10. Konvexní obal v dimenzi 3
Literatura
  • učební text na www.math.muni.cz/~slovak
  • DE BERG, M., M. VAN KREVELD, M. OVERMARS a O. SCHWARZKOPF. Computational Geometry. 1. vyd. Berlin: Springer-Verlag, 1997, 365 s. ISBN 3-540-61270-X. info
Metody hodnocení
Přednáška a písemná zkouška.
Informace učitele
http://www.math.muni.cz/~slovak
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích podzim 2007 - akreditace, podzim 1999, podzim 2010 - akreditace, podzim 2000, podzim 2001, podzim 2002, podzim 2003, podzim 2004, podzim 2006, podzim 2007, podzim 2009, podzim 2010, podzim 2011, podzim 2011 - akreditace, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018.