DM819: Geometriske algoritmer

Det Naturvidenskabelige Studienævn

Undervisningssprog: På dansk eller engelsk afhængigt af underviser, men engelsk ved internationale studerende
EKA: N340001112, N340001102
Censur: Intern prøve, en bedømmer, Ekstern prøve
Bedømmelse: Bestået/Ikke bestået, 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Efterår
Niveau: Kandidatkursus forhåndsgodkendt som Ph.d.-kursus

STADS ID (UVA): N340001101
ECTS-point: 10

Godkendelsesdato: 25-04-2019


Varighed: 1 semester

Version: Godkendt - aktiv

Kommentar

15013701 (tidligere UVA) er identisk med denne kursusbeskrivelse. 

Kandidatkursus forhåndsgodkendt som PhD-kursus 

Indgangskrav

Ingen

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

Se BlackBoard for pensumlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Forudsætningsprøve a)

Tidsmæssig placering

Efterår

Udprøvninger

Obligatoriske opgaver

EKA

N340001112

Censur

Intern prøve, en bedømmer

Bedømmelse

Bestået/Ikke bestået

Identifikation

Fulde navn og SDU brugernavn

Sprog

Følger, som udgangspunkt, undervisningssprog

Hjælpemidler

Oplyses på kurset

ECTS-point

0

Uddybende information

Forudsætningsprøven er en forudsætning for deltagelse i eksamenselement a)

Eksamenslement a)

Tidsmæssig placering

Januar

Forudsætninger

Type Forudsætningsnavn Forudsætningsfag
Delprøve Forudsætningsprøve a) N340001101, DM819: Geometriske algoritmer

Udprøvninger

Mundtlig eksamen

EKA

N340001102

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Studiekort

Sprog

Følger, som udgangspunkt, undervisningssprog

Hjælpemidler

 Oplyses på kurset

ECTS-point

10

Uddybende information

Reeksamen i samme eksamenstermin eller i umiddelbar forlængelse heraf. Med få studerende kan censurformen ændres til intern.

Vejledende antal undervisningstimer

56 timer per semester

Undervisningsform

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

Ansvarlig underviser

Navn E-mail Institut
Kim Skak Larsen kslarsen@imada.sdu.dk

Skemaoplysninger

Administrationsenhed

Institut for Matematik og Datalogi (datalogi, fiktiv)

Team hos Registrering & Legalitet

NAT

Anbefalede studieforløb

Profil Program Semester Periode