DM817: Netværksprogrammering: Teori og anvendelser

• Have kendskab basale algoritmer, som dem der undervises i DM578
• 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 DM578

Kurset bygger oven på den viden, der er erhvervet i kurserne DM578 Algoritmer og datastrukturer og DM553 Kompleksitet og Beregnelighed. 

• 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.

• 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.

• 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

Skemalagte undervisningstimer:
Antal undervisningstimer i alt: 45
Heraf:
Fællestimer i klasselokale/auditorium: 45

Forelæsning 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.

Opgaveregning: Disse opgaver gennemgås dels via videoer, dels ved de ugentlige møder.

• 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 refleksion over kursusmaterialerne.