Fundamentele Informatica 3 is een derdejaars vak binnen de bachelor
Informatica aan de Universiteit Leiden.
Practische informatie
Docent: Rudy van Vliet
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.
Assistent: Mathijs van de Nes
email: s0828599(at)umail(dot)leidenuniv(dot)nl Onderwijsvorm: hoorcollege, werkcollege en drie huiswerkopdrachten Collegetijden:
hoorcollege maandag van 13:45 - 15:30 uur van Rudy van Vliet
werkcollege dinsdag van 13:45 - 15:30 uur van Mathijs van de Nes
allemaal in zaal 403,
van maandag 3 februari tot en met maandag 19 mei 2014,
met uitzondering van maandag 10 maart en dinsdag 11 maart (hertentamenweek),
maandag 21 april (tweede paasdag)
en maandag 5 mei (bevrijdingsdag).
Studielast
Met het behalen van dit vak verdient u 6 EC.
Het niveau van het vak wordt aangeduid als `300'.
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.
Computers kunnen gebruikt worden voor het uitvoeren van vele soorten
berekeningen. Toch zijn hier ook grenzen aan. Bij dit vak onderzoeken
we de mogelijkheden en onmogelijkheden van een computer. We doen dit onder
andere door een theoretisch model van de computer te bestuderen.
Onderwerpen die aan de orde komen zijn:
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, Gödel nummering.
Toetsing
Schriftelijk tentamen aan het eind van het semester.
Het eindcijfer van het vak is gelijk aan het tentamencijfer
+ maximaal 1 bonuspunt van de huiswerkopdrachten
(het maximale eindcijfer blijft echter 10).
Het tentamencijfer zelf moet minstens 5.0 zijn
om een voldoende eindcijfer te krijgen.
Tentamens
Er zijn twee tentamens geweest: Eerste tentamen: vrijdag 6 juni 2014, 14:00-17:00.
Hertentamen: dinsdag 8 juli 2014, 14:00-17:00.
Beide tentamens zijn onderaan deze pagina terug te vinden.
Van het eerste tentamen staat er ook een handgeschreven uitwerking.
Beide tentamens zijn nagekeken.
U vindt de cijfers, inclusief eindcijfers
in het
overzicht van alle cijfers
van dit voorjaar.
Bij het hertentamen waren 103 punten te behalen. Het tentamencijfer ontstond
echter gewoon door de behaalde punten door 10 te delen.
U kunt uw eigen uitwerkingen (met opmerkingen van de docent) inzien op
zijn kamer.
Vragenuur
Op dinsdagmiddag 3 juni 2014 was er een vragenuur voor het tentamen.
Hierbij beantwoordde de docent
vragen die opgekomen waren tijdens het leren voor het tentamen.
Locatie: zaal 403.
Tijd: 13:45 tot maximaal 15:30 uur.
Huiswerkopgaven
In de loop van het semester zijn drie huiswerkopgaven opgegeven.
Hiermee kon je maximaal 1 bonuspunt voor het eindcijfer verdienen.
De huiswerkopgaven moesten individueel gemaakt worden.
Huiswerkopgaven dienden uiterlijk twee weken na publicatie ingeleverd
te worden bij de nakijker.
Haalde je die deadline niet, maar leverde je ze wel binnen (in totaal)
vier weken in, dan kon je nog de helft van de punten verdienen.
Daarna inleveren leverde geen punten meer op.
John C. Martin,
Introduction to Languages and the Theory of Computation,
4th edition,
McGraw Hill, 2010/2011 (dus niet 3rd edition).
We volgen dit boek nauwgezet, en tijdens het werkcollege doen
we er ook opgaven uit. Het is dus sterk aan te raden om het
daadwerkelijk aan te schaffen.
Twee keer de 4e editie: de Amerikaanse editie (ISBN-13: 978-0073191461)
en de internationale editie (ISBN-13: 978-0071289429)
NB: dit boek wordt ook gebruikt bij het college
Fundamentele Informatica 2
Er is een
lijst met
errata
bij dit boek beschikbaar.
Heeft u zelf (andere) foutjes in het boek ontdekt, meld het dan aan
de docent. Dan kunnen die ook in de lijst worden opgenomen. Te zijner tijd
zal hij de lijst naar de auteur van het boek sturen.
Tentamenstof
De tentamenstof is in grote lijnen
de stof die tijdens de colleges wordt
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 6 (slides 16,17);
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 (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
(bijgewerkt t/m 19 mei 2014, dus compleet).
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).
Antwoorden bij opgaven uit
hoofdstuk 10 van vierde editie.
Achterin het boek staan ook nog antwoorden van een aantal 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.:
vorig jaar is de tentamenstof verschoven. Onderstaande oude tentamens
uit 2012
gingen over hoofdstukken 5-9 van het boek, terwijl de tentamenstof
tegenwoordig hoofdstukken 7-10 beslaat.
Het vak Fundamentele Informatica 3 wordt al vele jaren gegeven.
De vorige keer was in het voorjaar van 2013. 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: 23 januari 2015
- http://www.liacs.leidenuniv.nl/~vlietrvan1/fi3/index.html
