M7130 Geometrické algoritmy

Přírodovědecká fakulta
podzim 2009
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.
Předmět si smí zapsat nejvýše 96 stud.
Momentální stav registrace a zápisu: zapsáno: 0/96, pouze zareg.: 0/96, pouze zareg. s předností (mateřské obory): 0/96
Mateřské obory/plány
Cíle předmětu
Cílem kurzu je seznámit studenty se základními geometrickými algoritmy. Po absolvování předmětu budou studenti znát *základní algoritmické metody (sweeping line, randomized incremental, rozděl a panuj) používané v této oblasti, *základní datové a vyhledávací struktury(connected edge list, kd-trees, range trees), *časovou a paměťovou náročnost v oblasti geometrických algoritmů. *Dále budou schopni samostatně implementovat probírané algoritmy.
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
Výukové metody
Přednášky.
Metody hodnocení
Písemná zkouška.
Informace učitele
http://www.math.muni.cz/~slovak
Další komentáře
Studijní materiály
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 2008, podzim 2010, podzim 2011, podzim 2011 - akreditace, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018.