Bachelor Informatica in Leiden, alle richtingen (Informatica, I&Economie, Bioinformatica en variant KI ).

FoCS 2021

Dit studiejaar wordt het vak Foundations of Computer Science weer gegeven door J.M. de Graaf. Zie ook Brightspace.

Foundations of Computer Science 2020

Discrete wiskunde voor Informatici. Verzamelingen, relaties, functies, grafen, bomen, inductie, combinatoriek, modulo rekenen, aftelbaarheid, reguliere talen en eindige automaten.

Docenten. H.J Hoogeboom (Hendrik Jan) en J.M. de Graaf (Jeannette)

Discussieforum. Via Brightspace. Voor tips en vragen over de organisatie en over de lesstof.

Archief. De docenten gaven het vak al eerder, onder de naam Fundamentele Informatica 1. De inhoud van het vak zal nauwelijks wijzigen, zie JMdG 2018 en HJH 2016. Als FoCS werd het vorig jaar door V. Dunjko gegeven.

Materiaal

College aan de hand van het boek Outline of Discrete Mathematics van Schaum. Zie de inhoudsopgave hieronder. Beschikbaar zijn de wekelijkse slides, video opnames en werkcollege opdrachten.
Extra stof wordt in dit overzicht aangegeven met ☒, net als in de slides.

Ik nummer de weken zó dat de college-vrijdag hoort bij de werkcollege-dinsdag met dezelfde stof

wk datum onderwerp slides 🎦videos werkgroep
1/0 di.1.9.20 Welkom overzicht introductie opdracht 0
2/1 vr.4.9.20 Verzamelingen
Sch 1.1 tm 1.4
verzamelingen 1-1 definities
verzameling { }, element ∈, gelijkheid, (echte) deelverzameling ⊆, inclusie, reflexief, anti-symmetrisch, transitief, partiele ordening, natuurlijke ℕ, gehele ℤ, rationale ℚ, reele getallen ℝ, universum U, lege verzameling ∅, doorsnede ∩, vereniging ∪, complement

1-2 Venndiagram
di.8.9.20 howto: bewijzen opdracht 1
3/- vr.11.9.20 excursie De Leidsche Flesch
di.15.9.20
4/2 vr.18.9.20 Sch 1.5 tm 1.7
(Sch 1.8 later)
2-1 verzamelingenalgebra
2-2 inclusie&exclusie, machtsverzameling
Russell paradox
di.22.9.20 opdracht 2
5/3 vr.25.9.20 Relaties
Sch. 2.1 tm 2.7
relaties 3-1 Cartesisch product, representatie
ℕxℕ, geordend paar (x,y), relatie van A naar B, in A, inverse, identiteit/gelijkheid/diagonaal, matrix, gerichte graaf, pijldiagram, grafiek, origineel, domein, beeld, bereik, n-tupel.

3-2 eigenschappen, compositie
3-3 relatie "in", afsluiting
di.29.9.20 opdracht 3
6/4 vr.2.10.20 Sch 2.8, 2.9
Functies
Sch 3.1 tm 3.3, 3.5

functies
4-1 relaties: equivalentie, partieel
4-2 functies: begrippen
4-3 bijecties, cardinaliteit
di.6.10.20 opdracht 4
7/5 vr.9.10.20
Grafen
Sch 8.2 tm 8.4, 8.6

grafen
4-4 rijen en reeksen
5-1 grafen introductie
5-2 basisbegrippen
5-3 paden en componenten
di.13.10.20 opdracht 5
8/6 vr.16.10.20 Sch 8.5, 8.7 5-4 Euler en Hamilton
6-1 isomorf, speciale grafen

Gerichte grafen
Sch 9.2, 9.3
6-2 ☒vlakke grafen
6-3 gerichte grafen
di.20.10.20 toets FoCS
9/- vr.23.10.20 (toetsweek)
di.27.10.20 opdracht 6
10/7 vr.30.10.20 Inductie en Recursie
Sch 1.8, 3.6, 6.6, 6.7, 11.3
inductie 7-1 voorbeelden recursie uit de informatica
Pythagorasboom, torens van Hanoi, quicksort, mergesort, Backus-Naur form, context-vrije grammatica, syntax propositie-logica, Fibonacci,

7-2 recurrente betrekkingen en inductieve definities
7-3 inductie als bewijsmethode
Volledige/natuurlijke inductie. Basis, inductie-aanname / -hypothese, inductiestap. Structurele inductie.

7-4 ☒Droste en Escher
di.3.11.20 opdracht 7
11/8 vr.6.11.20 Combinatoriek
Sch 5.x
Bomen
Sch. 8.8
combinatoriek

bomen
6-4 combinatoriek
Tellen. Som- en productregel. Objecten kiezen: met/zonder herhaling, wel/niet geordend. Faculteit n! permutatie, binoniaalcoefficient, n boven k, driehoek van Pascal, binomium van Newton, bomen, Catalangetallen.

8-0
bomen, introductie
8-1 ongerichte bomen
di.10.11.20 opdracht 8
12/9 vr.13.11.20 Sch. 9.4, 10. 9-1 gerichte bomen
9-2 binaire bomen
di.17.11.20 opdracht 9
13/10 vr.20.11.20 Modulo rekenen
Sch. 11.8 Aftelbaarheid
Sch. 3.7
twee equivalenties 10-0 introductie
10-1 modulo rekenen
10-2 (over)aftelbaar
di.24.11.20 opdracht10
14/11 vr.27.11.20 Talen en automaten
Sch. 12.2 tm 12.4
talen en automaten 11-0 introductie
11-1 formele talen
11-2 reguliere talen
di.1.12.20 opdracht11
15/12 vr.4.12.20 Sch. 12.5
Grammatica's, Turing machine
☒Sch. 12.6,13.4
11-3 eindige automaten
11-3a voorbeelden
12-1 ☒context-vrije grammatica
12-2 ☒Turing machine
Belangrijk machine model. Wát we kunnen berekenen (computability), en hoe efficient we dat kunnen (complexiteit).
di.8.12.20 opdracht12
16/13 alle slides
klaar!
zie hieronder

Oefenen!

Er is véél oefenmaterieel. Allereerst natuurlijke de wekelijkse opgaven hierboven, die voorzien zijn van uitwerkingen. Daarnaast sommen in Schaum, oude toetsen en oude tentamens, ook veelal met uitwerkingen. Over de laatste jaren hier een overzicht van de onderwerpen die in de tentamens aan de orde kwamen.
Tip: Eerst zelf proberen, dan naar de oplossingen kijken. * (verbeterd tov files die elders staan.)