Kursplan för

Avancerade algoritmer
Advanced Algorithms

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

Gäller för: Läsåret 2023/24
Fakultet: Lunds tekniska högskola
Beslutad av: Programledning C/D
Beslutsdatum: 2023-04-18

Allmänna uppgifter

Valfri för: C4-pv, D4-pv, E4, F4, 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: För godkänt betyg på kursen krävs fullgjorda obligatoriska moment (godkända laborationer och godkänd inlämningsuppgifter). Slutbetyget på kursen baseras på resultatet av den skriftliga tentamen.

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: Godkänd tentamen. Delmomentet omfattar: Skriftlig tentamen.
Kod: 0212. Benämning: Obligatoriska moment.
Antal högskolepoäng: 3. Betygsskala: UG. Prestationsbedömning: Godkända laborationer och godkänd inlämningsuppgifter. Delmomentet omfattar: Laborationer och inlämningsuppgifter.

Antagningsuppgifter

Förkunskapskrav:

Begränsat antal platser: Nej

Kurslitteratur

Kontaktinfo och övrigt

Kursansvarig: Susanna Rezende, susanna.rezende@cs.lth.se
Hemsida: http://cs.lth.se/edan55