Computability

voorjaar 2025

Toren Academiegebouw

Laatste nieuws

(24.03.2025) Op dinsdagmiddag 25 maart 2025 is er vanaf 13.15 uur een vragenuur voor het tentamen, in zaal BW.0.39. Zie verderop.

(20.03.2025) De tentamenstof staat overzichtelijk op een rijtje. Zie verderop.

(14.03.2025) Vanwege een aanpassing van het curriculum wordt dit vak dit jaar voor het laatst in de huidige vorm gegeven. Wellicht een extra reden om je best te doen.


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 BM.2.03 van het (nieuwe) Gorlaeus
telefoon: 071-527 2876
email: rvvliet(at)liacs(dot)nl
Assistenten: ...
Onderwijsvorm: per week twee uur hoorcollege en twee uur werkcollege. Daarnaast wordt er eenmalig een huiswerkopgave opgegeven.
Collegetijden: hoorcollege op maandag, 15.15-17.00, in zaal BM.1.33 in het (nieuwe) Gorlaeus van Rudy van Vliet,
werkcollege op dinsdag, 11.00-12.45, in zaal BM.1.33 in het (nieuwe) Gorlaeus van de assistenten,
allemaal van 3 februari t/m 18 maart 2025.

De hoorcolleges worden opgenomen, maar worden pas twee weken na opname beschikbaar gesteld op deze pagina. U kunt desgewenst al eerder kijken naar de weblectures van de hoorcolleges en de werkcolleges uit 2021. U vindt deze op de website van voorjaar 2022. Hoewel de inhoud van het vak weinig veranderd is, zijn er aan de oude weblectures geen rechten over de behandelde stof te ontlenen. Het is altijd beter om naar de colleges van dit jaar te gaan, en daar actief aan deel te nemen.

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 2024-2025 wordt men verwezen naar de algemene webpagina.

Doelstelling

Na afloop van dit vak zijn studenten in staat om

Toetsing

Een huiswerkopgave in de loop van de collegeperiode, en schriftelijk tentamen na afloop van de colleges. De huiswerkopgave is niet verplicht, maar telt wel mee voor het eindcijfer. Het minimumcijfer voor de huiswerkopgave is 0, het minimumcijfer voor het tentamen is 1. Het eindcijfer van het vak is gelijk aan het tentamencijfer + maximaal 0.4 bonuspunt van de huiswerkopgave. Als dit minstens 5.5 is, heb je het vak gehaald. Het maximale eindcijfer is 10.

Tentamens

Er zijn twee tentamens gepland, allebei on-campus:
Eerste tentamen: donderdag 27 maart 2025, 09.00-12.00, in Lecture Hall (schotel) C4/5.
Hertentamen: dinsdag 17 juni 2025, 09.00-12.00, in zalen Gorlaeus BE.0.17 en BE.0.18.
De cijfers van de tentamens zullen gepubliceerd worden in Brightspace. Zorg dus dat je je aanmeldt voor de cursus in Brightspace.

Vragenuur

Op dinsdag 25 maart 2025 is er een vragenuur voor het tentamen, in zaal BW.0.39. Daarbij kun je dan de vragen stellen die opgekomen zijn bij het leren voor het tentamen. Het vragenuur begint om 13.15 uur en duurt maximaal tot 15.00 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. In bijzondere gevallen kan ook een melding worden gedaan bij de examencommissie. In dat geval wordt de beoordeling van de opgave voor die studenten opgeschort, in afwachting van een oordeel van de examencommissie.
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 van de huiswerkopgave zullen gepubliceerd worden in Brightspace. Zorg dus dat je je aanmeldt voor de cursus in Brightspace.

Resultaten voor de huiswerkopgave van Computability / 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: dinsdag 4 maart 2025, 23.59 uur.
Uiterste inleverdatum voor 0.2 pt: dinsdag 18 maart 2025, 23.59 uur. Daarna inleveren levert geen punten meer op.

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 vanaf 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. In een eerder 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, hebben we per week bijgehouden welke stof en opgaven we hebben behandeld. U vindt dit overzicht hier (bijgewerkt t/m hoor-/werkcollege van 18 maart 2025, compleet dus!).

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

De vorige keer dat het vak werd gegeven, was in het voorjaar van 2024. 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: 24 maart 2025 - https://www.liacs.leidenuniv.nl/~vlietrvan1/computability/