|
|
 |
Fundamentele Informatica 2, najaar 2009
Marcello Bonsangue
Fundamentele Informatica 2 is het vervolg op het eerstejaars vak
Fundamentele Informatica 1. De doelstelling is het 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.
De nadruk van Fundamentele Informatica 2 ligt op formele talen, met
het accent op reguliere talen (reguliere expressies, eindige automaten;
niet-determinisme en de stelling van Kleene; criteria voor regulariteit)
en context-vrije talen (grammatica's, dubbelzinnigheid, normaalvormen,
structurele eigenschappen, bv. pomplemma's, afsluitingseigenschappen
en beslissingsproblemen).
Studenten worden geevalueert op basis van een schriftelijk tentamen
op Maandag 11 januari 2010 van 14:00 t/m 17:00 uur (zaal 174 and 401). Het
herkansing is op Maandag 23 augustus 2010 van 14:00 t/m 17:00 uur (zaal t.b.a.).
| Werkvorm: |
hoorcollege met werkgroep |
| Collegetijden: |
Dinsdag 11:15 – 13:00, zaal WI 403 |
| |
Dinsdag 13:45 – 15:30, zaal WI 403 (werkcollege) |
| (Werk)college rooster: |
September 1, 8, 15, 22, 29
Oktober 6, 13, 20, 27
November 3, 10, 17, 24
|
|
|
|
|
| Doelgroep: |
Bachelor Informatica - 2e jaar
|
|
|
| Studiepunten: |
5 ECTS |
|
|
| 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 vinden
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.
|
|
|
| Opmerkingen: |
Het hoorcollege wordt in het Engels gegeven |
|
|
| Collegestof: |
|
|
|
| Bibliography: |
[Mar03] John C. Martin, Introduction to Languages
and the Theory of Computation, 3rd edition, McGraw Hill, 2003.
|
|
|
| Tentamenstof: |
Uit het boek van John Martin, paragraaf 1.5, hoofdstuk 3 t/m 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 .pdf
file hierboven genoemd).
In hoofdstuk 6 vervallen de bewijzen van Theorems 6.3 en 6.4.
In hoofdstuk 7 vervallen de bewijzen van Theorems 7.1 en 7.2. Verder,
de tekst na bewijs van Theorem 7.2 tot en met het eind van de hoofdstuk 7 vervalt
Bij hoofdstuk 8 Theorem 8.3 kan net zo goed onder verwijzing naar context-vrije
grammatica's worden gegeven. verder 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. Sla de opgaven 8.4, 8.5 e,f,g, 8.7, 8.12, 8.13 over.
|
|
|
|
