Fundamentele Informatica 3 is een verplicht derdejaars vak binnen
de bachelor Informatica aan de Universiteit Leiden.
Practische informatie
Docent: Rudy van Vliet
te vinden op: kamer 140 van het Snellius
telefoon: 071-527 2876
email: rvvliet(at)liacs(dot)nl Assistent: Lieuwe Vinkhuijzen Onderwijsvorm: hoorcollege, werkcollege en een huiswerkopgave Collegetijden:
hoorcollege maandag van 11.00-12.45 uur van Rudy van Vliet,
in zaal B03
werkcollege maandag van 13.30-15.15 uur van Lieuwe Vinkhuijzen
in zaal 312
van 5 februari tot en met 26 maart 2018.
Vanwege de hertentamenweek zijn er op 12 maart 2018 geen colleges.
Studielast
Met het behalen van dit vak verdient u 3 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.
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 0.4 bonuspunt van de huiswerkopgave
(het maximale eindcijfer blijft echter 10).
Tentamens
Er zijn twee tentamens geweest: Eerste tentamen: maandag 16 april 2018, 14.00-17.00 uur.
Hertentamen: maandag 28 mei 2018, 14.00-17.00 uur.
Beide tentamens zijn nog terug te vinden onderaan deze pagina.
Bij het eerste tentamen staat daar ook een uitwerking van de docent.
Beide tentamens zijn nagekeken.
De resulterende cijfers, inclusief eindcijfers, vindt u
hier.
De gedetailleerde cijfers voor de huiswerkopgave vindt u
hier.
Je kunt je tentamen inzien bij de docent.
Vragenuur
Op donderdagmiddag 12 april 2018 was er een vragenuur voor
het tentamen.
Daarbij kon je de vragen stellen die opgekomen waren bij
het leren voor het tentamen.
Huiswerkopgave
In de loop van het semester is een huiswerkopgave opgegeven.
Hiermee kon je maximaal 0.4 bonuspunt voor het eindcijfer verdienen.
De huiswerkopgave moet 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.
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-9 van het boek van John Martin,
met de bijbehorende opgaven.
Concreet is dit geworden:
hoofdstuk 7, met uitzondering van
formele definities van delta en configuratie uit paragraaf 7.5
formele formulering van Stelling 7.26
bewijs van Stelling 7.26
bewijs van Stelling 7.31
blz 255-256
paragrafen 8.1, 8.3 en 8.5
de implementatie van de constructie van Stelling 8.13
zoals behandeld tijdens
college 5 (slides 17,18);
deze implementatie staat niet in het boek, maar is dus wel
tentamenstof
paragrafen 9.1 t/m 9.3, met uitzondering van
reducties tussen talen uit paragraaf 9.2
(we hebben alleen reducties tussen beslissingsproblemen behandeld)
Stelling 9.9(5) t/m Stelling 9.10
bewijs van Stelling 9.12
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,
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,
hielden we per week bij, welke stof en opgaven we hadden behandeld.
U vindt dit overzicht
hier
(bijgewerkt t/m werkcollege van 26 maart 2018).
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.
16 april 2018,
met de handgeschreven
uitwerking
van de docent (opgaven niet helemaal in volgorde)
Omdat het vak in zijn huidige versie voor het eerst wordt gegeven,
zijn er geen tentamens uit eerdere jaargangen beschikbaar.
U kunt wel kijken op
de website van de oude versie van het vak,
naar de tentamens bij die versie.
Bedenk echter dat niet alle onderwerpen van de oude versie nu nog
tot de tentamenstof behoren.
Vragen en opmerkingen kunt u sturen naar:
Rudy van Vliet;
rvvliet(at)liacs(dot)nl
Laatste wijziging: 26 november 2018
- http://www.liacs.leidenuniv.nl/~vlietrvan1/fi3/voorjaar2018/
