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

STADS: 15005701

Niveau
Kandidatkursus

Undervisningsperiode
Kurset er placeret i efterårssemesteret.
Udbydes efter behov.

Ansvarlige undervisere
Email: jbj@imada.sdu.dk

Yderligere undervisere
maddaloni@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

Kommentar:
Ubegrænset deltagerantal. 3. + 4. kvartal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Kendskab til algoritmer, datastrukturer og kompleksitet, svarende til f.eks. fra DM507 og DM508.

Kursusintroduktion
At introducere teorien for strømning i netværk og generalisationer af strømning samt anvendelser af disse metoder på en lang række vigtige problemer. Dette inkluderer metoder til at løse strømningsproblemer, modellering og løsning af problemer (herunder grafproblemer, skeduleringsproblemer, etc.) som strømningsproblemer, anvendelser på praktiske optimeringsproblemer, samt generalisationer af strømning i netværk, såsom og submodulære strømme. Strømning i netværk er nok en af de mest relevante grafteoretiske emner overhovedet med henblik på praktiske anvendelser. Utallige praktiske problemer kan formuleres og løses effektivt via en formulering som et strømningsproblem. Der er et eksplicit mål at bringe de studerende i stand til selv at anvende dette nyttige værktøj både i teori og i praksis.

Forventet læringsudbytte
Ved kursets afslutning forventes den studerende at kunne:

• opstille en generaliseret strømningsmodel ud fra en problembeskrivelse i ord
• redegøre for algoritmer fra kurset hvori strømningsproblemer indgår som en delkomponent. F.eks. udvidelse af kantsammenhængen i grafer, pardannelse i 2-delte grafer, skedulerings algoritmer, etc.
• anvende teorien fra kurset til at løse praktiske optimeringsproblemer, som for eksempel strømningsproblemer, transportproblemer, matching problemer, simple skeduleringsproblemer, orienteringsproblemer etc.
• redegøre for de i kurset gennemgåede algoritmer og anvende disse på problemer som ligner dem fra kurset.

Emneoversigt
Korteste veje, (min cost) flows, projektplanlægning, skedulering, lineær og heltals programmering, lagrange-relaksation, flows med konveks omkostningsfunktion, submodular flows, grafsammenhæng, pardannelse i grafer, Steiner træer 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:
Projektopgave, 7-trinsskalaen og ekstern censur. (15005702)

Reeksamen kan have en anden form end den ordinære eksamen.

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

Forelæsninger 40, Eksaminatorier 26
Aktiviteter i studiefasen

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

Bemærkninger
Kurset udbydes efter behov. Der må påregnes et betydeligt arbejde i forbindelse med projektet som udleveres ca. midt i 2. kvartal af kurset. Selvom der vil indgå emner vedrørende lineær programmering i kurset, er DM515 ikke en forudsætning for at kunne følge dette kursus. Vi introducerer de få ting vi har brug for undervejs i kurset.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. februar 2012 til 31. august 2013.