Zoek
English
  Studiegidsen 2012-2013
Radboud UniversiteitStudiegidsenFaculteit der Natuurwetenschappen, Wiskunde en Informatica > Bachelor Informatica en Informatiekunde

Algoritmen en Datastructuren 

Vakcode
NWI-IBC001
Studiepunten
3
Periode
derde kwartaal
Inleiding
In de informatica bestaan tal van verschillende datastructuren. Deze datastructuren worden bijvoorbeeld gebruikt om informatie efficient op te slaan en terug te vinden. In dit vak laten we zien hoe deze datastructuren gebruikt worden en hoe ze gerealiseerd kunnen worden in een imperatieve/object georienteerde programmeertaal.

 

Leerdoelen
  • pointers begrijpen en kunnen gebruiken voor het realiseren van recursieve datastructuren.
  • ingewikkeldere algoritmen begrijpen, afleiden en implementeren;
  • toepassingsmogelijkheden van zoekalgoritmen (b.v. back-tracking of breadth-first serach) herkennen, het meest geschikte algoritme kunnen kiezen en implementeren;
  • balanceertechnieken voor binaire zoekbomen begrijpen, toepassen en implementeren
  • gegeven programma's kunnen begrijpen en uitbreiden.
  • implementatiemethode voor graphen kunnen kiezen.
  • graphalgoritmen kunnen implementeren.
  • een parser kunnen realiseren voor een gegeven grammatica.
  • bepaalde inefficiënte recursieve algoritmes om kunnen zetten in efficiënte, niet-recursieve versies door resultaten van deelberekeningen te onthouden en te hergebruiken.
Onderwerpen
  • pointers, dynamische geheugenallocatie;
  • recursieve datastructuren: lijsten en bomen;
  • gebalanceerde bomen; AVL-bomen, rood-zwart bomen, 2-3-4 bomen;
  • grafen en graafalgoritmen;
  • backtracking, branch-and-bound;
  • parseren en parseerbomen;
  • dynamic programming.

     

Studielastverdeling
  • 32 uur computerpracticum
  • 16 uur hoorcollege
  • 16 uur werkcollege
  • 20 uur zelfstudie
Toelichting werkvormen
In deze cursus staat het practicum centraal: ontwerpen en implementeren van algoritmen leer je vooral door te oefenen. Het hoorcollege heeft een ondersteunende functie: hierin worden de hoofdpunten van de leerstof toegelicht. Aan de hand van relatief grote practicumopdrachten worden basisvaardigheden en –concepten aangeleerd. Tijdens het werk/responsiecollege wordt vooruitgekeken naar de nieuwe opdracht en eventueel teruggeblikt op de vorige opdracht.
Toetsvorm
De cursus wordt afgesloten met een schriftelijk tentamen. Om te worden toegelaten tot het tentamen dien je serieus aan het practicum te hebben deelgenomen. Dit houdt in dat je alle practicumopdrachten moet hebben gemaakt dan wel een aantoonbare serieuze poging hebt ondernomen om de opdrachten te maken.

Vereiste voorkennis
Het kunnen programmeren in een imperatieve taal bijvoorbeeld door de cursus Programmeren met goed gevolg te hebben afgerond. Het concept recursie goed begrijpen en toe kunnen passen, zoals bijvoorbeeld geleerd is in de cursus Functioneel Programmeren. Begrip van elementaire recursieve datastructuren als bomen uit Functioneel Programmeren.  Elementaire object-georienteerde programmeerconcepten kennen en kunnen gebruiken (cursus Object-orientatie).
Literatuur
De gebruikte datastructuren en algoritmen staan in het book Algorithms van Cormen et al. dat je hebt uit andere cursussen. De programmeer technieken die je nodig hebt hoor te kennen uit de inleidende programmeervakken. De literatuur die je daar voor hebt zou voldoende moeten zijn voor dit vak.
Bijzonderheden
Dit jaar zal deze cursus voor het eerst grotendeels in Java gegeven worden.