Prospectus

nl en

Datastructuren

Course
2012-2013

Toegangseisen

Geen

Beschrijving

Dit college is een vervolg op het college Algoritmiek. Dus het leren ontwerpen en begrijpen van algoritmen — op zijn minst de standaard algoritmen die tot het repertoire van elke computing expert behoren — zullen weer een belangrijke rol gaan spelen. Zoals bekend vormen het algoritme en de data die van belang zijn voor het algoritme een samenwerkend geheel. Bij data die van belang zijn voor het algoritme valt te denken aan input en output gegevens maar ook data die het algoritme bijhoudt voor zijn werking. Daarom zullen we ook ruim aandacht schenken aan het handig structureren en representeren van de data – vandaar de naam van het college. Er bestaan verschillende standaard datastructuren zoals lists, trees, arrays, sets, bags om er maar een paar te noemen. Elk van deze gegevensstructuren kun je karakteriseren vanwege hun structuur en hun access methods. De standaard datastructuren kunnen met een breed scala van algoritmen samenwerken. Er zijn natuurlijk ook datastructuren die toegesneden zijn op een beperkte klasse van algoritmen. Uiteraard zullen we de standaard datastructuren zoals stapels (stacks), rijen (queues), lijsten(lists), binaire en multiway bomen(binary en multiway trees), priority queues, grafen(graphs) de revue laten passeren. Onze aanpak van het ontwerp van datastructuren is via Abstract Data Types (hetgeen nauw aansluit bij OO-programmeren). Door gebruik te maken van ADT’s kunnen we het gebruik van de gegevensstructuur en de definitie van het gewenste gedrag ervan scheiden van de implementatie. Onderwerpen: Linked Lists, Stacks, Queues, Binary Trees, Multiway Trees, Graphs, Hashing, Data Compression, String Matching, Randomized Algorithms

Leerdoelen

Inzicht en gebruik van standaard datastructuren en bijbehorende algoritmen, verkrijgen van enig inzicht in efficiëntie verschillen, abstract leren denken: onderscheid gebruik en implementatie.

Rooster

Het meest recente rooster is te vinden via de Liacs website

Onderwijsvorm

Per week 2 uur hoorcollege voorafgaand aan 2 uur werkcollege/programmeeropdrachten.

Toetsing

Schriftelijk (50%). Daarnaast moet aan verplichte programmeeropdrachten (50%) zijn voldaan. Voor beide onderdelen moet minimaal een 5,5 zijn gehaald.

Literatuur

Data Structures and Algorithms in C++, Adam Drozdek, Third Edition, Thomson Course Technology, isbn 0-534-49182-0

Aanmelden

Aanmelden via Usis: Selfservice > Sudentencentrum > Inschrijven
Activiteitencodes te vinden via de facultaire website

Voor studenten die niet staan ingeschreven voor de bachelor Informatica is er een beperkte capaciteit. Neem contact op met de studieadviseur.

Contact

Onderwijscoördinator Informatica, Riet Derogee

Website

Datastructuren