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. H.L. Bodlaender
Telefoon+31 30 2534409
E-mailH.L.Bodlaender@uu.nl
Docenten
Docent
dr. H.L. Bodlaender
Overige cursussen docent
Blok
3  (05-02-2018 t/m 20-04-2018)
Aanvangsblok
3
TimeslotC: MA-middag/namiddag,DI-middag, DO-ochtend
Onderwijsvorm
Voltijd
Opmerkinghttp://www.cs.uu.nl/education/vak.php?vak=INFOAL
Cursusinschrijving geopendvanaf 30-10-2017 t/m 26-11-2017
AanmeldingsprocedureOsiris
Inschrijven via OSIRISJa
Inschrijven voor bijvakkersJa
VoorinschrijvingNee
Na-inschrijvingJa
Na-inschrijving geopendvanaf 22-01-2018 t/m 23-01-2018
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.
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.
Ingangseisen
Verplicht materiaal
-
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 (aanwezigheidsplicht)
Hoorcollege

Werkcollege

Toetsen
Eindresultaat
Weging100
Minimum cijfer-

SluitenHelpPrint
Switch to English