DM876: Graftegning

NYT kursus F20

Bestået bachelorgrad i Datalogi.

Studerende, der følger kurset, forventes at:

    • 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ålet med kurset er at give den studerende mulighed for at anvende og implementere graftegningsalgoritmer til at visualisere grafteoretiske mønstre. Kurset giver et overblik over graftegningsalgoritmer, der skal anvendes til forskellige graftyper, såsom træer, orienterede og ikke-orienterede grafer. Derudover diskuteres æstetiske kriterier og strategier til visualisering af strukturelle mønstrer i grafer på passende måder. Grafstrukturer er fundamentale for mange forskningsområder, såsom socialt netværksteori, biologi og kartografi, og deres visualisering er vigtig for domæneeksperter for at forstå topologiske egenskaber ved grafer, der er nødvendige for at verificere og generere hypoteser om det undersøgte emne.

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

Kurset indeholder følgende faglige hovedområder:

    • 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

Se BlackBoard for pensumlister og yderligere litteraturhenvisninger.

 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