Eerste semester
Tweede semester
Beide semesters
Niet ingericht
Dit jaar
Volgend jaar
Wisselende jaren
Extern
Voorwaarden
Docenten
Onderwijstaal
Duur
Identieke opleidingsonderdelenComplexiteitstheorie (B-KUL-G0Q63B)
Uitgesloten voor examencontractDoelstellingen
Het doel van deze cursus is het bestuderen en begrijpen van een aantal complexiteitsklassen bij de theoretische analyse van computationale problemen. De student heeft inzicht in de onderlinge samenhang en robuustheid van de definities en het computationele model. De student heeft inzicht in klassen voor tijds- en ruimtecomplexiteit. De student begrijpt hoe de klassen P, NP en co-NP het begin zijn van de polynomiale-tijd-hiërarchie en het belang van de open vraag P ?= NP. De student begrijpt hoe het gebruik van willekeurige elementen resulteert in klassen zoals RP, co-RP, ZPP en BPP. De student begrijpt hoe de bewijzen werken en is in staat om zelf eenvoudige bewijzen te maken. De student is in staat om wetenschappelijke literatuur over complexiteitstheorie te begrijpen en toe te passen.
Begintermen
De cursus steunt op kennis van programmeren, logica, statistiek en wiskundige bewijsvoering. Bij twijfel de docent contacteren.
Plaats in het onderwijsaanbod
- Master in de ingenieurswetenschappen: wiskundige ingenieurstechnieken (Leuven) 120 sp.
- Master in de ingenieurswetenschappen: computerwetenschappen (Leuven) (Hoofdoptie Artificiële intelligentie) 120 sp.
- Master in de ingenieurswetenschappen: computerwetenschappen (Leuven) (Hoofdoptie Computationele informatica) 120 sp.
- Master in de wiskunde (Leuven) 120 sp.
- Master of Mathematical Engineering (Leuven) 120 sp.
Onderwijsleeractiviteiten
4 sp. Complexiteitstheorie: hoorcollege (B-KUL-G0Q63a)
Inhoud
We behandelen de volgende onderwerpen (met mogelijke aanpassingen naar andere gerelateerde complexiteitsklassen):
- Het computationeel model (Turing machines)
- De basisklassen: P, NP, co-NP, NP-complete, EXP
- Diagonalisatie en zijn grenzen
- Ruimtecomplexiteit: PSPACE, NSPACE, L, NL
- De polynomiale hiërarchie en alternerende logische formules
- Booleaanse circuits, P/poly, NC
- Algoritmen met willekeurige elementen: BPP, RP, co-RP, ZPP
- Inleiding tot benaderende oplossingen
- Inleiding tot berekeningen met reële getallen en de relatie met de Turing machine
Studiemateriaal
Diverse teksten aangeleverd door de docent en beschikbare standaardteksten (PDF).
Toelichting werkvorm
De studenten bestuderen op voorhand het lesmateriaal in detail. In de les wordt een deel van het materiaal en de bewijzen interactief behandeld. De verdere bewijzen en voorbeeldalgoritmen worden door de student verwerkt in de oefenzitting.
2 sp. Complexiteitstheorie: oefeningen (B-KUL-H0O35a)
Inhoud
Bewijzen en oefeningen per topic.
Studiemateriaal
Zelfde als hoorcollege.
Toelichting werkvorm
Tijdens de oefenzitting werken de studenten verder door de bewijzen en voorbeeldalgoritmen. Zie ook de toelichting van de werkvorm bij het hoorcollege.
Evaluatieactiviteiten
Evaluatie: Complexiteitstheorie (B-KUL-G2Q63b)
Toelichting
Het examen is een gesloten boek schriftelijk examen dat nagaat of de student de bovenstaande doelstellingen behaald heeft. Het examen peilt naar inzicht, het begrijpen van de bewijzen en het kunnen gebruiken van deze bewijstechnieken.