Fundamentele Informatica 1 (I&E),

najaar 2014

Toren Academiegebouw

Laatste nieuws

De exacte tentamenstof staat opgesomd. Zie verderop.

Er zijn twee vragenuren voor het tentamen gepland. Zie verderop.

Er is een uitwerking van de huiswerkopgave gepubliceerd. Zie verderop.


Het vak Fundamentele Informatica 1 (I&E) is speciaal opgezet voor de opleiding Informatica en Economie aan de Universiteit Leiden. Het wordt gegeven op de Campus Den Haag van deze universiteit, om precies te zijn in gebouw Stichthage. De studenten Informatica aan de Universiteit Leiden krijgen (in Leiden) 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

Practische informatie

Docent (hoorcolleges): Rudy van Vliet
te vinden op: kamer 124 van het Snellius in Leiden, telefoon: 071-527 5777
of op: kamer 12.22 van gebouw Stichthage in Den Haag, telefoon: ...
email: rvvliet(at)liacs(dot)nl
Assistent (werkcolleges): Jeroen van den Heuvel
email: jeroenvandenheuvel(at)live(dot)nl
Opzet college: hoorcollege en werkcollege
Collegetijden: maandagen van 27 oktober tot en met 8 december 2014, steeds van 11:15-13:00 uur hoorcollege en van 13:45-15:30 uur werkcollege, beide in zaal Plein
woensdagen van 29 oktober tot en met 3 december 2014, meestal van 13:45-15:30 uur hoorcollege en van 15:45-17:30 uur werkcollege beide in zaal Noordeinde. Alleen op 26 november was dit van 10:15-12:00 hoorcollege en in principe van 12:15-14:30 werkcollege. In overleg met de assistent kan het tweede uur werkcollege iets naar voren geschoven worden.

Tentamens

Er zijn twee tentamens gepland:

Eerste tentamen: dinsdag 23 december 2014, 14:00-17:00, in zaal Bezuidenhout in Den Haag.

Hertentamen: maandag 16 februari 2015, 10:00-13:00.

Twee Vragenuren

Op vrijdag 19 december 2014 is er vanaf 13:45 uur een vragenuur voor het tentamen, in zaal 401 van het Snellius in Leiden. Tijdens het vragenuur kunnen die vragen gesteld worden die opkomen bij het leren van het tentamen. Het vragenuur duurt maximaal tot 15:30 uur. Als de vragen eerder op zijn, stoppen we ook eerder.

Er is een tweede vragenuur gepland op maandag 22 december 2014, vanaf 13:45, in zaal Babylon, in gebouw Stichthage in Den Haag. Afhankelijk van de opkomst bij het vragenuur op 19 december kan dit tweede vragenuur verplaatst worden naar Leiden. Hierover komt uiterlijk 19 december uitsluitsel op deze site.

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 maandag 8 december 2014, 11:15 uur. Zie verder de specificatie van de huiswerkopgave.

De huiswerkopgave dient individueel gemaakt te 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.

Het is niet meer mogelijk om de huiswerkopgave in te leveren. Je kunt wel kijken naar de uitwerking van de docent.

Studielast

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

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.

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.

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.

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)
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 de stof die tijdens de colleges is behandeld. 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 moet missen, houden we per week bij welke stof en opgaven we hebben behandeld. U vindt dit overzicht hier (bijgewerkt tot en met hoorcollege van 8 december 2014).

De slides die tijdens het college gebruikt zijn, worden na de colleges hieronder gepubliceerd:
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

Dit vak wordt in najaar 2014 voor de vierde keer gegeven. Hieronder vindt u de tentamens uit de laatste twee jaren.
Dit vak wordt in najaar 2014 voor de vierde keer gegeven. De vorige keer was in het najaar van 2013. 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: 9 december 2014 - http://www.liacs.leidenuniv.nl/~vlietrvan1/fi1ie/