Zoek
English
  Studiegidsen 2008-2009
Radboud UniversiteitStudiegidsenFaculteit der Natuurwetenschappen, Wiskunde en Informatica > Bachelor Informatica en Informatiekunde

Algoritmen en Datastructuren 

Vakcode
IBC001
Studiepunten
3
Periode
tweede semester
Inleiding
In tegenstelling tot Java en de meeste functionele programmeertalen kent C++ (en veel ander imperatieve talen) geen automatisch geheugenbeheer. In deze cursus wordt ingegaan op handmatig geheugenbeheer, waarbij de programmeur voor zijn datastructuren met de hand geheugen dient aan de vragen en dit zodra het niet meer nodig is weer vrij te geven. Ook zal worden ingegaan op de rol van verwijzingen (pointers) met name met betrekking tot het realiseren van recursieve datastructuren (b.v. lijsten, bomen). Daarnaast zullen enkele complexere algoritmes en programmeermethodieken aan de orde komen.

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 geschiktste algoritme kunnen kiezen en implementeren;
  • balanceertechnieken voor binaire zoekbomen begrijpen, toepassen en implementeren
  • gegeven programma's kunnen begrijpen en uitbreiden.
  • bepaalde inefficiënte recursieve algoritmes om kunnen zetten in efficiënte, niet-cursieve 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;
  • backtracking, branch-and-bound;
  • dynamic programming

Studielastverdeling
  • 42 uur computerpracticum
  • 14 uur hoorcollege
  • 7 uur werkcollege
  • 21 uur zelfstudie
Toelichting werkvormen
In deze cursus staat het practicum centraal: ontwerpen en implementeren van algoritmen leer je vooral door te oefenen. Het wekelijkse 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 worden de kleinere oefenopdrachten nabesproken en er wordt vooruitgekeken naar de eindopdracht van die week 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.
Literatuur
Dictaat.