Avancerede Datastrukturer

I kurset vil vi bygge videre på introducerende algoritme kurser. Vi vil fokusere på problemer der er målrettet mod anvendelser for massive data sæt. I 90'erne har en række gennembrudsresultater anvist nye avanceret tekniske muligheder, f.eks. at sortering kan gøres hurtigere end i $O(n \log n) tid. For de stadigt voksende datamængder man i dag er interesseret i at behandle, er det ofte mere og mere essentielt at udnytte sådanne avancerede teknikker til performanceforbedringer. Kurset vil præsentere helt nye forskningsresultater for problemstillinger i denne kontekst. Blandt anvendelserne for disse kan nævnes performance relaterede problemer for databaser/datawarehouses, konstruktion af dominanstræ for en "control flow graf", ruteteknikker, konstruktion af internet-søgemaskiner og DNA/RNA-sekvensanalyse. Blandt de mere klassiske algoritmiske problemstillinger, der vil kunne blive inddraget i kurset, er søgning i sublogatimisk tid, beregning af korteste vej i lineær tid, samt helt nye endnu ikke publicerede resultater for range searching. Kurset vil således præsentere algoritmiske "state of the art"-teknikker og give applikationer af disse.

Kurset henvender sig til ph.d.-studerende og kandidatstuderende som gerne vil stifte bekendtskab med den nyeste og mest aktuelle forskning i algoritmik og data strukturer.

Kursets målsætning

Målet med kurset er at du skal være fortrolig med både teoretisk og praktisk udfordrende problemstillinger i området. Du skal kunne tilegne dig ny forskning i området, samt lære at beherske og anvende flere af områdets nyeste teknikker og metoder.

Kurset giver dig et solidt grundlag for at udføre egen forskning inden for området.

Detaljeret indhold og målsætningkursusmål

Eksempler på emner vi kan gennemgå er Vi gennemgår emnerne med fokus på asymptotisk effektive løsninger. Fokus er således ikke lagt på implementering som i kurset Effektive algoritmer og programmer.

Forudsætninger

Introducerende kursus til algoritmik såsom Introduktion til algoritmik og data struktur på ITU eller DAT2P på DIKU. Det vil sige, at du er bekendt med emner som prioritetskøer, union-find, søgetræer, simple grafalgoritmer, sortering m.m.

Kursusform

Forelæsninger og seminarer, samt obligatoriske opgaver.

Evalueringsform

Bestået/dumpet på baggrund af stillede obligatoriske opgaver.

Lærer

Stephen Alstrup
Theis Rauhe
Samt gæsteforelæsere.