DM823: Strengalgoritmer (5 ECTS)

STADS: 15014301

Niveau
Kandidatkursus forhåndsgodkendt som PhD-kursus

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.

Kommentar:
Ubegrænset deltagerantal.

Indgangskrav:
Ingen.

Faglige forudsætninger:
Studerende, der følger kurset, forventes at:

• Have kendskab til metoder til design, korrekthedsanalyse og tidsanalyse af algoritmer, svarende til kurset DM507 Algoritmer og Datastrukturer.
• Kunne anvende disse metoder med en sikkerhed og på et abstraktionsniveau svarende til en bachelorgrad i datalogi.

Formål
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.

Formålet med kurset er at give den studerende kendskab til en række algoritmer og datastrukturer for beregningsproblemer på strenge, og gøre den studerende i stand til at anvende disse eller varianter heraf, hvilket er vigtigt i sammenhænge hvor data på strengform indgår.

Kurset bygger oven på den viden, der er erhvervet i kurset DM507 Algoritmer og datastrukturer, samt andre algoritmiske kurser i bachelorstudiet i datalogi, og giver kompetencer til specialeskrivning inden for området.

I forhold til uddannelsens kompetenceprofil har kurset eksplicit fokus på at:

• Give viden om et udvalg af specialiserede modeller og metoder udviklet inden for datalogi baseret på højeste internationale forskning, samt viden om datalogiske modeller og metoder beregnet til anvendelser i andre faglige områder.
• Give færdigheder i at beskrive, analysere og løse datalogiske problemstillinger ved hjælp af de lærte modeller, analysere fordele og ulemper ved forskellige datalogiske metoder, samt udvikle nye varianter af de lærte metoder, hvor det konkrete problem kræver det.
• Give kompetence til planlægge og udføre videnskabelige projekter på højt fagligt niveau.

Målbeskrivelse
For at opnå kursets formål er det læringsmålet for kurset, at den studerende demonstrerer evnen til at:

• Gøre rede for funktionaliteten og korrektheden af de gennemgåede algoritmer og datastrukturer.
• Analysere de gennemgåede algoritmer og datastrukturer mht. tids- og pladskompleksitet.
• Designe effektive algoritmer og datastrukturer for varianter af de belyste problemstillinger.
• 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.

Indhold
Kurset indeholder følgende faglige hovedområder:

• 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.

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

Forudsætningsprøver
Projektopgave. Bestået/ikke-bestået, intern bedømmelse ved underviser.

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

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

Aktiviteter i studiefasen

Undervisningsform
Aktiviteter i studiefasen: Projektopgave.

Sprog
Dette kursus undervises på engelsk, hvis der deltager internationale studerende, ellers undervises på dansk.

Kursustilmelding
Se tilmeldingsfrister.

Pris for åben uddannelse
Se priser for enkeltkurser.

Dette er den nyeste version af en kursusbeskrivelse, som trådte i kraft den 1. sep 2016.