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