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 2008 - 10 ECTS )

Rammer for udbud

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

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

Algoritmer og Datastrukturer 1 og 2

Underviser

Gerth Stølting Brodal

Undervisnings- og arbejdsform

Forelæsninger (3 t/uge)

Litteratur

Computational Geometry: Algorithms and Applications. Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Second Edition. Springer-Verlag, 367 pages, ISBN: 3-540-65620-0.

Kursushjemmeside

http://www.daimi.au.dk/~gerth/cg08/

Udbyder

Datalogisk Institut

Tilmelding til undervisning

http://www.brics.dk/~mis/enrollment.html

Studieordning og bedømmelse

Bacheloruddannelsen i datalogi

  • Mundtlig, bedømt efter 7-skala med intern censur

Bacheloruddannelsen i datalogi (1.del i datalogi-matematik)

  • Mundtlig, bedømt efter 7-skala med intern censur


Projekt og mundtlig eksamen
7-skala, intern censur