DM817: Netværksprogrammering: Teori og anvendelser (10 ECTS)

STADS: 15005701

Niveau
Kandidatkursus forhåndsgodkendt som PhD-kursus

Undervisningsperiode
Kurset udbydes efter behov.
Udbydes efter behov.

Ansvarlige undervisere
Email: jbj@imada.sdu.dk

Skemaoplysninger
Hold Type Dag Tidsrum Lokale Uger Kommentar
Fælles I Mandag 14-16 IMADA semi 15
Fælles I Mandag 12-16 IMADA semi 17
Fælles I Mandag 12-14 IMADA semi 18
Fælles I Tirsdag 14-16 IMADA semi 12
Fælles I Onsdag 12-14 IMADA semi 12
Fælles I Onsdag 14-16 IMADA semi 15-16
Fælles I Torsdag 10-12 U7 5,8-11
Fælles I Torsdag 10-12 IMADA semi 6-7,16
Fælles I Fredag 11-13 IMADA semi 5-11
H1 TE Mandag 09-11 U155 6
H1 TE Mandag 10-12 IMADA semi 7-8
H1 TE Mandag 14-16 IMADA semi 16
H1 TE Onsdag 12-14 IMADA semi 9-11
H1 TE Torsdag 12-14 IMADA semi 5,15
H1 TE Torsdag 10-12 U153 12
H1 TE Torsdag 10-12 IMADA semi 18
H1 TE Fredag 10-12 IMADA semi 16
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal

Indgangskrav:
Ingen

Faglige forudsætninger:
Studerende, der følger kurset, forventes at:
  • Have kendskab basale algoritmer, som dem der undervises i DM507
  • Gave kendskab til basal matematisk argumentation, herunder bevis ved induktion og bevis ved modstrid.
  • Have kendskab til kompleksitet af algoritmer
  • Have kendskab til basale datastrukturer som dem der undervises i DM507
 


Formål
Kurset har til formål at sætte den studerende i stand til at:
  • Anvende strømningsalgoritmer som et vigtigt værktøj til at løse praktiske optimeringsproblemer. Eksempler på disse er, udover egentlige strømningsproblemer, f.eks. matchingproblemer, orienteringsproblemer og simple skeduleringsproblemer
  • Modellere diverse optimeringsproblemer som strømningsproblemer 
  • Anvende teorien for strømning i netværk til at vise at et givet problem kan løses effektivt.
  • Bruge teorien for strømning i netværk til at udlede strukturelle beskrivelser af optimale løsninger til visse optimeringsproblemer.
  • Redegøre for de i kurset gennemgåede algoritmer, samt anvende disse på problemer som ligner dem fra kurset.
  • Opstille en (generaliseret) strømningsmodel ud fra en problembeskrivelse i ord.
  • Redegøre for algoritmer fra kurset, hvori strømningsalgoritmer indgår som en delkomponent, f.eks udvidelse af kantsammenhængen i digrafer, pardannelse i 2-delte grafer og skeduleringsalgoritmer.
Kurset bygger oven på den viden, der er erhvervet i kurserne DM507 Algoritmer og datastrukturer og DM553 Kompleksitet og Beregnelighed.
 
Kurset giver fagligt grundlag for valgfrie kandidatkurser indenfor kombinatorisk optimering og grafteoretiske emner. Desuden giver kurset et fagligt grundlag for at lave et speciale indenfor grafalgoritmer, samt naturligvis alle strømningsrelaterede emner.

I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at den studerende skal:
  • Kunne analysere og løse avancerede problemstillinger ved hjælp af de lærte strømningsmetoder.
  • Kunne udvikle nye varianter af de lærte strømningsmetoder med henblik på at anvende disse på nye problemtyper.
  • Kunne løse praktiske optimeringsproblemer ved hjælp af de lærte algoritmer.
 
 


Målbeskrivelse
For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evnen til at:
  • Kunne anvende teorien for strømning i netværk som et redskab til at løse problemer som i natur ligner dem fra kurset.
  • Kunne anvende strømningsalgoritmer som delkomponenter i mere komplekse algoritmer.
  • Kunne vurdere om man kan modellere et givet problem, som i natur ligner dem fra kurset, som et strømningsproblem.
  • Argumentere for kompleksiteten af algoritmer som baserer sig på strømningsalgoritmer.
  • Kunne redegøre for generalisationer af strømning i netværk og forklare med eksempler, hvorledes disse udvider anvendelsesområdet for teorien.
  • Kunne anvende teori og algoritmer fra kurset  til at løse praktiske optimeringsproblemer, som for eksempel strømningsproblemer, transportproblemer, matching problemer, simple skeduleringsproblemer og problemer vedrørende orienteringer af (vej) netværk.
 


Indhold
Kurset indeholder følgende faglige hovedområder:
  • Korteste veje 
  • Strømning og minimum omkostnings strømning
  • Polynomielle algoritmer til strømningsproblemer
  • Skedulering, herunder projektplanlægning
  • Strømninger med konvekse omkostningsfunktioner
  • Submodulære strømme
  • Grafsammenhæng
  • Pardannelse i grafer
  • Primal dual algoritmer
 


Litteratur
    Meddeles ved kursets start


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

Forudsætningsprøver
Ingen

Eksamen- og censurform:
  1. Projektopgaver. (10 ECTS). Ekstern censur, 7-trinsskala. 
Nærmere beskrivelse af eksamensreglerne vil blive offentliggjort under 'Course Information' på kursets side i Blackboard.
Reeksamen er en mundtlig eksamen.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
Introfase: 40 timer
Træningsfase: 26 timer, heraf:
 - Eksaminatorie: 26 timer

Aktiviteter i studiefasen
  • Løsning af ugentlige opgaver med henblik på diskussion af disse ved eksaminatorierne
  • Løsning af projektopgaverne
  • Selvstudium af visse emner fra lærebogen
  • Selvstændig opsamling på intro og træningsfasen
Undervisningsform
Introfasen består af forelæsninger ved underviser. Her gennemgås teori og metoder og disse  illustreres med eksempler. Introfasen suppleres af træningsfasen, hvor de studerende ugentligt arbejder med  nye opgaver, der belyser de emner som aktuelt studeres. Endeligt består studiefasen af yderligere selvstændig læsning af og reflektion over kursus materialerne, samt løsning af de 2 projektopgaver som udgør kursets evaluering.

Sprog
Dette kursus undervises på engelsk, hvis der deltager internationale studerende, ellers undervises på dansk.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. februar 2018 til 31. august 2020.