Vær opmærksom på at dette website indeholder et arkiv med historiske data. Det aktuelle kursuskatalog findes på kursuskatalog.au.dk

AU kursuskatalog arkiv

[Forside] [Hovedområder] [Perioder] [Udannelser] [Alle kurser på en side]

Computational Geometry (Q1+Q2) ( efterår 2010 - 10 ECTS )

Rammer for udbud

  • Uddannelsessprog: engelsk
  • Niveau: Kandidatkursus
  • Semester/kvarter: Q1+Q2
  • Timer per uge: 3
  • Deltagerbegrænsning: Ingen
  • Undervisningssted: Århus
  • Hovedområde: Det Naturvidenskabelige Fakultet
  • Udbud ID: 19015

Formål

Deltagerne vil efter kurset have detaljeret kendskab til fundamentale problemstillinger inden for "Computational Geometry" og generelle problemløsningsteknikker inden for området og praktisk erfaring med aspekterne involveret i at oversætte en geometrisk algoritme til et kørende program.

Obligatorisk program

3 projekter

Indhold

Kurset giver en introduktion til de centrale begreber, problemstillinger, problemløsningsteknikker og datastrukturer indenfor "Computation Geometry", inkluderende: Begreber (punkter, linier, planer, sfærer, dualitet, opdelinger, degenererede tilstande), problemstillinger (krydsende linier, konvekse hylstre, Voronoi diagram, trianguleringer, Delaunay trianguleringer, kombination af opdelinger, range-søgninger), problemløsningsteknikker (sweep-line, randomiseret inkrementiel konstruktion, fractional cascading), og datastrukturer (dobbelt-kædede kant-lister, intervaltræer, segmenttræer, prioritets søgetræer, Kd-træer, range-træer).

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:

  • konstruere algoritmer for simple geometriske problemstillinger.
  • implementere geometriske algoritmer.

Faglige forudsætninger

Underviser

Gerth Stølting Brodal

Undervisnings- og arbejdsform

Forelæsninger (3 t/uge)

Litteratur

Computational Geometry: Algorithms and Applications. Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Third Edition. Springer-Verlag, 386 pages, 2008. ISBN: 978-3-540-77973-5.

Kursushjemmeside

http://www.cs.au.dk/~gerth/cg10/

Eksamensterminer

December/januar, reeksamen august

Udbyder

Datalogisk Institut

Tilmelding til undervisning

https://mit.au.dk/

 

Bedømmelse

Projekt og mundtlig eksamen (20 minutter) uden forberedelse, 7-skala, intern censur