Algoritmen en datastructuren 1

5 ECTS credits
150 u studietijd

Aanbieding 2 met studiegidsnummer 1015255ANR voor alle studenten in het 1e semester met een inleidend bachelor niveau.

Semester

1e semester

Inschrijving onder examencontract

Niet mogelijk

Beoordelingsvoet

Beoordeling (0 tot 20)

2e zittijd mogelijk

Inschrijvingsvereisten

Studenten die dit opleidingsonderdeel opnemen, moeten geslaagd of ingeschreven zijn voor 'Structuur van computerprogramma's 1'.

Onderwijstaal

Nederlands

Faculteit

Faculteit Wetenschappen en Bio-ingenieurswetensch.

Verantwoordelijke vakgroep

Computerwetenschappen

Onderwijsteam

Wolfgang De Meuter (titularis)
Jens Nicolay

Onderdelen en contacturen

26 contacturen Hoorcollege
26 contacturen Werkcolleges, practica en oefeningen
125 contacturen Zelfstudie en externe werkvormen

Inhoud

AANBEVOLEN VOORKENNIS

De vakkenreeks "Algoritmen en Datastructuren 1&2" presenteert de algoritmen en datastructuren die tot het basisvocabularium van een informaticus behoren. In principe staan al deze algoritmen en datastructuren los van een specifieke programmeertaal maar omwille van de wetenschappelijke precisie wordt Scheme als formele taal gebruikt.

INHOUD

Volgende onderwerpen worden in detail besproken in deze cursus:

- Data abstractie en procedurele abstractie: Data constructoren, Abstracte Data Types (ADT's), Genericiteit, Uitvoeringstijd van algoritmen (grote O, Omega en Theta notatie).

- Patroonherkenning in Strings: het Brute-kracht algoritme, het Knutt-Morris-Pratt algoritme, het Sunday Quicksearch algoritme.

- Lineaire datastructuren: Vectoriële lijsten, enkel gelinkte lijsten, dubbel gelinkte lijsten, Zoeken in lineaire datastructuren, Ringen.

- Lineaire ADT's: Stacks, Queues, Prioriteitenqueues, Heaps.

- Sorteren: Taxonomie van sorteeralgoritmen, Simpele sorteeralgoritmen (bubble sort, insertion sort en selection sort), Geavanceerde algoritmen (Quicksort, Heapsort, Mergesort) en Lineaire algoritmen (Radix Sort, Counting Sort, Bucket Sort). Ondergrens op sorteren.

- Bomen en Toepassingen: Definitie van dictionaries, Het doorlopen van bomen recursief en iteratief, Binaire zoekbomen, AVL Bomen en balanceringstechnieken.

- Hashing: Opstellen van hashfuncties, Primaire en secondaire clustering, botsingsoplossingsstrategieën (external chaining, open addressing) en herhashen (lineair, kwadratisch, dubbel).

Studiemateriaal

Cursustekst (Vereist) : Algorithms and data structures in scheme (part 1), De Meuter, VUB, 2220170000206, 2015
Handboek (Aanbevolen) : Database System The Complete Book, Garcia-Molina, Ullman, Widom, 2de, Pearson, 9781292024479, 2013
Handboek (Aanbevolen) : Garbage Collection, Algorithms for Automatic Dynamic Memory Management, Jones, Lins, John Wiley & Sons, 9780471941484, 1996
Handboek (Aanbevolen) : Introduction to Algorithms, Cormen, Leiserson, 3de, Rivest; MIT Press, 9780262033848, 2009

Bijkomende info

Een cursustekst wordt ter beschikking gesteld op het Canvas system, samen met de in de les gebruikte transparanten. Er kan aanvullend gebruik gemaakt worden van referentiewerken als "Introduction to Algorithms" (door Cormen, Leiserson, Rivest; MIT Press; 1991).

Leerresultaten

Algemene competenties

Kennis en inzicht: Een belangrijk doel van deze cursus bestaat uit encyclopedische kennisoverdracht: de student wordt verondersteld van de verschillende algoritmen en datastructuren bij naam te kennen, hun werking en implementatie te begrijpen, en te kunnen inschatten waar en wanneer ze toepasbaar zijn. Er gaat daarbij veel aandacht naar het inschatten van de performantie van een algoritme of implementatie van een datastructuur.

Toepassen van de kennis en het inzicht: Een tweede belangrijk doel bestaat uit het toepassen van de kennis in een concrete situatie. De student moet bestaande algoritmen en implementaties van ADT's kunnen wijzigen om ze aan te passen aan nieuwe constraints. Hij/zij moet voor een gesteld probleem de juiste Abstract Data Types (ADT's) kunnen ontwerpen en moet deze kunnen van een implementatie kunnen voorzien door de juiste datastructuren en algoritmen uit te kiezen en toe te passen.

Oordeelvorming: De student moet bestaande algoritmen, datastructuren en implementaties van ADT's kunnen evalueren en vergelijken. Bovendien wordt van de student verwacht dat hij/zij na het volgen van de cursus een oordeel kan vormen over de kwaliteit van een implementatie van een datastructuur en/of algoritme.

Communicatie: De student wordt aangeleerd precies te communiceren over de functionaliteit van een ADT door het beschrijven ervan m.b.v. een formele ADT notatie. Doel is communicatie tussen de verschillende ontwikkelaars van een groot systeem aan te leren.

Leervaardigheden: De taxonomie gepresenteerd in de cursus moet de student een structureel inzicht geven om zelfstandig en zeer gericht in de literatuur variaties van de geziene algoritmen en datastructuren te herkennen en te kunnen opzoeken.

Beoordelingsinformatie

De beoordeling bestaat uit volgende opdrachtcategorieën:
Examen Mondeling bepaalt 45% van het eindcijfer

Examen Schriftelijk bepaalt 45% van het eindcijfer

WPO Verslag bepaalt 10% van het eindcijfer

Binnen de categorie Examen Mondeling dient men volgende opdrachten af te werken:

Mondeling examen met een wegingsfactor 45 en aldus 45% van het totale eindcijfer.

Toelichting: Het examen bestaat uit een schriftelijk en een mondeling gedeelte. Beide delen zijn even belangrijk in de eindevaluatie.

Binnen de categorie Examen Schriftelijk dient men volgende opdrachten af te werken:

Schriftelijk examen met een wegingsfactor 45 en aldus 45% van het totale eindcijfer.

Binnen de categorie WPO Verslag dient men volgende opdrachten af te werken:

Taken met een wegingsfactor 10 en aldus 10% van het totale eindcijfer.

Toelichting: Tijdens het academiejaar worden een aantal taken opgegeven die verplicht opgelost dienen te worden en meetellen in de eindbeoordeling.

Aanvullende info mbt evaluatie

Het examen bestaat uit een schriftelijk en een mondeling gedeelte. Beide delen zijn even belangrijk in de eindevaluatie. Tijdens het academiejaar worden een aantal taken opgegeven die verplicht opgelost dienen te worden en meetellen in de eindbeoordeling. Afwezigheid op 1 van de onderdelen impliceert afwezigheid op het hele vak.

Toegestane onvoldoende

Kijk in het aanvullend OER van je faculteit na of een toegestane onvoldoende mogelijk is voor dit opleidingsonderdeel.

Academische context