Algoritmiek
Inhoud
Deze cursus gaat over het ontwerpen van algoritmes. Je leert basis datastructuren en verschillende strategieën om abstracte problemen op te lossen (namelijk greedy algoritmen, verdeel-en-heers en dynamisch programmeren). Je leert deze strategieën te gebruiken om algoritmen te ontwerpen, maar ook om de correctheid van het gemaakt algoritme te bewijzen, en de tijd- en ruimtecomplexiteit van het algoritme te analyseren. Het vak sluit af met een in de informatica zeer bekende theorie over wat voor soort problemen efficiënt (polynomiaal) op te lossen zijn.
Doelen
- De looptijd van een algoritme/programmeercode analyseren.
- De correctheid van een algoritme bewijzen.
- Standaard datastructuren implementeren.
- Standaard algoritmen implementeren.
- Algoritmische oplossingen ontwerpen met behulp van standaard algoritmische strategieën.
- Complexiteitseigenschappen van abstracte problemen bewijzen.
Voorkennis
- Kennis van en ervaring met programmeren in Java of Python.
- Kennis van standaard bewijsstrategieën.
Materialen
- Lesmateriaal in de online lesomgeving.
- Eventueel het boek Algorithm Design van Jon Kleinberg & Éva Tardos (2005), Pearson.
Werkwijze
Een serie bijeenkomsten met deels interactieve colleges en deels onder begeleiding werken aan oefenopdrachten. Thuis kunnen de oefenopdrachten worden afgemaakt, en het college van de week erna worden voorbereid.
Toetsing
Het cijfer wordt bepaald door een schriftelijk tentamen in de laatste bijeenkomst. Om een geldig eindcijfer te halen moeten alle programmeeropdrachten correct zijn gemaakt (alle tests moeten slagen) of als voldoende zijn gemarkeerd. Een bonus van één punt kan worden verkregen door in de op één na laatste bijeenkomst een les te geven binnen het vakgebied van algoritmiek.
Docent
Ivo van Kreveld is voltijds docent in de Bachelor informatica binnen de leerlijn algoritmiek aan de TU Delft.
