Netværksoptimering

• beskrive hvordan teknikker fra lineær/heltasprogrammering kan bruges til at udvikle og bevise korrekthed af forskellige netværks algoritmer
• forklare primal-duale algoritmer og deres anvendelse
• beskrive og bruge de centrale algoritmer indenfor de klassiske netværksproblemstillinger: mindst udspændende træ, korteste vej, projektplanlægning, maximum flow, minimum cost flow og multicommodity flow.
• kunne anvende grafer og netværk som modellerings-sprog
• gengive betydningen af og indholdet af de centrale beviser indenfor netværksoptimering.
• analysere og beskrive værste-tids tidskompleksitet af en algoritme.
• beskrive simple datastrukturer til grafalgoritmer
• arbejde selvstændigt med et større netværksproblem
• udarbejde en rapport om fundne resultater

Algoritmer til netværk: Resume af relevant grafteori. Algoritmer til bestemmelse af korteste veje, maksimal strømning i netværk med kapacitetsbegrænsninger og strømning med minimal omkostning. Anvendelse af grafer og netværk til at formulere komplekse problemer.

Forelæsninger, øvelser, projektarbejde