9 studiepunten
255 u studietijd

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

Semester
1e en 2e semester
Inschrijving onder examencontract
Niet mogelijk
Beoordelingsvoet
Beoordeling (0 tot 20)
2e zittijd mogelijk
Ja
Inschrijvingsvereisten
Alvorens te kunnen inschrijven voor 'Algoritmen en Datastructuren 1' moet men ingeschreven of geslaagd zijn voor 'Structuur van Computerprogramma's I'
Onderwijstaal
Nederlands
Faculteit
Faculteit Wetenschappen en Bio-ingenieurswetensch.
Verantwoordelijke vakgroep
Computerwetenschappen
Onderwijsteam
Wolfgang DE MEUTER (titularis)
Onderdelen en contacturen
39 contacturen Hoorcollege
39 contacturen Werkvormen en Praktische Oef.
Inhoud

 

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, verspreid over beide vakken "Algoritmen en Datastructuren 1&2":

 

- 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).

- De geheugenhiërarchie: intern geheugen, extern geheugen, soorten files, caching

- Externe datastructuren: Indexering, B+-Bomen

- Extern sorteren (multiway balanced mergesort, polyphase sort).

- 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)

- Geheugenbeheertechnieken: taxonomie van de problematiek, first-fit systemen, best-fit systemen, buddy allocators

- Garbagecollectie: stop-and-copy, mark-and-sweep, Deutsch-Schorr-Waite algoritme voor blokken van vaste lengte en blokken van variabele lengte.

Studiemateriaal
Cursustekst (Vereist) : Algorithms and Datastructures in Scheme, Pointcarré
Handboek (Aanbevolen) : Introduction to Algorithms, Cormen, Leiserson, Rivest; MIT Press, 1991
Handboek (Aanbevolen) : Garbage Collection: Algorithms for Automatic Dynamic Memory Management, Jones, Lins, John Wiley & Sons, 1996
Handboek (Aanbevolen) : Database System Implementation, Garcia-Molina, Ullman, Widom, Prentice-Hall, 2000
Bijkomende info
Een cursustekst "Algorithms and Datastructures in Scheme" is in opbouw en wordt ter beschikking gesteld op het PointCarré system, 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), "Garbage Collection: Algorithms for Automatic Dynamic Memory Management" (door Jones, Lins; John Wiley & Sons; 1996) en "Database System Implementation" (door Garcia-Molina, Ullman, Widom; Prentice-Hall, 2000).
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:
Oral Exam bepaalt 50% van het eindcijfer

Written Exam bepaalt 50% van het eindcijfer

Binnen de categorie Oral Exam dient men volgende opdrachten af te werken:

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

    Toelichting: 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.

Binnen de categorie Written Exam dient men volgende opdrachten af te werken:

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

    Toelichting: 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.

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.

Academische context

Deze aanbieding maakt deel uit van de volgende studieplannen:
Bachelor of Science in de wiskunde: Standaard traject
Bachelor of Science in de computerwetenschappen: Standaard traject