SluitenHelpPrint
Switch to English
Cursus: INFOAL
INFOAL
Algoritmiek
Cursus informatieRooster
CursuscodeINFOAL
Studiepunten (ECTS)7,5
Categorie / Niveau3 (Bachelor Gevorderd)
CursustypeCursorisch onderwijs
VoertaalNederlands
Aangeboden doorFaculteit Betawetenschappen; Undergraduate School Bètawetenschappen;
Contactpersoondr. E.J. van Leeuwen
E-mailE.J.vanLeeuwen@uu.nl
Docenten
Docent
dr. E.J. van Leeuwen
Overige cursussen docent
Contactpersoon van de cursus
dr. E.J. van Leeuwen
Overige cursussen docent
Docent
dr. H.H. Liu
Overige cursussen docent
Blok
3  (07-02-2022 t/m 22-04-2022)
Aanvangsblok
3
TimeslotC: C (MA-mid/namiddag,DI-middag, DO-ocht)
Onderwijsvorm
Voltijd
Cursusinschrijving geopendvanaf 01-11-2021 t/m 28-11-2021
AanmeldingsprocedureOsiris
Inschrijven via OSIRISJa
Inschrijven voor bijvakkersJa
VoorinschrijvingNee
Na-inschrijvingJa
Na-inschrijving geopendvanaf 24-01-2022 t/m 25-01-2022
WachtlijstJa
Plaatsingsprocedureadministratie onderwijsinstituut
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.
Toetsing
  • twee deeltoetsen. Beide deeltoetsen zijn gesloten boek.
  • practicum

Iedere toets 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.
Om aan de aanvullende toets te mogen meedoen moet de oorspronkelijke uitslag minstens 4 zijn.


Voorkennis
Het vak vereist kennis van de programmeertaal C#, zoals onderwezen bij INFOIMP Imperatief Programmeren, voor het maken van de practica.
Daarnaast veronderstellen we basiskennis over datastructuren en de looptijd-analyse van algoritmes, zoals onderwezen bij Datastructuren (INFODS).
Mocht je vragen hebben m.b.t. het voldoen van je eigen voorkennis, neem dan even contact op met de cursusco├Ârdinator.
 
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.
In het vak Algoritmiek zullen we een aantal technieken bestuderen om efficiente algoritmen te ontwikkelen.
De technieken worden geïntroduceerd aan de hand van een aantal concrete problemen.

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.

Werkvorm
Hoorcollege, werkcollege, practicum.

Literatuur
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, "Introduction to Algorithms", third edition, MIT Press / McGraw Hill, 2009.
Competenties
-
Ingangseisen
-
Verplicht materiaal
-
Werkvormen
Hoorcollege

Werkcollege

Toetsen
Eindresultaat
Weging100
Minimum cijfer6

SluitenHelpPrint
Switch to English