Algoritmen en complexiteit

Studiegidsnr:1001WETALC
Vakgebied:Informatica
Academiejaar:2017-2018
Semester:2e semester
Inschrijvingsvereisten:Studenten INFORMATICA: min. 8/20 voor Discrete wiskunde, Talen en automaten en Gegevensabstractie en -structuren.
Studenten WISKUNDE: min. 8/20 voor Machines en berekenbaarheid.
Contacturen:60
Studiepunten:6
Studiebelasting:168
Contractrestrictie(s):Geen contractrestrictie
Instructietaal:Nederlands
Examen:2e semester
Lesgever(s)Dirk Janssens

Deze cursusinformatie is bedoeld om de student te ondersteunen bij het verwerken van de leerstof

3. Inhoud *

In het eerste deel van de cursus worden verschillende modellen van berekenbaarheid beschreven: RAM, RASP, Turing Machine. Deze modellen kunnen gezien worden als wiskundige talen voor het uitdrukken van algoritmen; ze verschillen in de keuze van gegevensstructuren en elementaire operaties.

Op basis van die modellen worden vervolgens de begrippen tijds- en ruimtecomplexiteit bestudeerd; met name wordt de complexiteit van een aantal sorteer- en andere algoritmen afgeleid.  Er wordt bekeken in hoeverre de complexiteit afhangt van het gekozen berekeningsmodel. Daarna wordt er ingegaan op het begrip "polynomiale complexiteit", inclusief NP-problemen, en op het verband tussen tijds- en plaatscomplexiteit.  Van een aantal concrete problemen wordt bewezen dat ze NP-compleet zijn. Tenslotte wordt ook aandacht besteed aan gerandomizeerde en gedistribueerde algoritmen.