3 ECTS credits
75 u studietijd
Aanbieding 1 met studiegidsnummer 4021170FNR voor alle studenten in het 1e semester met een gespecialiseerd master niveau.
1. Theorie van berekenbaarheid
- Herhaling: Turing machines, Beslisbaarheid en het stopprobleem
- Herleidbaarheid
- Recursiestelling
2. Complexiteitstheorie
- Tijdscomplexiteit:
+ de klassen P en NP
+ NP-volledigheid en de stelling van Cook-Levin
+ Andere NP-complete problemen
- Ruimtecomplexiteit:
+ De stelling van Savitch
+ PSPACE en PSACE-volledigheid
+ De klasses L en NL
Extra materiaal:
1. Hoofdstukken 9 en 10 van Hopcroft, J.E., Motwani, R. en J.D. Ulmann Introduction to Automata theory, Languages and Computation, 3rd edition, Addison-Wesley, 2006.
2. Delen IV en V en Appendices G{N van Rich, E. Automata, Computability and Complexity: Theory and Applications, Prentice-Hall, 2007.
3. Hofstadter, D.R. (1979) Godel, Escher, Bach: an Eternal Golden Braid, The Harvester Press, 1979.
Het algemeen doel van dit onderdeel is een introductie te geven tot de theorie van berekenbaarheid en de complexiteitstheorie en de relevantie hiervan aan te tonen voor de computerwetenschappen in het algemeen.
De beoordeling bestaat uit volgende opdrachtcategorieën:
Examen Schriftelijk bepaalt 100% van het eindcijfer
Binnen de categorie Examen Schriftelijk dient men volgende opdrachten af te werken:
Het examen is schriftelijk. Er zijn 2 theoretische vragen op 6 punten elk en 2 oefeningen op 4 punten elk. Deze oefeningen zijn gelijkaardig maar wel verschillend van de oefeningen die tijdens de cursus werden gezien.
Deze aanbieding maakt deel uit van de volgende studieplannen:
Master in de ingenieurswetenschappen: computerwetenschappen: afstudeerrichting Artificiële Intelligentie
Master in de ingenieurswetenschappen: computerwetenschappen: afstudeerrichting Multimedia
Master in de ingenieurswetenschappen: computerwetenschappen: afstudeerrichting Software Languages and Software Engineering
Master in de ingenieurswetenschappen: computerwetenschappen: afstudeerrichting Data Management en Analytics
Educatieve master in de wetenschappen en technologie: computerwetenschappen (120 ECTS, Etterbeek)