8 t/m 19

Opdracht 8 Onmogelijke vragen Met dank aan René Franquinet voor het bedenken van enkele onmogelijk vragen. a In de reisplanner voor het seizoen 1999-2000 was deze informatie niet voorhanden. b Een beetje merkwaardige vraag als het om het plannen van een reis gaat, maar dit geeft aan dat de precieze specificatie van de taken van de reisplanner ook beperkingen tot gevolg heeft. Het verloop van de prijzentabel is uit het spoorboekje direct duidelijk, maar in de reisplanner kun je die tabel niet direct inzien. De prijzen zijn gekoppeld aan een reis, normaal gesproken precies wat nodig is. Het bepalen van het maximumtarief is op zich niet lastig: bedenk een zeer lange reis, bijvoorbeeld Vlissingen naar Maastricht via Groningen. Om de grens bij benadering te vinden, moet je de reis inkorten, totdat de prijs opeens omlaag gaat. Dan ben je net onder de afstand van het maximumtarief gedoken. Vanaf mei 2001 zijn de grenzen: xxx c Merkwaardig genoeg kan de reisplanner voor het seizoen 1999-2000 geen reisschema’s aan met gelijke vertrekplaats en bestemming. De kaart met de route wordt wel getoond, maar er komt geen reisadvies. Je moet de rondreis daarom in tweeën knippen.

Opdracht 9 De specificatie van het proces ‘reisschema bepalen’ a/b Het aankomststation van een treinrit moet gelijk zijn aan het vertrekstation van de opvolgende rit. De aankomsttijd van een rit moet voor de vertrektijd van de volgende rit zijn. Bij de onder a gegeven schema’s is dit niet zo. d Vertrekplaats a, doelplaats b, datum d en vertrektijd t. e Het verschil is de voorlaatste zin: De vertrektijd van de eerste rit ligt zo dicht mogelijk bij (eventueel na) t.

Opdracht 10 Deelprocessen specificeren a Invoer: vertrekplaats en bestemming
Uitvoer: een lijst van trajecten (of ritten), elk met vertrekplaats en bestemming en eventueel het nummer van de tabel in het spoorboekje. De ritten moeten aansluiten, zie opdracht 10. b Ook bij dit proces moet onderscheid gemaakt worden tussen uitgaan van aankomsttijd en uitgaan van vertrektijd. We nemen hier de eerste. Invoer: vertrekplaats, bestemming, aankomsttijd. Uitvoer: vertrektijd. c Ook dit proces makt gebruik van het deelproces ‘Reisroute vinden’, precies als het andere proces. Bij het bepalen van de reistijden moet nu worden uitgegaan van de vertrektijd (de twee tijden ruilen van plaats). Een ander verschil is de volgorde waarin de reisroute wordt afgewerkt: bij de gegeven vertrektijd werk je de lijst van voren naar achter af, bij de gegeven aankomsttijd is dit andersom. NB: er zijn varianten mogelijk. Zo zou je één proces ‘Reistijden bepalen’ kunnen specificeren. Invoer: vertrek, bestemming, tijd en een variabele die aangeeft of de tijd vertrek of aankomst aanduidt. Uitvoer: de andere tijd.

Opdracht 11 De spoorkaart in een Access-gegevensbank

Voor de docent Pointe achter deze opdracht is leerlingen laten beseffen dat ook zoiets als een spoorkaart in een database gestopt kan worden en dat je dan nuttige informatie kunt opzoeken. Verder is het een eerste, zeer kleine kennismaking met Access en SQL. In principe heb je in Access genoeg aan één tabel met twee kolommen om reisroutes te zoeken: Station ligt op Lijn. Om kortste routes te vinden hebben we de positie op de lijn toegevoegd. De informatie is direct afkomstig uit het spoorboekje. We hebben de meeste grote lijnen en hoofdstations opgenomen. Sommige lijnen splitsen zich (Utrecht - Den Haag en Utrecht - Rotterdam staan in één tabel) In dat geval hebben we de afsplitsing een apart driecijferig nummer gegeven: het lijnnumer met een 1 erachter. Kleinere stations bij grote plaatsen zijn weggelaten, daardoor kun je toevoegingen als ‘CS’ weglaten. De reisroutes vind je door herhaald de tabel te koppelen met zichzelf: Je zoekt eerst de lijnen waarop een gekozen vertrekstation ligt. Door een join met de tabel zelf (kolommen Lijn gelijk) vind je de andere plaatsen op die lijnen. Extra eis: vertrekplaats ongelijk aan bestemming. Zo vind je alle directe verbindingen vanuit een gekozen plaats. De query (de tekst Geef_de_naam_van_het_vertrekstation zorgt ervoor dat Access een pop-up venstertje toont met deze vraag):

