DM819: Geometriske algoritmer
Kommentar
15013701 (tidligere UVA) er identisk med denne kursusbeskrivelse.
Kandidatkursus forhåndsgodkendt som PhD-kursus
Indgangskrav
Faglige forudsætninger
Der forudsættes kendskab til algoritmer og datastrukturer og analyse af disse, herunder algoritmedesignteknikker som del-og-hersk, balancerede binære søgetræer som rød-sorte træer, samt korrekthedsanalyse og kompleksitetsanalyse under anvendelse af rekursionsligninger og asymptotisk notation. Desuden forventes kendskab til resultater for nedre grænser for sortering, samt et basalt kendskab til sandsynlighedsteori. Forudsætningerne kan erhverves gennem kurserne DM507 og DM549, samt dele af DM551 og DM553.
Formål
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.
Målbeskrivelse
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
Indhold
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
Eksamensbestemmelser
Forudsætningsprøve a)
Tidsmæssig placering
Udprøvninger
Obligatoriske opgaver
EKA
Censur
Bedømmelse
Identifikation
Sprog
Hjælpemidler
ECTS-point
Uddybende information
Eksamenselement a)
Tidsmæssig placering
Forudsætninger
Type | Forudsætningsnavn | Forudsætningsfag |
---|---|---|
Delprøve | Forudsætningsprøve a) | N340001101, DM819: Geometriske algoritmer |