Stapsgewijze verfijning

Elk gegevens­verwerkend proces kan je opsplitsen in 3 grote fasen

INVOER -----> VERWERKING ------> UITVOER

Aangezien het nu juist de bedoeling wordt om algoritmen op te stellen die gegevens verwerken, zullen deze drie stappen in elk algoritme zeker moeten voorkomen.

Om een probleem efficiënt op te lossen moet je een aantal fasen doorlopen. Bij eenvoudige problemen kan je misschien een of andere stap overlaten, maar toch maken we er een gewoonte van om bij elk probleem alle stappen te doorlopen.

1 Probleemdefinitie

In een eerste fase, de probleemdefinitie, ga je duidelijk na wat het probleem is en wat het resultaat is. Het is belangrijk om na te gaan welke gegevens je nodig hebt. Bij de informatie is het belangrijk om na te gaan welke resultaten er juist gevraagd worden.

2 Probleemanalyse

Als je duidelijk weet wat de gegevens zijn en welke informatie je daaruit moet verkrijgen, kan je met het middelste blok van het gegevensverwerkend proces beginnen: de verwerking. Nu is het voor ingewikkelde problemen niet haalbaar om dit allemaal ineens te doen. Je doet er goed aan om een probleem op te splitsen in deelproblemen, die op hun beurt weer verder verfijnd kunnen worden. Dit principe wordt een stapsgewijze verfijning genoemd.

3 Schema

Eens je weet in welke deelproblemen je je probleem zal opsplitsen, kan je beginnen nadenken welke basisstructuren (of controlestructuren) je best gebruikt. De verschillende controlestructuren (sequentie, selectie, iteratie) komen verder aan bod.

Om alles overzichtelijk te houden wordt gebruik gemaakt van een schema. Er bestaan verschillende soorten schema's. Wij beperken ons tot Nassi-Schneidermann-diagrammen, kortweg NS-diagrammen.

Een goed schema bevat alle logica van de oplossing, zonder dat die teveel aan een of andere programmeertaal vasthangt.

4 Programmeren

Eens we definitief weten hoe we alles zullen oplossen kunnen we ons schema in een “echte” programmeertaal vertalen. Welke instructies daar juist voor gebruikt moeten worden hangt af van de programmeertaal die je gekozen hebt. We gebruiken Google App Script, afgekort met GAS, om ons algoritme te testen. We zullen ons schema dan ook vertalen naar een pseudo-code die wat van GAS meeheeft.

Pseudo-code is eigenlijk een soort nepprogrammeertaal die vrij duidelijk is en weinig kennis rond de syntax vereist. Vandaar dat je een sjabloon met algoritmen nodig hebt om deze cursus te kunnen gebruiken. Ze vertalen een aantal “begrijpbare” opdrachten zoals DRUK, LEES, CELOMHOOG, SELECTEER, ... in GAS.

Als je onmiddellijk begint te programmeren zonder eerst na te denken hoe je het programma zal opbouwen kan er achteraf veel tijd verloren gaan om je programma aan te passen tot het werkt. Je komt tot een oplossing met gissen en missen. Dit proberen we zoveel mogelijk te vermijden.

Als je iets op een computerscherm wil toveren, moeten daar een hele hoop instructies, de broncode, voor gegeven worden. Bij sommige zaken, zoals programma’s in GAS, is die eenvoudig op te vragen.

Een ander voorbeeld waar broncode gemakkelijk zichtbaar te maken is, is op Internet. Een Internetpagina wordt gemaakt met een bepaalde programmeertaal, die men HTML (HyperText Markup Language) noemt. Om Internetpagina’s te kunnen opvragen heb je een browser nodig zoals Chrome, Firefox of Safari. Een pagina komt niet binnen zoals je ze ziet. Ze wordt ter plaatse op je computer opgebouwd aan de hand van de broncode.

Naast HTML, dat enkel gebruikt wordt voor de layout van de pagina’s op Internet, wordt ook soms gebruik gemaakt van JAVA-scripts. Ook JAVA-script is een programmeertaal die door je browser geïnterpreteerd kan worden. In deze cursus gaan we niet verder in op HTML en JAVA-scripts.

