Algoritmisk problemlösning: Grafer och flöden

Mål

Målet med kursen är att utveckla förmågan att lösa algoritmiska problem genom att utnyttja kunskaper om algoritmer, data strukturer och komplexitetsteori med ett fokus på grafer och flöden. För att lösa den här typen av problem är det viktigt att kunna analysera problemet, välja eller designa en algoritm, avgöra hur mycket resursers (tid och minne) algoritmen kräver samt att implementera och testa algoritmen snabbt och korrekt.

Studentens lärandemål:

• Att känna till och förstå vanliga algoritmer och datastrukturer för grafer och flöden.
• Att kunna implementera algoritmer och datastrukturer relevanta för grafer och flöden.
• Att kunna lösa algoritmiska problem kopplade till grafer och flöden.
• Att analysera effektiviteten hos olika möjliga lösningar på ett algoritmiskt problem, med fokus på grafer och flöden, för att avgöra vilken som är tillräckligt effektivt för en given situation.

Innehåll

För att framgångsrikt lösa datavetenskapliga problem krävs en solid teoretisk grund samt förmågan att applicera teorierna vid praktisk problemlösning. Målet med den här kursen är att utveckla förmågan att lösa algoritmiska problem genom att utnyttja kunskaper om algoritmer, datastrukturer och komplexitetsteori. För att lösa den här typen av problem är det viktigt att kunna analysera problemet, välja eller designa en algoritm, avgöra hur mycket resursers (tid och minne) algoritmen kräver samt att implementera och testa algoritmen snabbt och korrekt.

Syftet är att studenterna ska kunna använda programmering och algoritmer, särskilt grafer och flöden, som ett effektivt verktyg för problemlösning samt få en möjlighet att tillämpa teoretiska kunskaper från andra kurser för att lösa praktiska problem.

Kursen ger praktiskt och teoretisk kunskap om viktiga datastrukturer och algoritmer för grafer och flöden som kortaste vägen, minsta uppspännande träd, maxflöde och minsta kostnadens maxflöde.