Hoppa till huvudinnehållet

DD2350 Algoritmer, datastrukturer och komplexitet 9,5 hp

Denna kurs ger en introduktion till teoretisk datalogi som är ett starkt forskningsområde på KTH. Du kommer att stöta på några av våra forskningsresultat i kursen.

Du får lära dig mer om algoritmkonstruktion och får se några ganska komplicerade, men mycket användbara, algoritmer. Komplexitetsdelen av kursen handlar om hur man undersöker vilka problem som kan lösas (i rimlig tid) med datorns hjälp, vilka som tar orimligt lång tid och vilka som inte kan lösas med en dator över huvud taget.

Problem som är för svåra för att lösa exakt kan ibland lösas approximativt. Du kommer att få se exempel på några approximationsalgoritmer och några problem som är så svåra att dom inte ens kan approximeras i rimlig tid.

Välj termin och kursomgång

Välj termin och kursomgång för att se information från rätt kursplan och kursomgång.

Rubriker med innehåll från kursplan DD2350 (HT 2022–) är markerade med en asterisk ( )

Innehåll och lärandemål

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, beständiga datastrukturer. 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 och därmed kan bidra till ekonomiskt och miljömässigt hållbar utveckling
  • i yrkeslivet kunna identifiera och angripa problem som är orealistiskt resurskrävande eller inte alls går att lösa med dator.

Kursupplägg

Ingen information tillagd

Kurslitteratur och förberedelser

Särskild behörighet

Kunskaper och färdigheter i programmering, 6 hp, motsvarande slutförd kurs DD1337/DD1310-DD1318/DD1321/DD1331/DD100N/ID1018.

Kunskaper i grundläggande datalogi, 6 hp, motsvarande slutförd kurs DD1338/DD1320-DD1327/DD2325/ID1020/ID1021.

Kunskaper i diskret matematik, 3 hp, motsvarande slutförd kurs SF1671/SF1610/SF1630/SF1662/SF1679.

Kunskaper i algebra och geometri, 7,5 hp, motsvarande slutförd kurs SF1624/SF1672.

Kunskaper i envariabelanalys, 7,5 hp, motsvarande slutförd kurs SF1625/SF1673.

Aktivt deltagande i kursomgång vars slutexamination ännu inte är Ladokrapporterad jämställs med slutförd kurs.
Den som är registrerad anses vara aktivt deltagande.
Med slutexamination avses både ordinarie examination och det första omexaminationstillfället.

Rekommenderade förkunskaper

För labb 2 behövs vissa kunskaper i Javaprogrammering. För några av kursens labbar behöver ett snabbare programspråk än Python användas, till exempel Java eller C/C++.

Sannolikhetsteori och statistik motsvarande SF1901 rekommenderas. Logik motsvarande DD1350/DD1351 rekommenderas men är inte nödvändigt.

Kunskaper i diskret matematik är nödvändigt. Den som vid kursstart inte har slutfört 7,5 hp diskret matematik motsvarande SF1610/SF1630/SF1662/SF1679 måste läsa SF1688 parallellt med DD2350, se under övriga föreskrifter i kursplanen.

Utrustning

Ingen information tillagd

Kurslitteratur

  • Algorithm Design av Kleinberg-Tardos, Pearson, 2014, ISBN 978-1292023946.

  • Det specialtryckta supplementet Algorithms and Complexity, a supplement to Algorithm Design, Pearson Custom Publishing, ISBN 978-1847764126. Säljs bara på kårbokhandeln.

Examination och slutförande

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

Betygsskala

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

Examination

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

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

Mästarproven utgörs av individuella uppgifter som redovisas både skriftligt och muntligt.

Möjlighet till komplettering

Betyget Fx kan kompletteras till E/godkänt för momenten MAS1, MAS2 och TEN1. Enskilda laborationer kan tillgodoräknas senare kursomgångar så länge laborationsuppgiften är oförändrad.

Möjlighet till plussning

Mästarprovsbetygen (MAS1 och MAS2) kan plussas i en senare kursomgång. Det är också tillåtet att plussa betyget på LAB1 från C eller B med den betygshöjande labben i en senare kursomgång. Däremot går det inte att få nya labbleveranspoäng i en senare kursomgång.

Examinator

Etiskt förhållningssätt

  • Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
  • Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
  • Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.

Ytterligare information

Kurswebb

Ytterligare information om kursen kan hittas på kurswebben via länken nedan. Information på kurswebben kommer framöver flyttas till denna sida.

Kurswebb DD2350

Ges av

Huvudområde

Datalogi och datateknik

Utbildningsnivå

Avancerad nivå

Påbyggnad

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

Kontaktperson

Viggo Kann (viggo@kth.se)

Övrig information

Betygskriterier meddelas vid kursstart.

Kursen har ersatt DD1352. DD2350 kan inte kombineras med DD1352, DD2352 eller DD2354.

I denna kurs tillämpas EECS hederskodex, se:
http://www.kth.se/eecs/utbildning/hederskodex

Övriga föreskrifter

Den som vid kursstart inte har slutfört 7,5 hp diskret matematik motsvarande SF1610/SF1630/SF1662/SF1679 måste läsa SF1688 parallellt med DD2350.