FI:M013 Geometrické algoritmy I - Informace o předmětu
M013 Geometrické algoritmy I
Fakulta informatikypodzim 2001
- Rozsah
- 3/0. 3 kr. (plus ukončení). Doporučované ukončení: k. Jiná možná ukončení: zk, z.
- Vyučující
- prof. RNDr. Jan Slovák, DrSc. (přednášející)
- Garance
- doc. RNDr. Jiří Kaďourek, CSc.
Ústavy – Přírodovědecká fakulta
Kontaktní osoba: prof. RNDr. Jan Slovák, DrSc. - Předpoklady
- M008 Algebra I
Doporučuje se zapsat zároveň P093 Projekt z geometrických algoritmů. Je výhodné před zapsáním absolvovat P009 Základy počítačové grafiky. - 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
- Informatika (program FI, B-IN)
- Informatika (program FI, M-IN)
- Učitelství výpočetní techniky pro střední školy (program FI, M-IN)
- Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
- Výpočetní technika (program FI, B-IN)
- Osnova
- Konvexní mnoúhelníky (průniky, incidence bodů, algoritmy pro konvexní obaly -- jednoprůchodový algoritmus, Grahamovo prohlížení, Jarvisův pochod, balení balíčku, algoritmy ve vyšších dimenzích).
- Voronoiho diagramy a jejich aplikace (algoritmus metodou rozděl a panuj, zobecnění, aplikace, problém nejbližších sousedů, geometrické transformace).
- 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 zjemňování).
- Průniky (průniky úseček metodou pročesávání, průniky polorovin a konvexních mnohoúhelníků, aplikace a vícerozměrné algoritmy).
- Vyhledávání podle rozsahu (multidimensionální binární stromy, metoda přímého přístupu, stromy úseček).
- Úlohy o obdélnících (míra sjednocení obdélníků, obvod sjednocení mnohoúhelníků, průniky obdélníků).
- Literatura
- O'ROURKE, Joseph. Computational geometry in C. 2nd ed. Cambridge: Cambridge University Press, 1998, xiii, 376. ISBN 0-521-64976-5. info
- PREPARATA, Franco P. a Michael Ian SHAMOS. Computational geometry : an introduction. New York: Springer-Verlag, 1985, 398 s. ISBN 0387961313. info
- Handbook of discrete and computational geometry. Edited by Jacob E. Goodman - Joseph O'Rourke. Boca Raton: CRC Press, 1997, xvi, 991 s. ISBN 0-8493-8524-5. info
- Metody hodnocení
- Výuka probíhá standardní formou. Doporučené ukončení je kolokvium, které probíhá formou jednoho písemného testu ve zkouškovém období po ukončení výuky. Ke zkoušce je třeba vypracovat praktický projekt a absolvovat po projití kolokviálním testem ještě ústní rozpravu. Lze přitom využít projekt vypracovaný v rámci P093 Projekt z geometrických algoritmů.
- Informace učitele
- http://www.math.muni.cz/~slovak/#1
- Další komentáře
- Poznámka k ukončení předmětu: K ukončení zkouškou je nutné vypracovat projekt
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
- Statistika zápisu (nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2001/M013