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 Assistenten: ... Onderwijsvorm: per week twee uur hoorcollege en twee uur werkcollege.
Daarnaast wordt er eenmalig een huiswerkopgave opgegeven. Collegetijden:
hoorcollege op vrijdag, 11.00-12.45, in zaal C2 in het Gorlaeus
collegegebouw (de schotel) of de Havingazaal (zie MyTimeTable),
van Rudy van Vliet,
werkcollege op maandag, 15.15-17.00, in zaal EM 1.09
in het Gorlaeus (de nieuwbouw), van de assistenten,
allemaal
van 9 februari t/m 18 maart 2024i,
en een gecombineerd hoor-/werkcollege op vrijdag 22 maart,
11.00-15.00
(niet meer 09.00-12.45),
in Van Steenis E0.04 / F1.04, van Rudy van Vliet
De colleges worden niet opgenomen, maar er zijn nog wel 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 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'.
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 2023-2024
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
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 28 maart 2024, 09.00-12.00
Dit tentamen is nog terug te vinden in de lijst met oude tentamens
onderaan deze pagina.
Hertentamen:
vrijdag 14 juni 2024, 13.00-16.00
Het hertentamen is gepland
in de Sporthal en de Danszaal van het Universitair Sportcentrum.
Mensen met recht op extra tijd kunnen in de Danszaal gaan zitten.
De cijfers van de tentamens zullen gepubliceerd worden in
Brightspace.
Zorg dus dat je je aanmeldt voor de cursus in Brightspace.
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. 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)
drie of vier weken (nog nader te bepalen) 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.
N.B.: Je Turingmachines hoeven niet te controleren of de invoer `klopt',
d.w.z.: of elke string in de invoer uit alleen 1'en of alleen 2'en
bestaat. Daar mag je vanuit gaan. (aanvulling per 5 maart 2024)
Uiterste inleverdatum voor 0.4 pt:
vrijdag 8 maart 2024, 23.59 uur.
Uiterste inleverdatum voor 0.2 pt: vrijdag 22 maart 2024, 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
de stof die tijdens de colleges wordt
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 26,27);
deze implementatie staat niet in het boek, maar is dus wel
tentamenstof
belangrijkste resultaten uit paragraaf 8.5 (zonder bewijs)
paragraaf 9.1
paragraaf 9.2, met uitzondering van
reducties tussen talen uit paragraaf 9.2
(we hebben alleen reducties tussen beslissingsproblemen behandeld)
paragraaf 9.3 t/m blz 311
(niet-triviale taaleigenschappen en de stelling van Rice behoren dit jaar
dus niet tot de tentamenstof)
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
moet missen,
zullen we per week bijhouden welke stof en opgaven we hebben behandeld.
U vindt dit overzicht
hier
(bijgewerkt t/m hoor-/werkcollege van 22 maart, compleet dus)
De slides die tijdens de colleges gebruikt worden,
worden voor elk college hieronder gepubliceerd.
De vorige keer dat het vak
werd gegeven, was in het voorjaar van 2023.
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: 1 april 2024
- https://www.liacs.leidenuniv.nl/~vlietrvan1/computability/
