Department of Information and Computing Sciences

Departement Informatica Onderwijs
Bachelor Informatica Informatiekunde Kunstmatige intelligentie Master Computing Science Game&Media Technology Artifical Intelligence Business Informatics

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. 23-4-2018 t/m 29-6-2018; herkansing week 28)
Timeslot:D
Deelnemers:tot nu toe 205 inschrijvingen
Rooster:De officiële roosters staan ook in Osiris
Docenten:
vormgroeptijdweekzaaldocent
college   wo 13.15-15.0017-25 KBG-COSMOS Gerard Tel
 
vr 11.00-12.4518 KBG-COSMOS
20 KBG-COSMOS
22-25 KBG-COSMOS
werkcollege groep 1 wo 15.15-17.0017-20 BBG-201 Marieke van der Wegen
Max Hessey
   
21 RUPPERT-D
22-25 BBG-201
vr 13.15-15.0018 BBG-209
20-25 BBG-209
groep 2 wo 15.15-17.0017-20 BBG-161 Ioannis Nemparis
Ivo Gabe de Wolff
   
21 RUPPERT-PAARS
22 BBG-161
23 BBG-061
24-25 BBG-161
vr 13.15-15.0018 BBG-201
20-25 BBG-201
groep 3 wo 15.15-17.0017-19 DDW-1.22 Stefan Schouten
Jelle Kroon
Jelle Oostveen
   
20 BBG-083
21 UNNIK-GROEN
22-25 DDW-1.22
vr 13.15-15.0018 BBG-214
20-25 BBG-214
Tentamen:
week: 26wo 27-6-201813.30-16.30 uurzaal: OLYMPOS-HAL2
week: 28wo 11-7-201813.30-16.30 uurzaal: EDUC-ALFAaanvullende toets
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 behandeld.

Voor veel problemen zijn er wezenlijk verschillende algoritmen of datastructuren te bedenken. In Datastructuren leer je ook hoe je de looptijd van algoritmen (en het geheugengebruik van datastructuren) kunt inschatten zonder dat daar een implementatie voor nodig is.

Een aantal van de onderwerpen die behandeld worden zijn: sorteren (quicksort, heap sort, bucket sort, ...); opslaan en zoeken (in priority queues, hash tabellen, zoekbomen) Daarnaast wordt wiskunde worden behandeld die nodig is voor de analyse van de algoritmen en datastructuren (inductie, sommeren, kansrekening, verwachting).

Literatuur:T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Third Edition, MIT Press / McGraw-Hill Book Company, 2009. (De vorige editie kan ook gebruikt worden.)

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 AEs2.
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 AEs2.
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 halve punten (en onvoldoendes op hele, maar die moeten sowieso over). 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 (na afronding, op halven vanaf 6 en helen onder de 6). Het eindcijfer E 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 een 4, 5 of AANV zijn. Met eindcijfer 3 of lager mag je niet repareren. Je mag aan de reparatietoetsing meedoen als je het eindcijfer 4 of 5 hebt gehaald. Als je nog geen cijfer hebt gekregen, mag je repareren wanneer je drie opdrachten en èèn toets hebt gedaan. In dat geval (P > 2 && T1 + T2 > 0) is je uitslag AANV.

Heb je minder dan drie opdrachten gemaakt of geen toets, dan is je uitslag NVD of ND, je hebt het vak dan niet gehaald en mag niet repareren.

Als reparatietoetsing maak je een toets (T1 of T2) opnieuw en/of maak je opdrachten af. Het huiswerk telt maar 10% mee en je kunt dit niet in de reparatie doen. De berekening van het eindcijfer is dan als boven. Voor de hertoets of het reparatieprogrammeren hoef je je niet op te geven. Als je mag repareren, ga ik ervan uit dat je dit doet. Bedenk wel vantevoren welke toets je gaat doen, en begin op tijd met programmeren!

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