Detaljer för kursplan för kurs EDAN55F giltig från och med HT 2017 Utskriftsvänlig visning Kurskod:EDAN55F Gäller från och med:Höstterminen 2017 Kursplanen är fastställd Allmänt Undervisningsspråk:Svenska Ges:Varje hösttermin Kurshemsida:http://cs.lth.se/edan55 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 Betygsskala: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 Litteratur: Kommentarer: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 Kurskod:EDAN55F Administrativ information Datum för fastställande: -03-22 Beslutad av:Professor Thomas Johansson Alla publicerade kurstillfällen för kursplanen Inga matchande kurstillfällen hittades. 0 kurstillfällen. Utskriftsvänlig visning