DD1352 Algoritmer, datastrukturer och komplexitet 9,0 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. 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.

Fackterminologi på svenska och engelska.

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,
• förklara hur man kan hantera problem med hög komplexitet

för 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.

För fristående kursstuderande: grundläggande högskolebehörighet samt 15 hp i matematik, inklusive diskret matematik och sannolikhetslära, och 12 hp datalogi eller programmeringsteknik.

Kleinberg-Tardos: Algorithm Design, 2005, Pearson, ISBN 978-0321372918 +

Algorithms and Complexity, a supplement to Algorithm Design, Pearson Custom Publishing, ISBN 978-1847764126.

• MAS2 - Mästarprov, 1,5 hp, betygsskala: A, B, C, D, E, FX, F
• MAS1 - Mästarprov, 1,5 hp, betygsskala: A, B, C, D, E, FX, F
• TEN2 - Tentamen, 3,0 hp, betygsskala: A, B, C, D, E, FX, F
• LAB1 - Laborationsuppgifter, 3,0 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.

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

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.

Slutbetyget är det lägsta av betygen på MAS1, MAS2 och TEN2.

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.

Kursen ersätts från 2017/2018 av den nya kursen DD2350 med samma kursnamn.

Endast en av följande kurser bör få räknas med i examen: 2D1352, 2D1353, 2D1354, DD1352, DD2350, DD2352, DD2354.