Discrete wiskunde
Domein Discrete wiskunde bevat telproblemen, grafen en recurrente betrekkingen. Het examen toetst of je een situatie kunt vertalen naar een graaf of betrekking, en of je de bijbehorende standaardtechniek foutloos uitvoert.
Kernregels
- Permutaties: n! ordeningen van n verschillende objecten. Combinaties: binom(n, k) = n!/(k!(n − k)!) deelverzamelingen van grootte k.
- Tellen met een rooster: het aantal kortste routes van (0,0) naar (a,b) is binom(a+b, a).
- Graaf: de graad van een punt is het aantal lijnen eraan. Een Euler-pad bestaat precies als er nul of twee punten met oneven graad zijn.
- Boom: samenhangend en zonder kring, met n − 1 lijnen. Een minimale opspannende boom vind je met Prim of Kruskal; voor het kortste pad gebruik je Dijkstra.
- Lineaire recurrente betrekking van de eerste orde: u(n) = a·u(n−1) + b. De oplossing is een evenwichtswaarde plus een homogeen deel A·a^n, waarbij je A uit de beginwaarde haalt.
Uitgewerkt voorbeeld
Gegeven u(n) = 3·u(n−1) + 4 met u(0) = 1. Zoek eerst een constante oplossing c: c = 3c + 4 geeft c = −2. De algemene oplossing is dus u(n) = A·3^n − 2. Met u(0) = 1 volgt A − 2 = 1, dus A = 3 en u(n) = 3^(n+1) − 2. Controle met n = 1: de betrekking geeft 3·1 + 4 = 7 en de formule geeft 9 − 2 = 7. Zo'n controle met één stap is de snelste manier om een rekenfout te vinden.
Valkuilen
- Bij combinaties maakt de volgorde niet uit, bij permutaties wel; lees de vraag op dat punt twee keer.
- Een graaf met twee oneven graden heeft wel een Euler-pad maar geen Euler-kring.
- Dijkstra werkt alleen betrouwbaar met niet-negatieve gewichten.