Stockholms universitet
Go to this page on our english site

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å

    Tentamensinformation

  • 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.

    Kurslitteraturlista Matematiska institutionen

  • Mer information

    Ny student
    Under utbildningen

    Kurshemsida

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

  • Kontakt