Teken een venndiagram en bepaal gebied voor gebied wat bij de verzamelingsuitdrukking hoort.
Vul bij telproblemen de gebieden van binnen naar buiten in: eerst alle verzamelingen, dan de paren, dan de losse verzamelingen en tot slot de buitenkant.
Gebruik inclusie–exclusie als controle: |A ∪ B| = |A| + |B| − |A ∩ B|.
Test bij een relatie elke eigenschap op elk paar en geef één tegenvoorbeeld als ze niet geldt.
Tel bij een functie de pijlen die aankomen bij elk element van B: hoogstens één betekent injectief, minstens één surjectief.
Grafentheorie
Handenschudlemma
Σ deg(v) = 2|E|
Volledige grafen
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Reguliere graaf
|E| = n·k/2
Boom en bos
|E| = n − 1, |E| = n − c
Bladeren van een boom
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
circuit: alle graden even; pad: precies 2 oneven graden
Hamiltoncircuits in Kn
(n − 1)!/2
Dijkstra-update
d(v) = min(d(v), d(u) + w(u, v))
Wandelingen van lengte L
(Mᴸ)ij
Methode
Schrijf de graad van elk hoekpunt op; de graden zijn samen twee keer het aantal kanten.
Controleer bij Eulervragen of de graaf samenhangend is en tel de hoekpunten met oneven graad.
Gebruik bij bomen n − 1 kanten en het handenschudlemma.
Houd bij Dijkstra een tabel met voorlopige afstanden bij en leg elke ronde het onafgehandelde hoekpunt met de kleinste afstand vast.
Sorteer voor een minimaal opspannende boom de kanten op gewicht en sla elke kant over die een cykel sluit (Kruskal), of laat één boom groeien vanuit een beginpunt (Prim).
Getaltheorie & modulair rekenen
Deling met rest
a = q·n + r, 0 ≤ r < n
Euclides
gcd(a, b) = gcd(b, a mod b)
Kleinste gemene veelvoud
lcm(a, b) = a·b/gcd(a, b)
Inverse
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Lineaire congruentie
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Eulers φ-functie
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Methode
Reduceer eerst elk getal modulo n; resten liggen tussen 0 en n − 1.
Deel voor een ggd herhaaldelijk met het algoritme van Euclides; de laatste rest ongelijk aan nul is de ggd.
Laat voor een inverse het uitgebreide algoritme lopen en houd de coëfficiënt van a; tel n erbij op als die negatief is.
Los a·x ≡ b op door met a⁻¹ te vermenigvuldigen; combineer twee congruenties door x = r₁ + m₁k te schrijven.
Schrijf bij machten de exponent binair en kwadrateer herhaaldelijk; in RSA is d = e⁻¹ mod φ(n) met φ(n) = (p − 1)(q − 1).
2Oefenopgaven
1.Propositielogica & bewijzenGemiddeld
Welke formule is logisch equivalent met (q ∧ p) → r? Klik erop.
(q ∧ p) → r
1(q → r) ∧ (p → r)
2q → (p → r)
3q ∧ (p → r)
4(q → p) → r
2.Propositielogica & bewijzenMoeilijk
In hoeveel van de 16 rijen van de waarheidstabel is (p ∨ ¬s) ∧ ((q ↔ ¬r) ↔ ¬(r ∧ s)) waar? Noem dit aantal N.
(p ∨ ¬s) ∧ ((q ↔ ¬r) ↔ ¬(r ∧ s))
N =
3.Verzamelingen, relaties & functiesGemiddeld
R = {(1, 1), (1, 3), (2, 3), (3, 1)} is een relatie op {1, 2, 3}. Wat is het kleinste aantal k geordende paren dat aan R moet worden toegevoegd om haar transitief te maken (de grootte van de transitieve afsluiting min |R|)?
R = {(1, 1), (1, 3), (2, 3), (3, 1)}
k =
4.Verzamelingen, relaties & functiesMoeilijk
Een equivalentierelatie R op {1, …, 10} heeft de klassen {3, 6, 10}, {9}, {1, 2, 4, 7}, {5, 8}. Hoeveel geordende paren bevat R? Noem het aantal |R|.
{3, 6, 10}{9}{1, 2, 4, 7}{5, 8}
|R| =
5.GrafentheorieGemiddeld
Heeft de samenhangende graaf een Eulercircuit, een Eulerpad dat geen circuit is, of geen van beide? Klik op je antwoord.
|V| = 7|E| = 11
1Eulercircuit
2Eulerpad, geen circuit
3geen van beide
6.GrafentheorieMoeilijk
Het algoritme van Dijkstra start bij A. Klik op het hoekpunt dat in ronde 4 wordt vastgelegd (definitief gemaakt); A zelf is ronde 1.
start: Aronde 4
1A
2B
3C
4D
5E
6F
7G
7.Getaltheorie & modulair rekenenGemiddeld
Vind de inverse van 60 modulo 71: het getal x met 0 < x < 71 en 60·x ≡ 1 (mod 71).
a = 60n = 71
60−1 mod 71 =
8.Getaltheorie & modulair rekenenMoeilijk
Een RSA-sleutel gebruikt p = 17, q = 41 en e = 11. Ontsleutel de cijfertekst c = 325: bepaal het bericht m.
p = 17q = 41e = 11c = 325
m =
3Oplossingen
1.Propositielogica & bewijzen
Antwoord: q → (p → r)
Logische equivalentie: twee formules zijn equivalent (≡) als ze in elke rij van de waarheidstabel dezelfde waarde hebben. Een tautologie is in elke rij 1, een contradictie in elke rij 0, en een contingentie is geen van beide. Nuttige wetten: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b en ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contrapositie); ¬(a → b) ≡ a ∧ ¬b; en de distributieve wetten, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
De wet
Exportatie: (a ∧ b) → c ≡ a → (b → c). Beide zijn alleen 0 als a = 1, b = 1 en c = 0.
(q ∧ p) → r ≡ q → (p → r)
Controleer met de waarheidstabel
p = 1, q = 1, r = 1: 1 | 1 1 1 1
p = 1, q = 1, r = 0: 0 | 0 0 0 0
p = 1, q = 0, r = 1: 1 | 1 1 0 1
p = 1, q = 0, r = 0: 1 | 0 1 0 0
p = 0, q = 1, r = 1: 1 | 1 1 1 1
p = 0, q = 1, r = 0: 1 | 0 1 1 1
p = 0, q = 0, r = 1: 1 | 1 1 0 1
p = 0, q = 0, r = 0: 1 | 1 1 0 0
Antwoord
q → (p → r)
De kolommen na de streep zijn de opties in de getoonde volgorde.
2.Propositielogica & bewijzen
Antwoord: N = 6
Waarheidstabellen: een formule met n verschillende variabelen heeft 2ⁿ rijen, één voor elke combinatie van waarheidswaarden (1 = waar, 0 = onwaar). Werk van binnen naar buiten en geef elke deelformule een eigen kolom. ¬a draait de waarde om; a ∧ b is alleen 1 als beide 1 zijn; a ∨ b is alleen 0 als beide 0 zijn; a → b is alleen 0 als a = 1 en b = 0; a ↔ b is 1 als beide kanten gelijk zijn.
Relaties: een relatie R op een verzameling X is een verzameling geordende paren (x, y). R is reflexief als (x, x) ∈ R voor elke x in X; symmetrisch als (x, y) ∈ R altijd samengaat met (y, x) ∈ R; antisymmetrisch als (x, y) en (y, x) alleen beide in R zitten als x = y; en transitief als (x, y) en (y, z) in R (x, z) ∈ R afdwingen. Een equivalentierelatie is reflexief, symmetrisch en transitief, en verdeelt X in disjuncte klassen.
Toe te voegen paren
{(2, 1), (3, 3)}
Tellen
k = 2
Antwoord
k = 2
4.Verzamelingen, relaties & functies
Antwoord: |R| = 30
Relaties: een relatie R op een verzameling X is een verzameling geordende paren (x, y). R is reflexief als (x, x) ∈ R voor elke x in X; symmetrisch als (x, y) ∈ R altijd samengaat met (y, x) ∈ R; antisymmetrisch als (x, y) en (y, x) alleen beide in R zitten als x = y; en transitief als (x, y) en (y, z) in R (x, z) ∈ R afdwingen. Een equivalentierelatie is reflexief, symmetrisch en transitief, en verdeelt X in disjuncte klassen.
Paren per klasse
|R| = 3² + 1² + 4² + 2² = 30
Antwoord
|R| = 30
5.Grafentheorie
Antwoord: Eulerpad, geen circuit
Euler, Hamilton en bomen: een samenhangende graaf heeft een Eulercircuit (elke kant één keer, terug naar het begin) als elk hoekpunt even graad heeft, en een Eulerpad dat geen circuit is als precies twee hoekpunten oneven graad hebben; het pad loopt dan van het ene oneven hoekpunt naar het andere. Een Hamiltoncircuit bezoekt elk hoekpunt één keer; Kn heeft er (n − 1)!/2. Een boom op n hoekpunten heeft n − 1 kanten, en een samenhangende graaf met m kanten houdt een opspannende boom over na het verwijderen van m − n + 1 kanten.
Het Eulerpad begint bij het ene oneven hoekpunt en eindigt bij het andere.
6.Grafentheorie
Antwoord: G
Kortste paden en opspannende bomen: het algoritme van Dijkstra legt per ronde één hoekpunt vast: het onafgehandelde hoekpunt met de kleinste voorlopige afstand. Zijn afstand is dan definitief, en elke buur v krijgt d(v) = min(d(v), d(u) + w(u, v)). Het algoritme van Kruskal bouwt een minimaal opspannende boom door de kanten van licht naar zwaar te nemen en elke kant over te slaan die een cykel zou sluiten; het algoritme van Prim laat één boom groeien vanuit een beginpunt door steeds de lichtste kant toe te voegen die eruit vertrekt. Een opspannende boom van n hoekpunten heeft n − 1 kanten.
Dijkstra ronde voor ronde
1. A (0): B: 6, C: 3
2. C (3): E: 18, G: 12
3. B (6): D: 21
4. G (12): E: 16
5. E (16)
6. D (21): F: 34
7. F (34)
ronde 4
G
Antwoord
G
7.Getaltheorie & modulair rekenen
Antwoord: 60−1 mod 71 = 58
Inversen en congruenties: a heeft een inverse modulo n precies als ggd(a, n) = 1. Het uitgebreide algoritme van Euclides schrijft 1 = s·n + t·a, en dan is a⁻¹ ≡ t (mod n). Een congruentie a·x ≡ b (mod n) met ggd(a, n) = 1 heeft de oplossing x ≡ a⁻¹·b. Twee congruenties x ≡ r₁ (mod m₁) en x ≡ r₂ (mod m₂) met onderling ondeelbare moduli hebben één oplossing modulo m₁·m₂ (Chinese reststelling). Eulers φ(n) telt de getallen van 1 tot n die onderling ondeelbaar zijn met n: φ(n) = n·∏(1 − 1/p).
Uitgebreid algoritme van Euclides
Elke rest r wordt geschreven als r ≡ t·60 (mod 71).
r = 71, t = 0
r = 60, q = 1, t = 1
r = 11, q = 5, t = −1
r = 5, q = 2, t = 6
r = 1, q = 5, t = −13
Inverse
1 ≡ −13·60 (mod 71)
x = 58
controle: 60·58 = 3480 = 49·71 + 1
Antwoord
60−1 mod 71 = 58
8.Getaltheorie & modulair rekenen
Antwoord: m = 178
Modulaire machten en RSA: bereken aᵏ mod n door herhaald kwadrateren: schrijf k binair, kwadrateer, reduceer na elke stap en vermenigvuldig de machten waarvan de bit 1 is. Fermat: aᵖ⁻¹ ≡ 1 (mod p) voor een priemgetal p dat a niet deelt, dus de exponent kan modulo p − 1 gereduceerd worden. RSA: kies priemgetallen p en q, n = p·q en φ(n) = (p − 1)(q − 1); de publieke exponent e is onderling ondeelbaar met φ(n), en de privé-exponent is d = e⁻¹ mod φ(n). Versleutel met c = mᵉ mod n en ontsleutel met m = cᵈ mod n.