5 ECTS credits
150 u studietijd

Aanbieding 2 met studiegidsnummer 2019971BNR voor alle studenten 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
Ja
Inschrijvingsvereisten
Studenten die dit opleidingsonderdeel opnemen, moeten geslaagd of ingeschreven zijn voor “Structuur van computerprogramma’s 1”.
Onderwijstaal
Nederlands
Faculteit
Faculteit Wetenschappen en Bio-ingenieurswetensch.
Verantwoordelijke vakgroep
Computerwetenschappen
Onderwijsteam
Ann Nowe (titularis)
Onderdelen en contacturen
26 contacturen Hoorcollege
26 contacturen Werkcolleges, practica en oefeningen
125 contacturen Zelfstudie en externe werkvormen
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, 6de, Jones & Bartlett Learning, 9781284077247, 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 studiemateriaal:

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 theorie examen met een wegingsfactor 1 en aldus 50% van het totale eindcijfer.

    Toelichting: Het examen is een gesloten boek examen. Om een voldoende te behalen moet een student goed scoren op een 2-tal basisvragen. De bijkomende vragen hebben een hogere moeilijkheidsgraad en bepalen de graad.

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.

    Toelichting: Er is een verplicht schriftelijk oefeningenexamen. Dit examen is ook geloten boek.

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 een 2-tal basisvragen. De bijkomende vragen hebben een hogere moeilijkheidsgraad en bepalen mee het cijfer.

Oefeningen: Er is een verplicht schriftelijk oefeningenexamen. Dit examen is ook geloten 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

Deze aanbieding maakt deel uit van de volgende studieplannen:
Schakelprogramma Master of Science in de ingenieurswetenschappen: computerwetenschappen: Standaard traject
Schakelprogramma Master of Science in de toegepaste informatica: Standaard traject
Voorbereidingsprogramma Master of Science in de ingenieurswetenschappen: computerwetenschappen: Traject C (Ind Ing, 61 ECTS)
Voorbereidingsprogramma Master of Science in de ingenieurswetenschappen: computerwetenschappen: Traject A (76 ECTS)
Voorbereidingsprogramma Master of Science in de ingenieurswetenschappen: computerwetenschappen: Traject B (65 ECTS)
Voorbereidingsprogramma Master of Science in de toegepaste informatica: Traject C (Ind Ing, 58 ECTS)
Voorbereidingsprogramma Master of Science in de toegepaste informatica: Traject A (58 ECTS)
Voorbereidingsprogramma Master of Science in de toegepaste informatica: Traject B (52 ECTS)