1. Inleidende begrippen en de programmeeromgeving

1.1 Wat is een algoritme?
1.2 Enkele begrippen.
1.3 De verschillende fasen bij het oplossen van een probleem
1.4 De stapsgewijze verfijning (grofstructuur en verfijningen)
1.5 Oefeningen
1.6 Basisstructuren
1.7 Wat zijn Javascripts?
1.8 Geraadpleegde bronnen

1.1 Wat is een algoritme?

Veronderstel dat je vrienden op bezoek komen en je wilt voor hen hun lievelingsgerecht klaarmaken: spaghetti met een heerlijke saus. Wanneer je reeds verschillende malen dit verrukkelijke gerecht bereidde, dan weet je meteen wat je te doen staat en kan je beginnen koken.

Heb je echter nog nooit spaghettisaus klaargemaakt dan zit je met een probleem. Je weet wel wat je wilt doen, maar je weet niet hoe.

Nu zijn er verschillende mogelijkheden om je probleem op te lossen:

• Je kijkt één van je kennissen heel lief in de ogen en vraagt smekend of zij/hij spaghettisaus voor je wil klaarmaken.
• Je gaat naar een supermarkt en koopt kant-en-klare spaghettisaus.
• Je gooit maar wat ingrediënten in een pot samen en hoopt dat het eindresultaat naar spaghettisaus smaakt.
• Je opent een kookboek en zoekt het recept voor het klaarmaken van spaghettisaus op.

Hoewel elke voorgestelde oplossing zijn voor- en nadelen heeft, lijkt de laatste oplossing ons toch de aangewezen manier om je vrienden een aangename avond te bezorgen.

Een recept is in feite niets meer dan een lijst van al de handelingen die je moet uitvoeren om een welbepaald gerecht klaar te maken. Daardoor is een recept een voorbeeld van een algoritme.

Een algoritme is een voorschrift, uit één of meer stappen opgebouwd, met al de handelingen die men achtereenvolgens moet verrichten om vanuit een gegeven beginsituatie tot het gewenste eindresultaat te komen.

Wanneer we nu willen dat een computer een bepaalde opdracht vervult, dan heeft de computer daarvoor een programma nodig. Een programma bestaat uit een rij instructies die de computer moet uitvoeren om een bepaalde opdracht te kunnen vervullen. Een computerprogramma is dus een voorbeeld van een algoritme.

Vooraleer we computerprogramma's kunnen maken, zullen we dus eerst algoritmen moeten leren opstellen. Met behulp van een programmeertaal kunnen we dan ons algoritme omzetten in een programma.

1.2 Enkele begrippen

Iets of iemand moet de handelingen, beschreven in een algoritme, uitvoeren. Bijvoorbeeld, als we voor het klaarmaken van onze spaghettisaus beroep doen op een recept uit een kookboek, dan zijn wij de uitvoerder van het recept. Een uitvoerder van een algoritme noemen wij een processor. In ons voorbeeld is de kok de uitvoerder (de processor) van het recept.

Ons recept zal waarschijnlijk ingedeeld zijn in verschillende stappen. Iedere afzonderlijke stap binnen een algoritme noemen we een deelalgoritme.

Bepaalde stappen binnen in een algoritme lijken ons vanzelfsprekend, vb. roer in de saus. Dat deelalgoritme kunnen wij zonder verdere uitleg (dat hoop ik toch) uitvoeren. In zo'n geval spreken we van een concreet algoritme.

Andere deelalgoritmen kan de processor niet direct uitvoeren. Er zijn bijkomende instructies nodig vooraleer de processor de handeling kan volbrengen. Dat zijn abstracte algoritmen. Ik kan me inbeelden dat velen met de handen in het haar zullen zitten als ze lezen dat ze eerst de tomaten moeten ontvellen en ontpitten alvorens ze in partjes te snijden en in de saus te mengen.

1.3 De verschillende fasen bij het oplossen van een probleem

Voor ieder probleem dat je wil oplossen, stel je best een algoritme op. Het is wenselijk dat je daarbij overzichtelijk te werk gaat. Zeker als je ook je algoritme wil omzetten in een computerprogramma doorloop je best de volgende fasen.

