DM819: Geometriske algoritmer

Intern kursuskode

DM819

Kommentar

Kurset udbydes efter behov og udbydes ikke nødvendigvis hvert år. Eksamensforsøg for DM819 udbydes efter følgende plan, når kurset udbydes:

Efterår: ordinær eksamen (januar), første reeksamen (marts) og 2. reeksamen i (juni)
Forår: ordinær eksamen (juni), første reeksamen (august) og 2. reeksamen i (januar)

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 algoritmekurser og kurser i diskret matematik og sandsynlighedsteori på en bacheloruddannelse i datalogi.

Kurset bygger på færdigheder opnået i algoritmekurser på en datalogisk bacheloruddannelse og giver kompetencer til specialeskrivning indenfor området.

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 itslearning for pensumlister og yderligere litteraturhenvisninger.

Eksamensbestemmelser

Eksamenselement a)

Tidsmæssig placering

Ved udbud i efterårssemester er eksamen i januar.

Ved udbud i forårssemester er eksamen i juni.

Udprøvninger

Mundtlig eksamen

EKA

N340001102

Censur

Ekstern prøve

Bedømmelse

7-trinsskala

Identifikation

Studiekort - Navn

Sprog

Følger, som udgangspunkt, undervisningssprog

Varighed

30 minutter

Hjælpemidler

Oplyses på kurset

ECTS-point

Uddybende information

Eksamen består af en mundtlig eksamen og et projekt med en samlet evaluering.

Vejledende antal undervisningstimer

56 timer per semester

Undervisningsform

Skemalagte undervisningstimer:

Antal undervisningstimer i alt: 56

Heraf:

Fællestimer i klasselokale/auditorium: 56

Strukturelt afvikles skematimerne med gennemgang af nyt stof cirka halvdelen af gangene og nærmere diskussion af egenskaber og varianter omkring stoffet i den anden halvdel. I den første del benyttes en modificeret udgave af klassisk forelæsning, hvor fagets grundbegreber og metoder præsenteres, med såvel teori som eksempler baseret på konkrete data. I disse timer er der mulighed for spørgsmål og diskussion. I den anden halvdel arbejdes der med opgaver og diskussionsemner, som relaterer sig til indholdet i de forudgående forelæsninger. I disse timer er der mulighed for at arbejde specifikt med særligt vanskelige emner. Også i denne forbindelse er der mulighed for at bringe spørgsmål op.

Andre planlagte undervisningsaktiviteter:

Opsamling af introduceret og behandlet stof
Løsning af opgaver med henblik på diskussion af disse ved eksaminatorierne
Løsning af projektopgaver
Selvstudium af visse emner fra lærebogen

Ansvarlig underviser

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

Skemaoplysninger

Odense

Vis fuldt skema (start E25)
Vis fuldt skema (start F26)

Administrationsenhed

Institut for Matematik og Datalogi (datalogi)

Team hos Registratur

NAT

Udbudssteder

Odense

Anbefalede studieforløb

Profil	Uddannelse	Semester	Udbuds periode

Overgangsordninger

Overgangsordninger beskriver, hvordan et kursus erstatter et andet kursus, når der ændres i et studieforløb.

Hvis der er lavet en overgangsordning for et kursus vil den fremgå af oversigten.
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.