3.4.oefeningen.md

Oefeningen 3.4 · Slide 45

Theorie

Oefening 3.4.1

Wat is ƒ(6)?

Dit soort vragen kan op een examen komen!

oefening 3.4.1 a)

ƒ(0) = 1
ƒ(1) = 2
ƒ(n) = ƒ(n - 1) + 2ƒ(n - 2)     als n > 1

Iteratief

n	0	1	2	3	4	5	6
ƒ(n)	1	2	4	8	16	32	64

ƒ(6) = 64

Uitwerking in pseudocode:

berekenRecursief(I: n: geheel getal): getal: geheel getal
    * Postconditie: n is een natuurlijk getal
    * Preconditie: ƒ(n) werd berekend
    * Gebruikt: berekenRecursief
BEGIN
    ALS (n = 0 OF n = 1) DAN
        getal <- n + 1
    ANDERS
        getal <- berekenRecursief(n - 1) + 2 . berekenRecursief(n - 2)
    EINDE ALS
    RETOUR (getal)
EINDE

Hoelang gaat dit duren?
T(0) = Θ(1)
T(1) = Θ(1)
T(n) = T(n - 1) + T(n - 2) + Θ(1) als n ≥ 2

Na vereenvoudiging:
T(0) = 1
T(1) = 1
T(n) = T(n - 1) + T(n - 2) als n ≥ 2

Exponentiële tijdscomplexiteit

berekenIteratief(I: n: geheel getal): getal: geheel getal
    * Postconditie: n is een natuurlijk getal
    * Preconditie: ƒ(n) werd berekend
    * Gebruikt: /
BEGIN
    voorvorig <- 1
    vorig <- 2
    getal <- 1
    ALS n = 1 DAN
        getal <- 2
    ANDERS
        VOOR i = 2 TOT n DOE
            getal <- vorig + (2 . voorvorig)
            voorvorig <- vorig
            vorig <- getal
        EINDE VOOR
    EINDE ALS
    RETOUR (getal)
EINDE

T(n) = Θ(n)

oefening 3.4.1 b)

oefening 3.4.1 c)

ƒ(1) = 2
ƒ(n + 1) = nƒ(n) - 1        als n ≥ 1

Stel m = n + 1 <=> n = m - 1

ƒ(1) = 2
ƒ(m) = (m - 1) . ƒ(m - 1) - 1       als (m - 1) ≥ 1 <=> m ≥ 2

Iteratief

n	1	2	3	4	5	6
ƒ(n)	2	1	1	2	7	34

ƒ(6) = 34

Uitwerking in pseudocode:

berekenRecursief(I: n: geheel getal): getal: geheel getal
    * Postconditie: n is een natuurlijk getal ≥ 1
    * Preconditie: ƒ(n) werd berekend
    * Gebruikt: berekenRecursief
BEGIN
    ALS n = 1 DAN
        getal <- 2
    ANDERS
        getal <- (n - 1) . berekenRecursief(n - 1) - 1 // n-1 is belangrijk hier, anders oneindige lus
    EINDE ALS
    RETOUR (getal)
EINDE

T(1) = 1
T(n) = T(n - 1) + Θ(1)

T(n) = n, T(n) = Θ(n)

berekenIteratief(I: n: geheel getal): getal: geheel getal
    * Postconditie: n is een natuurlijk getal ≥ 1
    * Preconditie: ƒ(n) werd berekend
    * Gebruikt: /
BEGIN
    getal <- 2
    VOOR i = 2 TOT n DOE
        getal <- (i - 1) . getal - 1
    EINDE VOOR
    RETOUR (getal)
EINDE

Oefening 3.4.2 a)

Gegeven: a ≠ 1
Te Bewijzen: 1 + a + a² + ... + aⁿ = (a^{n + 1} - )/(a - 1) als n ≥ 0

Bewijs:

1. Basisstap: n = 0
   LL: 1
   RR: (a^{n + 1} - )/(a - 1) = (a¹ - )/(a - 1) = 1
   
2. Inductiestap
   Stel dat 1 + a + a² + ... + a^m = (a^{m + 1} - 1)/(a - 1) als m ≤ n (Inductiehypothese)
   1 + a + a² + ... + aⁿ + a^{n + 1} = (1 + a + a² + ... + aⁿ) + a^{n + 1} (Onderlijnt = inductiehypothese)
   = (a^{n + 1} - 1)/(a - 1) + a ^{n + 1}
   = (a^{n + 1} - 1 + a^{n + 1}(a - 1)) / a - 1
   = (a^{n + 1} - 1 + a^{n + 1 + 1} - a^{n + 1}) / a -1
   = (a^{n + 2} - 1) / a - 1
   QED

Oefening 3.4.2 b)

Gegeven: n ∈ N₀
Te Bewijzen: (1/1.3) + (1/3.5) + (1/5.7) + ... + (1/(2n - 1)(2n + 1)) = n/(2n + 1) voor n ≥ 1

Bewijs:

1. Basisstap: n = 1
   LL: 1 / ((2n - 1)(2n + 1)) = 1/1.3
   RR: n / (2n + 1) = 1 / (2 . 1 + 1) = 1/1.3
   
2. Inductiestap:
   Stel dat (1/1.3) + (1/3.5) + (1/5.7) + ... + (1/(2m - 1)(2n + 1)) = m/(2m + 1) voor m ≤ n (inductiefase)

Oefening 3.4.6 a)

power(I: n: geheel getal): getal: geheel getal
    * Postconditie: n is een geheel getal
    * Preconditie: ƒ(n) werd berekend
    * Gebruikt: power
BEGIN
    ALS n = 0 DAN
        resultaat <- 1
    ANDERS
        resultaat <- x . power(x, n - 1)
    EINDE ALS
    RETOUR (resultaat)
EINDE

Oefening 3.4.6 b)

powerVerbeterd(I: n: geheel getal): getal: geheel getal
    * Postconditie: n is een geheel getal
    * Preconditie: ƒ(n) werd berekend
    * Gebruikt: powerVerbeterd
BEGIN
    ALS n = 0 DAN
        resultaat <- 1
    ANDERS
        ALS n % 2 = 0 DAN
            resultaat <- powerVerbeterd(x . x, n / 2)
        ANDERS
            resultaat <- x . powerVerbeterd(x, n - 1)
        EINDE ALS
    EINDE ALS
    RETOUR (resultaat)
EINDE