Fundamentele Informatica 3 was een derdejaars vak binnen de bachelor
Informatica aan de Universiteit Leiden.
Oude versie FI3
Vanwege een wijziging van het curriculum is dit vak
in het najaar van 2016
voor het laatst in zijn toenmalige vorm gegeven.
De huidige versie van het vak vindt u
hier.
Practische informatie
Docent: Rudy van Vliet
te vinden op: kamer 140
van het Snellius
telefoon: 071-527 7043
email: rvvliet(at)liacs(dot)nl Assistent: Lieuwe Vinkhuijzen Onderwijsvorm: hoorcollege, werkcollege en drie huiswerkopgaven Collegetijden:
hoorcollege dinsdag van 11.15-13.00 uur van Rudy van Vliet,
in zaal 174
werkcollege donderdag van 13.45-15.30 uur van de assistent
in zaal 412
van dinsdag 6 september tot en met donderdag 8 december 2016.
Studielast
Met het behalen van dit vak verdient u 6 EC.
Het niveau van het vak wordt aangeduid als `300'.
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.
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.
Toetsing
Schriftelijk tentamen aan het eind van het semester.
Het eindcijfer van het vak is gelijk aan het tentamencijfer
+ maximaal 1 bonuspunt van de huiswerkopgaven
(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 13 januari 2017, 14.00-17.00 uur.
Hertentamen: donderdag 9 maart 2017, 14.00-17.00 uur.
Beide tentamens zijn nog terug te vinden
in de lijst met oude tentamens onderaan, inclusief een uitwerking
van het eerste tentamen door de docent.
Beide tentamens zijn nagekeken.
De resulterende tentamencijfers, inclusief
eindcijfers, vindt u
hier.
De gedetailleerde cijfers voor de drie huiswerkopgaven vindt u
hier.
Extra tentamens
Het hertentamen was het laatste reguliere tentamen.
Omdat het vak niet meer in de oude vorm gegeven wordt,
zijn er twee extra tentamens gehouden.
Het eerste extra tentamen is geweest op
donderdag 22 juni 2017, 14.00-17.00, in zaal 174.
Het tweede = laatste extra tentamen is geweest
op maandag 14 augustus 2017, 14.00-17.00, in zaal 313 van het Snellius.
Beide extra tentamens zijn nog terug te vinden
in de lijst met oude tentamens onderaan.
Beide extra tentamens zijn nagekeken.
De cijfers vindt u
hier.
Je kunt je nagekeken tentamens inzien bij de docent, op kamer 140.
Vragenuur
Op woensdag 11 januari 2017 was er van 11.00-13.00 uur een vragenuur voor
het tentamen.
Daarbij kon je de vragen stellen die opgekomen waren bij
het leren voor het tentamen.
Huiswerkopgaven
In de loop van het semester zijn drie huiswerkopgaven opgegeven.
Hiermee kon je maximaal 1 bonuspunt voor het eindcijfer verdienen.
De huiswerkopgaven moeten individueel gemaakt worden.
Wanneer blijkt dat studenten teveel hebben samengewerkt voor hun oplossing,
zullen de (voor een enkele oplossing) verdiende punten worden 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.
De gedetailleerde cijfers
vindt u hier.
Nagekeken huiswerkopgaven die op papier waren ingeleverd,
kunnen worden opgehaald bij de docent.
Literatuur
John C. Martin,
Introduction to Languages and the Theory of Computation,
4th edition, McGraw Hill, 2010/2011.
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-007-128942-9)
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 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 in principe
helemaal (want we hebben deze vier
hoofdstukken vrijwel 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
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.
Ook hoef je van blz 346-347 Stelling 10.19 en de aanloop daarnaartoe
niet te kennen.
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
moest missen,
hebben we per week bijgehouden welke stof en opgaven
we hebben behandeld. U vindt dit overzicht
hier
(bijgewerkt t/m hoorcollege van 8 december 2016).
De slides die tijdens de colleges gebruikt zijn,
zijn hieronder nog te bekijken.
N.B:
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.
N.B.2:
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.
Het vak Fundamentele Informatica 3 is vele jaren gegeven.
De vorige keer was in het voorjaar van 2016. De website van die keer
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: 12 september 2017
- http://www.liacs.leidenuniv.nl/~vlietrvan1/fi3/