Je kan de broncode van een Internetpagina eenvoudig opvragen door met de rechtermuisknop te klikken op die pagina en in het snelmenu te kiezen voor Paginabron weergeven.

Broncode kan je uiteraard gewoon intikken. Dit vereist een grondige kennis van de programmeertaal. In de praktijk maakt men ook soms gebruik van programmageneratoren. Dit zijn hulpprogramma’s die in staat zijn om broncode voor jou te schrijven. Voor Internetpagina’s wordt vaak gebruik gemaakt van een “HTML-editor” zoals bijvoorbeeld Dreamweaver. Voor GAS zullen we de macrorecorder gebruiken als programmagenerator. Hiermee kan heel wat van de broncode automatisch gemaakt worden. Het is wel goed om iets van die code te begrijpen. Een programmagenerator zet er dikwijls veel overbodige zaken in, die je achteraf dan ook best verwijdert. Zo is een elementaire kennis van GAS nodig om efficiënt met GAS te kunnen werken. Trouwens: niet alles is mogelijk met programma­generatoren.

Wij zullen in deze cursus de “moeilijke” code overlaten aan een programmagenerator. De instructies binnen ons toepassingsprogramma gaan we opnemen; De eenvoudigere dingen, programmeermethodes, kunnen we zelf. Het komt erop neer dat we een aantal opdrachten met de macrorecorder zullen opnemen. Deze kunnen we dan als verfijningen gebruiken in een groter geheel dat we zelf ontwerpen.

5 Testen

Het is heel belangrijk om je programma, eens het af is, goed te testen. Doet het in alle gevallen wat het moet doen? Als er iets fout loopt kan je nog de laatste verbeteringen aanbrengen. Dit zou eerder uitzondering dan regel moeten zijn. Afhankelijk van de grote van je programma stel je scenario op.

6 Documenteren

Tot slot doe je er goed aan om in je programma wat commentaarlijnen op te nemen die achteraf duidelijk maken wat je met een bepaalde lijn bedoelt, waarvoor een deelalgoritme juist dient, wat je juist nodig hebt om een deelalgoritme te kunnen gebruiken, ...

Deze stap noemen we het documenteren (= documentatie maken). Een programma dat goed gedocumenteerd is, kan achteraf eenvoudiger aangepast worden.

Elk goed algoritme voldoet aan een aantal voorwaarden.

• Bij elk algoritme is er invoer vereist;

• Elk algoritme moet ook een uitvoer voorzien;

• Elke stap moet ondubbelzinnig zijn;

• Een algoritme moet zo algemeen mogelijk gemaakt worden. Dat wil zeggen dat je een en hetzelfde algoritme zodanig moet ontwerpen dat je het in verschillende situaties kan gebruiken. Een programma om een n-de machtswortel van een getal te berekenen is maar goed als je het zowel voor vierkantswortels, als voor derdemachtswortels, als voor tiendemachtswortels, als voor ... kan gebruiken;

• Zorg dat je algoritme juist en betrouwbaar is. En dit in alle denkbare situaties. Als het de helft van de keren niet werkt is je algoritme niets waard. Je algoritme mag niet van zijn pluimen verliezen bij vreemde situaties. In het algoritme voor het berekenen van de n-de machtswortels zal je er moeten op letten dat je geen wortel kan nemen uit een negatief getal, als de exponent even is. Je zal er ook moeten voor zorgen dan de wortelexponent alleen een natuurlijk getal kan zijn. Anders moet je programma dat “beleefd” opvangen, zonder dat het blokkeert.

Het principe

Je kan een complex probleem maar efficiënt aanpakken als je het uiteenrafelt in kleinere, los van elkaar staande deelproblemen. Deze deelproblemen kan je dan nog verder opsplitsen enz. Dit principe noemt men de methode van de stapsgewijze verfijning. Je combineert al deze deelalgoritmen dan tot één geheel en je hebt je algoritme.

We beginnen steeds met een beschrijving in grote lijnen, zonder ons om de details te bekommeren. We noemen dit de grofstructuur.

Voorbeeld

