DD2352 Algoritmer och komplexitet 7,5 hp

Algorithms and Complexity

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

  • Utbildningsnivå

    Avancerad nivå
  • Huvudområde

    Datalogi och datateknik
  • Betygsskala

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

Kurstillfällen/kursomgångar

VT19 algkomp19 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 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ö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. 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:

SF1604 Linjär Algebra, SF1625 Envaiabelanalys, DD1337 Programmering, DD1338 Algoritmer och Datastrukturer, SF1630 Diskret Matematik och SF1901 Sannolikhetsteori och statistik eller motsvarande kurser.

Rekommenderade förkunskaper

Motsvarande kurserna DD1344/DD1345 Grundläggande datalogi (alternativt DD1320/DD1321 Tillämpad datalogi), SF2736/SF1610/SF1631 Diskret matematik och SF1901 Sannolikhetslära och statistik I.

Litteratur

Kurslitteratur meddelas senast 4 veckor innan kursstart på kursens hemsida.

Examination

  • LAB1 - Laborationer, 1,5, 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
  • TEN1 - Tentamen, 3,0, betygsskala: A, B, C, D, E, FX, F

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

Ges av

EECS/Datavetenskap

Kontaktperson

Johan Karlander, e-post: karlan@kth.se

Examinator

Johan Karlander <karlan@kth.se>

Övrig information

Denna kurs har ersatt DD2354 Algoritmer och komplexitet.

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

Påbyggnad

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

Versionsinformation

Kursplan gäller från och med VT2019.
Examinationsinformation gäller från och med VT2019.