In English

DD2354 Algoritmer och komplexitet 6,0 hp

Algorithms and Complexity

En fortsättningskurs i datalogi med inriktning på algoritmer och komplexitet, mer teoretisk än DD1352.

  • Utbildningsnivå

    Avancerad nivå

  • Kursnivå (A-D)

    C

  • Huvudområde

    Informationsteknik

  • Betygsskala

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

Det finns inget planerat kurstillfälle.

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 med hänsyn till effektivitet och pålitlighet,
  • definiera begreppen P, NP, NP-fullständighet, PSPACE och oavgörbarhet,
  • jämföra problem med hänsyn till komplexitet med hjälp av reduktioner,

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. Algoritmanalys. Probabilistiska algoritmer. Approximation. Tillämpningar med algoritmer för problem på mängder, grafer, aritmetik och geometri.

Beräkningsbarhet och komplexitet: reduktionsbegreppet, komplexitetsklasserna P (polynomisk tid) och NP (ickedeterministisk polynomisk tid) och NC (effektivt parallelliserbara problem), NP-fullständiga problem, oavgörbara problem.

Behörighet

För fristående kursstuderande krävs 90 högskolepoäng varav 45 högskolepoäng inom matematik eller informationsteknik. Dessutom krävs engelska B eller motsvarande.

Litteratur

Meddelas senast 4 veckor före kursstart på kursens hemsida.

Examination

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

Mästarprov (MAS1; 1,5 hp och MAS2; 1,5 hp) en tentamen (TEN1; 3 hp).

Ges av

CSC/Datalogi

Kontaktperson

Johan Karlander, tel: 790 6340, e-post: johank@nada.kth.se

Examinator

Johan Karlander

Övrig information

Denna kurs har ersatts av DD2352.

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

Påbyggnad

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

Versionsinformation

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