Je wil het 7 uur journaal van één op video opnemen. Je bent niet thuis en vraagt je broer dit te doen. Die heeft dit nog nooit gedaan, dus leg je hem de zaak uit:

Dit wordt in het volgende NS-diagram voorgesteld:

Dit zou je als de grofstructuur kunnen aanzien. Het probleem “Opnemen van 7 uur jounaal” werd uiteengerafeld in een aantal deelproblemen. Een aantal van die deelproblemen zijn misschien concreet, zoals “Wacht tot vijf voor zeven”, maar sommige andere misschien niet. Zo kan je de opdracht “Zet de band juist” verder verfijnen met de volgende opdrachten:

Op een gelijkaardige manier kan je ook nog de andere abstracte deelalgoritmen die in de grofstructuur voorkomen verder verfijnen. We zeggen dat dit opdrachten zijn die voorkomen op diepte 1. Het zijn verfijningen van opdrachten uit de grofstructuur.

Ook dit kan nog verder verfijnd worden. Zo zou je de opdracht “PLAATS de cassette” bijvoorbeeld als volgt kunnen verfijnen:

Deze opdrachten zijn een verfijning van een abstract deelalgoritme uit diepte 1. We zeggen dat dit deelalgoritme zich op diepte 2 bevindt. Hoe groter de diepte, hoe gedetailleerder de omschrijvingen, maar ook hoe kleiner het deel van het probleem dat aangepakt wordt.

Wat is daar nu het voordeel van?

Dit lijkt in het begin fantastisch ingewikkeld. Toch heeft deze methode van werken enkele serieuze voordelen.

Veronderstel dat je op reis wil gaan naar Nice. Dan zou je je reisroute kunnen voorbereiden en gedetailleerd opstellen.

• rijd tot het einde van de straat

• draai naar links

• volg de straat tot op het einde

• draai naar rechts

• rijd tot op het einde

• draai linksaf

• draai aan de derde verkeerslichten linksaf

• ....

• parkeer je wagen

• ga naar de receptie van het hotel.

Dit zou een mogelijkheid zijn. Maar wat als je één foutje hebt gemaakt en op één plaats links hebt gezet in plaats van rechts? Of wat als ergens op je reisweg er een wegomlegging is? Hoe zou je in zo’n geval weten waar het juist is misgelopen en wat je dan moet doen.

Het zou veel meer aangewezen zijn om eerst in heel grote lijnen de reisroute vast te leggen

• Rijd naar de E17

• Neem de E17 tot in Rijsel

• Rijd naar Reims

• Rijd naar Lyon

• Volg de autoroute du soleil tot aan Marseille

• Rijd naar Nice

Dan kan je deze 6 algoritmen, die op zich misschien nog abstract zijn, afzonderlijk verder verfijnen.

Allereerst is deze methode van werken veel overzichtelijker dan alle opdrachten zo maar achter elkaar te plaatsen. Daarenboven is het eenvoudiger om op deze manier een betrouwbare oplossing te bedenken. Je kan je aandacht besteden aan de grote lijnen. Als dit op punt staat kan je deel per deel afzonderlijk afwerken. Ten derde is het met deze manier van werken vrij eenvoudig om fouten te lokaliseren.

Elk deelalgoritme moet een naam hebben. Die namen moeten aan enkele voorwaarden voldoen. Je gebruikt best dezelfde namen in je NS-diagram als deze die je in je eigenlijk programma zal gebruiken.

We maken de volgende afspraken om ons programma duidelijk leesbaar te maken:

• De concrete deelalgoritmen komen volledig in hoofdletters. Voorbeeld

LEES

• De abstracte deelalgoritmen krijgen een naam die bestaat uit één woord.

• De naam bestaat uit afwisselend hoofdletters en kleine letters. De eerste letter van elk woord is een hoofdletter, de andere letters zijn kleine letters. Zo kan je opdracht toch uit meerdere woorden bestaan en blijft alles leesbaar. Voorbeeld:

KleurAchtergrondRood

• De naam van je deelalgoritme moet logisch gekozen zijn. Aan de hand van de naam moet je al kunnen vermoeden wat het deelalgoritme gaat doen, zonder dat je zelf de verfijningen bekijkt.