Fundamentele Informatica 1 (I&E),

najaar 2015

Toren Academiegebouw

Het vak Fundamentele Informatica 1 (I&E) is speciaal opgezet voor de opleiding Informatica en Economie aan de Universiteit Leiden.
De colleges worden dit jaar gegeven in het Snellius in Leiden. Stichthage was namelijk al volgeboekt.
De studenten Informatica aan de Universiteit Leiden krijgen een vak Fundamentele Informatica 1 met een heel andere inhoud! De website van dat vak vindt u hier.

Een deel van de inhoud van het Leidse vak Fundamentele Informatica 1 is in Den Haag behandeld bij het vak Studievaardigheden I&E. De inhoud van Fundamentele Informatica 1 (I&E) is een selectie uit de onderwerpen van de Leidse vakken

Laatste jaar FI1 (I&E)

Vanwege een wijziging van het curriculum wordt dit vak in het najaar van 2015 voor het laatst gegeven. Extra reden dus om je best te doen.

Practische informatie

Docent (hoorcolleges): Rudy van Vliet
te vinden op: kamer 124 van het Snellius in Leiden, telefoon: 071-527 5777
email: rvvliet(at)liacs(dot)nl
Assistent (werkcolleges): Jeroen van den Heuvel
email: jeroenvandenheuvel(at)live(dot)nl
Onderwijsvorm: hoorcollege, werkcollege en een huiswerkopgave
Collegetijden: dinsdagen van 27 oktober tot en met 8 december 2015, steeds van 11:15-13:00 uur hoorcollege en van 13:45-15:30 uur werkcollege
vrijdagen van 30 oktober tot en met 4 december 2015, steeds van 11:15-13:00 uur hoorcollege en van 13:45-15:30 uur werkcollege
Zowel hoorcollege als werkcollege in zaal 408 van het Snellius.

Studielast

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

Voorkennis

Er wordt weinig specifieke voorkennis verondersteld. Het is echter wel van belang dat de studenten op een abstract niveau kunnen denken en logisch kunnen redeneren.

Inhoud

Dit vak behandelt de theoretische achtergrond van de computer. Veel computerprogramma's voeren een berekening uit van een invoer naar een bijbehorende uitvoer. We onderzoeken welke soorten berekeningen uitgevoerd kunnen worden door diverse modellen van een computer. Onderwerpen die hierbij aan de orde komen, zijn: talen, eindige automaten, reguliere expressies, context-vrije talen, stapelautomaten, pomplemma's, Turing machines en algemene grammatica's.

Doelstelling

Kennismaken met fundamentele inzichten die ten grondslag liggen aan de informatica als wetenschappelijke discipline. In het bijzonder met formele talen en abstracte machines om zulke talen te verwerken. Van eenvoudige machines tot machines die net zo krachtig zijn als een (echte) computer.

Toetsing

Schriftelijk tentamen aan het eind van het semester. Het eindcijfer voor het vak is gelijk aan het tentamencijfer + maximaal 0.4 bonuspunt van de huiswerkopgave.

Tentamens

Er zijn twee reguliere tentamens geweest:

Eerste tentamen: donderdag 7 januari 2016, 10:00-13:00, in zaal 174 van het Snellius.
Hertentamen: maandag 22 februari 2016, 10:00-13:00, in zaal 408 van het Snellius.
Beide tentamens zijn nog terug te vinden in het lijstje met oude tentamens onderaan, inclusief een handgeschreven uitwerking van het eerste tentamen.

Beide tentamens zijn nagekeken. De resulterende cijfers vindt u in het overzicht met alle cijfers.
Omdat het eerste tentamen vrij lang was, konden met de opgaven bij dat tentamen in totaal 105 punten verdiend worden. Het aantal verdiende punten werd vervolgens gewoon door 10 gedeeld.
Je kunt je nagekeken tentamens inzien bij de docent, op kamer 124 van het Snellius.

Extra tentamens

Omdat het vak in het najaar van 2015 voor het laatst gegeven is, zijn er twee extra tentamens geweest: op dinsdag 19 juli 2016, van 14.00-17.00, en op vrijdag 27 januari 2017, van 14.00-17.00.
Het tentamen van 19 juli 2016 is nog terug te vinden in het lijstje met oude tentamens onderaan.

Ook het extra tentamen van 27 januari 2017 is nagekeken. De resulterende cijfers vindt u in het overzicht met alle cijfers.
Je kunt je nagekeken tentamen inzien bij de docent, op kamer 143 van het Snellius.

Vragenuur

Op woensdag 6 januari 2016 was er vanaf 16:00 uur een vragenuur voor het tentamen, in zaal 402 van het Snellius. Daarbij kon je die vragen stellen die opgekomen waren bij het leren voor het tentamen.

Huiswerkopgave

Bij dit vak valt een kleine bonus (maximaal 0.4pt) voor het tentamen te verdienen met de volgende huiswerkopgave. Daarmee zou je, afhankelijk van de afrondingen, je cijfer net iets kunnen opkrikken, of zelfs van een onvoldoende een voldoende kunnen maken. In te leveren, uiterlijk vrijdag 11 december 2015, 13:45 uur. Zie verder de specificatie van de huiswerkopgave.

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 is nagekeken. De resultaten zijn hier te bekijken. Het is de bedoeling om het nagekeken werk (voor zover op papier ingeleverd) mee te nemen naar het vragenuur op 6 januari. Wil je het eerder hebben, dan kun je het komen halen op werkkamer 124 van de docent in het Snellius. De uitwerking van de docent zelf is hier te bekijken (een beetje licht gescand, dus goed kijken).

Literatuur

John C. Martin, Introduction to Languages and the Theory of Computation, 4th edition, McGraw Hill, 2010/2011.
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)
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.

Meer gedetailleerde inhoud / Tentamenstof

De tentamenstof is

Dit zijn de volgende paragrafen van het boek met bijbehorende onderwerpen en opgaven:

Grote, gedetailleerde bewijzen hebben we niet behandeld, en behoren dus ook niet tot de tentamenstof. De grote lijnen van bewijzen of kleinere, gedetailleerde bewijzen zijn echter wel aan de orde gekomen en behoren dus wel tot de tentamenstof. Bedenk verder dat er tijdens de colleges ook nog extra opgaven zijn behandeld, die niet in het boek staan.

Behandelde stof, opgaven en slides

Voor wie door omstandigheden een hoorcollege of werkcollege moest missen, hielden we per week bij welke stof en opgaven we hadden behandeld. U vindt dit overzicht hier (compleet).

De slides die tijdens het college gebruikt zijn, zijn hieronder nog te bekijken.
N.B.: om gemakkelijk naar eerdere definities/resultaten 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

Van een deel van de opgaven uit het boek zijn nette uitwerkingen beschikbaar. Deze vindt u hieronder. Bedenk echter dat niet al de uitgewerkte opgaven tot de tentamenstof behoren. Zie daarvoor uiteindelijk de lijst met de tentamenstof hierboven.

Oude tentamens

Hieronder vindt u de tentamens van de afgelopen twee jaren, alsmede die van dit collegejaar.
Dit vak wordt in najaar 2015 voor de vijfde keer gegeven. De vorige keer was in het najaar van 2014. De website van dat jaar vindt u hier. U vindt daar ook nog meer oude tentamens.
Vragen en/of opmerkingen kunt u sturen naar:
Rudy van Vliet; rvvliet(at)liacs(dot)nl
Laatste wijziging: 9 mei 2017 - http://www.liacs.leidenuniv.nl/~vlietrvan1/fi1ie/