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ålKurset 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ålbeskrivelseFor 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.
IndholdKurset 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
LitteraturMeddeles ved kursets start
Kursets hjemmeside
Dette kursus benytter
e-learn (blackboard).
Forudsætningsprøver
Ingen
Eksamen- og censurform:
- 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
UndervisningsformIntrofasen 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.