Kursplan för

Avancerade algoritmer
Advanced Algorithms

EDAN55, 7,5 högskolepoäng, A (Avancerad nivå)

Gäller för: Läsåret 2017/18
Beslutad av: Programledning C/D
Beslutsdatum: 2017-04-03

Allmänna uppgifter

Valfri för: C5-pv, D4-pv, E4-pv, F4, F4-pv, F4-bs, Pi4-bs, Pi4-pv
Undervisningsspråk: Kursen ges på engelska

Syfte

Algoritmer spelar en viktig roll inom datavetenskap och andra ingenjörsvetenskaper. De ingår redan i många grundkurser inom naturvetenskap och teknik. Denna avancerade kurs behandlar ett antal nya områden utöver vad som ingår i grundkurser.

Randomisering spelar en viktig roll i många avseenden för algoritmer och datastrukturer.  Detta inkluderar basala lösningar såsom hashtabeller eller quicksort, som ingår i de standardbibliotek som alla programmerare använder. En stor del av internet, från routingtabeller till storskaliga bolag som Google, är helt beroende av randomisering.  Även om idéerna är enkla, effektiva och användbara så behandlas de vanligen inte i grundkurser eftersom studenterna där saknar de förkunskaper i diskret sannolikhetsteori som behövs.

Ett stort antal problem är beräkningsmässigt svårhanterliga i den mening att de klassas som svåra i komplexitetsklasserna NP och #P. Trots detta måste de lösas. Kursen presenterar design- och analystekniker, utöver de som ingår i grundkurser, för att hantera dessa problem såsom approximativa algoritmer, exponentiella algoritmer, parametriserad komplexitet, heuristisk och randomiserade lösningar.

Många algoritmiska lösningar måste bedömas i förhållande till de massiva datamängder som hanteras inom många tillämpningsområden, såsom Googles stora databaser och  vetenskaper i informationsåldern. När instanserna växer i storlek till att omfatta mega- eller gigabytes måste basala datastrukturer och lagringstekniker omprövas. Detta ger upphov till nya frågor där randomisering ofta spelar en stor roll för lösningarna.

Många av de områden som ingår i kursen är aktuella och aktiva forskningsområden. Kursen befinner sig därmed vid forskningsfronten för algoritmteori och kan därför vara en lämplig grund för dem som vill göra examensarbete eller påbörja forskarstudier inom området.

 

Mål

Kunskap och förståelse
För godkänd kurs skall studenten

 

 

Färdighet och förmåga
För godkänd kurs skall studenten

 

 

Värderingsförmåga och förhållningssätt
För godkänd kurs skall studenten

 

 

Kursinnehåll

Parametriserade algoritmer och komplexitet. Design, tillämpningar och analys av randomiserade algoritmer; hashfunktioner, randomiserade datastrukturer, markovkedjor och random walks, chernoffgränser, villkorliga sannolikhetsmetoder, probabilistisk metodik, bollar och lådor. Approximativa algoritmer. Modeller och datastrukturer för mycket stora datamängder.

Kursens examination

Betygsskala: TH - (U,3,4,5) - (Underkänd, Tre, Fyra, Fem)
Prestationsbedömning: Slutbetyg på kursen baseras på resultatet av den skriftliga tentamen. För godkänt betyg på kursen krävs dessutom fullgjorda obligatoriska moment.

Om så krävs för att en student med varaktig funktionsnedsättning ska ges ett likvärdigt examinationsalternativ jämfört med en student utan funktionsnedsättning, så kan examinator efter samråd med universitetets avdelning för pedagogiskt stöd fatta beslut om alternativ examinationsform för berörd student.

Delmoment
Kod: 0112. Benämning: Tentamen.
Antal högskolepoäng: 4,5. Betygsskala: TH. Prestationsbedömning: Slutbetyg på hela kursen baseras på resultatet av den skriftliga tentamen. Delmomentet omfattar: Skriftlig tentamen.
Kod: 0212. Benämning: Obligatoriska moment.
Antal högskolepoäng: 3. Betygsskala: UG. Prestationsbedömning: För godkänt krävs fullgjorda laborationer och inlämningsuppgift. Delmomentet omfattar: Laborationer och inlämningsuppgift.

Antagningsuppgifter

Förkunskapskrav:

Begränsat antal platser: Nej

Kurslitteratur

Kontaktinfo och övrigt

Kursansvarig: Professor Thore Husfeldt, Thore.Husfeldt@cs.lth.se
Hemsida: http://cs.lth.se/edan55