Geen FI3 in 2005-2006
Vanwege een roosterwijziging zal Fundamentele Informatica 3 in het studiejaar
2005-2006 NIET worden gegeven. Voortaan wordt het vak 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).
NIEUW: Tentamen 12 januari.
Docent:
Jetty Kleijn
Assistent:
Richard Velden
Doelstelling:
Vertrouwd maken met formele technieken binnen de informatica en hun
toepassingen. Naast vaardigheid verwerven in constructie en analyse van talen,
grammatica's en automaten wordt beoogd de studenten enig abstractieniveau bij
te brengen wat betreft het lezen en geven van formele definities, constructies
en bewijzen.
Inhoud:
Inleiding formele talen. Reguliere talen: reguliere expressies,
eindige automaten; niet-determinisme en de stelling van Kleene; criteria voor
regulariteit (o.a. pomplemma). Context-vrije talen:
grammatica's, dubbelzinnigheid, normaalvormen,
structurele eigenschappen (pomplemma's), afsluitingseigenschappen en
beslissingsproblemen.
voorkennis: Fundamentele Informatica 1
literatuur: John C. Martin,
Introduction to Languages and the Theory of Computation,
3rd edition, McGraw Hill, 2003
NB: dit boek zal ook worden gebruikt bij het college
Fundamentele Informatica 3
In aanvulling op het boek kan je
hier een ps file vinden met een
beschrijving van de methode van Brzozowski en McCluskey horend bij Theorem 4.5.
Opgave 4.38 die naar Theorem 4.5 verwijst, kan nu beter
(efficienter) worden gemaakt met behulp van deze methode.
werkvorm: hoorcollege met werkgroep
collegetijden: maandag, 13.45-15.30 uur (zaal 403); woensdag, 9.00-10.45 (zaal 401)
TENTAMENSTOF 2005-2006
Uit het boek van John Martin, paragraaf 1.5, hoofdstuk 3 t/m hoofdstuk 6 en hoofdstuk 8
met de bijbehorende opgaven (bekijk ook de "more challenging" opgaven).
Part I: Mathematical Notation and Techniques,
bestaande uit de hoofdstukken 1 en 2,
wordt verder bekend verondersteld,
d.w.z. alle notaties en technieken, met name inductie, moeten kunnen worden gebruikt!
Opmerkingen:
Bij hoofdstuk 4 gebruiken we niet het L(p,q,k) algoritme uit het bewijs van
Theorem 4.5 (zie ook Example 4.10 en opgave 4.38) om een reguliere expressie te maken bij een
gegeven eindige automaat, maar de methode van Brzozowski en McCluskey (zie de ps
file hierboven genoemd).
In hoofdstuk 6 vervallen de bewijzen van Theorems 6.3 en 6.4.
Bij hoofdstuk 8 hoort het gebruiken van begrippen uit hoofdstuk 7, met name
pushdown automaten (PDA) en deterministisch context-vrije talen (DCFL),
niet tot de stof.
NB1: Bewijs Theorem 8.3 kan net zo goed onder verwijzing naar context-vrije
grammatica's worden gegeven.
NB2: Theorem 8.4 hoort wel bij de stof, maar zonder bewijs; ook de tekst na dat
bewijs tot en met het eind van paragraaf 8.2 vervalt.
NB3: Sla de opgaven 8.4, 8.5 e,f,g, 8.7, 8.12, 8.13 over.
Er is geen apart vragenuur.
Voor een persoonlijke afspraak kan je tot uiterlijk donderdag 5
januari mailen naar de docent.
Daarna is zij afwezig en slechts sporadisch via email te bereiken.
Zie onderaan voor uitwerkingen van geselecteerde opgaven.
tentamen: donderdag 12 januari 2006, 14-17 uur
herkansing: maandag 7 augustus 2006, 14-17 uur
tentamen: schriftelijk
Oude tentamens
januari 2004, ps file
augustus 2004, ps file
januari 2005, ps file
augustus 2005, ps file
januari 2006, ps file
Uitwerkingen van opgaven
bij hoofdstuk 1 als
ps file
en als
pdf file
bij hoofdstuk 3 als
ps file
en als
pdf file
bij hoofdstuk 4 als
ps file
en als
pdf file
bij hoofdstuk 5 als
ps file
en als
pdf file
bij hoofdstuk 6 als
ps file
en als
pdf file
bij hoofdstuk 8 als
ps file
en als
pdf file .
Vragen en opmerkingen kunnen worden gestuurd naar: kleijn@liacs.nl.