DD1352 Algoritmer, datastrukturer och komplexitet 9,0 hp

Algorithms, Data Structures and Complexity

OBS!

Detta är en nedlagd kurs.

En fortsättningskurs i datalogi med inriktning på algoritmer, datastrukturer och komplexitet. Samma kursinnehåll som DD2352 men med större laborationsdel.

  • Utbildningsnivå

    Grundnivå
  • Huvudområde

    Informationsteknik
    Teknik
  • Betygsskala

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

Sista planerade examination: HT19.

Det finns inget planerat kurstillfälle.

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

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.

Fackterminologi på svenska och engelska.

Behörighet

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.

Rekommenderade förkunskaper

Motsvarande kurserna DD1339/DD1340/DD1341 Introduktion till datalogi (alternativt DD1320/DD13321 eller DD1345), SF1630/SF1631 Diskret matematik (kan läsas parallellt), samt SF1901 Sannolikhetsteori och statistik.

Litteratur

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

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

Examination

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

Krav för slutbetyg

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

Ges av

CSC/Teoretisk datalogi

Kontaktperson

Viggo Kann, tel: 790 6292, e-post: viggo@kth.se

Examinator

Viggo Kann <viggo@kth.se>

Övrig information

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.

Påbyggnad

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

Versionsinformation

Kursplan gäller från och med HT2016.
Examinationsinformation gäller från och med HT2007.