3 ECTS credits
75 u studietijd

Aanbieding 1 met studiegidsnummer 4021170FNR voor alle studenten in het 1e semester met een gespecialiseerd master niveau.

Semester
1e semester
Inschrijving onder examencontract
Niet mogelijk
Beoordelingsvoet
Beoordeling (0 tot 20)
2e zittijd mogelijk
Ja
Onderwijstaal
Nederlands
Faculteit
Faculteit Wetenschappen en Bio-ingenieurswetensch.
Verantwoordelijke vakgroep
Computerwetenschappen
Onderwijsteam
Bart Bogaerts (titularis)
Onderdelen en contacturen
18 contacturen Hoorcollege
18 contacturen Werkcolleges, practica en oefeningen
Inhoud

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

Bijkomende info


Dit vak is gebaseerd op het boek
Introduction to the theory of computation (third edition) van Michael Sipser

 

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.

Leerresultaten

Algemene competenties

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.

  • Kennis en inzicht: De student heeft inzicht in welke problemen en functies in principe oplosbaar en berekenbaar zijn en welke niet. Zij/hij begrijpt de complexiteit van oplosbare problemen en berekenbare functies en kent de verschillende complexiteitsklassen.
  • Toepassing en inzicht: De student is in staat om de berekenbaarheid en de complexiteit van problemen te bepalen die zij/hij ontmoet in de praktijk.
  • Oordelingsvorming: De student begrijpt de verschillende technieken die bestaan om (on)berekenbaarheid aan te tonen en in het geval van een berekenbaar probleem te bepalen tot welke complexiteitsklasse dit probleem behoort.
  • Communicatie: De student is in staat om met experten te communiceren wanneer het gaat over de aspecten van berekenbaarheid en complexiteitsklasse van een probleem.
  • Leervaardigheden: De student kan een probleem exact formuleren, het bewijs hiervan geven en voldoende creativiteit aan de dag leggen om dit bewijs te vinden.

Beoordelingsinformatie

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:

  • Examen schriftelijk met een wegingsfactor 1 en aldus 100% van het totale eindcijfer.

Aanvullende info mbt evaluatie

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.

Toegestane onvoldoende
Kijk in het aanvullend OER van je faculteit na of een toegestane onvoldoende mogelijk is voor dit opleidingsonderdeel.

Academische context

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)