KURSPLAN

Algoritmer för geometriska problem 7,5 Högskolepoäng

Computional Geometry
Avancerad nivå, D7013E
Version
Kursplan gäller: Höst 2012 Lp 1 - Tillsvidare
Vald version visar för vilken termin och läsperiod som denna kursplanen gäller för. Senaste version visas först.

Kursplanen fastställd
av Institutionen för systemteknik 2007-12-17

Reviderad
av Jonny Johansson, HUL SRT 2012-03-12

Utbildningsnivå
Avancerad nivå
Fördjupningskod
A1N
Betygskala
G U 3 4 5
Ämne
Datalogi
Ämnesgrupp (SCB)
Datateknik

Behörighet

Kursen förutsätter att man kan programmera datorer och analysera algoritmer och datastrukturer. De två kurserna D0010E och D0012E ger en minsta lämplig nivå på dessa kunskaper.


Urval

Högskolepoäng 20-285 hp



Mål/Förväntat studieresultat

Efter kursen ska studenten

  1. uppvisa stor kunskap om den vetenskapliga grunden för datavetenskapen i form av konstruktion, presentation och analys av algoritmer och datastrukturer för geometriska problem innefattande fördjupade kunskaper inom delar av algoritmteorin,
  2. i omfattande utsträckning visa på förmåga att med helhetssyn kritiskt, självständigt och kreativt identifiera, formulera och hantera komplexa algoritmiska frågeställningar,
  3. uppvisa förmåga att i stor omfattning skapa, analysera och kritiskt granska algoritmer och datastrukturer för geometriska problem, samt utgående från egen planering och med adekvata metoder implementera sådana algoritmer och datastrukturer baserat på för ämnet beprövad erfarenhet och genom att systematiskt integrera kunskap,
  4. i omfattande utsträckning visa förmåga att muntligt klart redogöra för egna lösningar på algoritmiska problem av geometrisk natur och diskutera sina slutsatser och den kunskap och de argument som ligger till grund för dessa, och slutligen
  5. uppvisa viss insikt i aktuellt forskning- och utvecklingsarbete.

Kursinnehåll

Exempel på praktiska tillämpningar där geometriska algoritmer och datastrukturer är användbara, t ex robotik, datorgrafik, VLSI-design, virtuella miljöer (simuleringsverktyg och datorspel), geografiska informationssystem (GIS) och datorstödd design/konstruktion (CAD/CAM).

Teoriavsnitten omfattar bland annat geometriska beräkningsprimitiver och bevisföring, polygoner, triangulering, visibilitet, konstgalleriproblem, konvexa höljen, Voronoi. och Delaunaydiagram, närhetsberäkningar, lokaliseringsproblem, linjer, hyperplan, geometrisk dualitet, visibilitetsgrafer, beräkning av kortaste vägar, rörelse- och vägplanering, samt skärningar och unioner av geometriska objekt.


Genomförande

Undervisningen består av lektioner, föreläsningar, några obligatoriska laborationer samt ett projekt. På lektionerna presenterar studenter lösningar på hemuppgifter som ges efter föreläsningarna. Alla lösta uppgifter ger bonus på den avslutande tentan. Lösningarna diskuteras även i hela gruppen och under ledning av examinator. Det är frivilligt att lösa hemuppgifter och även den som inte löst dem är välkommen att vara med i diskussionen. Laborationerna syftar endast till att bli bekväm med utvecklingsmiljön och lära känna några vetenskapliga primärkällor (tidskrifter och konferenser). Projektet går ut på att självständigt implementera en geometrisk algoritm eller datastruktur. Resultatet presenteras sedan muntligt för klassen.


Examination

Kursmålen examineras med en avslutande skriftlig tentamen med differentierade betyg (delmål 1 och 2) och ett projekt som ska färdigställas på utsatt tid (3 och 5) och presenteras (4).


Övrigt
Kursen ges ej varje år.

Övergångsbestämmelser

Kursen D7013E motsvarar den gamla kursen SMD156.


Examinator
Håkan Jonsson

Övergångsbestämmelser
Kursen D7013E motsvarar kursen SMD156

Litteratur. Gäller från Höst 2012 Lp 1 (Kan ändras fram till 10 veckor innan studiestart)
Vetenskapliga artiklar.
de Berg, van Kreveld, Overmars och Schwartzkopf, Computational Geometry: Algorithms and Applications, 3:e upplagan.

Kursgivare
Institutionen för system- och rymdteknik

Prov
ProvnrTypHpBetyg
0002Projekt4.0U G#
0004Tentamen3.5G U 3 4 5

Studiehandledning