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.

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å

Tentamensinformation

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.


Observera att kurslitteraturen kan ändras fram till två månader före kursstart.

Cormen, Leiserson, Rivest, and Stein: Introduction to algorithms.

Kurslitteraturlista Matematiska institutionen

Kursrapporter visas för de tre senaste kurstillfällena.

Ny student
Under utbildningen

Kurshemsida

Vi använder inte Athena, utan du hittar kurshemsidan på kurser.math.su.se.