SluitenHelpPrint
Switch to English
Cursus: INFOAL
INFOAL
Algoritmiek
Cursus informatie
CursuscodeINFOAL
Studiepunten (EC)7,5
Cursusdoelen
De cursus draait om het specificeren, ontwerpen, analyseren en implementeren van algoritmen. Na afloop van de cursus kun je:
  • gewenste eigenschappen van programma's uitdrukken in logische taal;
  • een optimaliseringsprobleem formuleren in termen van zoekruimte, toelaatbaarheid, en doelfunctie.
  • de ontwerp-methode divide-and-conquer toepassen en daarbij de begrippen Recursie, Deelprobleem, Atomaire instantie benoemen;
  • van een recursief algoritme de asymptotische complexiteit berekenen door het formuleren van een recurrente betrekking en het oplossen van die betrekking met de Master Theorem.
  • de ontwerp-methoden dynamisch programmeren en greedy algoritme toepassen en daarbij de begrippen topkeuze, alternatieven, instantie, deelinstantie benoemen;
  • van een dynamisch algoritme de asymptotische complexiteit berekenen door het aantal deelinstanties en de rekentijd per deelinstantie te analyseren;
  • van een dynamisch algoritme de eigenschap Optimale SubStructuur formuleren en bewijzen;
  • van een dynamisch algoritme de eigenschap Overlappende DeelProblemen aantonen;
  • voor een greedy algoritme de eigenschap greedy-choice property formuleren en bewijzen;
  • een geamortiseerde analyse uitvoeren;
  • voor een graaf-probleem een goede representerende data-structuur selecteren;
  • de geschiktheid van Breadth-First Search voor de oplossing van een probleem beargumenteren;
  • de geschiktheid van Depth-First Search voor de oplossing van een probleem beargumenteren;
  • BFS en DFS toepassen en van deze oplossing de rekentijd analyseren;
  • de eigenschappen van een Netwerk-Flow benoemen;
  • de flow algoritmen van Ford-Fulkerson en Edmonds-Karp beschrijven en implementeren;
  • de Max-Flow-Min-Cut stelling toepassen;
  • de eigenschappen van een Minimum Spanning Tree benoemen;
  • de MST algoritmen van Prim en Kruskal beschrijven en implementeren;
  • de eigenschappen van kortste paden benoemen;
  • de kortste-pad algoritmen van Dijkstra en Bellman-Ford beschrijven;
  • de keuze voor een kortste-pad algoritme beredeneren en het algoritme implementeren;
  • het begrip NP-volledigheid toepassen om de oplosbaarheid van een probleem te beoordelen;
  • van een probleen bewijzen dat het NP-volledig is;
  • een gegeven of zelf ontworpen algoritme implementeren, het programma testen en debuggen.
Inhoud
Veel van de algoritmen in het college worden behandeld in het kader van een algoritmische techniek: divide-and-conquer; greedy algoritmen; dynamisch programmeren; probabilistische algoritmen. Daarbij komen verschillende algoritmen aan bod, met name ook een aantal algoritmen voor problemen op grafen, bijvoorbeeld: kortste paden, network flow. Ook worden het begrip NP-volledigheid en de benaderingsalgoritmen behandeld.
SluitenHelpPrint
Switch to English