Algoritmen en datastructuren 2

5 ECTS credits
150 u studietijd

Aanbieding 2 met studiegidsnummer 2023913BNW voor werkstudenten in het 2e semester met een verdiepend bachelor niveau.

Semester

2e 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 “Algoritmen en datastructuren 1".

Onderwijstaal

Nederlands

Faculteit

Faculteit Wetenschappen en Bio-ingenieurswetensch.

Verantwoordelijke vakgroep

Computerwetenschappen

Onderwijsteam

Joeri De Koster
Bart Bogaerts (titularis)

Onderdelen en contacturen

39 contacturen Hoorcollege
39 contacturen Werkcolleges, practica en oefeningen
200 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. Wij gebruiken een combinatie van pseudo-code en Scheme.

INHOUD

Volgende onderwerpen worden in detail besproken in deze cursus:

Geamortisseerde Analyse: disjuncte verzamelingen, het union-find probleem, uptrees, padcompressie
Grafen: voorstelling van grafen met adjacencystructuren
Graaftraversals: DFS, BFS, karakteriseringen van DFS en BFS door classificatie van de bogen
Ongerichte graafproblemen: samenhangendheid, boogsamenhangendheid, biconnectiviteit, en spanningsbomen (Prim, Kruskal,Boruvka).
Gerichte Graafproblemen: Topologisch Sorteren van DAGs, Sterk samenhangendheid, Bereikbaarheid en kortste paden in Grafen (Bellman-Ford, Dijkstra, Floyd-Warshall, Lawler)
Dynamisch Programmeren
Het SAT probleem: Geavanceerde zoekalgoritmes

Studiemateriaal

Digitaal cursusmateriaal (Vereist) : Algorithms and Datastructures in Scheme
Handboek (Aanbevolen) : Database System The Complete Book, Garcia-Molina, Ullman, Widom, 2de, Pearson, 9781292024479, 2013
Handboek (Aanbevolen) : Introduction to Algorithms, Cormen, Leiserson, 3de, Rivest; MIT Press, 9780262033848, 2009

Bijkomende info

Een cursustekst wordt ter beschikking gesteld op het leerplatform, samen met de in de les gebruikte transparanten. Voor de niet-beschreven onderwerpen kan er aanvullend gebruik gemaakt worden van de referentiewerken als "Introduction to Algorithms" (door Cormen, Leiserson, Rivest; MIT Press; 1991) en "Database System Implementation" (door Garcia-Molina, Ullman, Widom; Prentice-Hall, 2000).

Leerresultaten

Algemene competenties

Kennis en inzicht: Het eerste doel van de cursus bestaat uit het vervolledigen van de basiskennis van algoritmen en -datastructuren die door elke informaticus dient gekend te zijn. Het doel is dus om de encyclopedische kennis van de student hieromtrent verder aan te dikken. De student dient de gepresenteerde algoritmen en datastructuren te kunnen evalueren, vergelijken, implementeren en aanpassen aan nieuwe situaties. Het tweede doel bestaat erin de student vertrouwd te maken met de werking en de analyse van een reeks specialistische algoritmen waarvan de complexiteit uitstijgt boven de basiskennis die in klassieke handboeken over algoritmiek te vinden zijn. Ook voor deze algoritmen dient de student inschattingen te kunnen maken wat betreft inzetbaarheid, dient de student implementaties ervan te kunnen doorgronden en in staat te zijn om zelfstandig een reeks varianten van de gepresenteerde algoritmen te kunnen bouwen en analyseren.

Toepassing van kennis en inzicht: Net zoals bij Algoritmen en Datastructuren 1, moet de student na de cursus in staat zijn om de behandelde algoritmen en datastructuren aan te passen aan een nieuwe concrete situatie. Ook moet de student in staat zijn nieuwe algoritmen en datastructuren te bedenken voor problemen die aansluiten bij de geziene materie.

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: Studenten moeten na afloop van de cursus in staat zijn hun algoritmen en datastructuren voldoende precies te documenteren teneinde de communicatie tussen verschillende ontwikkelaars van een project 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 50% van het eindcijfer

WPO Praktijkopdracht bepaalt 50% van het eindcijfer

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

examen andere met een wegingsfactor 1 en aldus 50% van het totale eindcijfer.

Toelichting: De opdrachtcategorie "Examen Mondeling" bestaat uit een aantal theorievragen.

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

schriftelijk examen met een wegingsfactor 1 en aldus 50% van het totale eindcijfer.

Toelichting: Voor de opdrachtcategorie "WPO Praktijkopdracht" zullen tijdens het academiejaar een aantal programmeertaken ingediend moeten worden. Deze taken moeten vervolgens nog verdedigd worden (tijdens of na het mondeling examen). Elk van de taken weegt even zwaar door.

Aanvullende info mbt evaluatie

Het examen bestaat uit een theoretisch en een praktisch (oefeningen of project) gedeelte. Beide gedeelten zijn even belangrijk in de eindbeoordeling. Afwezigheid op 1 van de onderdelen impliceert afwezigheid op het volledige vak.

Toegestane onvoldoende

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

Academische context