Deze bladzijde is gearchiveerd.
Het vak FoCS wordt inmiddels in gewijzigde vorm door andere docenten gegeven.
Raadpleeg de studiegids.
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.
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 | |||