Fundamentele Informatica 3

voorjaar 2020

Toren Academiegebouw

Fundamentele Informatica 3 is een verplicht tweedejaars en 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: ...
Onderwijsvorm: hoorcollege, werkcollege en een huiswerkopgave
Collegetijden: hoorcollege op een dag en een tijd (nog onduidelijk) van Rudy van Vliet, in een zaal
werkcollege op een dag en een tijd (nog onduidelijk) van de assistent, eveneens in een zaal
van begin februari tot eind maart 2020.

Studielast

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

Aanbevolen 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, algemene grammatica's.
Het stopprobleem, (on)beslisbare problemen.

Voor globale informatie over het vak in studiejaar 2019-2020 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: donderdag 26 maart 2020, 10.15-13.15 uur, in het Snellius.
Hertentamen: dinsdag 2 juni 2020, 14.15-17.15 uur.
Alle cijfers komen te zijner tijd in Blackboard.

Vragenuur

Indien daar belangstelling voor bestaat, kan er een vragenuur voor het (eerste) tentamen worden ingepland. Daarbij kun je dan de vragen stellen die opgekomen zijn bij het leren voor het tentamen.

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.
De huiswerkopgave dient uiterlijk twee weken na publicatie ingeleverd te worden bij de nakijker. Haal je die deadline niet, maar lever je hem wel binnen (in totaal) vier weken in, dan kun je nog de helft van de punten verdienen. Daarna inleveren levert geen punten meer op.

De cijfers komen te zijner tijd in Blackboard. Resultaten voor de huiswerkopgave van dit vak uit een eerder studiejaar zijn dit jaar niet meer geldig.

Literatuur

John C. Martin, Introduction to Languages and the Theory of Computation, 4th edition, McGraw Hill, 2010/2011.


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 werd t/m najaar 2018 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.

Dit boek schijnt niet meer in de winkel te liggen. De docent is dan ook van plan een dictaat te schrijven.

Tentamenstof

De tentamenstof is in grote lijnen Het zal weinig afwijken van de tentamenstof van het vak in voorjaar 2019. Een compleet, gedetailleerd overzicht van de tentamenstof, komt na het laatste college op deze site.

Opmerkingen: Begrippen en notaties behandeld bij Fundamentele Informatica 2 worden bekend verondersteld; notaties en technieken uit het eerste hoofdstuk moeten kunnen worden gebruikt!

Behandelde stof, opgaven en slides

Voor wie door omstandigheden een hoorcollege of werkcollege moet missen, zullen we per week bijhouden welke stof en opgaven we hebben behandeld. U vindt dit overzicht hier (nog leeg).

De slides die tijdens de colleges gebruikt zijn, worden na elk college hieronder gepubliceerd.
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 of dictaat, te begrijpen.

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

De vorige keer dat de huidige versie van het vak Fundamentele Informatica 3 werd gegeven, was in het voorjaar van 2019. De website van die keer vindt u hier.
Omdat het vak in zijn huidige versie pas voor de derde 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: 10 december 2019 - http://www.liacs.leidenuniv.nl/~vlietrvan1/fi3/