Fundamentele Informatica 3

voorjaar 2019

Toren Academiegebouw

Laatste nieuws

Alle inzendingen voor de huiswerkopgave zijn nu nagekeken. Zie verderop.


Fundamentele Informatica 3 is een verplicht derdejaars vak binnen de bachelor Informatica aan de Universiteit Leiden.

Praktische informatie

Docent: Rudy van Vliet
te vinden op: kamer 140 van het Snellius
telefoon: 071-527 2876
email: rvvliet(at)liacs(dot)nl
Assistent: Koen Castelein
Onderwijsvorm: hoorcollege, werkcollege en een huiswerkopgave
Collegetijden: hoorcollege maandag van 11.00-12.45 uur van Rudy van Vliet, in zaal 312
werkcollege maandag van 13.30-15.15 uur van de assistent, eveneens in zaal 312
van 4 februari tot en met 25 maart 2019. Vanwege de hertentamenweek zijn er op 11 maart 2019 geen colleges.

Studielast

Met het behalen van dit vak verdient u 3 EC. Het niveau van het vak wordt aangeduid als `300'.

Voorkennis

Fundamentele Informatica 1 en Fundamentele Informatica 2.

Inhoud

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 en recursieve talen.
Het stopprobleem, (on)beslisbare problemen.

Voor globale informatie over het vak in studiejaar 2018-2019 wordt men verwezen naar de algemene webpagina.

Doelstelling

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 gepland:
Eerste tentamen: maandag 15 april 2019, 14.00-17.00 uur. Hertentamen: maandag 27 mei 2019, 14.00-17.00 uur.

Vragenuur

Op donderdagmiddag 11 april 2019 is er een vragenuur voor het tentamen, in zaal B03. Daarbij kun je dan de vragen stellen die opgekomen zijn bij het leren voor het tentamen. Het vragenuur begint om 15.30 uur en duurt maximaal tot 17.15 uur. Als de vragen eerder op zijn, stoppen we ook eerder.

Huiswerkopgave

In de loop van het semester wordt een huiswerkopgave opgegeven. Hiermee kun 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.

Resultaten voor de huiswerkopgave van dit vak uit een eerder studiejaar zijn dit jaar niet meer geldig.

De huiswerkopgave is beschikbaar. Hiermee kun je maximaal 0.4 bonuspunt voor het eindcijfer verdienen. Uiterste inleverdatum voor 0,4 pt: maandag 25 maart 2019, 11.05 uur. Uiterste inleverdatum voor 0,2 pt: maandag 8 april 2019, 11.05 uur. Daarna inleveren levert geen punten meer op.

Aanvulling: Wellicht ten overvloede, om verwarring te voorkomen: Als er bij onderdeel (b) sprake is van 2^k, wordt het getal 2-tot-de-macht-k bedoeld. Als er sprake is van 1^k, wordt de string bedoeld, bestaande uit k 1-en.

Alle inzendingen voor de huiswerkopgave zijn nagekeken. De opmerkingen en cijfers vindt u hier. Mocht je cijfer toch ontbreken, dan is er waarschijnlijk iets misgegaan. Neem dan contact op met 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.

Tentamenstof

De tentamenstof is in grote lijnen Concreet is dit geworden:

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 hebben behandeld. U vindt dit overzicht hier (compleet, bijgewerkt t/m laatste hoor-/werkcollege van 25 maart 2019).

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.

Antwoorden bij opgaven

Van een deel van de opgaven uit het boek zijn nette uitwerkingen beschikbaar. Deze vindt u hieronder. Achterin het boek staan ook nog antwoorden van een aantal opgaven.

Oude tentamens

Omdat het vak in zijn huidige versie pas voor de tweede keer wordt gegeven, zijn er geen tentamens uit eerdere jaargangen dan voorjaar 2018 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: 20 april 2019 - http://www.liacs.leidenuniv.nl/~vlietrvan1/fi3/