SELECT Vert.Station, Vert.Lijn, Aank.Station, ABS(Vert.Km-Aank.Km) AS Afstand
FROM StationsLijnen AS Vert, StationsLijnen AS Aank
WHERE Vert.Lijn = Aank.Lijn AND Vert.Station <> Aank.Station AND Vert.Station = Geef_de_naam_van_het_vertrekstation;

Door dit te herhalen vind je ook de verbindingen over twee lijnen. Dit wordt een query waarin de tabel vier keer nodig is. Het is niet mogelijk om een query te maken die routes vindt ongeacht het aantal lijnen. Dit is een beperking van de taal SQL.

Uitwerking c Utrecht ligt op de lijnen 14, 20, 24, 32, 33, 42 en 50. In werkelijkheid zijn dit er nog meer, omdat niet de volledige spoorkaart in de dartabase zit. d Direct vanuit Tilburg: Roosendaal, Breda (2 lijnen), Den Bosch, Venlo, Eindhoven, Dordrecht. e Vijftien stations kunnen met een tussenstap vanuit Tilburg beriekt worden, zeven daarvan via twee verschillende routes, Geldermalsen zelfs via drie routes. Het resultaat heeft daarom 24 rijen. f Utrecht - Geldermalsen (via lijn 24) - Dordrecht (lijn 19): 75 kilometer. Utrecht - Rotterdam (via lijn 50) - Dordrecht (lijn 11): 76 kilometer. Utrecht - Eindhoven (via lijn 24) - Dordrecht (lijn 27): 168 kilometer.

Opdracht 12 Het kortste-pad-algoritme van Dijkstra

Voor de docent De applet op de cdrom bij het werkboek biedt de mogelijkheid om een flink algoritme te volgen. Het gaat hier om het inzicht dat een algoritme zeer gestructureerd en volgens precieze regels te werk gaat.

De werking van het algoritme is als volgt: · Vanuit de vertrekplaats bekijk je alle mogelijke directe verbindingen naar buurplaatsen. Vanuit Leiden op de kaart van midden- en zuid-Nederland zijn dat Den Haag, Haarlem en Woerden. We hebben nu een lijstje van drie ‘bereikte’ plaatsen. In de applet worden deze groen. · De dichtsbijzijnde (Den Haag) kan onmogelijk via een korter pad bereikt worden. We markeren deze als ‘kortste-pad-gevonden’, blauw in de applet. · Vervolgens kijken we naar nieuwe verbindingen vanuit deze plaats (Rotterdam en Gouda), We krijgen nu een lijst van vier (Haarlem, Woerden, Rotterdam en Gouda) · Dichtstbijzijnde is nu Haarlem, het proces herhaalt zich. · Soms komt het voor dat er een tweede route naar een plaats gevonden wordt, bijvoorbeeld naar Gouda: eerst via Den Haag, daarna via Woerden. Het algoritme neemt dan de kortste van de twee routes en kleurt de afgewezen verbinding rood. Het komt regelmatig voor dat er eerst een lange route gevonden wordt en daarna pas de kortste, probeer bijvoorbeeld Utrecht-Nijmegen.

Zo ontstaat er een steeds groter wordende kring van ‘groene’ plaatsen rondom het vertrekpunt. Hoe weet je zeker dat de dichtsbijzijnde op deze kring niet via een korter pad te bereiken is? De reden is: alles binnen de groene kring is al geprobeerd, de verbindingen zijn gekleurd. Als je via een andere ‘groene’ plaats gaat, kan de route alleen maar langer worden. Het algoritme zoekt in alle richtingen en heeft de kaart eigenlijk niet nodig, dit kun je zien als je het algoritme in de matrix-view laat werken. Het vindt onderweg kortste paden naar veel plaatsen, alles wat blauw gekleurd wordt. Er bestaan ook varianten van het algoritme die wel rekening houden met de ligging van plaatsen, die proberen in de goede richting te zoeken.

