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
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
de stof die tijdens de colleges wordt
behandeld uit hoofdstukken 1-8 van het boek van John Martin,
met de bijbehorende opgaven.
Dit zijn de volgende paragrafen van het boek
met bijbehorende onderwerpen en opgaven:
Uit Hfst 1: Wiskundige tools en technieken:
1.4: talen
Hierbij horen opgaven 1.31-1.37.
Uit Hfst 2: Eindige automaten en de talen die ze accepteren
2.1: eindige automaten: voorbeelden en definities
2.2: accepteren van vereniging, doorsnede en verschil van twee talen
2.4: het pomplemma
Hierbij horen opgaven 2.1-2.4, 2.9-2.12, 2.22-2.27, 2.29.
Uit Hfst 3: Reguliere expressies, niet-determinisme
3.1: reguliere talen en reguliere expressies
3.2: niet-deterministische eindige automaten
3.3: niet-determinisme in eindige automaat kan ge-elimineerd worden
(geen formele bewijzen, maar wel de resultaten en constructies)
3.4: stelling van Kleene, deel 1 (inclusief constructie uit Stelling 3.25,
maar zonder precieze bewijs dat constructie correct is)
3.5: stelling van Kleene, deel 2 (alleen formulering Stelling 3.30)
Hierbij horen opgaven 3.1-3.5, 3.7-3.9, 3.18-3.23, 3.37-3.50.
Uit Hfst 4: Context-vrije talen
4.1: grammatica's om een taal te definieren
4.2: context-vrije grammatica's: definities en meer voorbeelden
4.3: reguliere talen en reguliere grammatica's
4.4: afleidingsbomen en dubbelzinnigheid
(alleen afleidingsbomen, dus tot en met Definitie 4.16)
4.5: vereenvoudigde vormen en normaalvormen
(inclusief algoritmes, maar zonder recursieve definities en bewijzen)
Hierbij horen opgaven 4.1-4.6, 4.9-4.14, 4.22, 4.25ab, 4.26-4.30, 4.49, 4.50,
4.54.
Uit Hfst 5: Stapelautomaten
5.1: definities en voorbeelden stapelautomaten
5.2: deterministische stapelautomaten
(behalve bewijs Stelling 5.16)
5.3: een stapelautomaat bij een context-vrije grammatica
(zonder details bewijs Stelling 5.18, en zonder bewijs Stelling 5.23)
Hierbij horen opgaven 5.1-5.8, 5.10, 5.12, 5.16-5.19, 5.28-5.31, 5.33, 5.34.
Uit Hfst 6: Context-vrije en niet-context-vrije talen
6.1: pomplemma voor context-vrije talen
(tot en met Voorbeeld 6.6)
Hierbij horen opgaven 6.2-6.5.
Uit Hfst 7: Turing machines
7.1: algemeen model van berekenbaarheid
(preciese notatie van configuraties en stappen in een TM hoeft
niet gekend te worden voor tentamen)
7.2: Turing machines om talen te accepteren
7.3: Turing machines om partiele functies te berekenen
(tot en met Voorbeeld 7.12)
Hierbij horen opgaven 7.4-7.9, 7.17a-c,e-g.
Uit Hfst 8: Recursief opsombare talen
8.3: Meer algemene grammatica's (behalve bewijzen Stellingen 8.13 en 8.14)
Hierbij horen opgaven 8.17-8.20.
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.
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.
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/
