Strengalgoritmer (Q2) ( efterår 2007 - 5 ECTS )
Rammer for udbud
-
Uddannelsessprog:
(se under Undervisnings- og arbejdsform)
-
Niveau:
Valgfrit overbygningskursus
-
Semester/kvarter:
Q2 i 2007
-
Timer per uge:
-
Deltagerbegrænsning:
-
Undervisningssted:
Århus
-
Hovedområde:
Det Naturvidenskabelige Fakultet
-
Udbud ID:
7990
Formål
Deltagerne vil efter kurset have indsigt i design og analyse af algoritmer og datastrukturer til analyse og indeksering af strenge og praktisk erfaring med implementation af disse algoritmer og datastrukturer. Kursets arbejdsform vil også træne deltagernes evne til at formidle og kommunikere faglige problemstillinger og til at læse og forstå videnskabelige artikler.
Obligatorisk program
Tre programmeringsprojekter
Indhold
Streng-algoritmer (dvs. algoritmer og datastrukturer til analyse og indeksering af strenge) er en vigtig del af mange datalogiske discipliner, som data-kompression, kryptografi, tale- og billedgenkendelse og bioinformatik. Strengalgoritmer er yderligere et interessant teoretisk område i sig selv, med mange spændende problemer med elegante løsninger. Dette kursus giver en introduktion til strengalgoritmer. Kurset gennemgår konkrete teknikker og strengalgoritmer og deres implementation og analyse: eksakt og approksimativ mønsterfinding; beregning af strengafstande; søgning efter strenggentagelser og periodisitet i strenge; konstruktion og anvendelser af suffix-træer og suffix-arrays.
Læringsmål
Deltagerne skal ved afslutningen af kurset kunne:
-
definere
og
beskrive
basale begreber relateret til strengalgoritmer,
-
beskrive
og
analysere
kendte algoritmer og datastrukturer til analyse og indeksering af strenge,
-
implementere
og
evaluere
strengalgoritmer baseret på kendte teknikker,
-
diskutere
brugen af kendte strengalgoritmer og teknikker til løsning af mere komplekse problemstillinger i forbindelse med analyse og indeksering af strenge.
Faglige forudsætninger
dADS1+2
Underviser
Thomas Mailund og Christian Nørgaard Storm Pedersen
Undervisnings- og arbejdsform
Forelæsninger (2+1 t/uge)
Litteratur
Udvalgte artikler og lærebog (Bill Smyth, Computing Patterns in Strings, Addison Wesley, 2003)
Litteratur
Selected papers and text book (Bill Smyth, Computing Patterns in Strings, Addison Wesley, 2003)
Kursushjemmeside
http://www.daimi.au.dk/~cstorm/courses/StrAlg
Udbyder
Datalogisk Institut
Tilmelding til undervisning
http://www.brics.dk/~mis/enrollment.html
Studieordning og bedømmelse
-
Mundtlig, bedømt efter 7-skala med intern censur
Mundtlig eksamen uden forberedelse (20 min)
7-skala, intern censur
