Inhoud:
- Theorie van berekenbaarheid
– Turing machines
– Church-Turing thesis
– Beslisbaarheid
– Stopprobleem
– Herleidbaarheid
– Recursiestelling
- Complexiteitstheorie
– Tijdscomplexiteit en de klassen P en NP
– NP-volledigheid en de stelling van Cook-Levin
– Andere NP-complete problemen
Leerresultaten:
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.
Algemene competenties:
- 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.
All detailed and official information about the course here >
