Programmeren met spreadsheets/Voorbeeld: groeiprocessen

Voorbeeld: groeiprocessen

Processen met groei (of krimp) kom je overal tegen:

• de hoeveelheid geld op een bankrekening
• de groei van bacteriën op een voedingsbodem
• de groei van het aantal (mogelijke) verbindingen in een netwerk
• het vollopen van een emmer water onder een kraan
• het leeglopen van een vat met water via een kraan onderin
• en veel andere vergelijkbare voorbeelden.

Deze groei hoeft niet altijd een functie van de tijd te zijn: in de informatica gebruik je het begrip complexiteit om aan te geven hoe de hoeveelheid rekenwerk afhangt van de omvang van het probleem. Voor verschillende algoritmen groeit de hoeveelheid rekenwerk verschillend bij eenzelfde toenamen van de omvang van het probleem.

Het triviale model is *nulgroei*: de hoeveelheid H blijft gelijk.

Lineaire groei

Het eenvoudigste niet-triviale model is lineaire groei: de hoeveelheid H neemt elke stap met een constante toe: $H(t_{n+1})=H(t_{n})+K$. Of ook wel: $H(t+\Delta )=H(t)+K\cdot \Delta$

We kunnen dit groeiproces eenvoudig in een spreadsheet weergeven:

• de eerste kolom (A) geeft de tijd (of het nummer van de stap) weer: $t$; we beginnen, zoals gebruikelijk in de informatica, bij 0.
• de eerste rij beschrijft de begintoestand: $H(0)$, in kolom B
  • C1 bevat de constante </math>K</math>
• elke volgende rij heeft dezelfde formule: =B1 + $C$1

Voorbeelden:

• lineair zoeken

Kwadratische groei

Voorbeelden:

• netwerken (van internet tot Facebook etc.): het aantal mogelijke (directe) verbindingen; wet van Metcalfe (over de waarde van een netwerk)
• (minder slimme) sorteeralgoritmen

Exponentiële groei

Voorbeelden:

• rente (samengestelde interest, "rente op rente")
• sommige rekenprocessen (algoritmen): bijvoorbeeld Traveling Salesman, SAT (voor welke waarden van de logische variabelen levert een bepaalde logische uitdrukking true op?)

Logaritmische groei

Voorbeelden:

• binair zoeken (zie Programmeren met spreadsheets/Voorbeeld: zoeken en sorteren

Simulatie van processen uit de natuur

De manier van werken die we hiervoor gebruikt hebben lijkt sterk op het werken met differentievergelijkingen. Dit zijn de discrete varianten van differentiaalvergelijkingen. Veel processen in de natuur kun je beschrijven met een stelsel differentiaalvergelijkingen. Als je de stapjes in de tijd maar voldoende klein maakt ten opzichte van de snelheid van het proces, dan is deze differentievergelijking een bruikbare benadering van de differentiaalvergelijking.

Tabellen uitrekenen via optellen en aftrekken

De tabel van een groeifunctie maken we door de volgende waarde steeds uit de vorige uit te rekenen. We kunnen dit principe (o.a. voor polynomen) consequent zo doorvoeren dat we voor het uitrekenen van een volgende waarde alleen hoeven op te tellen en af te trekken. We geven hiervan voorbeelden voor $y(n)=n^{2}$ en $y(n)=n^{3}$.

Afleiding voor $y(n)=n^{2}$: y(n) = n^2

y(n+1) = (n+1)^2

           = n^2 + 2.n + 1
           = y(n) + 2.n + 1
           = y(n) + dy(n)

dy(n) = 2.n + 1

dy(n+1) = 2.(n+1) + 1

             = 2.n + 2 + 1
             = dy(n) + 2

Afleiding voor $y(n)=n^{3}$:

y(n) = n^3

y(n+1) = (n+1)^3

           = n^3 + 3.n^2 + 3.n + 1
           = y(n) + 3.n^2 + 3.n + 1

dy(n) = 3.n^2 + 3.n + 1

dy(n+1) = 3.(n+1)^2 + 3.(n+1) + 1

             = 3.n^2 + 6.n + 3 + 3.n + 3 + 1
             = dy(n) + 6.n + 6

ddy(n) = 6.n + 6

ddy(n+1) = 6.(n+1) + 6

               = 6.n + 6 + 6
               = ddy(n) + 6