Onderwijs Informatica en Informatiekunde

Vak-informatie Informatica en Informatiekunde

Datastructuren

Website:

website met extra informatie

Vakcode:

INFODS

Studiepunten:

7.5 ECTS

Periode:

periode 4 (week 17 t/m 26, d.w.z. 26-4-2021 t/m 2-7-2021; herkansing week 28)

Timeslot:

Deelnemers:

tot nu toe 307 inschrijvingen

Rooster:

De officiële roosters staan in MyTimetable

Docenten:

vorm	groep	docent
college		Gerard Tel
werkcollege	groep 1	Sukanya Pandey
werkcollege	groep 2	Hieke Keuning

Nota bene:

Er is geen recente vakbeschrijving beschikbaar.
Onderstaande tekst is een oude vakbeschrijving uit collegejaar 2018/2019

Inhoud:

Thema van Datastructuren is: met wiskunde het programmeren naar een hoger niveau tillen. Voor je een computerprogramma kunt schrijven om een probleem op te lossen, moet een aanpak (een reeks stappen) bedacht worden die het programma kan volgen om het probleem op te lossen: een algoritme genoemd. In dit vak worden algoritmen besproken voor het sorteren van en het zoeken in een verzameling gegevens. Zoekalgoritmen spelen een speciale rol, want ze hangen af van de manier waarop de gegevens zijn opgeslagen. Een methode voor gegevensopslag wordt een datastructuur genoemd. In het college worden diverse datastructuren en bijbehorende wiskundige methoden behandeld en in het practicum moet je die ook implementeren.

Concreet volgen hieruit de volgende Leerdoelen: Na afloop van het vak kan de student eenvoudige algoritmische problemen modelleren en oplossen met een zelfgeschreven programma.

Datastructuren. De student kent elementaire datastructuren, hun eigenschappen, de complexiteit van hun operaties, em hoe ze toe te passen in een programma: Stack, Queue, PriorityQueue, HashTable, Tree.
Sorteren. De student kent sorteeralgoritmen en hun eigenschappen: QuickSort, InsertionSrt, HeapSort, CountingSort, RadixSort, BucketSort, in-situ, stabiel, ondergrens, complexiteit O(n lgn).
Analyse. De student kan de asymptotisch complexiteit van algoritmen analyseren: statements, loop, recurrente betrekking.
Programmeren. In aanvulling op eerdere cursussen over programmeren kan de student loops analyseren met een invariant, recursie gebruiken, pass-by-reference gebruiken.
Wiskunde. De student kan wiskundige gereedschappen hanteren voor het rekenen aan programma's en modellen: bewijzen met inductie, sommaties, Master Theorem, kansrekening en verwachting, recurrenties, Taylorreeks.
Implementeren. De student kan een C# programma schrijven waarin bovenstaande wordt toegepast.

Literatuur:

Kan veranderen!
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Third Edition, MIT Press / McGraw-Hill Book Company, 2009.

Op de website van het vak verschijnen voorbeeldprogramma's (PILletjes) en weblinks.

Werkvorm:

Hoor- en werkcollege; programmeerpracticum, huiswerk. Ook is er een programmeerwedstrijd, het muKP, georganiseerd door AEs².

Toetsvorm:

Datastructuren wordt getoetst in

Twee toetsen, T1 en T2: Je moet beide toetsen maken en je krijgt daarvoor een cijfer tussen 0,1 en 10.
Let op: De toetsen zijn Gesloten Boek, je mag dus geen literatuur of aantekeningen gebruiken!
Twee huiswerksets, H1 en H2: De huiswerksets zijn niet verplicht, maar tellen wel voor een deel van je cijfer. Als je huiswerk maakt, kijk je ook huiswerk van een ander team na.
Zeven programmeeropdrachten, P: Van de zeven opdrachten moet je er minstens vijf maken (dwz., het programma schrijven en op tijd en succesvol inleveren in DomJudge). Voor de opdrachten krijg je geen cijfer. Alleen het aantal succesvol ingeleverde opdrachten telt, dit is je getal P.
Het muKP, M: Het klein programmeerkampioenschap is geen activiteit van Datastructuren maar van AEs².

Je krijgt voor Datastructuren een Eindcijfer (getal) als je beide toetsen hebt gedaan (T1 * T2 > 0) en vijf of meer programmeeropdrachten (P > 4). Heb je dat niet, maar wel minstens 1 toets en minstens 3 programmeeropdrachten, dan krijg je een voorlopige Eindbeoordeling AANV, en mag je meedoen aan de reparatietoetsing.

Voldoendes worden bij Datastructuren afgerond op tiende punten . De twee toetsen en huiswerkopdrachten worden gewogen gemiddeld. Met 6 of 7 voltooide programmeeropdrachten krijg je een bonus van een halve of hele punt. Voor deelname aan het muKP kun je ook een bonus krijgen van 0,2 per goede inlevering (M, max. 3): B = (P-5)/2 + M/5. Je eindcijfer is het gemiddelde van de toetsen en huiswerk plus bonus: E = 0,45*(T1+T2) + 0,05*(H1+H2) + B. Het wordt afgerond op helen als het tussen 5 en 6 is, anders op tienden. Het eindcijfer moet minstens 6 zijn, dan ben je geslaagd voor Datastructuren.

Inspanningsverplichting voor aanvullende toets:

Om aan de aanvullende toets te mogen meedoen moet de oorspronkelijke uitslag minstens 4 zijn.

Beschrijving:

Als aanvullende toetsing kun je een van de toetsen (weer) maken, en/of een of twee programmeeropgaven.

wijzigen?

Department of Information and Computing Sciences

Onderwijs Informatica en Informatiekunde

Datastructuren