Belangrijk is dat dit algoritme breed inzetbaar is. Wanneer we de afstanden in kilometers vervangen door reistijden in minuten werkt het ook. Het zal dan soms ook andere routes vinden. Zo is de reistijd Amersfoort-Ede minder wanneer je over Utrecht reist, met intercity’s.

Ter informatie, hieronder staat het algoritme in Java-pseudocode:

/** * Het algoritme van Dijkstra in één methode (pseudocode) * NB Knopen (plaatsen) hebben een ‘distance’ tot de startplaats en twee booleans die de * status aangeven: ‘reached’ (er is een pad gevonden) en ‘shortestPathFound’ * * @param: startknoop en doel * @return: boolean die aangeeft of doel gevonden is (graaf is mogelijk niet samenhangend) * * public boolean void dijkstra(Knoop start, Knoop doel) * { declareer Knoop huidige: de knoop vanwaaruit we nieuwe verbindingen onderzoeken * declareer en maak lege rij 'leaves' van knopen die bereikt zijn * maak start shortestPathFound, distance 0 * maak huidige gelijk aan start * while (doel not shortestPathFound && huidige not null ) * { maak rij met alle verbindingen van huidige naar knopen die 'not shortestPathFound' zijn * for ( alle verbindingen in deze rij (mogelijk nul!) ) * { noem de bereikte Knoop 'nieuw' * if ( nieuw 'not reached' ) // knoop nog niet eerder bereikt * { maak nieuw reached * distance van nieuw = distance van huidige + lengte verbinding * voeg nieuw toe aan leaves * } else // knoop eerder bereikt, mogelijk korter pad * { if ( distance nieuw > distance van huidige + lengte verbinding) // korter? * { distance van nieuw = distance van huidige + lengte verbinding * } * } * } * if ( leaves niet leeg) * { haal dichtsbijzijnde uit leaves, maak deze de 'huidige' * maak huidige 'shortestPathFound' * } else * { huidige = null * // NB: zoeken stopt, er is geen pad mogelijk * } * } * return ( shortestPathFound van doel) * } */

Het is mogelijk de applet te lokaliseren met een eigen regiokaart, plaatsen en verbindingen. Verander dan het html-document waarin de applet wordt aangeroepen. Daarin wordt een en ander met parameters vastgelegd:

.... etc tot Knoop23..... .... etc tot Verbinding36.....

Verander de vetgedrukte code niet. Plaatsen worden aangeduid met naam, x en y, gescheiden door komma’s. De andere parameters spreken voor zich. Zorg er bij het kopiëren van de applet altijd voor dat de class-bestanden in de map ‘graafdemo’ blijven staan. NB: Het kan voorkomen dat de achtergrondkaart bij twee keer inzoomen niet te zien is. Dan heeft de Java-VM niet genoeg geheugen tot zijn beschikking. De applet blijft werken.

Uitwerking b Interessant zijn de routes Leiden-Eindhoven (de route over Utrecht wint) en Utrecht Nijmegen. c Zie hierboven. d Zie hierboven. In de html van de applet staan nog enkele opdrachten die na inlevering van de kopij voor het werkboek bedacht zijn: 1 De extra verbindingen in de kaart met reistijden staan voor intercity’s. Zo kun je vanuit Utrecht met de stoptrein via Geldermalsen naar Den Bosch. Er is ook een snellere intercity die niet stopt in Geldermalsen. Deze is weergegeven door een extra verbinding Utrecht - Den Bosch, die Geldermalsen passeert. 2 Voorbeelden zijn Amersfoort-Ede en Utrecht-Dordrecht. Bij de laatste is de route via Geldermalsen in kilometers het kortst (75 km), maar de intercity over Rotterdam is veel sneller.

