Bachelor Informatica in Leiden (I, I&E en I&B).

Het vak Fundamentele Informatica 1 zal met ingang van najaar 2017 door collega dr. Jeannette de Graaf gegeven gaan worden. Deze bladzijde is gearchiveerd.

φ1 Fundamentele Informatica 1

Docent. H.J. Hoogeboom

Archief. FI1 vorige jaren, tot en met 2016.

Vakbeschrijving

Uit de studiegids: Beschrijving. Dit vak verschaft een elementaire wiskundige basis die bij veel informaticavakken impliciet of expliciet als voorkennis wordt verondersteld. Er wordt een begin gemaakt met het formaliseren van begrippen uit de fundamentele informatica.

Leerdoelen. Kennismaken met discrete wiskundige structuren van algemeen belang voor de informatica, leren omgaan met formalisaties, abstracties en bewijstechnieken.

Inhoud. verzamelingenleer, relaties en functies, equivalentierelaties, partiële ordeningen, recursieve definities, volledige en structurele inductie, grafen, bomen en expressies, strings en talen, eindige automaten.

Materiaal

Boek. Schaum's Outline of Discrete Mathematics, door Seymour Lipschutz, Marc Lipson. 'Revised? third' editie, ISBN 0071615865. (De kaft is tegenwoordig minder kleurrijk, maar de inhoud lijkt ongewijzigd.)

Niet alle hoofdstukken worden behandeld tijdens dit college, zie de specificatie van de collegestof.

Collegedictaat. Bestaat uit aanvullingen op het gebruikte boek; de rest is verloren gegaan.
Hoofdstuk 2 (Iteratie, Recursie en Inductie)
Hoofdstuk 3 (Equivalentierelaties: Modulo Rekenen & Aftelbaarheid)
Hoofdstuk 4 (Talen en Automaten)
voorbeeldje verzamelingen, driehoeken in grafen,

Overhead transparanten/slides. De laatste versie van de door de docent gemaakte overheads komen in de loop der tijd op hieronder te staan. pdf gemaakt uit de powerpointjes. Let op de kleurcoderingen.  Rood  is uit het college,  blauw  is uitleg,  groen  is extra rond de stof.

Ch00:FI-Introductie, Ch01:Verzamelingen, Ch02:Relaties, Ch03:Functies, Ch08:Grafen, Chxx:Recursie&Inductie [dragon-curve], Ch10:(binaire)Bomen, Ch12:Talen, Ch02:Aftellen&Modulo, Ch12:Automaten.

Opgaven. Het boek bevat een groot aantal opgaven. Een selectie (aangevuld met eigen bedenksels) vormt de oefenstof [=opgaven] voor de werkcolleges. Er is ook een groot aantal opgaven uitgewerkt. Alternatief de uitwerkingen van Jeroen Laros.

Oude tentamens, bijna allemaal uitgewerkt, om flink te oefenen (en om te kijken hoe de vragen er uit gaan zien)!

Links uit dictaat & overheads


Fundamentele Informatica 2 (inleiding 'theory of computation' / Bonsangue)
Fundamentele Informatica 3 (Formele Talen en Berekenbaarheid / van Vliet)