Innehåll och lärandemål

Kursinnehåll och lärandemål från kursplanen för DD2350 Algoritmer, datastrukturer och komplexitet.

Kursinnehåll

Konstruktionsprinciper för algoritmer: Dekomposition, giriga algoritmer, dynamisk programmering, lokal och total sökning. Algoritmanalys. Approximationsalgoritmer och heuristiker. Tillämpningar med algoritmer för problem på mängder, grafer, aritmetik och geometri. Implementation av algoritmer.

Datastrukturer: Repetition av hashtabeller och heapar; balanserade träd, bloomfilter. Användning och implementation av datastrukturer. Beräkningsbarhet och komplexitet: Reduktionsbegreppet, komplexitetsklasserna P (polynomisk tid) och NP (ickedeterministisk polynomisk tid). NP-fullständiga problem, oavgörbara problem. Hur man kan hantera problem med hög komplexitet. Ämnesterminologin på svenska och engelska.

Lärandemål

Efter godkänd kurs ska studenten kunna

• utveckla och implementera algoritmer med datastrukturer och analysera dem med avseende på korrekthet och effektivitet,
• jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet,
• definiera och översätta centrala begrepp som P, NP, NP-fullständighet och oavgörbarhet,
• jämföra problem med hänsyn till komplexitet med hjälp av reduktioner,
• hantera problem med hög komplexitet

i syfte att

• självständigt kunna konstruera datorprogram som effektivt utnyttjar tid och minne,
• i yrkeslivet kunna identifiera och angripa problem som är orealistiskt resurskrävande eller inte alls går att lösa med dator.

Kopplingar till examensmål

ADK-kursen bidrar till att följande mål för civilingenjörsexamen uppfylls:

• visa kunskap om det valda teknikområdets (datatekniks) vetenskapliga grund och beprövade erfarenhet
  (Kursens område utgör själva kärnan i datalogins vetenskapliga grund. Både teoretiskt sett optimala algoritmer och datastrukturer och erfarenhetsmässigt goda sådana behandlas i kursen.)
• visa brett kunnande inom det valda teknikområdet (datateknik), inbegripet kunskaper i matematik och naturvetenskap, som väsentligt fördjupade kunskaper inom vissa delar av området
  (Kursen är på avancerad nivå och bygger vidare på flera tidigare kurser i matematik och datalogi. Den ger fördjupade kunskaper inom teoretisk datalogi och algoritmkonstruktion.)
• självständigt identifiera, formulera och hantera komplexa frågeställningar
  (Matematisk modellering och konstruktion av heuristiker för hantering av svåra problem examineras i kursen.)
• skapa, analysera och kritiskt utvärdera olika tekniska lösningar
  (Analys av komplexitet och korrekthet för algoritmer är centralt i kursen.)
• planera och med adekvata metoder genomföra kvalificerade uppgifter inom givna ramar
  (Individuell självständighet i kreativ problemlösning - expertsituationen - visas i mästarproven. Den teoretiska grunden och verktyg för bedömning av problems komplexitet ges och examineras.)

• muntligt och skriftligt klart redogöra för och diskutera sina slutsatser och den kunskap och de argument som ligger till grund för dessa
  (Labbar redovisas med programkod och muntligt i par. Mästarproven redovisas med skriftlig rapporter och muntligt individuellt. Förmågan att förklara och genomföra matematiska resonemang, vilket är ett explicit programmål för datateknikprogrammet, examineras vid mästarproven. Ämnesterminologin på både svenska och engelska examineras.)
• visa insikt i teknikens möjligheter och begränsningar
  (I kursen behandlas NP-­svåra och oavgörbara problem och studenterna övar på att visa att problem är svåra och att finna metoder att ändå hantera dessa problem med dagens teknik.)

Undervisningsspråk

Svenska. Kursböckerna är på engelska. Använd listan med nyckelbegrepp för att se vilka svenska och engelska termer som motsvarar varandra.