Algoritmen en Datastructuren I

  • in Dutch (Bachelor Level)

Voorkennis

De programmeertaal Scheme, zie cursus Structuur van Computerprogramma’s I.

Leerdoelen

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. De student moet bestaande algoritmen en implementaties van Abstract Data Types (ADT’s) kunnen evalueren en vergelijken.

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 ADT’s kunnen opstellen en moet deze kunnen van een implementatie voorzien door de juiste datastructuren en algoritmen uit te kiezen en toe te passen.

Inhoud

Deze cursus presenteert een reeks algoritmen en datastrukturen die tot het basisvocabularium van een informaticus behoren. De voertaal in deze cursus is Scheme, maar in principe bestaan al deze algoritmen en datastrukturen los van een specifieke programmeertaal. Het vak omvat de volgende onderwerpen:

  • Hoofdstuk 1 Data abstractie en procedurele abstractie: Data constructoren, Abstracte Data Types (ADT’s), Genericiteit, Uitvoeringstijd van algoritmen (grote O notatie).
  • Hoofdstuk 2 Patroonherkenning: Brutekracht algoritme, Knutt-Morris-Pratt algoritme, Quicksearch.
  • Hoofdstuk 3 Lineaire datastructuren: Vectoriële lijsten, enkel gelinkte lijsten, dubbel gelinkte lijsten, Zoeken in lineaire datastructuren, ringen.
  • Hoofdstuk 4 Lineaire ADT’s: Stacks (vectoriële en gelinkte implementatie), Queues (vectoriële en gelinkte implementatie) en Priority Queues (vectoriële, gelinkte en heap implementatie).
  • Hoofdstuk 5 Sorteren: Simpele sorteeralgoritmen zoals bubble sort, insertion sort en selection sort. Geavanceerde sorteeralgoritmen a la Quicksort, Heapsort, Mergesort. Lineaire sorteeralgoritmen: Radix Sort, Counting Sort, Bucket Sort.
  • Hoofdstuk 6 Bomen en Toepassingen: Implementatie van dictionaries, Het doorlopen van bomen, Binaire zoekbomen, AVL Bomen en balanceringstechnieken.
  • Hoofdstuk 7 Hashing: Opstellen van hashfuncties, Primaire en secondaire clustering, botsingsoplossingsstrategieën en herhashen.
  • Hoofdstuk 8 Externe Opslagmedia: Soorten geheugen, Disks, File Systems, Freelists, Sequentiële Files, Caching.
  • Hoofdstuk 9 Extern Sorteren: Multiway Balanced Merge-sort, Polyphase Sort, n-Polyphase Sort.
  • Hoofdstuk 10 Data-Files: Het relationele model, Opslag van het schema, Opslag van tupels.
  • Hoofdstuk 11 Index-Files: B-Trees, B+-Trees, SQL-Querying.

Studiemateriaal

Een cursustekst “Algorithms and Datastructures in Scheme” is beschikbaar. Er kan ter aanvulling gebruik gemaakt worden van het referentiewerk “Introduction to Algorithms” (door Cormen, Leiserson, Rivest, MIT Press).

Examen

Het examen bestaat uit een schriftelijk en een modeling gedeelte. Tijdens het schriftelijke gedeelte wordt de student beoordeeld op het praktische luik: het toepassen van de kennis in concrete situaties en het bouwen van variaties op de geziene algoritmen en datastructuren. Het mondelinge gedeelte beoogt een toetsing van de theoretische kennis van de student.

 
edu/algo1.txt · Last modified: 25.09.2011 12:47 by wdmeuter
 

© 2014 • Software Languages Lab • Submit comments and bugs to our Bugzilla or to the webmaster