Avancerade algoritmer
Advanced Algorithms

EDAN55F, 7.5 högskolepoäng

Gäller från och med: Höstterminen 2017
Beslutad av: Professor Thomas Johansson
Datum för fastställande: 2017-03-22

Allmänna uppgifter

Avdelning: Datavetenskap (LTH)
Kurstyp: Gemensam kurs, avancerad nivå och forskarnivå
Kursen ges även på avancerad nivå med kurskod: EDAN55
Undervisningsspråk: Svenska

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 doktoranden

• känna till enkla randomiserade algoritmer och datastrukturer
• känna igen olika beräkningspardigm för att lösa "hårda" problem
• ha kunskap om moderna datastrukturer för stora datamängder
• kunna resonera kring olika modeller för beräkningar på stora datamängder

Färdighet och förmåga

För godkänd kurs skall doktoranden

• kunna analysera en randomiserad algoritm med avseende på både effektivitet och korrekthet med verktyg från diskret sannolikhetsteori
• kunna analysera svårigheten att approximera ett beräkningsmässigt svårhanterligt problem
• kunna implementera och testa lösningar till beräkningsmässigt svårhanterliga problem
• kunna implementera och testa effektiva datastrukturer för storskaliga problem

Värderingsförmåga och förhållningssätt

För godkänd kurs skall doktoranden

• kunna föreslå lämpliga och välmotiverade lösningar för beräkningsmässigt svårhanterliga problem
• kunna välja mella probabilistiska modeller för randomiserade beräkningar
• kunna bedöma om algoritmiska lösningar är genomförbara baserat både på experimentell och formell analys av deras effektivitet och giltighet
• kunna bedöma relevansen hos en algoritmisk lösning som presenteras i forskningslitteraturen

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.

Kurslitteratur

Kleinberg J, Tardos E: Algorithm Design. Addison-Wesley, 2005, ISBN: 0321295358. Delar av denna bok har använts i kursen EDAF05. Mitzenmacher M, Upfal E: Probability and Computing: Randomized Algorithms and Probabilistic Ananlysis. Cambridge University Press, 2005, ISBN: 0-521-83540-2. Hromkovic J: Algorithmics for Hard Problems. Springer, 2002, ISBN: 3-540-44134-4. Ett urval forskningspapper.

Kursens undervisningsformer

Undervisningsformer: Föreläsningar, laborationer

Kursens examination

Examinationsform: Skriftlig tentamen
Betygsskala: Underkänd, godkänd
Examinator:

Antagningsuppgifter

Förkunskapskrav: Godkänt betyg på kursen EDAA01 (Programmeringsteknik - fördjupningskurs) och godkänd på de obligatoriska momenten eller på tentamen i kurserna EDAF05 (Algoritmer, datastrukturer och komplexitet) och FMS012 (Matematisk statistik allmän kurs)

Kurstillfällesinformation

Kontaktinformation och övrigt

Kursansvariga:
Hemsida: http://cs.lth.se/edan55