Vær opmærksom på at dette website indeholder et arkiv med historiske data. Det aktuelle kursuskatalog findes på kursuskatalog.au.dk

AU kursuskatalog arkiv

[Forside] [Hovedområder] [Perioder] [Udannelser] [Alle kurser på en side]

Strengalgoritmer (Q4) ( 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: 27098

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

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

 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 (20 min)
7-skala, intern censur