DM819: Geometriske algoritmer (10 ECTS)

STADS: 15006601

Niveau
Kandidatkursus

Undervisningsperiode

Udbydes efter behov

Ansvarlige undervisere
Email: kslarsen@imada.sdu.dk

Skemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.

Kommentar:
Ubegrænset deltagerantal. Kurset kører i 1.+2. kvartal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra DM508 Algortimer og kompleksitet skal være kendt.

Kursusintroduktion
Kurset er en introduktion til de væsentligste emner indenfor algoritmer omkring geometriske objekter. Som en integreret del af kurset opøves deltagerne i implementation indenfor området. Geometriske algoritmer er en vigtig del af anvendelser indenfor computerspil og computergrafik generelt, geografiske informationssystemer, robotkontrol, design, billedeanalyse, mm. Da disse anvendelsesområder involverer meget store datamængder, stilles der store krav til effektiviteten af de grundlæggende algoritmer og datastrukturer. Fokus er dog ikke på anvendelserne, men på kerneproblemerne indenfor geometriske algoritmer.

Forventet læringsudbytte
Ved kursets afslutning forventes den studerende at kunne:
• gøre rede for funktionaliteten og korrektheden af de gennemgåede algoritmer og datastrukturer
• analysere de gennemgåede algoritmer og datastrukturer mht. tids- og pladskompleksitet
• designe effektive algoritmer og datastrukturer for varianter af de belyste problemstillinger
• gøre detaljeret rede for problemstillinger omkring implementation af de gennemgåede algoritmer og datastrukturer i et standard programmeringssprog

Emneoversigt
Overlappende linier, trianguleringer, lineær programmering, interval- og punktsøgninger, Voronoi-diagrammer, konvekst hylster, ray tracing, motion planning, træbaserede geometriske strukturer, samt teknikker som plane-sweep, fractional cascading, randomisering, mm.

Litteratur

Meddeles ved kursets start.

Pensum
Se pensumbeskrivelse.

Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Ingen

Eksamen- og censurform:
Mundtlig eksamen, 7-skalaen, ekstern censur
Obligatoriske opgaver, Bestået/ikke-bestået, Intern censur ved underviser

Reeksamen følger terminerne i eksamensbekendtgørelsen. Med få studerende kan censurformen ændres til intern.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

Forelæsninger: 28 timer
Eksaminatorietimer/opgaveregning: 28 timer
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på dansk eller engelsk, afhængigt af underviseren. Dog altid på Engelsk ved deltagelse af internationale studerende.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. september 2009 til 31. august 2013.