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:
- Data abstractie en procedurele abstractie: Data constructoren, Abstracte Data Types (ADT's), Genericiteit, Uitvoeringstijd van algoritmen (grote O, Omega en Theta notatie).
- Patroonherkenning in Strings: het Brute-kracht algoritme, het Knutt-Morris-Pratt algoritme, het Sunday Quicksearch algoritme.
- Lineaire datastructuren: Vectoriële lijsten, enkel gelinkte lijsten, dubbel gelinkte lijsten, Zoeken in lineaire datastructuren, Ringen.
- Lineaire ADT's: Stacks, Queues, Prioriteitenqueues, Heaps.
- Sorteren: Taxonomie van sorteeralgoritmen, Simpele sorteeralgoritmen (bubble sort, insertion sort en selection sort), Geavanceerde algoritmen (Quicksort, Heapsort, Mergesort) en Lineaire algoritmen (Radix Sort, Counting Sort, Bucket Sort). Ondergrens op sorteren.
- Bomen en Toepassingen: Definitie van dictionaries, Het doorlopen van bomen recursief en iteratief, Binaire zoekbomen, AVL Bomen en balanceringstechnieken.
- Hashing: Opstellen van hashfuncties, Primaire en secondaire clustering, botsingsoplossingsstrategieën (external chaining, open addressing) en herhashen (lineair, kwadratisch, dubbel).
Algemene competenties
Kennis en inzicht: Een belangrijk doel van deze cursus bestaat uit encyclopedische kennisoverdracht: de student wordt verondersteld van de verschillende algoritmen en datastructuren bij naam te kennen, hun werking en implementatie te begrijpen, en te kunnen inschatten waar en wanneer ze toepasbaar zijn. Er gaat daarbij veel aandacht naar het inschatten van de performantie van een algoritme of implementatie van een datastructuur.
Toepassen van de kennis en het inzicht: Een tweede belangrijk doel bestaat uit het toepassen van de kennis in een concrete situatie. De student moet bestaande algoritmen en implementaties van ADT's kunnen wijzigen om ze aan te passen aan nieuwe constraints. Hij/zij moet voor een gesteld probleem de juiste Abstract Data Types (ADT's) kunnen ontwerpen en moet deze kunnen van een implementatie kunnen voorzien door de juiste datastructuren en algoritmen uit te kiezen en toe te passen.
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: De student wordt aangeleerd precies te communiceren over de functionaliteit van een ADT door het beschrijven ervan m.b.v. een formele ADT notatie. Doel is communicatie tussen de verschillende ontwikkelaars van een groot systeem 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.