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

Deze bladzijde is gearchiveerd.
Het vak FoCS wordt inmiddels in gewijzigde vorm door andere docenten gegeven. Raadpleeg de studiegids.

🦊 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.

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
Grafische methode om te redeneren met verzamelingen.
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
Algebraisch redeneren met verzamelingen: Boolese algebra. Idempotent, associatief, commutatief, distributief, identiteit, dubbel complement, complement, De Morgan. Absorptie.
2-2 inclusie&exclusie, machtsverzameling
Tellen van de elementen in overlappende verzamelingen. De verzameling ℘(A) van alle deeelverzamelingen van een verzameling A: X⊆ A desda X∈ ℘(A).
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
combinatoriek 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.
Bomen
Sch. 8.8
bomen 8-0 bomen, introductie
8-1 ongerichte bomen
Eigenlijk ongerichte grafen, samenhangend, zonder cykels. Bij n knopen zijn er n-1 lijnen.
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
Er zijn verschillende soorten "oneindig": ℕ is aftelbaar, ℝ is overaftelbaar (Cantor). In het algemeen heeft ℘(A) meer elementen dan A.
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
Talen die gemaakt kunnen worden met behulp van vereniging, concatenatie, en ster. Dit zijn de taal-equivalenten van de programmeerconcepten selection, sequence en iteration. Ook bekend als reguliere expressies.
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
Gerichte grafen met letters op de pijlen om talen te specificeren. Toestand, transitie, accepteren. Determinisme. Kleene: eindige automaten accepteren precies de reguliere talen.
11-3a voorbeelden
Even, oneven. Posities, eerste en laatste. Boolse combinaties. Volgorde.
12-1 ☒context-vrije grammatica
Elementaire recursie om talen te definieren.
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.)