2D1354 Algoritmer och komplexitet, 4 poäng
2D1354 Algoritmer och komplexitet, 4 poäng


Mål
Kursens mål är att
  • ge grundlig förmåga att utveckla algoritmer och analysera dem med avseende på korrekthet och effektivitet
  • ge orientering om komplexitetsteori
för att eleverna ska
  • kunna konstruera datorprogram som effektivt utnyttjar datorresurser,
  • inse att de finns problem som är orealistiskt resurskrävande eller inte alls går att lösa med dator.

Förkunskaper
Motsvarande kurserna 2D1340 (eller 2D1341) Introduktion till datalogi, 5B1103 Differential- och integralkalkyl II och 5B1302 Algebra och kombinatorik.

Kursinnehåll
Konstruktionsprinciper för algoritmer: dekompo-sition, giriga algoritmer, dynamisk programmering. Algoritmanalys. Probalistiska algoritmer. Approximation. Tillämpningar med algoritmer för problem på mängder, grafer, aritmetik och geometri.
Beräkningsbarhet och komplexitet: reduktions-begreppet, komplexitetsklasserna P (polynomisk tid) och NP (ickedeterministisk polynomisk tid) och NC (effektivt parallelliserbara problem), NP-fullständiga problem, oavgörbara problem.

Kursuppläggning
Föreläsningar 30 h period 1,2
Övningar 18 h period 1,2

Kursfordringar
En skriftlig tentamen (TEN1; 4 p)
Betygsskala: 3,4,5