text: DE ALGORITHMISCHE METHODE
  door Prof. Dr. J. Ponstein
  Tegenstelling met de formulewiskunde
  
  Veel mensen die wiskunde in de praktijk toepassen zullen er weinig bezwaar
  tegen hebben dit vak/ormw/ewiskunde te noemen, omdat er een overstelpen­
  de hoeveelheid wiskundige resultaten is dat de vorm heeft van een formule.
  Wat is de inhoud van een bol met straal R? Antwoord: 47rR3/3. Wat is de
  waarde van een kapitaal na 12 jaar als de aanvankelijke waarde K was, en dit
  bedrag op de bank werd gezet tegen een rente van p procent per jaar, als ook
  telkens de rente van de rente werd gekweekt? Antwoord: K (l + p/100)* 2.
  Tenslotte nog een derde voorbeeld, en daarop zullen we steeds terugkomen.
  Als men telkens de voorraad van een produkt moet aanvullen, als elke aan­
  vulling onmiddellijk geschiedt nadat de wens ertoe wordt geuit en c kost, als
  de voorraadkosten om het produkt in opslag te houden per dag en per
  eenheid k zijn, en de vraag naar het produkt v eenheden per dag is, hoe groot
  moet de aanvulling dan telkens zijn en na hoeveel dagen is de voorraad
  uitgeput, indien men het totaal van aanvullingskosten en voorraadkosten per
  dag zo klein mogelijk wil houden? Antwoorden respectievelijk: (2cv/k)D 2
  en (2c/kv)1I2.
  De formulewiskunde heeft een paar aantrekkelijke voordelen. Vooreerst
  lost men er hele klassen van problemen in één klap mee op. Zo kan men in
  de gegeven voorbeelden R, resp. K en p, resp. c, v en k nog willekeurige
  waarden geven, en voor al deze waarden zijn de formules van toepassing.
  Bovendien hebben die formules een aangename taakverdeling tot gevolg: de
  theoreticus leidt ze af, de practicus past ze toe. De laatste hoeft zich niet in
  te laten met wiskundige bijzonderheden. Wel moet hij de onderstellingen van
  de eerste zorgvuldig nagaan.
   Op een aantal gekompliceerde uitzonderingen na zijn formules ideaal, zo­
  lang ze geldig zijn. Maar reeds voor een eenvoudig probleem als het bovenge­
  noemde derde voorbeeld is die geldigheid twijfelachtig. De gegeven antwoor­
  den hebben namelijk betrekking op een aantal dagen en een aantal eenheden.
  Het is in de praktijk vaak heel redelijk om te eisen dat de uitkomsten dan
  ook gehee/tallig zijn, en dat zijn ze doorgaans volgens de formules niet, ook
  al zijn c, k en v zelf geheeltallig. Met de eis van geheeltalligheid erbij zijn de
  formules in voorbeeld drie in de meeste gevallen fout, en moeten ze worden
  vervangen door het volgende antwoord.
  A l. Bereken (2c/kv)1 °2.
  A2. Als de uitkomst een geheel getal is, dan zijn de formules juist, als we
  bovendien nog aannemen dat v een geheel getal is, en dit zullen we nu
  steeds onderstellen.
  A3. Als de uitkomst geen geheel getal is, bereken dan het grootste getal q
  dat kleiner is dan (2c/kv)G 2. (Dus als c = v = l ; k = 1/10, dan is
  (2c/kv)112 = 4,5 en q = 4.)
  A4. Als q (q + l) > 2c/kv, dan is het optimaal aantal dagen q, en is de opti­
  male aanvulling qv.
  m a b blz. 166
  
  A5. Als q ( q + l ) < 2c/kv, dan is het optimaal aantal dagen q+1, en is de
  optimale aanvulling (q + l)v.
   Het antwoord is er aanzienlijk ingewikkelder op geworden. Soms is het niet
  eens eenduidig, en wel als q (q + l) = 2c/kv, want dan zijn er twee optimale
  oplossingen van het probleem (het probleem met c = v = 1 e n k = l / 1 0 i s e r
  toevallig zo één). Het antwoord heeft de vorm gekregen van een reeks op­
  drachten in een bepaalde volgorde. Dit nu is karakteristiek voor het algo­
  rithme. Eerlijkheidshalve moeten we opmerken dat de formulering van enke­
  le van de stappen A1-A5 te wensen over laat, omdat ze meer iets hebben van
  een bewering, dan van een opdracht. Om dit laatste gaat het: men moet
  precies weten wat men doen moet, ook al zal menigeen willen weten waarom
  de opdrachten zo en niet anders moeten worden uitgevoerd. Uit een precieze
  formulering zal ook moeten blijken wat er gedaan moet worden
  als q (q+1) = 2c/kv in ons voorbeeld. We hebben dan de keus uit drie
  mogelijkheden:
  a. Neem als aantal dagen q.
  b. Neem als aantal dagen q+1.
  c. Kies als aantal dagen q of q + 1.
  Als het aantal dagen eenmaal vast ligt, dan geldt dat natuurlijk ook van de
  aanvulling, reden waarom we die verder buiten beschouwing laten. Keuzen a.
   en b. zijn eenvoudiger dan keus c., zodat men in de praktijk de laatste keus
  buiten beschouwing zal laten. Wij zullen hier echter juist met keus c. verder
  gaan teneinde een zekere graad van ingewikkeldheid te bereiken! We zullen
  dus kiezen tussen q of q+ 1 , of beter we zullen laten kiezen tussen deze twee
  mogelijkheden. De vraag is dan „wie kiest er? ” . Het zal vaak voorkomen dat
  we de uitwerking van een probleem overlaten aan een rekenautomaat, zodat
  we dit redeloze ding zullen moeten laten kiezen. Een rekenautomaat kan
  echter niet kiezen, zodat mogelijkheid c. dreigt te vervallen. Laten we daar­
  om mogelijkheid c. vervangen door:
  c Neem als aantal dagen q o f q+ 1 al naar de uitslag van een kansexperi­
  ment, waarbij de kans op beide uitkomsten 1/2 is.
  Opnieuw komt er een kink in de kabel, omdat opdracht c' niet uitvoerbaar
  is, althans niet door een (digitale) rekenautomaat, want zo’n apparaat is voor
  de volle honderd procent deterministisch van aard, en kan dus strikt genomen geen kansexperimenten uitvoeren. Het blijkt echter dat het volgende
  algorithme zeer goed als een benadering kan dienen (over het waarom ervan
  zullen we cms niet uitlaten).
  BI. Stel x 0 = 1.
  B2. Bereken x 0 maal 455470314 (nu nog een triviale opdracht! ).
  B3. Deel de gevonden uitkomst door 2147483647, en bepaal van die deling
  de rest (het quotiënt doet er niet toe).
  B4. Stel de rest gelijk aan X! en deel Xj door 2147483647, en stel de
  uitkomst gelijk aan r (dus r is een echte breuk).
  B5. Herhaal opdracht B2 t/m B4, maar vervang eerst overal Xi door x2 en
  daarna x 0 overal door x, (opdracht BI blijft ongewijzigd).
   m a b blz. 167
  
  Herhaal opdrachten B2 t/m B4 opnieuw, maar vervang eerst overal x 2
  door x 3 en daarna X! door x 2 . Enzovoort.
  Bereken zo X j, x 2 . . . , x n, . . ..
  In het bovenstaande zijn telkens tussen haakjes mededelingen gedaan die niet
  bij het algorithme horen. Veronderstel nu dat x , , . . . , xn zijn uitgerekend,
  maar dat de waarde van n niet bekend is, bijvoorbeeld doordat het
  algorithme B1-B5 voor allerlei doeleinden dienst heeft gedaan; en dat we
  worden geconfronteerd met de keus tussen q en q + 1 . Dan kunnen we op­
  dracht c' als volgt als een reeks uitvoerbare opdrachten herschrijven:
  C l. Bereken xn+ 1 en de daarbij horende waarde van r volgens de stappen
  B2 t/m B4.
  C2. Als r < 0,5 neem dan als aantal dagen q.
  C3. Als r > 0,5 neem dan als aantal dagen q+1.
   Ook al is het algorithme dan een eindig, welomschreven, uitvoerbaar pro­
  ces van konstruktieve aard, toch kunnen er zich allerlei verrassingen voor­
  doen bij de uitvoering van een algorithme. Zo is het vaak vrijwel onmogelijk
  een goede schatting te geven van het aantal bewerkingen dat moet worden
  uitgevoerd, alvorens het resultaat bekend is. Dit opent de mogelijkheid van
  algorithmen die zeer veel tijd in beslag nemen, in vele gevallen te veel tijd,
  zodat ze halverwege moeten worden afgebroken, met dikwijls als triest ge­
  volg dat de reeds bestede tijd voor niets werd besteed. Het is vanwege deze
  en dergelijke problemen dat het voor de meer ingewikkelde algorithmen een
  vereiste is dat de theoreticus, die het algorithme heeft bedacht, en de practi­
  cus, die er mee moet werken, veel meer samenwerken dan bij de traditionele
  formulewiskunde nodig is. Dit draait er meestal op uit dat de practicus zich
  zal moeten inlaten met een aantal technische details van de algorithmen die
  hij hanteert. Welbekende voorbeelden zijn de algorithmen voor het oplossen
  van lineaire programmeringsproblemen. Wil men volledig profijt trekken van
  bijvoorbeeld primaire en duale technieken en van parametrisch programme­
  ren, dan zal men in staat moeten zijn zelfstandig variaties te bedenken, en
  dat vereist natuurlijk inzicht in deze technieken. Bij primaire technieken
  werkt men voortdurend met oplossingen die aan alle voorwaarden voldoen,
  behalve aan die van optimaliteit; bij duale technieken zorgt men er omge­
  keerd voor dat steeds aan een optimaliteitsvoorwaarde wordt voldaan, maar
  dit gaat ten koste van het nietgeldigzijn van andere voorwaarden. Bij beide
  technieken streeft men naar de situatie waar aan alle voorwaarden is voldaan.
   Parametrisch programmeren betekent de effecten vaststellen van het wijzigen
  van parameters. Daarbij spelen de zojuist genoemde technieken ook weer een
  rol. Overigens zij opgemerkt dat veel van deze variaties in de algorithmen
  zijn ingebouwd, waarvoor men soms moet betalen met een zekere gebonden­
  heid aan de ingebouwde mogelijkheden en met een niet altijd strikt nodige
  omvang en gecompliceerdheid.
  Over de vorm van het algorithme
  
  Hij die een algorithme formuleert moet er van uitgaan dat noch de program­
  meur die het in een computerprogramma vertaalt, noch de gebruiker, kennis,
  laat staan inzicht, moeten hebben in de details van het algorithme. Een
  algorithme kan derhalve in hoge mate onbegrijpelijk zijn voor programmeur
  of gebruiker, als we hier met het woord „onbegrijpelijk” doelen op het
  waarom van het algorithme. Voor de meeste lezers zal dit vermoedelijk het
  geval zijn ten aanzien van het algorithme B1-B5. Des te belangrijker is het
  daarom dat een algorithme verstaanbaar is, dat men het kan lezen en dat men
  dan precies weet wat men moet doen. Het is als het ware een zaak van
  bevelen uitvoeren, ook al ziet men de zin van die bevelen niet in. De ver­
  staanbaarheid van algorithmen (en ook van andere zaken) wordt bevorderd
  door het gebruik van zoveel mogelijk geformaliseerde taal. Hoe meer formalim a b blz. 169
  
  satie, des te minder kans op interpretatiefouten. In het uiterste geval past
  men een volledige formalisatie toe. Dan is het verschil tussen de gehanteerde
  taal en een zogenaamd probleem-georienteerde computertaal (zoals Algol,
  Fortran, Cobol, enz.) niet groot meer, en is het niet meer dan verstandig zich
  te bedienen van zo’n reeds bestaande taal.
   Laten we terugkeren tot het algorithme B1-B5 en zien wat het gevolg is
  van een zekere formalisatie. Daarbij letten we in het bijzonder op stap B5,
  waar in verband met een precieze formulering heel wat aan mankeert, al was
  het alleen maar om het gebruik van het woord „enzovoort” , want hoe moet
  je dit woord vertalen? We voeren twee nieuwe symbolen in, het eerste komt
  in vrijwel elk geformaliseerd algorithme voor (of zou er dienst kunnen doen),
  het tweede komt toevallig voor omdat we te maken krijgen met gehele
  getallen. In plaats van te schrijven „stel de waarde van p gelijk aan . . .” ,
  schrijven we „p: = . . .” , waarin
  = ” als één symbool moet worden opgevat.
  BI kunnen we zodoende vervangen door x 0 : = 1. Het tweede symbool heeft
  betrekking op het bepalen van een rest. Met [p] geven het grootste gehele
  getal aan dat niet groter is dan p. Dan is na te cijferen dat de rest die wordt
  verkregen als we a delen door b, gelijk is aan a-[a/b]b. Laat nu het nietnegatieve gehele getal n gegeven zijn (dus bijvoorbeeld n = 0 o f n =15, enzo­
  voort). Dan kunnen we B1-B5 als volgt formaliseren:
  D l. x 0 : = 1.
  D2. i: = 0.
  D3. als i = n stop, zo niet ga naar D4.
  D4. xi+ 1 : = 455470314xi -[4 5 5 4 7 0 3 1 4 xi/2147483647]2l47483647.
  D5. r: = xj + j /2147483647 en gebruik r in kansexperiment.
  D6. i: = i+1.
  D7. ga naar D3.
   Hoe staat het nu met de uitvoerbaarheid van dit algorithme? Stappen D l en
  D2 geven geen problemen in een computer, want men kan met behulp van
  een computer waarden geven aan variabelen. In stap D3 moeten twee waar­
  den worden vergeleken, en moet eventueel worden gestopt. Beide operaties
  zijn in de computer ingebouwd. In stap D4 staat rechts van het : = symbool
  een uitdrukking waarvan de waarde moet worden bepaald. Dat geeft ook
  geen problemen, omdat de waarde van xj bekend is! In D5 komt de clausule
  voor „en gebruik r in kansexperiment” . Deze clausule is als zodanig natuur­
  lijk volkomen onaanvaardbaar, maar is hier gebruikt als een afkorting van een
  subalgorithme, waarin het gebruik van r in een kansexperiment nauwkeurig
  wordt omschreven. Dit subalgorithme zou er als volgt uit kunnen zien, waar­
  bij we verwijzen naar C1-C3 en met d het optimaal aantal dagen aangeven:
  E l. d : = q.
  E2. als r > 0,5 d: = q + 1, zo niet ga naar E3.
  E3. . ..
   In D6 wordt de waarde van i met één verhoogd! D7 tenslotte bevat de
  opdracht terug te keren naar stap D3, en ook op dergelijke sprongopdrachten
  is de computer berekend. Terugspringen naar een reeds eerder uitgevoerde
  
  m a b blz. 1 70
  
  opdracht betekent een herhaling van de uitvoering van een aantal opdrach­
  ten, mogelijk met inbegrip van de sprongopdracht zelf. Kennelijk dreigt een
  eeuwig durende rondgang. Maar van deze dreiging behoeven we ons niets aan
  te trekken, omdat de waarde van i bij elke rondgang één hoger wordt en dus
  vroeg of laat gelijk zal worden aan de waarde van n, op welk moment het
  programma stopt via stap D3. Het algorithme is dus ook eindig. Verificatie
  van de andere aan algorithmen gestelde eisen laten we aan de lezer over.
  Al bestaat het algorithme uit zeven stappen, de duur van het algorithme is
  ge$n konstante waarde, maar hangt af van n. Gemakkelijk is vast te stellen
  dat het aantal stappen dat wordt uitgevoerd gelijk is aan 5n+3. In verzwakte
  vorm krijgen we hetzelfde voordeel dat we bij het gebruik van formules
  hebben, waarbij we immers allerlei parameters onbepaald mochten laten: de
  waarde van n moet weliswaar bekend zijn voordat we starten met de uitvoe­
  ring van het algorithme, maar het algorithme zelf is goed voor alle (nietnegatieve gehele) waarden van n. Bij het gebruik van de computer is het slechts
  nodig de waarde van n zoals dat in het computerjargon heet ,,in te lezen”.
   Een enkel woord over de noodzaak van algorithmen
  
  Zelfs in een vak als fysica, waar de formulewiskunde een uiterst belangrijke
  rol speelt, zijn de algorithmen reeds lang in gebruik, en wel voor het bepalen
  van de numerieke waarde van allerlei variabelen. Want reeds een simpele
  formule als K (l + p/100)12 levert niet onmiddellijk de numerieke waarde van
  het antwoord, als bijvoorbeeld K = 2500 en p = 4,75. Numerieke wiskunde is
  nodig voor de uiteindelijke bepaling van de waarde van de uitkomsten, en
  deze tak van de wiskunde maakt een intens gebruik van algorithmen. Zal
  men in de fysica veelal toch van formules uitgaan, de economie en aanver­
  wante vakken leveren talrijke problemen, waarvoor het antwoord niet in
  formulevorm bekend is en vermoedelijk ook niet te geven is. Twee bijzonder­
  heden zijn hiervoor op de eerste plaats verantwoordelijk. Aan de ene kant
  het feit dat vaak iets moet worden geoptimaliseerd (zie het derde voorbeeld),
  en aan de andere kant het feit dat allerlei samenhangen niet met vergelij­
  kingen kunnen worden beschreven, maar met behulp van ongelijkheden moe­
  ten worden vastgelegd, zoals dat bijvoorbeeld bij lineaire programmeringspro­
  blemen meestal het geval is.
  m a b blz. 1 71.
  