DD2350 Algoritmer, datastrukturer och komplexitet 9,5 hp

Algorithms, Data Structures and Complexity

  • Utbildningsnivå

    Avancerad nivå
  • Huvudområde

    Datalogi och datateknik
  • Betygsskala

    A, B, C, D, E, FX, F

Kurstillfällen/kursomgångar

HT19 adk19 för programstuderande

HT18 adk18 för programstuderande

Lärandemål

Efter fullgjord 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.

Kursens huvudsakliga innehå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.

Behörighet

Programmering och datalogi motsvarande DD1338/DD1320/DD1321/DD1325/DD1327/DD1339/ID1020.

Rekommenderade förkunskaper

För vissa av kurserns labbar måste ett snabbare programspråk än Python användas, varför kunskaper i Java eller C/C++ rekommenderas. Diskret matematik motsvarande SF1671 och SF1688 eller någon av SF1630, SF1662, SF1679 (kan läsas parallellt). Sannolikhetsteori och statistik motsvarande SF1901. Logik motsvarande DD1350/DD1351 rekommenderas men är inte nödvändigt.

Litteratur

Meddelas senast 10 veckor före kursstart på kurswebben.

Examination

  • LAB1 - Laborationsuppgifter, 4,0, betygsskala: A, B, C, D, E, FX, F
  • MAS1 - Individuellt mästarprov, 1,5, betygsskala: A, B, C, D, E, FX, F
  • MAS2 - Individuellt mästarprov, 1,5, betygsskala: A, B, C, D, E, FX, F
  • TEN1 - Teoritentamen, 2,5, betygsskala: P, F

Om särskilda skäl finns kan annan examinationsform användas.
I denna kurs tillämpas skolans hederskodex, se: http://www.kth.se/csc/student/hederskodex

Ges av

EECS/Datavetenskap

Kontaktperson

Viggo Kann (viggo@kth.se)

Examinator

Viggo Kann <viggo@kth.se>

Övrig information

Betygskriterier meddelas vid kursstart.

Kursen har ersatt  DD1352.

DD2350 kan inte kombineras med DD1352, DD2352 eller DD2354.

Påbyggnad

DD2440 Avancerade algoritmer, DD2442 Seminariekurs i teoretisk datalogi, DD2445 Komplexitetsteori, DD2448 Kryptografins grunder, DD2458 Problemlösning och programmering under press.

Versionsinformation

Kursplan gäller från och med VT2019.
Examinationsinformation gäller från och med VT2019.