Algoritmen en datastructuren 2

AANBEVOLEN VOORKENNIS

• De vakkenreeks “Algoritmen en Datastructuren 1&2” presenteert de algoritmen en datastructuren die tot het basisvocabularium van een informaticus behoren. In principe staan al deze algoritmen en datastructuren los van een specifieke programmeertaal maar omwille van de wetenschappelijke precisie wordt Scheme als formele taal gebruikt.

Inhoud:

• Volgende onderwerpen worden in detail besproken in deze cursus:
• Geamortisseerde Analyse: disjuncte verzamelingen, het union-find probleem, uptrees, padcompressie
• Grafen: voorstelling van grafen met adjacencystructuren
• Graaftraversals: DFS, BFS, karakteriseringen van DFS en BFS door classificatie van de bogen
• Ongerichte graafproblemen: samenhangendheid, boogsamenhangendheid, biconnectiviteit, en spanningsbomen (Prim, Kruskal,Boruvka).
• Gerichte Graafproblemen: Topologisch Sorteren van DAGs, Sterk samenhangendheid, Bereikbaarheid en kortste paden in Grafen (Bellman-Ford, Dijkstra, Floyd-Warshall, Lawler)
• Geheugenbeheertechnieken: taxonomie van de problematiek, first-fit systemen, best-fit systemen, buddy allocators
• Garbagecollectie: stop-and-copy, mark-and-sweep, Deutsch-Schorr-Waite algoritme voor blokken van vaste lengte en blokken van variabele lengte.
• Dynamisch Programmeren

Leerresultaten:

• Kennis en inzicht:
  Het eerste doel van de cursus bestaat uit het vervolledigen van de basiskennis van algoritmen en -datastructuren die door elke informaticus dient gekend te zijn. Het doel is dus om de encyclopedische kennis van de student hieromtrent verder aan te dikken. De student dient de gepresenteerde algoritmen en datastructuren te kunnen evalueren, vergelijken, implementeren en aanpassen aan nieuwe situaties. Het tweede doel bestaat erin de student vertrouwd te maken met de werking en de analyse van een reeks specialistische algoritmen waarvan de complexiteit uitstijgt boven de basiskennis die in klassieke handboeken over algoritmiek te vinden zijn. Ook voor deze algoritmen dient de student inschattingen te kunnen maken wat betreft inzetbaarheid, dient de student implementaties ervan te kunnen doorgronden en in staat te zijn om zelfstandig een reeks varianten van de gepresenteerde algoritmen te kunnen bouwen en analyseren.
• Toepassing van kennis en inzicht:
  Net zoals bij Algoritmen en Datastructuren 1, moet de student na de cursus in staat zijn om de behandelde algoritmen en datastructuren aan te passen aan een nieuwe concrete situatie. Ook moet de student in staat zijn nieuwe algoritmen en datastructuren te bedenken voor problemen die aansluiten bij de geziene materie.
• Oordeelvorming: 
  De student moet bestaande algoritmen, datastructuren en implementaties van ADT’s kunnen evalueren en vergelijken. Bovendien wordt van de student verwacht dat hij/zij na het volgen van de cursus een oordeel kan vormen over de kwaliteit van een implementatie van een datastructuur en/of algoritme.
• Communicatie:
  Studenten moeten na afloop van de cursus in staat zijn hun algoritmen en datastructuren voldoende precies te documenteren teneinde de communicatie tussen verschillende ontwikkelaars van een project aan te leren.
• Leervaardigheden: 
  De taxonomie gepresenteerd in de cursus moet de student een structureel inzicht geven om zelfstandig en zeer gericht in de literatuur variaties van de geziene algoritmen en datastructuren te herkennen en te kunnen opzoeken.

All detailed and official information about the course here >