|
Begrip van berekenbaarheidstheorie en complexiteitstheorie.
|
|
Deze cursus maakt deel uit van het verdiepingspakket Reasoning and Language.
In de cursus worden de beginselen van berekenbaarheidstheorie en de complexiteitstheorie behandeld.
Eindige automaten worden geïntroduceerd en hun belang voor de informatica en de linguïstiek wordt besproken. Automaten met beperkt geheugen (push-down automaten) en hun verband met context-vrije grammatica’s worden behandeld.Turing machines als volledig model van berekenbaarheid worden uitgebreid bestudeerd. Op grond van dit model worden talen ingedeeld in een hiërarchie van berekenbaarheid, waarbij de beslisbare talen het begin van de hiërarchie vormen. Turings beroemde diagonalisatie argument dat aantoont dat er onbeslisbare talen zijn wordt behandeld, en er wordt aangetoond hoe op grond daarvan vele andere onbeslisbaarheidsresultaten verkregen kunnen worden. Ook de universele Turing machine en de Church-Turing These komen aan bod.
Het tweede deel van de cursus richt zich op complexiteitstheorie, dat wil zeggen op de studie van de complexiteit van beslisbare talen. De beroemde tijdscomplexiteitsklassen P en NP worden geïntroduceerd, alsmede de ruimtecomplexiteitsklasse PSPACE. Er wordt uitgelegd wat polynomiale reductie is en wat het betekent als een taal volledig is met betrekking tot een complexiteitsklasse. Saillante voorbeelden van talen die NP-volledig zijn worden behandeld, zoals SAT en CLIQUE.
|
 |
|