FI:MA017 Geometric Algorithms - Informace o předmětu

MA017 Geometric Algorithms

Rozsah

2/0/0. 2 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.

Vyučující

doc. John Denis Bourke, PhD (přednášející)
doc. RNDr. Martin Čadek, CSc. (přednášející)

Garance

doc. RNDr. Martin Čadek, CSc.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta

Rozvrh

Po 16:00–17:50 A,01026

Předpoklady

Basic course on algorithms, high school geometry.

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

• Aplikovaná informatika (program FI, N-AP)
• Bezpečnost informačních technologií (angl.) (program FI, N-IN)
• Bezpečnost informačních technologií (program FI, N-IN)
• Bioinformatika (program FI, N-AP)
• Informační systémy (program FI, N-IN)
• Informatika (program FI, B-INF) (2)
• Paralelní a distribuované systémy (program FI, N-IN)
• Počítačová grafika (program FI, N-IN)
• Počítačové sítě a komunikace (program FI, N-IN)
• Počítačové systémy (program FI, N-IN)
• Programovatelné technické struktury (angl.) (program FI, N-IN)
• Programovatelné technické struktury (program FI, N-IN)
• Služby - výzkum, řízení a inovace (angl.) (program FI, N-AP)
• Služby - výzkum, řízení a inovace (program FI, N-AP)
• Teoretická informatika (program FI, N-IN)
• Umělá inteligence a zpracování přirozeného jazyka (program FI, N-IN)
• Zpracování obrazu (program FI, N-AP)

Cíle předmětu

The aim of the course is to introduce the principles of basic algorithms in computational geometry. This course can be followed by the PA093 Computational Geometry Project where the students are implemented selected algorithms in practice.

Výstupy z učení

Students will gain knowledge about state-of-the-art algorithmic methods in this field, along with their complexity and underlying data and searching structures.

Osnova

• 1. Algorithms for construction of convex hulls in two-dimensional space 2. Line segment intersections 3. Triangulations 4. Linear programming in two-dimensional space 5. Range searching (kd-trees, range trees) 6. Point localization 7. Voronoi diagrams 8. Duality and arrangements 9. Delaunay triangulation 10. Convex hulls in in three-dimensional space

Literatura

doporučená literatura
• DE BERG, Mark, Otfried CHEONG, Marc VAN KREVELD a Mark OVERMARS. Computational geometry. 3rd ed. Berlin, Heidelberg: Springer, 2008. ISBN 978-3-540-77973-5. URL info

Výukové metody

Lectures.

Metody hodnocení

Written exam. Requirements: to prove the knowledge of the theory from lectures and to be able to apply it to related problems.

Vyučovací jazyk

Angličtina

Informace učitele

https://is.muni.cz/auth/do/sci/UMS/el/geometricke-alg/index.html

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

• Statistika zápisu (podzim 2020, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/podzim2020/MA017