Automaten en berekenbaarheid

5 ECTS credits
150 u studietijd

Aanbieding 1 met studiegidsnummer 2019970BNW voor werkstudenten in het 2e semester met een verdiepend bachelor niveau.

Semester

2e semester

Inschrijving onder examencontract

Niet mogelijk

Beoordelingsvoet

Beoordeling (0 tot 20)

2e zittijd mogelijk

Inschrijvingsvereisten

'Automaten en berekenbaarheid’ opnemen houdt in dat je gelijktijdig ‘Structuur van computerprogramma's 1’ of 'Higher-Order Programming' volgt of reeds geslaagd bent voor ‘Structuur van computerprogramma's 1’ of 'Higher-Order Programming'.

Onderwijstaal

Nederlands

Faculteit

Faculteit Wetenschappen en Bio-ingenieurswetensch.

Verantwoordelijke vakgroep

Computerwetenschappen

Onderwijsteam

Ann Nowe (titularis)
Joost Vennekens

Onderdelen en contacturen

26 contacturen Hoorcollege
26 contacturen Werkvormen en Praktische Oef.
50 contacturen Zelfwerk en -studie

Inhoud

1. Syntax (formele talen):

1.1. Reguliere talen en eindige automaten: equivalentie, (non)determinisme, optimalizatie.
1.2. Contextvrije grammatica's: definities en algemene eigenschappen (b.v. normaalvormen), stapelautomaten.
1.3. Contextsensitieve grammatica's: definities en algemene eigenschappen, lineair gebonden automaten
1.4. Inleiding tot parsen.

2. Berekenbaarheid: Oplosbare en onoplosbare problemen, Theorema van Church, Turing Machines.

3. Berekenbaarheid in de context van Formele Talen.

Studiemateriaal

Digitaal cursusmateriaal (Vereist) : Automaten en berekenbaarheid, Kopieën van de transparanten van de titularis, Leerplatform
Handboek (Vereist) : An Introduction to Formal Languages and Automata, Peter Linz, 7de, Jones & Bartlett Learning, 9781284231601, 2017

Bijkomende info

Kopieën van de slides, korte samenvattingen van elke les, en gedetailleerde bewijzen zijn beschikbaar op het leerplatform.

Opgelet : De slides en/of samenvattingen zijn op zich geen voldoende studiemateriaal, de slides dienen aangevuld te worden met het verplichte handboek.

Verplicht handboek: Linz: 'An Introduction to Formal Languages and Automata,Jones & Bartlett Learning, 2017.

Aanvullend materiaal:
Inleiding in de theorie van de formele talen, V.J. Rayward-Smith
Berekenbaarheid, V.J. Rayward Smith

Leerresultaten

Algemene competenties

Herinneren:
De student kan basisbegrippen uit de cursus (zoals: reguliere talen, contextvrije talen, eindige (niet-)deterministische accepters, Turing machines, contextsensitieve grammaticas, ...) definiëren.

Begrijpen:
De student kan redeneren over de mogelijkheden en de beperkingen van formele talen zoals reguliere, context-vrije en contextsensitieve talen en de corresponderende automaten voor deze talen.
De student kan de basisbegrippen van de theorie van berekenbaarheid uitleggen.
De student kan de geziene bewijzen herconstrueren en mondeling toelichten.

Toepassen:
De student kan de geziene stellingen en technieken toepassen op nieuwe talen/automaten/grammaticas.

Analyseren & Evalueren:
De student kan ongeziene formele talen classificeren in de Chomsky hierarchie en zijn/haar classificatie beargumenteren
De student kan evalueren of een ongezien probleem tot de klasse van de (semi-)beslisbare of (semi-)berekenbare problemen behoort en zijn/haar oordeel beargumenteren.
De student kan correcte wiskundige redeneringen opstellen en foutieve wiskundige redeneringen analyseren en identificeren.

Creëren:
De student kan een wiskundig correct bewijs opstellen voor varianten van geziene eigenschappen.
De student kan een automaat/grammatica opstellen die een gegeven formele taal accepteert.

Beoordelingsinformatie

De beoordeling bestaat uit volgende opdrachtcategorieën:
Examen Mondeling bepaalt 50% van het eindcijfer

Examen Schriftelijk bepaalt 50% van het eindcijfer

Binnen de categorie Examen Mondeling dient men volgende opdrachten af te werken:

Mondeling examen theorie met een wegingsfactor 1 en aldus 50% van het totale eindcijfer.

Binnen de categorie Examen Schriftelijk dient men volgende opdrachten af te werken:

Schriftelijk oefeningen examen met een wegingsfactor 1 en aldus 50% van het totale eindcijfer.

Aanvullende info mbt evaluatie

50% oefeningen,
50% theorie

Theorie: Er is een verplicht mondeling examen. Het examen is een gesloten boek examen. Om een voldoende te behalen moet een student goed scoren op twee of drie basisvragen. De extra vraag zal het uiteindelijke cijfer vormen.

Oefeningen: Er is een verplicht schriftelijk oefeningenexamen. Dit examen is ook gesloten boek.

Beide examens worden afgenomen in de zittijd van het 2de semester.

Toegestane onvoldoende

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

Academische context