DM876: Graftegning
Kommentar
Indgangskrav
Faglige forudsætninger
- have kendskab til grundlæggende datastrukturer
- have kendskab til grundlæggende algoritmer til behandling af data og manipulation af datastrukturer
- kunne bestemme kompleksiteten af algoritmer og anvende optimeringsstrategier
Formål
Kurset bygger på den viden, der er erhvervet i kurserne DM550 (Introduktion til programmering), DM507 (Algoritmer og datastrukturer) og DM553 (Kompleksitet og beregnelighed), og giver et akademisk grundlag for at forberede et speciale, hvor grafstrukturer er i fokus.
I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at:
- give ekspertviden om et udvalgt studieområde, der er relateret til flere forskningsområder
- give kompetence til at beskrive graftegning algoritmer præsenteret i løbet af kurset
- give færdigheder til at anvende de gennemgåede graftegningsalgoritmer på kompetent vis
- give kompetence til at tilpasse graftegningsalgoritmer til applikationskrav, herunder evnen til at tage beslutte om layout-begrænsninger og visuelle funktion aniteter
- give kompetence til at overføre gennemgåede algoritmer til forskellige applikationsområder
- udfordre den studerende med virkelige datasæt og problemløsning
Målbeskrivelse
- beskrive, hvordan graftegningsalgoritmer fungerer
- vælge passende graftegningsalgoritmer til givne grafer
- overveje æstetiske kriterier, når man tegner grafer
- implementere graftegningsalgoritmer
- tilpasse standard graftegningsalgoritmer til forekommende data anomalier
- opdage flaskehalse i graftegningsalgoritmer og anvende optimeringsstrategier
- designe og implementere brugergrænseflader til grafvisualisering
Indhold
- graf embedding, planaritetstest og planarisering af grafer
- æstetiske kriterier, der skal overvejes, når man tegner grafer
- lineære, ortogonale, rektangulære og polylinje tegningsalgoritmer
- kraftorienterede tegningsalgoritmer
- hierarkiske tegningsalgoritmer
- træ-tegningsalgoritmer
- diverse graftegninger, fx radiale layouts, kantdiagrammer, produkt-graftegninger, topologisk graf-layout
- anvendelser af graftegningsalgoritmer inden for forskellige forskningsområder, fx biologi, kartografi, dataanalyse og digital humaniore
- visuelle funktioner, der skal bruges til formidling af grafteoretiske mønstre i en visuel form
- implementering af valgte graftegningsalgoritmer
Litteratur
Eksamensbestemmelser
Eksamenselement a)
Tidsmæssig placering
Udprøvninger
Mundtlig eksamen
EKA
Censur
Bedømmelse
Identifikation
Sprog
Hjælpemidler
ECTS-point
Uddybende information
Vejledende antal undervisningstimer
Undervisningsform
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
- Introfase (forelæsning, holdtimer) - Antal timer: 24
- træningsfase: Antal timer: 24, heraf eksaminatorietimer 24
Introfasen letter introduktionen af nyt materiale og emner, der i træningsfase behandles med øvelser, der forberedes hjemme og diskuteres i klassen for at validere den erhvervede viden. Studiefase i form af praktiske anvendelser giver eleverne mulighed for at anvende den opnåede viden.
Studiefaseaktiviteter:
- Små projekter, der sigter mod at visualisere grafiske datasæt i den virkelige verden ved at implementere lærte graftegningsalgoritmer
- Undersøgelse af specialiserede graftegningsalgoritmer baseret på videnskabelige artikler