		Universiteit Leiden
Fundamentele Informatica 3, voorjaar 2011

Laatste nieuws

Dit is nog de site van het vak voor voorjaar 2011.
Er is inmiddels een opgeschoonde site, voor voorjaar 2012.

Vanwege een roosterwijziging wordt Fundamentele Informatica 3 in het vervolg in het voorjaar (zesde semester) gegeven, voor het eerst in het voorjaar van 2011. Fundamentele Informatica 2 blijft geroosterd in het derde semester (dus in het najaar).

Practische informatie

Docent: Rudy van Vliet
te vinden op: kamer 128 van het Snellius
telefoon: 071-527 7903
email: rvvliet(at)liacs.nl
Assistent: Wouter Duivesteijn
Opzet college: hoorcollege en werkcollege
Collegetijden: hoorcollege maandag van 13:45 - 15:30 uur in zaal 405 van Rudy van Vliet
werkcollege dinsdag van 13:45 - 15:30 uur in zaal 412 van Wouter Duivesteijn
van maandag 31 januari tot en met dinsdag 3 mei 2011, met uitzondering van dinsdag 8 februari (dies van de universiteit) en maandag 25 april (tweede paasdag).

Tentamens

Er zijn twee tentamens geweest:
Eerste tentamen: maandag 6 juni 2011, 10:00-13:00. De eindcijfers van dit tentamen (inclusief huiswerkopgaven) zijn bekend. U vindt ze hier . Omdat het tentamen vrij lang was, hebben we bij alle tentamencijfers een half punt opgeteld. De uitwerkingen van de studenten (inclusief opmerkingen van de docent) zijn op te halen bij de docent, kamer 128 van het Snellius.
Hertentamen: maandag 8 augustus 2011, 10:00-13:00. De eindcijfers van dit hertentamen (inclusief huiswerkopgaven) zijn bekend. U vindt ze hier . De uitwerkingen van de studenten (inclusief opmerkingen van de docent) zijn op te halen bij de docent, kamer 128 van het Snellius.

Op woensdag 1 juni 2011 was er een vragenuur. Hierbij beantwoordde de docent alle vragen die opgekomen waren tijdens het leren voor het tentamen.

Studielast

Met het behalen van dit vak verdient u 6 EC. Het niveau van het vak wordt aangeduid als `300'.

Huiswerkopgaven

In de loop van het semester zijn drie huiswerkopgaven opgegeven. Hiermee kun je 1 punt voor het tentamen verdienen. Met het tentamen zelf kun je dan nog 9 punten verdienen.
Je dient de huiswerkopgaven individueel te maken. Indien geconstateerd wordt dat er (teveel) is samengewerkt, wordt in principe het verdiende puntenaantal gedeeld door het aantal betrokken studenten.
Huiswerkopgaven dienen uiterlijk twee weken na publicatie ingeleverd te worden bij Wouter Duivesteijn. Haal je die deadline niet, maar lever je ze wel binnen (in totaal) vier weken in, dan kun je nog de helft van de punten verdienen. Daarna inleveren levert geen punten meer op.

Doelstelling

Verwerven van inzicht in de mogelijkheden en beperkingen van computers (algoritmes). Kennismaken met fundamentele inzichten die ten grondslag liggen aan de informatica als wetenschappelijke discipline.

Inhoud

Context-vrije talen: grammatica's en stapelautomaten, determinisme, parsing.
De Turingmachine als algemeen model voor berekenbaarheid: accepteren, herkennen en rekenen met Turingmachines, niet-determinisme, universele Turingmachines, Church-Turing These.
Recursief opsombare talen, de Chomsky hierarchie.
Het stopprobleem, berekenbaarheid, (on)beslisbare problemen.

Voorkennis

Fundamentele Informatica 1 en Fundamentele Informatica 2

Literatuur

John C. Martin, Introduction to Languages and the Theory of Computation, 3rd edition, McGraw-Hill, 2003 (dus niet 4th edition)
NB: dit boek wordt ook gebruikt bij het college Fundamentele Informatica 2

Tentamenstof

De tentamenstof is in grote lijnen

de stof die tijdens de colleges is behandeld uit hoofdstuk 7, paragraaf 8.2 en 8.3 en hoofdstuk 9-11 van het boek van John Martin,
met de bijbehorende opgaven (bekijk ook de "more challenging" opgaven).

Opmerkingen: Begrippen en notaties behandeld bij Fundamentele Informatica 2 worden bekend verondersteld; notaties en technieken, met name inductie, uit de eerste twee hoofdstukken moeten kunnen worden gebruikt!
Let op: de stof uit hoofdstuk 8 die bij FI2 is overgeslagen omdat hoofdstuk 7 niet was behandeld, hoort nu WEL tot de tentamenstof; het gaat met name om de plaatsen waar wordt verwezen naar pushdown automaten (PDA) en deterministisch context-vrije talen (DCFL).
Om het allemaal op een rijtje te zetten, de tentamenstof is:

hoofdstuk 7, met uitzondering van
- details van de bewijzen van Stelling 7.2 en Stelling 7.4,
- vb. 7.11,
- paragraaf 7.6.2 bottom-up parsing,
- en de opgaven 7.32 t/m 7.36;
paragraaf 8.2 en paragraaf 8.3 met de opgaven 8.5 e,f,g, 8.7, 8.12, 8.13, 8.19, 8.20 8.21, 8.22, 8.24, 8.25, met uitzondering van
- details van het bewijs van Stelling 8.4;
hoofdstuk 9;
hoofdstuk 10;
hoofdstuk 11, met uitzondering van
- het bewijs van Stelling 11.11,
- vb. 11.2,
- paragraaf 11.6 vanaf halverwege blz. 432 (alleen formulering van stelling 11.15 moet je nog wel kennen)
- en de opgaven 11.17, 11.22.

Behandelde stof en opgaven

Voor wie door omstandigheden een hoorcollege of werkcollege heeft moeten missen, hebben we per week bijgehouden welke stof en opgaven we hebben behandeld.

Behandeld tijdens het hoorcollege.
Behandeld tijdens het werkcollege (inclusief cijfers alle huiswerkopgaven!)

Antwoorden bij opgaven

Van een deel van de opgaven uit het boek zijn nette uitwerkingen beschikbaar. Deze vindt u hieronder:

Antwoorden bij opgaven uit hoofdstuk 7 en (met name eind) hoofdstuk 8
Antwoorden bij opgaven uit (begin) hoofdstuk 8
Antwoorden bij opgaven uit hoofdstuk 9
Antwoorden bij opgaven uit hoofdstuk 10
Antwoorden bij opgaven uit hoofdstuk 11

Oude tentamens

januari 2009, pdf file
uitwerking januari 2009, pdf file
maart 2010, pdf file
juni 2011, pdf file
augustus 2011, pdf file

Vragen en opmerkingen kunt u sturen naar:
Rudy van Vliet; rvvliet(at)liacs.nl
Laatste wijziging: 4 augustus 2015 - http://www.liacs.leidenuniv.nl/~vlietrvan1/fi3/fi3_vj2011/

Fundamentele Informatica 3, voorjaar 2011