DM201: Grafalgoritmer med praktiske anvendelser (10 ECTS)

STADS: 15003201

Niveau
PhD-kursus

Undervisningsperiode
Kurset er placeret i forårssemesteret.
udbydes efter behov

Ansvarlige undervisere
Ingen ansvarlige undervisere angivet, kontakt eventuelt instituttet

Skemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.

Kommentar:
AFLYST F2009!

Indgangskrav:
Ingen

Faglige forudsætninger:
Bachelorgrad skal være bestået. Stoffet fra DM507 og DM508 forudsættes bekendt.

Kursusintroduktion
Formålet med kurset er at bibringe de studerende et indgående kendskab til algoritmer vedrørende grafer. Flere af de metoder som behandles har stor praktisk anvendelighed i f.eks. løsning af transportproblemer, netværksdesign, jobtildeling og planlægning af arbejdsprocesser. Disse sammenhænge vil blive belyst grundigt i kurset.

Forventet læringsudbytte
Ved kursets afslutning forventes de studerende at kunne

• anvende algoritmerne fra kurset på konkrete probleminstanser
• redegøre for de i kurset gennemgåede algoritmer og for deres kompleksiteter
• anvende teorien for strømning i netværk til at bevise strukturelle resultater for grafer
• redegøre for de i kurset gennemgåede resultater for matroider og vise hvordan disse kan anvendes på grafproblemer
• redegøre for algoritmer til at finde en maksimum (vægt) pardannelse i en graf, samt anvendelsen af disse i praktiske jobtilordningsproblemer
• redegøre for de i kurset gennemgåede resultater vedrørende sammenhæng i (di)grafer
• redegøre for de i kurset gennemgåede resultater vedrørende orienteringer af grafer
• redegøre for algoritmer til de i kurset gennemgåede ruteproblemer, herunder traveling salesman problemet
• redegøre for graffarvningsproblemet, heuristikker til at konstruere lovlige farvninger, samt anvendelser af graffarvning indenfor skedulering
• redegøre for de i kurset gennemgåede praktiske anvendelser af grafalgorimer
• redegøre for den såkaldte ”colour-coding” metode og vise hvordan man anvender den til at finde ”lange” kredse/veje i (di)grafer i polynomiel tid
• anvende algoritmer og algoritmiske ideer fra kurset i nye problemsammenhænge, der i natur ligner de i kurset behandlede emner

Emneoversigt
Strømning i netværk, jobtilordnings og transportproblemer, primal-dual algoritmer, pardannelser, sammenhæng i grafer, veje og kredse i grafer, traveling salesman problemet, orienteringer af grafer, grådige algoritmer og matroidealgoritmer, disjunkte veje og træer, minimums omkostnings branchings, polynomielle algoritmer til at finde veje og kredse i grafer med garanteret minimums længde, graffarvning.

Litteratur
Der er i øjeblikket ikke angivet nogle materialer for kurset.

Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Ingen

Eksamen- og censurform:
(a) Projektrapporter, der bedømmes med B/IB og intern censur ved underviser. Censor får adgang til at se rapporterne ved den mundtlige eksamen. Projekterne kan involvere programmeringsarbejde.
(b) Efter 4. kvartal afholdes en 30 minutters mundtlig eksamen med 30 minutters forberedelse med alle hjælpemidler. Der kan spørges i projektemnerne til den mundtlige eksamen. Bedømmelse efter 7-skalaen og ekstern censur.
(c) Reeksamen efter 2. kvartal.

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

Forelæsninger: 2 timer om ugen
Eksaminatorietimer: 2 timer om ugen
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på dansk eller engelsk, afhængigt af underviseren. Dog altid på Engelsk ved deltagelse af internationale studerende.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Dette er den nyeste version af en kursusbeskrivelse, som trådte i kraft den 1. feb 2008.