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
|