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 (voor hoor- en werkcollege)
te vinden op: kamer 124 van het Snellius
telefoon: 071-527 5777
email: rvvliet(at)liacs(dot)nl
Op de homepage
van de docent kunt u zien of hij op zijn werk te bereiken is.
Opzet college: hoorcollege en werkcollege (gecombineerd) Collegetijden:
maandag van 13:45 - 15:30 uur
en
dinsdag van 13:45 - 15:30 uur, allemaal in zaal 405,
van maandag 4 februari tot en met dinsdag 21 mei 2013,
met uitzondering van maandag 25 maart en dinsdag 26 maart (hertentamenweek),
maandag 1 april (tweede paasdag),
dinsdag 30 april (koninginnedag/inhuldigingsdag)
en maandag 20 mei (tweede pinksterdag).
Tentamens
Er zijn twee tentamens gepland: Eerste tentamen: woensdag 5 juni 2013, 14:00-17:00.
Dit tentamen is geweest. Het is onderaan deze pagina terug te vinden,
met een handgeschreven uitwerking.
Bij dit tentamen was er ook een aparte versie over
de tentamenstof van vorig jaar,
voor (alleen) de studenten die het vak toen geprobeerd maar
niet gehaald hebben. Dat betreft grofweg hoofdstukken 5-9 van het boek,
zie de website
van vorig jaar.
Dit tentamen (beide versies) is nagekeken.
U vindt de cijfers, inclusief eindcijfers in
de lijst met alle cijfers van het vak
dit voorjaar.
U kunt uw eigen uitwerkingen (met opmerkingen van de docent) ophalen op
zijn kamer. Wilt u weten of hij er (mogelijk) is, kijk dan op
zijn homepage.
Omdat de stof wat lastiger is geworden dit jaar, is uiteindelijk besloten
om de punten van de huiswerkopgaven rechtstreeks op te tellen bij het
tentamencijfer, in plaats van bij 90% van het tentamencijfer.
Dit geldt ook voor de studenten die het tentamen hebben
gedaan over de tentamenstof van vorig jaar (die hebben dus `geluk').
Dit is ook bij het hertentamen gebeurd. En bij het hertentamen was
er ook een aparte versie over de tentamenstof van vorig jaar,
voor de studenten die het vak toen geprobeerd maar
niet gehaald hebben.
Op dinsdagmiddag 4 juni 2013 was er een vragenuur voor het tentamen.
Hierbij beantwoordde de docent
vragen die opgekomen waren tijdens het leren voor het tentamen.
Hertentamen: dinsdag 6 augustus 2013, 14:00-17:00.
Dit tentamen is geweest. Het is onderaan deze pagina terug te vinden.
Ook dit hertentamen is nagekeken.
U vindt de cijfers, inclusief eindcijfers in
de lijst met alle cijfers van het vak
dit voorjaar.
U kunt uw eigen uitwerkingen (met opmerkingen van de docent) ophalen op
zijn kamer. Wilt u weten of hij er (mogelijk) is, kijk dan op
zijn homepage.
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 kon je 1 punt voor het tentamen verdienen.
Met het tentamen zelf kun je dan nog 9 punten verdienen
(deze berekening is uiteindelijk aangepast, zie boven).
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 de nakijker.
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.
Alle huiswerkopgaven zijn nagekeken.
U vindt de cijfers in
de lijst met alle cijfers.
U kunt uw eigen uitwerkingen (met opmerkingen van de docent) ophalen
bij de docent.
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
Met ingang van het collegejaar 2012-2013 is de inhoud van het vak anders dan
tot en met 2011-2012.
We behandelen niet meer hoofdstukken 5-9, maar
hoofdstukken 7-10 van het boek. De hoofdstukken 7-10 gaan over de volgende
onderwerpen:
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.
Primitief recursieve functies, Godel nummering.
John C. Martin,
Introduction to Languages and the Theory of Computation,
4th edition,
McGraw-Hill, 2011.
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 is
behandeld uit hoofdstukken 7-10 van het boek van John Martin,
met de bijbehorende opgaven.
Concreet is dit geworden:
hoofdstukken 7-10 uit het boek helemaal (want we hebben deze vier
hoofdstukken helemaal behandeld),
met de bijbehorende opgaven,
extra opgaven en voorbeelden behandeld tijdens de (werk-)colleges;
deze zijn eenvoudig terug te vinden in
het overzicht
met behandelde stof en opgaven (zoek op `Extra'),
en vervolgens in de collegeslides,
de implementatie van de constructie van Stelling 8.13
zoals behandeld tijdens
college 12 (slides 7,8);
deze implementatie staat niet in het boek, maar is dus wel
tentamenstof
Alleen de technische details van het bewijs van Stelling 9.16
(waarom is de constructie correct?) hoef je niet te kennen.
Je moet de betreffende constructie echter wel uit kunnen voeren.
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!
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.
Voor wie door omstandigheden een (hoor- en/of werk-)college heeft
moet missen, houden we per week bij welke stof en opgaven
we hebben behandeld. U vindt dit overzicht
hier
(compleet, dus bijgewerkt tot en met het laatste college,
van dinsdag 21 mei 2013).
Ook de slides die tijdens het college gebruikt 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.
N.B.2:
De slides zijn niet bedoeld ter vervanging van het boek.
Het kan dus lastig zijn om de stof puur met behulp van de slides,
zonder het boek, te begrijpen.
Bij de opgaven in de
derde editie van het boek
was een flink aantal nette uitwerkingen beschikbaar.
Deze zijn omgeschreven naar de vierde editie.
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 11 van derde editie, maar opgavenummering
komt natuurlijk niet overeen).
Helaas geen antwoorden bij opgaven uit hoofdstuk 10 van vierde editie.
Achterin het boek staat wel een aantal antwoorden van opgaven.
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.
Oude tentamens
N.B.: dit jaar is de tentamenstof verschoven. Onderstaande oude tentamens
uit 2011 en 2012
gingen dus over hoofdstukken 5-9 van het boek, terwijl de tentamenstof
dit jaar hoofdstukken 7-10 beslaat.
Het vak Fundamentele Informatica 3 wordt al vele jaren gegeven.
De vorige keer was in het voorjaar van 2012. De website van dat jaar
vindt u hier.
U vindt daar ook nog meer oude tentamens.
Vragen en opmerkingen kunt u sturen naar:
Rudy van Vliet;
rvvliet(at)liacs(dot)nl
Laatste wijziging: 4 augustus 2015
- http://www.liacs.leidenuniv.nl/~vlietrvan1/fi3/fi3_vj2013/
