SluitenHelpPrint
Switch to English
Cursus: INFOAL
INFOAL
Algoritmiek
Cursus informatie
CursuscodeINFOAL
Studiepunten (EC)7,5
Cursusdoelen
Cursusdoelen:
De cursus draait om het specificeren, ontwerpen, analyseren en implementeren van algoritmen. Na afloop van de cursus kun je:
- de ontwerp-methode divide-and-conquer toepassen;
- van een recursief algoritme de asymptotische complexiteit berekenen door het formuleren van een recurrente betrekking en het oplossen van die betrekking;
- de ontwerpmethoden dynamisch programmeren en greedy algoritme toepassen;
- van een dynamisch programmeer algoritme de eigenschap Optimale SubStructuur formuleren en bewijzen;
- voor een greedy algoritme de eigenschap greedy-choice property formuleren en bewijzen;
- een geamortiseerde analyse uitvoeren;
- een dynamische zoekboom beschrijven en operaties erop toepassen;
- voor een graafprobleem een goede representerende datastructuur selecteren;
- voor een graafprobleem Breadth-First Search of Depth-First Search toepassen en de looptijd analyseren;
- een toewijzingsprobleem als een matching of netwerk flow probleem formuleren;
- de flow algoritmen van Ford-Fulkerson en Edmonds-Karp beschrijven en implementeren en de Max-Flow-Min-Cut stelling toepassen;
- de eigenschappen van een Minimum Spanning Tree benoemen en de MST algoritmen van Prim en Kruskal beschrijven en implementeren;
- de kortste-pad algoritmen van Dijkstra, Bellman-Ford, Floyd-Warshall en Johnson beschrijven;
- voor een graaf-probleem een kortste-pad algoritme toepassen en het algoritme implementeren;
- het begrip NP-volledigheid toepassen om de oplosbaarheid van een probleem te beoordelen;
- een gerandomiseerd algoritme of benaderingsalgoritme beschrijven en analyseren;
- de string matching algoritmen van Rabin-Karp, Knuth-Morris-Pratt evenals eindige automaten beschrijven en toepassen;
- een gegeven of zelf ontworpen algoritme implementeren, het programma testen en debuggen.



Ingangseisen/voorkennis:
Het vak vereist kennis van de programmeertaal C#, zoals onderwezen bij Imperatief Programmeren (INFOIMP), voor het maken van de practica. Daarnaast veronderstellen we basiskennis over datastructuren en de looptijd-analyse van algoritmes, zoals onderwezen bij Datastructuren (INFODS) of Datastructuren en Algoritmen voor KI (INFOB2DAKI). Mocht je vragen hebben m.b.t. het voldoen van je eigen voorkennis, neem dan even contact op.



Toetsing:
- twee deeltentamens. Beide deeltentamens zijn gesloten boek.
- zes practicumopgaven.

Ieder deeltentamen telt voor 50 procent van het eindcijfer. Door het maken van 5 of 6 van de practicumopgaven kun je 0.5 of 1 punt bonus krijgen. Je moet tenminste 4 practicumopgaven correct hebben om een cijfer te krijgen.

Als je niet aan de cijfervoorwaarde van de cursus voldoet, of je onafgeronde eindcijfer is zowel tenminste een 4 als minder dan 5.50, dan heb je misschien recht op aanvullende toetsing. Je moet dan wel: een cijfer voor beide deeltentamens, een gemiddeld tentamencijfer van minstens 5.50 en precies twee practica correct hebben; of, een cijfer voor tenminste een van beide deeltentamens en tenminste drie practica correct hebben.

Voor de aanvullende toetsing zijn er vier mogelijkheden, waarvan je er één mag kiezen: je haalt een practicum in, of je haalt twee practica in, of je doet het hertentamen, of je doet het hertentamen en haalt een practicum in.

Het hertentamen beslaat de gehele stof van de cursus. Je cijfer van het hertentamen vervangt het laagste deeltentamencijfer.



Aanbevolen materiaal:
Boek
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, third edition, MIT Press / McGraw Hill, 2009. (De tweede editie, uit 2001, is vrijwel gelijk en kan ook worden gebruikt.)



Werkvormen:
Hoorcollege
Werkcollege
Practicum
 
Inhoud
Voor veel toepassingen is de snelheid van de gebruikte software van groot belang. Vaak betekent dit dat er, naast bijvoorbeeld snelle computers en goede compilers, efficiente algoritmen nodig zijn. Om zulke efficiente algoritmen te kunnen ontwikkelen bestudeer je in het vak Algoritmiek een aantal technieken.

De belangrijkste algoritmische technieken die je leert zijn divide-and-conquer, greedy, dynamisch programmeren en probabilistische algoritmen. Deze worden geintroduceerd aan de hand van concrete problemen. Ook bestudeer je verschillende algoritmen, met name voor problemen op grafen, bijvoorbeeld kortste paden en network flow. Daarnaast leer je het begrip NP-volledigheid en bestudeer je benaderingsalgoritmen. Ten slotte leer je geavanceerde analysetechnieken voor het doen van geamortiseerde analyse en het oplossen van recurrente betrekkingen.

Het vak benadrukt zowel de fundamentele aspecten (looptijdanalyse en correctheidsbewijzen) als de praktische aspecten van Algoritmiek. Het hoorcollege legt de basis hiervoor. Analyse en correctheid komen aan bod in de werkcolleges, terwijl je implementatie-uitdagingen aangaat in de practica.
SluitenHelpPrint
Switch to English