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: 05-02-2022
Varighed: 1 semester
Version: Godkendt - aktiv
Kommentar
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 E22) udbydes: Ordinær eksamen januar 2023, første reeksamen marts 2023 og 2. reeksamen i juni 2023.
Eksamensforsøg for DM817 (en del af kursusudbud E22) udbydes: Ordinær eksamen januar 2023, første reeksamen marts 2023 og 2. reeksamen i juni 2023.
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
Mundtlig eksamen
EKA
N340083102
Censur
Ekstern prøve
Bedømmelse
7-trinsskala
Identifikation
Studiekort
Sprog
Følger, som udgangspunkt, undervisningssprog
Varighed
30 minutter forberedelse og 30 minutter eksamination
Hjælpemidler
Oplyses på kurset.
ECTS-point
10
Vejledende antal undervisningstimer
Undervisningsform
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.
- Introfasen vil for en stor dels vedkommende bestå af videoer som deltagerne ser og senere diskuterer med underviser ved ugentlige møder. Der vil være fysisk gennemgang af udvalgte emner.
- Træningsfasen består opgaveregning. Disse opgaver gennemgås dels via videoer, dels ved de ugentlige møder.
Aktiviteter i studiefasen:
- Løsning af ugentlige opgaver med henblik på diskussion af disse ved eksaminatorierne
- Selvstudium af visse emner fra lærebogen
- Selvstændig opsamling på intro og træningsfasen.
Introfasen består af (video)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.
Ansvarlig underviser
Skemaoplysninger
Administrationsenhed
Team hos Uddannelsesjura & Registratur
Udbudssteder
Anbefalede studieforløb
Overgangsordninger
Overgangsordninger beskriver, hvordan et kursus erstatter et andet kursus, når der ændres i et studieforløb.
Hvis der er lavet en overgangsordning for et kursus vil den fremgå af oversigten.
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.
Se overgangsordninger for alle kurser på Det Naturvidenskabelige Fakultet.