Computability

voorjaar 2021

Toren Academiegebouw

Laatste nieuws

Het hertentamen van 27 mei is nagekeken. De cijfers, inclusief eindcijfers, staan in Brightspace. Omdat het tentamen wellicht wat lastig was, heeft iedereen een punt (van de 10) extra gekregen. Als je je nagekeken tentamen wil inzien, laat dat dan uiterlijk 18 juli weten aan de docent. Dan krijg je in de week daarna een scan toegestuurd.


Computability is een verplicht tweedejaars vak binnen de bachelor Informatica aan de Universiteit Leiden. Tot en met voorjaar 2020 heette dit vak Fundamentele Informatica 3.

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: weblectures voor hoorcollege en werkcollege, online vragenuren en een huiswerkopgave
Collegetijden: hoorcollege als weblecture op donderdag, 11.15-13.00
werkcollege als weblecture op vrijdag, 14.15-15.00
interactief vragenuur op vrijdag, 15.15-16.00,
allemaal van Rudy van Vliet, van 1 februari t/m 19 maart 2021.
In afwijking van de eerdere aankondiging staan ook de eerste weblectures weer online, en ze blijven ook, tot en met het hertentamen, online. Net als andere onderdelen van deze website, zoals de collegeslides.

Studielast

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

Aanbevolen voorkennis

Foundations of Computer Science en Automata Theory.

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 2020-2021 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, allebei on-campus:
Eerste tentamen: vrijdag 26 maart 2021, 09.00-12.00. Dit tentamen is nagekeken. De cijfers staan in Brightspace. Hierbij geldt de volgende legenda.
Hertentamen: donderdag 27 mei 2021, 09.00-12.00. Zie ook de richtlijnen tentamens en onderwijs, en houd je er aan.
Beide tentamens zijn nog terug te vinden in het lijstje met oude tentamens onderaan deze pagina. Voor het eerste tentamen staat daar ook een handgeschreven uitwerking van de docent.

Vragenuur

Op woensdagmiddag 24 maart 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 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.

Resultaten voor de huiswerkopgave van Fundamentele Informatica 3 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: donderdag 11 maart 2021, 23.59 uur.
Uiterste inleverdatum voor 0.2 pt: donderdag 1 april 2021, 23.59 uur. Daarna inleveren levert geen punten meer op.

De huiswerkopgave is nagekeken. De cijfers staan in Brightspace. Hierbij geldt de volgende legenda.

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, en in najaar 2020 ook bij het college Automata Theory.
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. Vorig jaar heeft de docent daarom een (klein) stukje dictaat geschreven. Het bevat hoofdzakelijk de benodigde voorkennis vanuit het vak Automata Theory.

Tentamenstof

De tentamenstof is in grote lijnen Concreet is dit geworden:

Opmerkingen: Begrippen en notaties behandeld bij Automata Theory 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 (compleet, t/m werkcollege van 19 maart 2021).

De slides die tijdens de colleges gebruikt zijn, worden na elk college hieronder gepubliceerd, samen met de links naar de weblectures.
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 (ook onder de naam Fundamentele Informatica 3)

De vorige keer dat het vak (onder de oude naam dus) werd gegeven, was in het voorjaar van 2020. De website van die keer vindt u hier. Daar vindt u ook nog meer oude tentamens.
Vragen en opmerkingen kunt u sturen naar:
Rudy van Vliet; rvvliet(at)liacs(dot)nl
Laatste wijziging: 11 juli 2021 - https://www.liacs.leidenuniv.nl/~vlietrvan1/computability/