PřF:M7130 Geometrické algoritmy - Informace o předmětu
M7130 Geometrické algoritmy
Přírodovědecká fakultapodzim 2004
- Rozsah
- 3/0/0. 3 kr. (příf plus uk plus > 4). Doporučované ukončení: zk. Jiná možná ukončení: k.
- Vyučující
- prof. RNDr. Jan Slovák, DrSc. (přednášející)
- Garance
- prof. RNDr. Jan Slovák, DrSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Kontaktní osoba: prof. RNDr. Jan Slovák, DrSc. - Rozvrh
- St 10:00–12: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
- předmět má 6 mateřských oborů, zobrazit
- Cíle předmětu
- Přehled tzv. "Computational Geometry". Důraz je kladen na srovnávání různých paradigmat při návrhu algoritmů (jednoprůchodové, rekurzivní "rozděl a panuj", pročesávací, náhodnostní, geometrické transformace problémů), potřebnost vhodných datových struktur, odhady nejhorších i očekávaných parametrů algoritmů.
- Osnova
- 1.Úlohy o konvexních mnoúhelnících (průniky, incidence bodů). 2.Algoritmy pro konvexní obaly (jednoprůchodový algoritmus, Grahamovo prohlížení, Jarvisův pochod, balení balíčku). 3.Voronoiho diagramy a jejich aplikace (algoritmus metodou rozděl a panuj, zobecnění, aplikace, problém nejbližších sousedů, geometrické transformace). 4.Triangulace a vyhledávání v rovinných rozděleních (Delaunayova triangulace, "lakomecká" triangulace, postupné triangulování s předem zadanými hranami, geometrické vyhledávání, metoda pásů, metoda cest, redukované vyhledávací struktury, metoda postupného zjemnování). 5. Průniky a podobné problémy (průniky úseček metodou pročesávání, aplikace a vícerozměrné algoritmy). 6.Vyhledávání podle rozsahů (multidimensionální binární stromy, metoda přímého přístupu, stromy úseček). 7.Úlohy o obdélnících (míra sjednocení obdélníků, obvod sjednocení mnohoúhelníků, průniky obdélníků)
- 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ísemná zkouška zpravidla bez ústní rozpravy
- Informace učitele
- http://www.math.muni.cz/~slovak
- Další komentáře
- Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je vyučován každoročně.
- Statistika zápisu (podzim 2004, nejnovější)
- Permalink: https://is.muni.cz/predmet/sci/podzim2004/M7130