Algoritmer og datastrukturer 2

Algoritmer og Datastrukturer  2

 

Målbeskrivelse

Målet med kurset er at introducere den studerende til generelle designteknikker til konstruktion af effektive algoritmiske løsninger til kombinatoriske problemstillinger, samt at gøre den studerende bekendt med effektive løsninger til vigtige graf- og strengproblemer.

Indholdsbeskrivelse

· Algoritmeparadigmer
Del-og-kombiner, dynamisk programmering, grådighed

· Grafalgoritmer
Grafgennemløb, sammenhængsegenskaber, topologisk sortering, udspændende træer, korteste veje, transitiv lukning

· Tekstprocessering
Mønstergenkendelse

Undervisning

Forelæsninger 4 timer (2+2).
Øvelser 3 timer

Bemanding

Gert Brodal Stølting

Litteratur:

Michael T. Goodrich and Roberto Tamassia: Algorithm design - Foundations, Analysis and Internet Examples. John Wiley & Sons, Inc. ISBN: 0-471-38365-1.

Obligatorisk program

6 opgaver

Eksamensform

4 timers skriftlig eksamen, ekstern censur, 13 skalaen

Placering

4. kvarter

Omfang

5 ECTS