Fundamentele Informatica 3

voorjaar 2015

Toren Academiegebouw

Fundamentele Informatica 3 is een derdejaars vak binnen de bachelor Informatica aan de Universiteit Leiden.

Practische informatie

Docent: Rudy van Vliet
te vinden op: kamer 124 van het Snellius
telefoon: 071-527 5777
email: rvvliet(at)liacs(dot)nl
Assistent: Mathijs van de Nes
email: s0828599(at)umail(dot)leidenuniv(dot)nl
Onderwijsvorm: hoorcollege, werkcollege en drie huiswerkopgaven
Collegetijden: hoorcollege maandag van 13:45 - 15:30 uur van Rudy van Vliet, in zaal 409
werkcollege dinsdag van 13:45 - 15:30 uur van Mathijs van de Nes, in zaal 405,
van maandag 2 februari tot en met dinsdag 19 mei 2015, met uitzondering van maandag 9 maart en dinsdag 10 maart (hertentamenweek), maandag 6 april (tweede paasdag), maandag 27 april (koningsdag) en dinsdag 5 mei (bevrijdingsdag).
Op maandag 9 februari was het hoorcollege niet van 13:45 - 15:30 uur, maar van 11:15 - 13:00 uur in zaal 407, vanwege de Diesviering die middag. Vanwege de vrije maandagen in april waren de hoorcolleges in die maand op dinsdag 7, 14 en 21 april, en de werkcolleges op maandag 13, maandag 20 en dinsdag 28 april. Op maandag 18 mei en dinsdag 19 mei was er gecombineerd hoor-/werkcollege.

Studielast

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

Voorkennis

Fundamentele Informatica 1 en Fundamentele Informatica 2

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.

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 talen, de Chomsky hierarchie.
Het stopprobleem, berekenbaarheid, (on)beslisbare problemen.
Primitief recursieve functies, Gödel nummering.

Toetsing

Schriftelijk tentamen aan het eind van het semester. Het eindcijfer van het vak is gelijk aan het tentamencijfer + maximaal 1 bonuspunt van de huiswerkopgaven (het maximale eindcijfer blijft echter 10). Het tentamencijfer zelf moet minstens 5.0 zijn om een voldoende eindcijfer te krijgen.

Tentamens

Er zijn twee tentamens geweest:
Eerste tentamen: vrijdag 5 juni 2015, 14:00-17:00, in zaal 312.
Hertentamen: dinsdag 7 juli 2015, 14:00-17:00, in zaal 412.
Ook het hertentamen is nagekeken. U vindt de cijfers, inclusief eindcijfers in het overzicht van alle cijfers van dit voorjaar. U kunt uw eigen uitwerkingen (met opmerkingen van de docent) inzien op zijn kamer.
Beide tentamens zijn onderaan deze pagina terug te vinden. Van het eerste tentamen staat er ook een handgeschreven uitwerking.

Vragenuur

Voor het eerste tentamen werd er een vragenuur georganiseerd. Hierbij beantwoordde de docent vragen die opgekomen waren tijdens het leren voor het tentamen.
Datum: donderdag 4 juni 2015.
Locatie: zaal 405.
Tijd: 13:45 tot maximaal 15:30 uur.

Huiswerkopgaven

In de loop van het semester zijn drie huiswerkopgaven opgegeven. Hiermee kun je maximaal 1 bonuspunt voor het eindcijfer verdienen.
Je dient de huiswerkopgaven individueel te maken. Indien geconstateerd wordt dat er (teveel) is samengewerkt, wordt in principe het verdiende puntenaantal gedeeld door het aantal betrokken studenten.
Huiswerkopgaven dienen uiterlijk twee weken na publicatie ingeleverd te worden bij de nakijker. Haal je die deadline niet, maar lever je ze wel binnen (in totaal) vier weken in, dan kun je nog de helft van de punten verdienen. 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 (dus niet 3rd edition).
We volgen dit boek nauwgezet, en tijdens het werkcollege doen we er ook opgaven uit. Het is dus sterk aan te raden om het daadwerkelijk aan te schaffen.

Twee keer de 4e editie: de Amerikaanse editie (ISBN-13: 978-0073191461) en de internationale editie (ISBN-13: 978-0071289429)
NB: dit boek wordt 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. Te zijner tijd zal hij de lijst naar de auteur van het boek sturen.

Tentamenstof

De tentamenstof is in grote lijnen Concreet is dit geworden: Alleen de technische details van het bewijs van Stelling 9.16 (waarom is de constructie correct?) hoef je niet te kennen. Je moet de betreffende constructie echter wel uit kunnen voeren.

Opmerkingen: Begrippen en notaties behandeld bij Fundamentele Informatica 2 worden bekend verondersteld; notaties en technieken, met name inductie, uit het eerste hoofdstuk moeten kunnen worden gebruikt!

Behandelde stof, opgaven en slides

Voor wie door omstandigheden een (hoor- en/of werk-)college heeft moeten missen, hielden we per week bij welke stof en opgaven we hebben behandeld. U vindt dit overzicht hier (compleet, t/m 19 mei 2015).

Ook de slides die tijdens het college gebruikt zijn, zijn nog te bekijken.
N.B.: 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.
N.B.2: 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.

Antwoorden bij opgaven

Bij de opgaven in de derde editie van het boek was een flink aantal nette uitwerkingen beschikbaar. Deze zijn omgeschreven naar de vierde editie. Heb je een derde editie van het boek, dan kun je de uitwerkingen volgens de nummering van die editie vinden op de website van Fundamentele Informatica 3, voorjaar 2011.

Oude tentamens


Het vak Fundamentele Informatica 3 wordt al vele jaren gegeven. De vorige keer was in het voorjaar van 2014. De website van dat jaar vindt u hier. U vindt daar ook nog meer oude tentamens.
Vragen en opmerkingen kunt u sturen naar:
Rudy van Vliet; rvvliet(at)liacs(dot)nl
Laatste wijziging: 4 augustus 2015 - http://www.liacs.leidenuniv.nl/~vlietrvan1/fi3/voorjaar2015/