In English

DD1352 Algoritmer, datastrukturer och komplexitet 9,0 hp

Algorithms, Data Structures and Complexity

En fortsättningskurs i datalogi med inriktning på algoritmer, datastrukturer och komplexitet. Mindre teoretiskt inriktad än DD2352.

  • Utbildningsnivå

    Grundnivå

  • Kursnivå (A-D)

    C

  • Huvudområde

    Informationsteknik
    Teknik

  • Betygsskala

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

Kurstillfällen/kursomgångar

HT12 adk12 för programstuderande

HT13 adk13 för programstuderande

Lärandemål

Efter kursen 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 begreppen 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. Approximation, algoritmer 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.

Behörighet

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

Rekommenderade förkunskaper

För KTH-studerande: 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, ISBN978-0321372918 +

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

Examination

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

I denna kurs tillämpas skolans hederskodex, se: http://www.kth.se/csc/student/hederskodex.

Krav för slutbetyg

Tentamen (TEN2; 3 hp).
Laborationsuppgifter (LAB1; 3 hp).
Mästarprov (MAS1; 1,5 hp) och (MAS2; 1,5 hp).

Ges av

CSC/Datalogi

Kontaktperson

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

Examinator

Viggo Kann <viggo@kth.se>

Övrig information

Betygskriterier meddelas vid kursstart.

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

Påbyggnad

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

Versionsinformation

Kursplan giltig från och med HT12.
Examinationsinformation giltig från och med HT07.