DM823: Strengalgoritmer (5 ECTS)

STADS: 15014301

Niveau
Kandidatkursus

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

Ansvarlige undervisere
Email: rolf@imada.sdu.dk

Skemaoplysninger
Vis hele skemaet
Vis personligt skema for dette kursus.

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
Der er i øjeblikket ikke angivet nogle materialer for kurset.

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

Forudsætningsprøver
Projektopgave. Det er en forudsætning for at kunne gå til den mundtlige eksamen at projektet er bestået.

Eksamen- og censurform:
Mundtlig eksamen der bedømmes efter 7-trins skalaen ved ekstern censur. (15008002)

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 2013 til 31. august 2016.