AU kursuskatalog arkiv

Strengalgoritmer (Q4) honours ( forår 2011 - 5 ECTS )

Rammer for udbud

• Uddannelsessprog: engelsk
• Niveau: Kandidatkursus
• Semester/kvarter: Q4
• Timer per uge: 3
• Deltagerbegrænsning: Ingen
• Undervisningssted: Århus
• Hovedområde: Det Naturvidenskabelige Fakultet
• Udbud ID: 27489

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. Endvidere vil deltagerne efter kurset kunne reflektere over algoritmiske løsninger i aktuelle problemstillinger relateret til analyse og indeksering af strenge samt have erfaring med generalisering af disse til selvstændige algoritmiske problemer. 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 samt fremlæggelse af aktuel forskningsartikel.

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.

De obligatoriske projekter vil omfatte generaliseringer af kendte metoder samt krav til reflektion over disses anvendelighed og egenskaber.

Faglige forudsætninger

Algorithms and Datastructures 1+2

Underviser

Thomas Mailund og Christian Nørgaard Storm Pedersen

Undervisnings- og arbejdsform

Forelæsninger (2+1t/uge)

Engelsk (eller dansk)

Litteratur

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

Kursushjemmeside

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

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.
• reflektere over brugen af algoritmiske løsninger i aktuelle problemstillinger relateret til analyse og indeksering af strenge.
• generalisere brugen af algoritmiske løsninger i aktuelle problemstillinger relateret til analyse og indeksering af strenge til selvstændige algoritmiske problemer.

Skemaplacering (forelæsninger)

http://cs.au.dk/studies/computer-science-programme/schedules/  

Eksamensterminer

Juni/juli, reeksamen foregår efter aftale med underviseren

Udbyder

Datalogisk Institut & Center for Bioinformatik

Tilmelding til undervisning

http://mit.au.dk

Bedømmelse

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