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 (na de labels) beschrijft de begintoestand: $H(0)$, in kolom B
  • C2 bevat de constante $K$
• elke volgende rij heeft dezelfde formule: =B1 + $C$2

	A	B	C
1	n	H(n)	K
2	0	0	1
3	1	=B(2) + $C$2
...	...	...

Een voorbeeld van een algoritme dat lineair groeit met de omvang van het probleem is Lineair Zoeken. In dit geval ga je voor elk element in de zoekverzameling na of dit voldoet: het aantal elementen dat je (gemiddeld of worst-cast) moet onderzoeken is evenredig met het totale aantal elementen in de verzameling.

Kwadratische groei

In dit geval hangt de toename per stap af van het rangnummer van de stap: $H(n+1)=H(n)+K*n+C$

	A	B	C
1	n	H(n)	K
2	0	0	2
3	1	=B(2) + $C$2*A2 + 1
...	...	...

Voorbeelden van algoritmen en andere situaties met kwadratische groei:

• minder slimme sorteeralgoritmen zoals bubble sort
• netwerken (van internet tot Facebook etc.): het aantal mogelijke (directe) verbindingen groeit kwadratisch; volgens de Wet van Metcalfe (https://nl.wikipedia.org/wiki/Wet_van_Metcalfe) groeit daarom de waarde van een netwerk ook kwadratisch met het aantal elementen (deelnemers).
  • het toevoegen van punt (n+1) aan een netwerk met n punten betekent dat je een verbinding moet maken met alle n bestaande punten: dat geeft de term $K*n$.

Exponentiële groei

Bij exponentiële groei hangt de toename af van de bestaande hoeveelheid: $H(n+1)=H(n)+K*H(n)+C$

	A	B	C
1	n	H(n)	K
2	0	1	0.1
3	1	=B(2) + $C$2*B2
...	...	...

(Vraag: waarom beginnen we hier met $H(0)=1$? Is dat ook nodig als we een waarde voor C (in de eerste formule) groter dan 0 kiezen?)

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.

• voorbeeld: leeg laten lopen van een vat water via een kraan;
• voorbeeld: predator-prey probleem.

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}$. Uitgewerkt in een spreadsheet zijn deze te vinden in REF

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

${\begin{aligned}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\\\end{aligned}}$

Uitgewerkt in een spreadsheet wordt dit:

	A	B	C
1	n	y(n)	dy(n)
2	0	0	1
3	1	= B2 + C2	= C2 + 2
4	...	...	...

Opdracht: controleer dit in een spreadsheet

Deze aanpak: het benoemen van het verschil als hulpfunctie (hulpvariabele), kunnen we voor alle soorten polynomen gebruiken. We geven als voorbeeld nog de afleiding voor $y(n)=n^{3}$:

${\begin{aligned}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\\&=y(n)+dy(n)\\\\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\\&=dy(n)+ddy(n)\\\\ddy(n)&=6.n+6\\ddy(n+1)&=6.(n+1)+6\\&=6.n+6+6\\&=ddy(n)+6\end{aligned}}$

Opdracht werk dit uit in een spreadsheet.

Historie: Babbage's Difference Engine

Tabellen van functies werden in de 18e en 19e eeuw voor veel doeleinden gebruikt. Deze werden gewoonlijk met de hand gemaakt, door menselijke "computers"; de resultaten werde daarna met de hand gezet om te drukken. Een fout bij het rekenen en bij het zetten was snel gemaakt: voor de gebruikers van de tabel was dat soms rampzalig. Charles Babbage bedacht dat een mechanische computer dit zonder fouten zou kunnen doen: hij ontwierp daarvoor de Difference Engine, zie https://en.wikipedia.org/wiki/Difference_engine. Deze gebruikte de bovenstaande aanpak voor het uitrekenen van een tabel van een polynoom. Het resultaat moest ook automatisch gezet worden, om fouten in het drukproces te voorkomen. Tijdens het bouwen van de Difference Engine bedacht Babbage de Analytical Engine: een echte universele computer - uitgevoerd in mechanische technologie. Door de uitdagingen van de mechanische technologie van dat moment, door gebrek aan geld en tijd, en mogelijk door de afleiding door het ontwerp van de Analytical Engine, heeft Babbage de Difference Engine nooit voltooid.