• Fase 1: De probleemdefinitie.
  In deze eerste fase ga je duidelijk het op te lossen probleem definiëren: je omschrijft dus nauwkeurig en ondubbelzinnig het gestelde probleem en verwoordt de essentie van de opdracht. Je besteedt hierbij vooral aandacht aan de beschikbare gegevens en de wijze waarop die gegevens ingevoerd kunnen worden. Ook de gewenste resultaten en de vorm waarin men die resultaten wil bekomen, worden hier bepaald.
  
• Fase 2: De probleemanalyse.
  In deze fase wordt het algemene probleem geanalyseerd, uiteengerafeld. Er wordt een strategie ontwikkeld om tot een juiste oplossing te komen. Het globale probleem deel je op in een aantal deelproblemen, die indien nodig verder verfijnd kunnen worden. Om de uiteenrafeling van het probleem in verschillende stappen beter te kunnen begrijpen, maak je een schematische voorstelling van de voorgestelde oplossingsmethode. Verschillende technieken (boomstructuur, stroomschema's, Nassi-Schneidermanndiagrammen, pseudo-code,...) kunnen hiervoor aangewend worden.

• Fase 3: Het programmeren
  Nadat fase 2, misschien wel de moeilijkste fase, doorlopen is, kan je het voorgestelde algoritme met behulp van een programmeertaal omzetten in een programma.

• Fase 4: Testen
  Nu ga je het programma uit fase 3 uitproberen. Je laat het programma uitvoeren door de processor (in ons geval, een computer) en je controleert of je programma werkt. Eventuele fouten verbeter je. Het is belangrijk tijdens het testen rekening te houden met alle mogelijke omstandigheden die in fase 1 beschreven werden.

• Fase 5: Documentatie
  Tenslotte ga je het opgemaakte programma documenteren. Dit is bijzonder belangrijk als je, of iemand anders, later wijzigingen of uitbreidingen aan je programma wil aanbrengen.

1.4 De stapsgewijze verfijning

1.4.1 Top-down ontwerpmethode

Zoals hierboven blijkt, is de moeilijkste fase bij het oplossen van een probleem fase 2, de analyse van het probleem. Probleemanalyse wordt een stuk makkelijker als je als volgt te werk te gaat.

• Deel eerst je probleem op in een aantal grote stappen, een aantal deelproblemen. Dit heet de grofstructuur of het hoofdalgoritme.
• Elk deelprobleem in de grofstructuur dat abstract is voor de processor, behoeft verdere instructies. Je zult dit deelprobleem op zijn beurt moeten opsplitsen in kleinere deelproblemen en desnoods nog verder opsplitsen tot ieder deelprobleem concreet genoeg is voor de processor om het uit te voeren. Het opsplitsen van een probleem in deelproblemen die zich op een lager niveau bevinden, noemt men de stapsgewijze verfijning. Hoe meer er gedetailleerd, verfijnd wordt, hoe beter de processor het algoritme begrijpt, m.a.w. hoe concreter het algoritme voor hem wordt.
• De hierboven beschreven methode om een proces te analyseren, noemt men de top-down ontwerpmethode. Die komt grafisch perfect tot uiting in een boomstructuur.

1.4.2 Voorbeeld

Wij weten hoe we een goede spaghetti moeten maken. Een vriend belt op en vraagt of we voor hem even willen opschrijven hoe hij dat moet doen. Laten we te werk gaan zoals hierboven beschreven.

We bepalen eerst de grote lijnen van ons algoritme en stellen dit schematisch voor met een boomstructuur.

Dit noemen we de grofstructuur of het hoofdalgoritme die we schematisch als volgt voorstellen:

Een opdracht in de grofstructuur is doorgaans abstract voor de processor en behoeft verdere verfijning. In ons voorbeeld lijkt me bereid de saus niet direct begrijpbaar voor onze vriend, vandaar dat we die opdracht verder gaan verfijnen:

Indien nodig kun je bepaalde stappen in ons algoritme nog verder concretiseren, nog verder verfijnen.

1.4.3 Voordelen van de stapsgewijze verfijning

Deze manier van werken heeft onmiskenbaar een aantal voordelen.

• Geleidelijk aan zie je zelf beter in hoe je een probleem kunt oplossen.
• Je oplossing is betrouwbaarder, ze is namelijk systematisch bedacht.
• Je oplossing is overzichtelijker en voor iedereen begrijpbaar.
• Je zult makkelijker fouten kunnen opsporen en verbeteren.
• Deeloplossingen kunnen bruikbaar zijn voor het oplossen van andere problemen (zie hieronder).

1.4.4 De bottum-upmethode, tegenhanger van top-down

Bepaalde algoritmen komen veelvuldig terug en kun je hergebruiken als bouwstenen bij het opmaken van een nieuw algoritme. Ideaal ware de situatie waarin we ieder probleem konden terugbrengen tot een algoritme waarvoor al een oplossing bestaat. Jammer genoeg zijn niet alle problemen op te splitsen in deelproblemen die allemaal al opgelost zijn.

Het ontwikkelen van een algoritme door vroeger opgestelde (deel)algortimen te gebruiken, noemt men de bottom-upmethode. Bottom-up is een welgekomen aanvulling op de top-down techniek. Je begint met stapsgewijs te verfijnen. Komt de oplossing van een deelprobleem overeen met een bestaand algoritme, dan gebruik je dit als deeloplossing.

1.5 Oefeningen

Stel algoritmen op voor onderstaande problemen.

Maak een keuze uit onderstaande opgaven. Houd rekening met de verschillende fasen bij het oplossen van een probleem. Vooral de eerste twee fasen zijn hier belangrijk. Voor het analyseren van het probleem gebruik je de stapsgewijze verfijning. Teken boomstructuren om je oplossing schematisch voor te stellen.

1.5.1 Bereken de gemiddelde leeftijd van je gezin.

oplossing

1.5.2 Bak een spiegelei

oplossing

1.5.3 Een trapeziumvormige akker heeft een grote basis van 250 m, een kleine basis van 190 m en een hoogte van 85 m en is beplant met aardappelen. De opbrengst is 225 kg per are. De aardappelen worden verkocht tegen 650 BEF. per 100 kg. Hoeveel heeft dit veld aardappelen opgebracht?

oplossing

1.5.4 Sander heeft een vierde van zijn kapitaal uitgezet tegen 3% en een derde tegen 2.5%. Van het overschot dat 4% opbrengt, ontvangt hij op 3 maanden 3500 BEF. intrest. Hoeveel intrest brengt het gehele kapitaal jaarlijks op?

oplossing

1.5.5 Een btw-aangifte (uitwerking volgt)

oplossing

1.6 Basisstructuren

Het formuleren van een algoritme in gewone spreektaal is omslachtig en vaak voor interpretatie vatbaar. Daarom maken we een aantal afspraken waaraan de formulering en de voorstelling van een algoritme moeten voldoen.

Elk algoritme structureren wij aan de hand van drie basis- of controlestructuren. Elke controlestructuur heeft een bepaalde programmeercode. Voor de voorstelling van onze basisstructuren gebruiken wij Nassi-Schneidermanndiagrammen.

Hoewel hierop in de volgende hoofdstukken uitvoerig op deze basisstructuren teruggekomen wordt, geven wij hier al een korte opsomming van die drie basisstructuren en hun grafische voorstelling.

1.6.1 De sequentie of opeenvolging

Een sequentie is een controlestructuur opgebouwd uit één of meer opdrachten die elkaar opvolgen. Deze controlestructuur legt vast in welke volgorde de deelalgoritmen zullen uitgevoerd worden.

1.6.2 De selectie of keuze

Een selectie is een basisstructuur die een keuze aangeeft tussen twee mogelijke sequenties, gekoppeld aan een voorwaarde.

Voorbeeld: In een winkel wordt 20% korting gegeven als het aankoopbedrag groter is dan 10 000 BEF, 10% korting in alle andere gevallen.

1.6.3 De iteratie of de herhaling

Een iteratie is een controlestructuur die een bepaalde opdracht een aantal keer herhaalt.

Voorbeeld: Voor een groot familiefeest moet je 100 identieke taarten bakken.

1.7 Wat zijn Javascripts?

Om onze algoritmen om te zetten in een programma, zodat we het door de computer op zijn juistheid en bruikbaarheid kunnen laten uittesten, gebruiken we een programmeertaal. Wij opteren voor een eenvoudige programmeertaal, namelijk Javascripts.

Om een Javascript uit te voeren heb je een webbrowser nodig (bv. Microsoft explorer of Netscape Navigator). Een webbrowser wordt in eerste instantie gebruikt om pagina's van het Internet te plukken en in een toonbare vorm aan de gebruiker te presenteren, om te surfen dus. Internetpagina's worden in een speciale taal geschreven, namelijk HTML. Onze Javascripts zullen wij dus altijd in een HTML-document moeten plaatsen.

HTML is de afkorting van Hyper Text Markup Language. Het is de taal waarin alle pagina’s op het World Wide Web zijn geschreven. In simpele bewoordingen uitgedrukt, HTML vertelt aan de Internetbrowser - Netscape Navigator of Microsoft Explorer - hoe de tekst moet getoond worden, of er afbeeldingen in de pagina staan, enz.

Het formaat en de opmaak van de tekst en de afbeeldingen worden aangeduid door TAGS, een soort van code. Voor elk formaat bestaat er een aparte tag, bv. om een stukje tekst vet voor te stellen, gebruikt HTML de volgende code : <B>deze tekst is vet</b>.

Hieronder zie je een eenvoudig voorbeeld van een eenvoudige webpagina met de bijhorende HTML-code.

HTML kun je op twee manieren gebruiken:

• Je ontwerpt je pagina met een eenvoudige teksteditor en je plaatst de codes zelf. Dit betekent natuurlijk dat je alle HTML-tags kent en kunt gebruiken.
• Je gebruikt een speciale HTML-editor. Je typt nog steeds zelf je tekst in, maar nu plaats je de HTML-codes via een simpele klik op de muis, net zoals je een tekstverwerkingsprogramma zou gebruiken.

Net zoals HTML moet je Javascripts aanmaken met een simpele teksteditor, bijvoorbeeld kladblok, meegeleverd met Windows 95. Om duidelijk te maken waar je Javascript begint, moet het script tussen een <script language="Javascript"> en </script>tag in een HTML-document geplaatst worden.

Net zoals elke programmeertaal moet je bijzonder oppassen voor syntaxfouten. Een haakje, komma, ... op een verkeerde plaats kan ervoor zorgen dat je programma niet werkt.

De Javascripttaal maakt een onderscheid tussen hoofd- en kleine letters.

Wil je commentaar aan je programma toevoegen dan laat je die lijn voorafgaan door //. Heb je meerdere lijnen commentaar dan begin je met /* en eindig je met */.

Het volgende voorbeeld toont de algemene vorm van een Javascript binnen een HTML-document. Open kladblok, typ de hieronderstaande codes precies over en bewaar je bestand als basis.htm. Dit bestand doet dienst als basis voor elk programma dat je zal maken in Javascript.

<html>
<head>
</head>
<body>

<script language="javascript">
//hier begint het eigenlijke script

//hier komt de code

</script>

</body>
</html>

In de hiernavolgende hoofdstukken kom je alles te weten over het opmaken van programma's met de Javascripttaal. Stap voor stap zal je heel wat commando's aanleren. Ook het omzetten van de drie basisstructuren wordt aangeleerd. Veel succes!!

1.8 Geraadpleegde werken

W. De Raedt, e.a. Algoritmen in, Inform, Basisboek 4.1, Uitgeverij Pelckmans, Kapellen, 1998. p. 72-84.
L. Robben, e.a. Ontwerpen en beschrijven van oplossingen, Uitgeverij Wolters.
Javascript in 20 stappen, Uitgeverij Sybex, Soest, 1998.

filip.santens@burgerschool.be

Naar inhoudstafel