M7130 Geometrické algoritmy

Přírodovědecká fakulta
podzim 2011 - akreditace

Údaje z období podzim 2011 - akreditace se nezveřejňují

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
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 140 stud.
Momentální stav registrace a zápisu: zapsáno: 0/140, pouze zareg.: 0/140, pouze zareg. s předností (mateřské obory): 0/140
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
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
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 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018.