Automata and Complexity

Doel vak

Het eerste deel van de cursus, over automaten en talen, behandelt de concepten van formele taal, grammatica en automaat. Twee soorten talen komen aan bod: reguliere en contextvrije talen. Reguliere talen in de vorm van reguliere expressies zijn alomtegenwoordig in de informatica. Ze worden gebruikt in zoekopdrachten en tekstmanipulatie.

Contextvrije talen en grammatica's (bijvoorbeeld de Backus-Naur-vorm) zijn de gangbare standaarden voor het beschrijven van programmeertalen. We bespreken ook parseeralgoritmen om te bepalen of een gegeven tekenreeks zich in een contextvrije taal bevindt.

De automaattheoretische tegenhangers voor reguliere en contextvrije talen zijn eindige automaten en de krachtigere pushdown-automaten.

De studenten leren:

• eindige automaten ontwerpen en reguliere expressies maken voor een gegeven reguliere taal, [Kennis en begrip] [Toepassen van kennis en begrip]
• algoritmen toepassen om te vertalen tussen eindige automaten, rechtslineaire grammatica's en reguliere expressies, [Kennis en begrip] [Toepassen van kennis en begrip]
• algoritmen toepassen om automaten deterministisch en minimaal te maken, [Kennis en begrip] [Toepassen van kennis en begrip]
• pushdown-automaten ontwerpen en contextvrije grammatica's maken voor een gegeven contextvrije taal, [Kennis en begrip] [Toepassen van kennis en begrip]
• algoritmen toepassen om te vertalen tussen pushdown-automaten en contextvrije grammatica's, [Kennis en begrip] [Kennis en begrip toepassen]
• Gebruik pomplemma's om te redeneren of een taal regulier of contextvrij is. [Kennis en begrip toepassen] [Oordelen vellen]
• Pas algoritmen toe voor het ontleden van contextvrije talen. [Kennis en begrip] [Kennis en begrip toepassen]

In het tweede deel van de cursus, over berekenbaarheidstheorie, is de centrale vraag: welke berekeningen kunnen op een computer worden uitgevoerd? Om over berekenbaarheid te redeneren, introduceren we het wiskundige model van Turingmachines en bespreken we de Church-Turing-these. We bespreken voorbeelden van onbeslisbare problemen: het stopprobleem en het Post-correspondentieprobleem. Er wordt aangetoond hoe de onbeslisbaarheid van nieuwe problemen kan worden aangetoond door reductie van een bekend onbeslisbaar probleem. Tot slot bespreken we een classificatie van beslisbare/berekenbare problemen in belangrijke complexiteitsklassen, met name P-, NP- en NP-complete problemen, samen met de bijbehorende reductieargumenten.

De studenten leren:

• redeneren of een gegeven probleem beslisbaar (berekenbaar) of onbeslisbaar (niet berekenbaar) is, [Oordelen vellen]
• de classificatie van beslisbare problemen in de complexiteitshiërarchie (bijv. P, NP, EXP) te begrijpen, en [Kennis en begrip]
• redeneren over de complexiteit van een probleem door middel van reductie naar/van problemen met bekende complexiteit. [Oordelen vellen] [Communicatie] [Vaardigheden voor levenslang leren]

Inhoud vak

Deze cursus behandelt automaten, formele talen en berekenbaarheidstheorie.

De student maakt kennis met belangrijke begrippen en algoritmen met betrekking tot formele talen, automaten, grammatica's, compilers, berekenbaarheid en complexiteit.

Deze cursus behandelt fundamentele vragen in de informatica:

• Wat kan er berekend worden? Wat zijn de beperkingen van wat computers kunnen doen?
• Hoeveel tijd en geheugen is er nodig om een ​​probleem op te lossen?
• Wat is een (programmeer)taal?
• Hoe kunnen talen door computers (automaten) herkend worden?
• Welke problemen kunnen door welke soorten automaten opgelost worden?

Deze cursus brengt het belangrijke idee over dat bepaalde problemen niet door computers opgelost kunnen worden. Een informaticus moet kunnen redeneren of een gegeven probleem berekenbaar (beslisbaar) is of niet.

Bovendien moet een computerwetenschapper in staat zijn om te beredeneren tot welke taal-/complexiteitsklasse een bepaald probleem behoort, en dus welke soorten automaten/algoritmen nodig zijn om het probleem aan te pakken.

Aanvullende informatie onderwijsvormen

4 uur colleges per week; 4 uur oefenlessen per week.

De beoordeling in deze cursus is gebaseerd op een digitaal eindexamen. Er geldt een geen AI-beleid. Dat wil zeggen dat de beoordeling volledig zonder AI-ondersteuning in een gecontroleerde omgeving wordt afgenomen, zodat studenten uitsluitend kunnen vertrouwen op hun bestaande kennis, begrip en vaardigheden. De huiswerkopdrachten worden niet in een gecontroleerde omgeving gemaakt. Desondanks verwachten we dat de oplossingen voor de huiswerkopdrachten uw eigen werk zijn en niet door AI worden gegenereerd. U mag echter wel vrijelijk AI gebruiken voor het bestuderen en leren van de concepten van deze cursus.

Toetsvorm

Het huiswerk is verplicht om in aanmerking te komen voor het examen (70% van de huiswerkpunten is vereist om te mogen deelnemen aan het examen). Bij een score van minimaal 90% van de huiswerkpunten wordt 0,5 bonuspunt toegekend voor het eindcijfer. Aan het einde van de cursus is er een eindexamen.

Het eindcijfer is het cijfer van het eindexamen plus de eventueel behaalde 0,5 bonuspunten voor het huiswerk. (De bonuspunten worden alleen toegekend aan studenten die het examen met een cijfer van minimaal 5,5 halen.)

Er is geen mogelijkheid tot herkansing van het huiswerk.

Literatuur

Peter Linz, Een inleiding tot formele talen en automaten, Jones & Bartlett, 4e of 5e editie

Aanvullende informatie doelgroep

BSc Informatica (3e jaar)
BSc Kunstmatige Intelligentie (3e jaar)
BSc Wiskunde (keuzevak)