AU kursuskatalog arkiv

Strengalgoritmer (Q3) ( forår 2009 - 5 ECTS )

Rammer for udbud

• Uddannelsessprog: engelsk (eller dansk)
• Niveau: Kandidatkursus
• Semester/kvarter: Q3
• Timer per uge: 3
• Deltagerbegrænsning: Ingen
• Undervisningssted: Århus
• Hovedområde: Det Naturvidenskabelige Fakultet
• Udbud ID: 8004

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 data-strukturer. 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 billed-genkendelse og bioinformatik. Streng-algoritmer 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 streng-algoritmer. Kurset gennemgår konkrete teknikker og streng-algoritmer og deres implementation og analyse: eksakt og approksimativ mønster-finding; beregning af streng-afstande; søgning efter streng-gentagelser 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

Algoritmer og Datastrukturer 1+2

Underviser

Thomas Mailund og Christian Nørgaard Storm Pedersen

Undervisnings- og arbejdsform

Forelæsninger (2+1t/uge)

Litteratur

Udvalgte artikler og lærebog (Bill Smyth, Computing Patterns in Strings, Addison Wesley, 2003)

Kursushjemmeside

http://www.daimi.au.dk/~cstorm/courses/StrAlg

Eksamensterminer

Marts/april, reeksamen august

Udbyder

Datalogisk Institut & Center for Bioinformatik

Tilmelding til undervisning

http://www.brics.dk/~mis/enrollment.html

Bedømmelse

Mundtlig eksamen uden forberedelse (20 min)
7-skala, intern censur