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
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.
Tentamens
Er zijn twee tentamens geweest:
Eerste tentamen: dinsdag 23 december 2014,
14:00-17:00,
in zaal Bezuidenhout in Den Haag.
Het tentamen is nagekeken.
De resulterende cijfers vindt u in het
overzicht met alle cijfers.
Hertentamen: maandag 16 februari 2015, 10:00-13:00,
in het Snellius in Leiden.
Ook dit hertentamen is nagekeken.
Omdat het hertentamen misschien wat lastig was, heeft iedereen een half punt
extra gekregen.
De resulterende cijfers vindt u in het
overzicht met alle cijfers.
Beide tentamens zijn nog terug te vinden in de lijst met oude tentamens
onderaan.
Het nagekeken werk is in te zien bij de docent, op kamer 124 van het Snellius.
Maak eventueel een afspraak.
Twee
Vragenuren
Op vrijdag 19 december 2014 was
er vanaf 13:45 uur
een vragenuur voor het tentamen, in zaal 401 van het Snellius
in Leiden.
Tijdens het vragenuur konden die vragen gesteld worden die opgekomen waren bij
het leren van het tentamen.
Er was een tweede vragenuur op maandag 22 december 2014,
vanaf 13:45, in zaal Babylon, in gebouw Stichthage in Den Haag.
Huiswerkopgave
Bij dit vak valt een kleine bonus (maximaal 0.4pt) voor het tentamen
te verdienen met een huiswerkopgave.
Daarmee zou je, afhankelijk van de afrondingen, je cijfer net iets kunnen
opkrikken, of zelfs van een onvoldoende een voldoende kunnen maken.
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.
De huiswerkopgave is nagekeken.
De resultaten zijn
hier te bekijken.
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:
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
moet missen,
houden we per week bij welke stof en opgaven
we hebben behandeld. U vindt dit overzicht
hier
(compleet, tot en met werkcollege van 8 december 2014).
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 2014 voor de vierde keer gegeven.
Hieronder vindt u de tentamens van de afgelopen twee jaren,
en ook de beide tentamens van dit jaar.
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: 3 augustus 2015
- http://www.liacs.leidenuniv.nl/~vlietrvan1/fi1ie/
