DD2350 Algoritmer, datastrukturer och komplexitet 9,5 hp

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.

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.

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.

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.

• 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.

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

• 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.

Frivilliga teoriuppgifter med kamratbedömning ger bonuspoäng till teoritentamen.

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ä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.

Viggo Kann

• 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 om kursen kan hittas på kurswebben via länken nedan. Information på kurswebben kommer framöver flyttas till denna sida.

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

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

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.