Y-sektionens studienämnd är ansvariga för att informationen på guiden är aktuell. Om du hittar någonting som inte stämmer kan du mejla SNY.

Budgetår

Institution

IDA

Examinator

Peter Jonsson

Schemablock

Halvtermin
VT1: block 3

Huvudområden

Datateknik
Datavetenskap
Informationsteknologi

Nivå

A1N

Tidsfördelning

6,0HP
Schemalagd tid: 30 timmar
Självstudietid: 130 timmar

Innehåll

Kursens innehåll består av tre huvuddelar:

  • Del 1: Grundläggande tekniker. Giriga algoritmer, dekomposition och dynamisk programmering.
  • Del 2: NP-fullständighet. Teorin för NP-fullständighet och dess konsekvenser.
  • Del 3: Inexakta metoder. Konstruktion och analys av approximationsalgoritmer och randomiserade algoritmer.

Mål

Kursen syftar till att studenterna ska förvärva fördjupade kunskaper om tekniker för att konstruera och analysera algoritmer. Efter avslutad kurs ska studenterna kunna:

  1. konstruera algoritmer för ett givet beräkningsproblem,
  2. bevisa korrekthet för en given algoritm och
  3. analysera och värdera algoritmer för ett givet beräkningsproblem

 

Examinationsmoment

TEN1 - 6,0 HP
Skriftlig tentamen (U, 3, 4, 5)

Organisation

Under föreläsningarna presenteras teorin och exempel ges på hur olika problem kan lösas algoritmiskt. Dessutom ges möjligheter för studenterna att öva på konstruktion och analys av algoritmer.

Litteratur

Böcker

  • Cormen, T.H., Leiserson, C.E., Rivest, R.L. och Stein, C., Introduction to Algorithms Second or Third Edition The MIT Press.

Relaterade profiler

Teoretisk datalogi
TDL - IDA

Kommentarer

Logga in för att kunna läsa och skriva kommentarer.