Algoritmisk problemlösning: Sökning och dynamisk programmering

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å sökning och dynamisk programmering. 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 sökning och dynamisk programmering.
• Att kunna implementera algoritmer och datastrukturer relevanta för sökning och dynamisk programmering.
• Att kunna lösa algoritmiska problem kopplade till sökning och dynamisk programmering.
• Att analysera effektiviteten hos olika möjliga lösningar på ett algoritmiskt problem, med fokus på sökning och dynamisk programmering, 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 sökning och dynamisk programmering, 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 tar upp sökning och dynamisk programmering som är två generella metoder för att lösa algoritmiska problem. Många optimerings- och strängalgoritmer bygger på dynamisk programmering som kappsäcksproblemet och strängmatchning. Sökmetoder som tas upp innefattar binärsökning, djupet först, bredden först, A* och heuristisk sökning.