lu.se

Forskar­utbildnings­kurser

Lunds tekniska högskola | Lunds universitet

Detaljer för kursplan för kurs EDAN55F giltig från och med HT 2017

Utskriftsvänlig visning

Allmänt
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.
Innehå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.
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
Undervisningsformer
  • Föreläsningar
  • Laborationer
Examinationsformer
  • Skriftlig tentamen
  • Underkänd, godkänd
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)
Förutsatta förkunskaper
Urvalskriterier
Litteratur
  •  
  • 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.
Övrig information
Kurskod
  • EDAN55F
Administrativ information
  •  -03-22
  • Professor Thomas Johansson

Alla publicerade kurstillfällen för kursplanen

Inga matchande kurstillfällen hittades.

0 kurstillfällen.


Utskriftsvänlig visning