Alle drie huiswerkopgaven zijn nagekeken. Zie verderop voor de uitslagen.
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 gepland: Eerste tentamen: maandag 11 juni 2012, 10:00-13:00.
Hertentamen: maandag 20 augustus 2012, 10:00-13:00.
Wellicht wordt er enkele dagen voor het eerste tentamen nog
een vragenuur belegd. Hierbij beantwoordt de docent
alle vragen die opgekomen zijn 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 worden 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.
Inmiddels zijn alle huiswerkopgaven beschikbaar:
Huiswerkopgave 1
(gepubliceeerd: dinsdag 21 februari 2012;
uiterste inleverdatum: dinsdag 6 maart 2012, 13:45)
Huiswerkopgave 2
(gepubliceeerd: maandag 12 maart 2012;
uiterste inleverdatum: dinsdag 27 maart 2012, 13:45)
Huiswerkopgave 3
(gepubliceeerd: dinsdag 3 april 2012;
uiterste inleverdatum: dinsdag 17 april 2012, 13:45)
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).
Om het allemaal op een rijtje te zetten, de tentamenstof is:
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
3e editie van het boek
was een flink aantal nette uitwerkingen
Deze vindt u hieronder:
Vragen en opmerkingen kunt u sturen naar:
Rudy van Vliet;
rvvliet(at)liacs.nl
Laatste wijziging: 15 mei 2012
- http://www.liacs.nl/home/rvvliet/fi3/index.html
