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.
Studielast
Met het behalen van dit vak verdient u 3 EC.
Het niveau van het vak wordt aangeduid als `300'.
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
Verwerven van inzicht in de mogelijkheden en beperkingen van
computers (algoritmes).
Kennismaken met fundamentele inzichten die ten grondslag liggen
aan de informatica als wetenschappelijke discipline.
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.
Hertentamen:
donderdag 27 mei 2021, 09.00-12.00.
Zie ook de
richtlijnen tentamens en onderwijs,
en houd je er aan.
Beide tentamens zijn nagekeken. De cijfers staan in
Brightspace.
Hierbij geldt de volgende
legenda.
De 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.
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
de stof die tijdens de colleges is
behandeld uit hoofdstukken 7-9 van het boek van John Martin,
met de bijbehorende opgaven.
Concreet is dit geworden:
hoofdstuk 7, met uitzondering van
formele definities van delta en configuratie uit paragraaf 7.5
formele formulering van Stelling 7.26
bewijs van Stelling 7.26
bewijs van Stelling 7.31
blz 255-256
paragrafen 8.1 en 8.3
de implementatie van de constructie van Stelling 8.13
zoals behandeld tijdens
college 5
(slides 17,18);
deze implementatie staat niet in het boek, maar is dus wel
tentamenstof
belangrijkste resultaten uit paragraaf 8.5 (zonder bewijs)
paragrafen 9.1 t/m 9.3, met uitzondering van
reducties tussen talen uit paragraaf 9.2
(we hebben alleen reducties tussen beslissingsproblemen behandeld)
met de bijbehorende opgaven,
extra opgaven en voorbeelden behandeld tijdens de (werk-)colleges;
deze zijn eenvoudig terug te vinden in
het overzicht
met behandelde stof en opgaven (zoek op `Extra'),
en vervolgens in de collegeslides,
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
moest missen,
hebben we per week bijgehouden 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,
zijn 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, 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.
29 juni 2020,
met de handgeschreven
uitwerking
van de docent.
Dit was een online tentamen en daarmee ook een open boek tentamen.
Het type vragen was dan ook wellicht iets anders dan gebruikelijk.
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: 4 februari 2022
- https://www.liacs.leidenuniv.nl/~vlietrvan1/computability/voorjaar2021/
