Algoritmer och komplexitet
Vad kostar en algoritm, räknat i tid och minne? Lär dig att jämföra alternativa algoritmer, konstruera datorprogram som effektivt utnyttjar tid och minne och att identifiera och angripa problem som är orealistiskt resurskrävande eller inte alls går att lösa med dator.
I denna kurs lär du dig utveckla, implementera och analysera algoritmer avseende korrekthet och effektivitet; definiera begreppen P, NP, NP-fullständighet, oavgörbarhet, m m, för att kunna identifiera/angripa orealistiskt resurskrävande/olösliga problem samt konstruera program som effektivt utnyttjar tid/minne.
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; randomiserade datastrukturer. 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.
-
Kursupplägg
Kursen består av tre moment; teori, individuella uppgift samt laborationer.
Undervisning
Undervisningen består av föreläsningar, övningar, och laborationer.
Examination
Kursen examineras genom ett skriftligt prov, skriftlig och muntlig redovisning av laborationer, och hemuppgift och muntlig redovisning av den individuella uppgiften.
Examinator
Lista över examinatorer finns på
-
Schema
Schema finns tillgängligt senast en månad före kursstart. Vi rekommenderar inte utskrift av scheman då vissa ändringar kan ske. Vid kursstart meddelar utbildningsansvarig institution var du hittar ditt schema under utbildningen. -
Kurslitteratur
Observera att kurslitteraturen kan ändras fram till två månader före kursstart.
Cormen, Leiserson, Rivest, and Stein: Introduction to algorithms.
-
Mer information
Kurshemsida
Vi använder inte Athena, utan du hittar kurshemsidan på kurser.math.su.se.
-
Kontakt
