Stockholms universitet logo, länk till startsida
Go to this page on our english site

Algoritmer och komplexitet

  • 7,5 hp

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.

Förkunskapskrav

De kurser som nämns under Särskild behörighet är gamla kursversioner, och motsvarar de nuvarande kurserna DA3018 Datalogi för matematiker och MM5023 Matematik III - Kombinatorik.

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 fyra moment; teori, två individuella uppgifter samt laborationer.

    Undervisning

    Undervisningen består av föreläsningar, övningar, och laborationer.

    Examination

    Kursen examineras genom ett skriftligt och muntligt prov, och muntlig och skriftlig redovisning av laborationer och de individuella uppgifterna. För godkänt betyg på kursen krävs att du är godkänd på alla fyra momenten.

    Examinator

    Lista över examinatorer finns på

    Kurser på grund- och avancerad nivå

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

    Kurslitteratur Matematiska institutionen

  • Mer information

    Se tider för webbregistrering och annat viktigt på

    Aktuell information för studenter

    Kurshemsida

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

  • Kontakt