Opdracht 13 PSD Deze opdracht is een voorproefje op het werken met PSD’s in hoofdstuk 6 en later. In dit hoofdstuk eisen we nog niet dat leerlingen zelf PSD’s kunnen opstellen, maar we denken dat het afmaken van dit eenvoudige PSD wel zal lukken, net als het veranderen van de eenvoudige query in opdracht 11. Eventueel kan de opdracht gedemonstreerd worden. a Invoer: de afstand. b Uitvoer: de prijs c Eerst moet je de berekening maken volgens de formule ‘afstand*0,25 + 1’. Daarna kijk je of de uitkomst meer is dan 34. In dat geval wordt de prijs 34 euro. d Het PSD in het werkboek begint met de prijs op 1 te zetten. Daarna zou je in regel 3 ‘prijs = prijs + afstand*0,25’ kunnen zetten. Dit alles kan natuurlijk ook in één keer. Deze uitwerking geven we hier.

Figuur 3 PSD

Opdracht 14 Eenduidige specificatie van invoerinformatie a/b/c De reisplanner kiest steeds uit een lijst mogelijkheden de dichtstbijzijnde: Bij ‘Amsterdam’ zal dit bijvoorbeeld Amsterdam Amstel zijn. Wanneer iets wordt ingetikt dat niet in de lijst voorkomt, reageert de reisplanner niet meer op toetsaanslagen.

d De reisplanner vraagt de systeemdatum van de computer op. e OVR geeft een keuzelijst met locaties en straatnamen die op de invoer lijken.

Opdracht 15 Besturing van de reisplanner a Invoer: Van (station) naar, via, reisdatum, V/A, tijd, overstaptijd. b Besturing: knoppen: geef reisadvies en annuleren, diverse menukeuzes.

Opdracht 16 Wel en niet in de reisplanner a/b Perrons (reden onduidelijk), vertragingen (actuele informatie), aantal kilometers (staat wel in spoorboekje).

Opdracht 17 Treinkaartjes uit de automaat a (•3) Kaartjes voor een willekeurige datum zijn niet te krijgen (vandaag of ‘zonder datum’. (•7) Geen abonnementen. (•6) Geen folders. (•5) Geen meermanskaarten, wel Zomertour. (•3) Wel kaartjes met een afwijkend vertrekstation: codes: 0000, , . b Een goede omschrijving in woorden is voldoende, met name van de eerste twee mogelijkheden. Voor de precieze specificatie van de rest is het nodig een automaat te bekijken. De betaling kan buiten beschouwing worden gelaten. Er zijn de volgende mogelijkheden: * * 0000 * * *

Figuur 4 Speciale codes De eerste viercijferige code maakt het onderscheid tussen deze mogelijkheden: de codes voor railrunnerkaartjes verschillen dus van stationscodes. c 2222 is de code voor een strippenkaart. Vanwege b is er geen station met die code. d De automaat geeft de naam van de bestemming en de prijs van het kaartje in de display, alle informatie over het kaartje wordt afgedrukt.

Opdracht 18 De kaartautomaat als systeem a De kaartautomaat heeft als functie de verkoop van een aantal kaartsoorten (zie opdracht 13 voor de inperking daarvan). Niet tot de functies van de automaat behoren alle vormen van het verstrekken van reisinformatie, anders dan de prijs. b Handleiding, lijst van (stations)codes, invoertoetsen, display, printer. c/d Een belangrijk proces is het bepalen van de prijs op basis van de gegeven invoer. In de informatiebank moeten de prijzen op de een of andere manier aanwezig zijn.

Opdracht 19 Cd-foongids Extra De Cd-foongids is een voorbeeld van een systeem waarin de invoer zeer nauw gespecificeerd is, waardoor de onderliggende informatiebank maar beperkt bevraagd kan worden. Een vraag begint met plaats en een (een deel van) de naam en levert telefoonnummers. Terugzoeken a Plaats b Terugzoeken kan niet. c Zie b. d In de Cd-foongids van 1997 staan inderdaad precies 30533 Jansen’s. De informatie is verkregen uit een gekraakte versie van de Cd-foongids, waardoor allerlei vrije zoekopdrachten wel mogelijk zijn geworden.