Nieuw: uitslag hertentamen 5 maart
Tentamendata:
tentamen: vrijdag 8 januari 2010, 10-13 uur
herkansing: vrijdag 5 maart 2010, 10-13 uur
TENTAMENSTOF
is als behandeld tijdens de colleges,
i.h.b. uit het boek van John Martin, hoofdstuk 7, paragrafen 8.2 en 8.3,
hoofdstuk 9, 10 en 11,
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).
Dus, samenvattend:
Hoofdstuk 7, met uitzondering van
de 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 de details van het bewijs van Stelling 8.4;
paragraaf 8.3.
Hoofdstuk 9
met uitzondering van de details van de bewijzen van Stellingen 9.1 en 9.2.
Hoofdstuk 10 met uitzondering van de details van de bewijzen van
Stelling 10.2 (voor deterministische TM's moet je dit bewijs wel kennen) en
Stelling 10.12.
Hoofdstuk 11, met uitzondering van de bewijzen van Stelling 11.11,
Lemma 11.2, Stelling 11.14 en Lemma 11.3.
Oude tentamens
januari 2008, pdf file
uitwerking januari 2008,
pdf file
maart 2008, pdf file
januari 2009, pdf file
uitwerking januari 2009,
pdf file
maart 2009, pdf file
ALGEMENE INFORMATIE
In 2009-2010 is FI3 hetzelfde vak als in 2008-2009; Jetty Kleijn (kleijn at liacs.nl) is de docent en Julia Dmitrieva (jdmitrie at liacs.nl) is de assistent.
FI3 is een verplicht vak voor studenten Informatica die geen minor doen.
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.
Voorkennis: Fundamentele Informatica 1 en Fundamentele Informatica 2
Fundamentele Informatica 2 en Fundamentele Informatica 3 vormen het vervolg op Fundamentele Informatica 1 dat in het eerste jaar wordt gegeven. De nadruk bij FI2 en FI3 ligt respectievelijk op formele talen en berekenbaarheid.
Beide vakken gebruiken het boek:
John C. Martin,
Introduction to Languages and the Theory of Computation,
3rd edition, McGraw Hill, 2003
FI3 wordt in 2009 gegeven op
maandag en dinsdag
vanaf DINSDAG 1 SEPTEMBER
tot en met dinsdag 1 december.
Tijd: 13.45-15.30
Plaats: 412
Werkvorm: hoorcollege met werkgroep (niet noodzakelijk om en om!)
Tentamen: schriftelijk
Data:
tentamen: vrijdag 8 januari 2010, 10-13 uur
herkansing: vrijdag 5 maart 2010, 10-13 uur
UITSLAG tentamen 5 maart 2010
0752975 6.5
0601977 6
0231347 2
0639877 7.5
0379786 6
0404659 5
Vragen en opmerkingen kunnen worden gestuurd naar: kleijn(at)liacs.nl