DM817: Netværksprogrammering: Teori og anvendelser (10 ECTS)
STADS: 15005701
Niveau
Kandidatkursus
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 |
12-14 |
IMADA Seminarrum |
36-41 |
|
Fælles |
I |
Mandag |
14-16 |
IMADA Seminarrum |
45-51 |
|
Fælles |
I |
Tirsdag |
12-14 |
IMADA Seminarrum |
45-51 |
|
Fælles |
I |
Onsdag |
08-10 |
IMADA Seminarrum |
45-51 |
|
Fælles |
I |
Torsdag |
12-14 |
IMADA Seminarrum |
36-41 |
|
Fælles |
I |
Fredag |
08-10 |
IMADA Seminarrum |
36-41 |
|
Vis hele skemaet
Vis personligt skema for dette kursus.
Indgangskrav:
Ingen
Faglige forudsætninger:
Kendskab til algoritmer, datastrukturer og kompleksitet, svarende til f.eks. fra DM507 og DM508.
KursusintroduktionAt 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æringsudbytteVed 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.
EmneoversigtKorteste 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.
LitteraturDer er i øjeblikket ikke angivet nogle materialer for kurset.
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.
Introfase: 40 timer
Træningsfase: 26 timer, heraf:
- Eksaminatorie: 26 timer
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. september 2013 til 31. januar 2018.