DM823: Strengalgoritmer (5 ECTS)

STADS: 15008001

Niveau
Kandidatkursus

Undervisningsperiode
Kurset er placeret i efterårssemesteret.
Kurset udbydes efter behov.

Ansvarlige undervisere
Email: rolf@imada.sdu.dk

Skemaoplysninger
Der er ingen skemaoplysninger for den valgte periode.

Kommentar:
Ubegrænset deltagerantal. Kurset kører i 1. kvartal.

Indgangskrav:
Ingen

Faglige forudsætninger:
Stoffet fra DM507 Algoritmer og datastrukturer og DM508 Algoritmer og komleksitet antages kendt.

Kursusintroduktion
Data bestående helt eller delvist af strenge forekommer ofte: I næsten alle databaseapplikationer er strenge blandt de anvendte datatyper, og for nogle områder, såsom tekstbehandling, bioinformatik og websøgning, er strenge helt centrale. Derudover udgør strenge en generisk og fundamental datamodel i datalogi, der indeholder både heltal og multidimensionale data som specialtilfælde.

I dette kursus gennemgås en række af de mere avancerede algoritmer og data strukturer for fundamentale beregningsproblemer på strenge.

Forventet læringsudbytte
Ved kursets afslutning forventes den studerende at kunne:

- Gengive algoritmer og datastrukturer gennemgået i kurset.
- Anvende præcist sprog og notation under udførelsen af ovenstående.
- Implementere algoritmer og datastrukturer gennemgået i kurset.
- Udføre eksperimenter med disse implementationer, samt reflektere over resultaterne heraf.
- Beskrive disse implementationer og det udførte eksperimentelle arbejde i et klart og præcist sprog, og på en struktureret måde.

Emneoversigt
Pattern matching, eksakt og approksimativ. Suffixtræer, suffixarrays og andre datastrukturer for strenge. Sortering af strenge. Komprimeringsalgoritmer. Algoritmer for afstandsmål på strenge.

Litteratur

Meddeles ved kursets start.

Pensum
Se pensumbeskrivelse.

Kursets hjemmeside
Dette kursus benytter e-learn (blackboard).

Forudsætningsprøver
Ingen

Eksamen- og censurform:
(a) Projektopgave der bedømmes med bestået/ikke bestået ved intern censur ved underviser. (15008012)
(b) Mundtlig eksamen der bedømmes efter 7-trins skalaen ved ekstern censur. (15008002)

Det er en forudsætning for at kunne gå til den mundtlige eksamen at projektet er bestået.

Tidsplacering af reeksamen fremgår af læseplanen.

Vejledende timetal
På naturvidenskab er undervisningen tilrettelagt efter trefasemodellen dvs. intro, trænings- og studiefasen.

Forelæsninger: 28 timer
Aktiviteter i studiefasen

Sprog
Dette kursus undervises på dansk eller engelsk, afhængigt af underviseren. Dog altid på Engelsk ved deltagelse af internationale studerende.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Denne kursusbeskrivelse var gyldig fra 1. september 2010 til 31. august 2013.