DM817: Netværksprogrammering: Teori og anvendelser
Det Naturvidenskabelige Studienævn
Undervisningssprog: Dansk, men engelsk ved internationale studerende
EKA: N340083102
Censur: Ekstern prøve
Bedømmelse: 7-trinsskala
Udbudssteder: Odense
Udbudsterminer: Efterår
Niveau: Kandidatkursus forhåndsgodkendt som Ph.d.-kursus
STADS ID (UVA): N340083101
ECTS-point: 10
Godkendelsesdato: 02-03-2020
Varighed: 1 semester
Version: Arkiv
Kommentar
15005701 (tidligere UVA) er identisk med denne kursusbeskrivelse.
Kurset udbydes efter behov og udbydes ikke nødvendigvis hvert år. Eksamensforsøg for DM817 udbydes efter følgende plan, når kurset udbydes: Ordinær eksamen (januar), første reeksamen (marts) og 2. reeksamen i (juni).
Eksamensforsøg for DM817 (en del af kursusudbud E20) udbydes: Ordinær eksamen januar 2021, første reeksamen marts 2021 og 2. reeksamen i juni 2021.
Indgangskrav
Faglige forudsætninger
Studerende, der følger kurset, forventes at:
- Have kendskab basale algoritmer, som dem der undervises i DM507
- Have 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.
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
Eksamensbestemmelser
Eksamenselement a)
Tidsmæssig placering
Januar
Udprøvninger
Projektopgaver
EKA
N340083102
Censur
Ekstern prøve
Bedømmelse
7-trinsskala
Identifikation
Studiekort
Sprog
Følger, som udgangspunkt, undervisningssprog
Varighed
Mundtlig reeksamen - 60 minutter
Hjælpemidler
Nærmere beskrivelse af eksamensreglerne vil blive offentliggjort i itslaerning.
ECTS-point
10
Uddybende information
Reeksamen er en mundtlig eksamen.
Vejledende antal undervisningstimer
Undervisningsform
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
- Introfase 40 timer
- Træningsfase 26 timer, heraf eksaminatorier 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.
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.