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.

God färdighet i programmering (motsvarande DD1337/DD1310-1319/DD1331/DD1332/ID1018). 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++.

Begrepp från algoritmer och datastrukturer (motsvarande DD1338/DD1320-DD1328/ID1021) som algoritmanalys, ordoklasser, pseudokod, motivering av algoritmer, algoritmer för sökning och sortering, datastrukturer: listor, köer, stackar, mängder, binärträd, prioritetsköer, hashtabeller.

Begrepp från sannolikhetsteori (motsvarande SF1900-SF1935) som sannolikhet, betingad sannolikhet, oberoende, väntevärde.

Begrepp från logik (motsvarande DD1351) som satslogik, induktion och programverifiering.

Begrepp från algebra och geometri (motsvarande SF1624) som vektorer, matriser, linjära ekvationssystem, vektorgeometri med skalärprodukt och vektorprodukt.

Begrepp från envariabelanalys (motsvarande SF1625) som funktioner, definitionsmängd, värdemängd, växande och avtagande funktioner, exponentialfunktioner och logaritmer, potenslagar, logaritmlagar, gränsvärden, l'Hôpitals regel, talföljder och serier.

Begrepp från diskret matematik som mängder, induktion, rekursionsekvationer, talbaser, delbarhet, Euklides algoritm, primtal, entydig faktorisering, modulär aritmetik, grafer, eulerkretsar, hamiltoncykler, träd, graffärgning, bipartita grafer, permutationer, ringar. 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.

Betyget på LAB1 beror på hur många datorlabbar som redovisas muntligt inom angiven tid.

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

Frivilliga teoriuppgifter med kamratbedömning ger bonuspoäng till teoritentamen. 
Teoritentamen genomförs som ett digitalt quiz med efterföljande kamraträttning.

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.

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

Information inför kursstart.

Information om redovisning av rester i kursen.

Betygskriterier meddelas vid kursstart.

DD2350 kan inte kombineras med DD1352, DD2352 eller DD2354 i samma examen.

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.