Fundamentele Informatica 3

voorjaar 2020

Toren Academiegebouw

Fundamentele Informatica 3 was dit jaar 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: Sebastiaan Brand
Onderwijsvorm: hoorcollege, werkcollege en een huiswerkopgave
Collegetijden: hoorcollege op woensdagmiddag, 16.15-18.00 uur, van Rudy van Vliet, in de De Sitterzaal
werkcollege op donderdagmiddag, 16.15-18.00 uur van de assistent, eveneens in de De Sitterzaal
van 5 februari t/m 19 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 geweest:
Eerste tentamen: maandag 29 juni 2020, 14.15-17.15 uur (online).
Hertentamen: maandag 17 augustus 2020, 11.15 uur-14.15 uur. Dit was `gewoon' een fysiek tentamen. Het was dan ook GEEN open boek tentamen, maar een regulier tentamen. Vanwege Corona waren er wel speciale richtlijnen.
Beide tentamen zijn nog terug te vinden in de lijst met oude tentamens onderaan deze pagina. Voor het eerste tentamen staat daar ook een handgeschreven uitwerking van de docent.
Beide tentamens zijn nagekeken. Alle cijfers staan in Blackboard. Hierbij geldt de volgende legenda.

Online tentamen

Het eerste tentamen was dit jaar online. Bij het online tentamen maakten we gebruik van het digitale tentamenplatform Ans. Half juni is er een oefententamen klaargezet, zodat je kon oefenen met dit platform. Er was ook een korte instructie voor het werken met Ans beschikbaar.

Omdat het tentamen online werd gehuden, had het een open boek karakter. Je mocht het boek, je aantekeningen, de slides, en al het andere materiaal op deze website gebruiken bij het maken van het tentamen. Dit betekende wel dat het type vragen iets anders was dan bij tentamens in eerdere jaren: geen/minder directe weetvragen, en meer vragen naar inzicht, het bedenken en analyseren van Turingmachines, grammatica's en bewijzen, en het toepassen van constructies.

Het was niet toegestaan om bij het tentamen samen te werken, noch met elkaar, noch met andere personen. Het was ook niet toegestaan om antwoorden letterlijk te kopieren uit het beschikbare materiaal. Formuleer je antwoorden altijd in je eigen woorden. Als onderdeel van het tentamen moest je ook schriftelijk bevestigen dat je het tentamen zelf had gemaakt. We hielden je tijdens het tentamen echter niet met webcams in de gaten.

Het hertentamen was weer gewoon fysiek! Dat betekende tevens dat het geen open boek tentamen was, maar een regulier tentamen.

Vragenuur

Op vrijdagmiddag 26 juni, vanaf 14.15, was er een vragenuur voor het tentamen, in de Kaltura Live Room van het vak. 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 moest 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 nagekeken. De cijfers staan in Blackboard. Hierbij geldt de volgende legenda. Het nagekeken werk (met opmerkingen van de nakijker) is per email opgestuurd.

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 was dan ook van plan een dictaat te schrijven, maar het is slechts een zeer beperkt stuk van het dictaat geworden. Het behandelt de stof van de eerste helft van college 1, met name met de benodigde voorkennis vanuit het vak Fundamentele Informatica 2. Toch kan het zeker de moeite zijn om te bekijken. U vindt het hier.

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 uit het eerste hoofdstuk moeten kunnen worden gebruikt!

Omdat het eerste tentamen online was, en daarmee ook open-boek, werden er minder directe weetvragen gesteld. Er werd meer getoetst op inzicht, het zelf bedenken en analyseren van Turingmachines, grammatica's en bewijzen, en het toepassen van constructies.

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 (compleet!)

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 of dictaat, 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

De tentamens in eerdere jaren waren geen open boek tentamens. Het eerste tentamen van dit jaar kan dus een iets ander karakter hebben. 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: 20 november 2020 - http://www.liacs.leidenuniv.nl/~vlietrvan1/fi3/