Vanwege een roosterwijziging wordt Fundamentele Informatica 3 in het
vervolg in het najaar (vijfde
semester) gegeven, voor het eerst in het najaar van 2006. Fundamentele
Informatica 2 blijft geroosterd in het derde semester (dus ook in het najaar).
Practische informatie
Docent: Rudy van Vliet
te vinden op: kamer 150 van het Snellius
telefoon: 071-527 7050
email: rvvliet@liacs.nl Opzet college: hoorcollege en werkcollege (gecombineerd) Collegetijden: maandag van 13:45 - 15:30 uur in zaal 412
en dinsdag van 13:45 - 15:30 uur in zaal 401,
van 4 september tot en met 5 december 2006.
Op maandag 2 oktober en dinsdag 3 oktober was er geen college.
Tentamens
Het tentamen van vrijdag 26 januari 2007 is nagekeken.
Iedereen heeft een halve punt cadeau gekregen.
De resulterende cijfers (inclusief eventuele bonus van de huiswerkopgaven)
zijn hier te vinden.
Je kunt je uitwerkingen ophalen bij Rudy van Vliet.
Ook het herkansingstentamen van maandag 20 augustus 2007 is nagekeken.
En opnieuw heeft iedereen een halve punt cadeau gekregen.
De resulterende cijfers
zijn hier te vinden.
Je kunt je uitwerkingen ophalen bij Rudy van Vliet.
Studielast
In afwijking van eerdere mededelingen, krijgen mensen die het tentamen halen
niet 6 EC, maar slechts 5 EC.
De studie-adviseur heeft verzekerd
dat dit geen nadelige consequenties zal hebben voor de betrokken studenten.
Huiswerkopgaven:
In de loop van het semester zijn drie huiswerkopgaven opgegeven,
waarmee je bonuspunten voor het tentamen kon verdienen.
Verdiende bonuspunten zijn alleen geldig voor het eerste-kans tentamen,
op vrijdag 26 januari 2007.
Een lijst met verdiende bonussen hangt bij de deur van kamer 150.
Als Rudy van Vliet zelf aanwezig is, kun je bij hem je uitwerkingen
met commentaar ophalen.
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:
herkennen, beslissen en rekenen met Turingmachines, niet-determinisme,
universele Turingmachines, Church-Turing These. Recursief opsombare talen
en de Chomsky hierarchie. Het stopprobleem, berekenbaarheid,(on)beslisbare
problemen.
John C. Martin,
Introduction to Languages and the Theory of Computation,
3rd edition, McGraw Hill, 2003
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 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
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 en paragraaf 7.6.2 bottom-up parsing (blz. 285-290),
en de opgaven 7.32 t/m 7.36,
paragraaf 8.2 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, met uitzondering van
details van de bewijzen van Stelling 10.2
(voor deterministische TM's moet je dit bewijs wel kennen)
en Stelling 10.12,
paragraaf 10.5, en de opgaven 10.24 t/m 10.33;
hoofdstuk 11, met uitzondering van
het bewijs van Stelling 11.11,
vb. 11.2, paragraaf 11.6 vanaf halverwege blz. 432, en de opgaven
11.17, 11.21, 11.22.
Tijdens het college van 9 oktober 2006 is de
uitwerking van een eerder behandelde opgave (een variant van
opgave 7.28.b) uitgedeeld. Ook is een algemene uitwerking van
opgave 11.12.l beschikbaar. Beide uitwerkingen vindt u hier,
als ps file
en als pdf file .
Oude tentamens:
mei 2004, ps file
augustus 2004, ps file
mei 2005, ps file
augustus 2005, ps file
januari 2007, ps file
en pdf
augustus 2007, ps file
en pdf
Het vak Fundamentele Informatica 3 wordt al enkele jaren gegeven.
De vorige keer was in het voorjaar van 2005. De website van dat jaar
vindt u hier.
Vragen en opmerkingen kunt u sturen naar:
Rudy van Vliet;
rvvliet@liacs.nl
Laatste wijziging: 9 januari 2012
- http://www.liacs.nl/home/rvvliet/fi3/fi3_nj2006.html
