Fagligt indhold: | I kurset vil vi bygge videre på de introducerende algoritmekurser. Vi vil fokusere på problemer der er målrettet mod anvendelser for massive datasæt. I 90'erne har en række gennembrudsresultater anvist nye avancerede 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 sub-logaritmisk 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.
|
Eksamensform og -beskrivelse: | X. experimental examination form (7-scale; external exam), 13-skala, Intern censur Bedoemmelse "bestaaet/ikke bestaaet" uden censur, baseret på aflevering og godkendelse af obligatoriske opgaver.
|