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

STADS: 15005701

Niveau
Kandidatkursus

Undervisningsperiode


Ansvarlige undervisere
Email: jbj@imada.sdu.dk

Skemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.

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 flervare strømningsproblemer 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, travelleling salesman problemet, 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, multicommodity flows, 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.

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å engelsk, hvis der deltager internationale studerende, ellers undervises på dansk.

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 2011 til 31. januar 2012.