In het collegejaar 2012-2013 verandert de inhoud van het vak.
We behandelen dan niet meer hoofdstuk 5-9, maar
(globaal) hoofdstuk 7-10 van het boek.
Fundamentele Informatica 3 is een derdejaars vak binnen de bachelor
Informatica aan de Universiteit Leiden.
Met ingang van het collegejaar 2010-2011 wordt het in het voorjaar (zesde
semester) gegeven. Fundamentele
Informatica 2 blijft geroosterd in het derde semester (dus in het najaar).
Practische informatie
Docent: Rudy van Vliet
te vinden op: kamer 124 van het Snellius
telefoon: 071-527 5777
email: rvvliet(at)liacs.nl
Op de homepage
van de docent kunt u zien of hij op zijn werk te bereiken is.
Assistent: Wouter Duivesteijn Opzet college: hoorcollege en werkcollege Collegetijden:
hoorcollege maandag van 13:45 - 15:30 uur in zaal 403 van Rudy van Vliet
werkcollege dinsdag van 13:45 - 15:30 uur in zaal 403
van Wouter Duivesteijn
van maandag 6 februari tot en met dinsdag 15 mei 2012,
met uitzondering van maandag 9 april (tweede paasdag)
en maandag 30 april (koninginnedag).
Tentamens
Er zijn twee tentamens geweest: Eerste tentamen: maandag 11 juni 2012, 10:00-13:00.
Dit tentamen is onderaan deze pagina terug te vinden.
Het tentamen is nagekeken. Omdat het tentamen nogal lang was,
zijn de punten voor de huiswerkopgaven gewoon bij het tentamencijfer
opgeteld (in plaats van bij 90% van het tentamencijfer).
Je vindt de resulterende eindcijfers
hier.
De eigen uitwerkingen kunnen worden opgehaald bij de docent.
Hertentamen: maandag 20 augustus 2012, 10:00-13:00.
Dit tentamen is onderaan deze pagina terug te vinden.
Ook dit hertentamen is nagekeken.
Je vindt de cijfers, inclusief de resulterende eindcijfers,
hier.
De eigen uitwerkingen kunnen worden opgehaald bij de docent.
Op vrijdagmiddag 8 juni 2012 was er een vragenuur voor het tentamen.
Hierbij beantwoordde de docent
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, beslissen en rekenen met Turingmachines, niet-determinisme,
universele Turingmachines, Church-Turing These.
Recursief opsombare talen, de Chomsky hierarchie.
Het stopprobleem, berekenbaarheid, (on)beslisbare problemen.
John C. Martin,
Introduction to Languages and the Theory of Computation,
4th edition,
McGraw-Hill, 2011 (dus niet meer 3rd 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 wordt
behandeld uit hoofdstuk 5, paragraaf 6.2 en 6.3 en hoofdstuk 7-9 van het
boek van John Martin,
met de bijbehorende opgaven.
Opmerkingen:
Begrippen en notaties behandeld bij Fundamentele Informatica 2 worden bekend
verondersteld; notaties en technieken, met name inductie,
uit het eerste hoofdstuk moeten kunnen worden gebruikt!
Let op: de stof uit hoofdstuk 6 die bij FI2
is overgeslagen omdat hoofdstuk 5 niet was behandeld, hoort nu WEL tot de
tentamenstof; het gaat
met name om de plaatsen waar wordt verwezen naar
stapel automaten (PDAs) en deterministisch context-vrije talen (DCFLs).
Een compleet overzicht van de tentamenstof,
inclusief een verwijslijst tussen de vierde en de derde editie
van het boek van John Martin, vindt u
hier
(nu ook met opgaven in de vierde editie).
Behandelde stof, opgaven en slides
Voor wie door omstandigheden een hoorcollege of werkcollege heeft moeten
missen, houden we per week bij welke stof en opgaven
we hebben behandeld.
Behandeld tijdens het
hoorcollege.
(bijgewerkt tot en met 14 mei 2012).
Behandeld tijdens het
werkcollege
(bijgewerkt tot en met 15 mei 2012,
en inclusief uitslagen alle huiswerkopgaven.
).
Ook de slides die tijdens het college gebruikt (zouden moeten...) zijn,
zijn nog te bekijken.
N.B.: om gemakkelijk naar eerdere definities/resultaten/plaatjes te
kunnen verwijzen tijdens het college, worden slides regelmatig hergebruikt.
Er zitten dus nogal wat dubbele slides bij.
Maandag 14 mei 2012,
slides college 15,
en desgewenst een
kleine versie,
om zuinig af te drukken.
Slide nr. 29 biedt een mooi overzicht van onbeslisbare beslissingsproblemen,
en hoe we de onbeslisbaarheid hebben vastgesteld.
Antwoorden bij opgaven
Bij de opgaven in de
derde editie van het boek
was een flink aantal nette uitwerkingen beschikbaar.
Een deel daarvan is voor het vak Fundamentele Informatica 2
omgeschreven naar de vierde editie.
De rest is inmiddels ook omgeschreven naar de vierde editie!
Antwoorden bij opgaven uit
hoofdstuk 5 van vierde editie
(komt overeen met hoofdstuk 7 van derde editie, maar opgavenummering
komt natuurlijk niet overeen).
Antwoorden bij opgaven uit
hoofdstuk 6 van vierde editie
(komt overeen met hoofdstuk 8 van derde editie, maar opgavenummering
komt natuurlijk niet overeen).
Antwoorden bij opgaven uit
hoofdstuk 7 van vierde editie
(komt overeen met hoofdstuk 9 van derde editie, maar opgavenummering
komt natuurlijk niet overeen).
Antwoorden bij opgaven uit
hoofdstuk 8 van vierde editie
(komt overeen met hoofdstuk 10 van derde editie, maar opgavenummering
komt natuurlijk niet overeen).
Antwoorden bij opgaven uit
hoofdstuk 9 van vierde editie
(komt overeen met hoofdstuk 10 van derde editie, maar opgavenummering
komt natuurlijk niet overeen).
Heb je een derde editie van het boek, dan kun je de uitwerkingen
volgens de nummering van die editie vinden op de website van
Fundamentele Informatica 3, voorjaar 2011.
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_vj2012/
