Informatica

Informatica in het pta

wi1.jpg 

Leerlingen kunnen gedurende een aantal maanden ( september t/m half januari) alleen of in kleine groepjes werken aan de opdrachten uit de eerste ronde.

1. De relatie tussen de onderwerpen die in de informatica olympiade aan de orde komen en het examenprogramma.

Bij de Informatica Olympiade gaat het om het oplossen van problemen door middel van een zelf geschreven computerprogramma. Het gaat daarbij om algoritmische problemen. Bijvoorbeeld een probleem waarbij het computerprogramma de optimale oplossing dient te leveren binnen een bepaalde tijd.

Tijdens de eerste ronde krijgt de leerling de gelegenheid om  zich een programmeertaal eigen te maken en drie opgaven op te lossen. Een eenvoudige cursus programmeren staat op de website: www.informaticaolympiade.nl

De opgaven in de eerste ronde zijn opklimmend in moeilijkheidsgraad en vereisen steeds meer vernuft om ze volledig correct op te lossen. Daarbij staat niet de kennis van de programmeertaal centraal maar het vermogen om algoritmische problemen op te lossen. Een eenvoudig algoritme zal wellicht bij de helft van de testgevallen een juiste oplossing leveren.

Voor gevorderde of snelle leerlingen is opgave drie zeer uitdagend. Bij deze opgave gaat het doorgaans om een bordspel waarbij geen oplossing bekend is. Van boter-kaas-en-eieren is die er wel. Bij een juist uitgevoerde strategie hoeft geen van beide spelers te verliezen. De eerste helft van de opgave bestaat uit het programmeren van het spel zodat twee spelers met het programma het spel kunnen spelen volgens de spelregels. Dammen is zo’n spel. Maar elk jaar betreft het een ander spel.

Het tweede deel van opgave 3 bestaat uit de opdracht om bij een willekeurige stand een zo slim mogelijke zet af te geven. Het juryprogramma laat nu elk programma tegen elk ander programma spelen. De derde opgave staat onder de naam CodeCup open voor leerlingen, studenten en docenten vanuit de gehele wereld. 

Relatie met examenprogramma

Vanuit het curriculum van het keuzevak Informatica in de tweede fase is “het ontwikkelen van een ICT systeem” een mogelijke projectopdracht. Het zal duidelijk zijn dat opgave drie hieraan voldoet. Opgaven 1 en 2 zijn de aanloop waarmee men kan aantonen voldoende vaardigheid te hebben om te beginnen aan opgave 3.

In de maanden tussen 1 oktober en 15 januari is er elke twee a drie weken een tussenronde, waarbij men met één programma kan deelnemen. Naar aanleiding van de uitslag en het naspelen van het spel kan men ontdekken op welke momenten en bij welke zet het programma  slim speelt of juist niet.

De Informatica Olympiade is bezig met een interactieve cursus programmeren. Dat wil zeggen dat men telkens na een korte introductie een opgave krijgt. De oplossing kan men uploaden en wordt door het cursussysteem automatisch beoordeeld. Men krijgt aanwijzingen bij een niet correcte oplossing. Is de oplossing wel correct dan krijgt men het volgende stukje theorie en opnieuw een opdracht. Een alfaversie van dit systeem is ontworpen en gedeeltelijk gerealiseerd. Zodra de financiën het toelaten wordt begonnen met het implementeren en testen met leerlingen.

Examenprogramma

Subdomein B3: Software

De kandidaat beheerst eenvoudige datatypen, programmastructuren en programmeertechnieken.

2. De olympiade krijgt een plaats in het pta van leerjaar: 

havo 

x leerjaar 4
O leerjaar 5

vwo

O leerjaar 4
x leerjaar 5
O leerjaar 6

3. Opties

Het nieuwe examenprogramma biedt voor de meeste vakken meer vrijheid dan in het verleden. Zo is inhoud, vorm en tijdstip van de toetsing is, binnen de kaders van de school, aan de sectie. Schoolkaders kunnen beperkingen opleggen aan de keuzevrijheid.  Bovendien zijn alle vormvoorschriften voor het schoolexamen verdwenen. Dat betekent dat secties naast toetsen met open en/of gesloten vragen bijvoorbeeld ook andere onderdelen deel kunnen laten uitmaken van het schoolexamen. Ook kan de sectie zelf bepalen of de leerlingen een praktische opdracht moeten maken en wat het onderwerp is. De weging van de diverse schoolexamens is niet meer vastgelegd en wordt overgelaten aan de sectie. Bovendien kan de sectie ervoor kiezen onderdelen te examineren die niet voor alle leerlingen hetzelfde zijn.

Als u  de olympiade wilt opnemen in het PTA zijn er verschillende mogelijkheden:

3.1 De leerlingen met informatica in hun pakket bepalen zelf of zij, alleen of als groepje, aan de olympiade meedoen. Als zij meedoen kunnen zij de deelname laten meetellen als praktische (keuze)opdracht.
De aard van de opdracht maakt een verplichting voor alle leerlingen minder voor de hand liggend.

3.2 Alle leerlingen doen mee aan de olympiade. Bij een bepaalde score krijgen de leerlingen een extra herkansing. Deze optie kan de motivatie stimuleren.

4. Voorbeeld opgave 

Opgaven voorronde natuurkunde olympiade 2010

Opgave 1. De orde tellen

In het spel Chaos en Orde zetten twee spelers om de beurt een steen op een leeg vakje van een vierkant spelbord. Het spelbord bestaat uit 36 vakjes. Als het bord vol is wordt een score berekend. Daarbij worden de rijen op het spelbord bekeken. Als er meerdere stenen van dezelfde speler naast elkaar liggen geeft dat punten: Een rij van n aaneengesloten stenen levert (n-1)2 punten op. Er zijn twee manieren om de score voor het spel te berekenen.
De vlakke score is de som van de punten op de zes horizontale rijen.
De totale score is de som van de punten op de zes horizontale en de zes verticale rijen en de punten op de beide diagonalen.

inf1.jpg

Hierboven zie je een berekening van de vlakke score: Voor dit spel is die 19.

inf2.jpg

En hier zie je de berekening van de totale score: Voor dit spel is die 79.

Links- en rechtsonder het spelbord staan de scores van de diagonalen.

Bij het spel gaat het erom dat de ene speler de score zo hoog mogelijk moet zien te krijgen terwijl de andere die juist zo laag mogelijk moet zien te krijgen. In deze opgave zijn we alleen geïnteresseerd in het berekenen van de scores.

Invoer:

Bij deze opgave moet je twee programma's schrijven die een vol spelbord inlezen uit een tekstbestand. Dit bestand heet orde.in en bestaat uit zes regels; op iedere regels staan zes tekens, die de verschillende stenen op het bord weergeven. Voor deze stenen worden de hoofdletters O en X gebruikt.

Voorbeeld:

OOXXOX
XOXOOO
XOOOXX
XOOXOX
OOXXOX
XOOXXX

Opgave 1a:

Schrijf een programma nio1a dat een bestand orde.in inleest. Je programma berekent voor het spelbord in de invoer de vlakke score. Uitvoer is een tekstbestand nio1a.uit van één regel, waarop de vlakke score van de invoer staat vermeld.

Voorbeeld:

19

Opgave 1b:

Schrijf een programma nio1b dat een bestand orde.in inleest. Je programma berekent voor het spelbord in de invoer de totale score. Uitvoer is een tekstbestand nio1b.uit van één regel, waarop de totale score van de invoer staat vermeld.

Voorbeeld:

79               

Opgave 2. Verstop je codewoord

Onderdeel 2A

Inleiding
Bij deze opgave gaat het om het schrijven van een programma nio2 dat in staat is om van een codewoord een letterbrij van een aangegeven lengte te maken. Als dat onmogelijk is geeft het programma een foutmelding.

Letterbrij en codewoord
Een codewoord is een tekst van tenminste één en ten hoogste vijftien kleine letters zonder leestekens.
De letterbrij moet voldoen aan de eisen van opgave 1: Als je alleen elke derde keer dat een letter voorkomt in de letterbrij hem niet wegstreept, kom je op het codewoord uit.

Invoer
Invoer is een bestand nio2.in dat bestaat uit twee regels:
Op de eerste regel staat een tekst van tenminste één en ten hoogste vijftien kleine letters zonder leestekens.
Op de tweede regel staat een getal L dat aangeeft hoe lang de letterbrij die je moet maken dient te worden. Er geldt dat 1 ≤ L ≤ 150.

Uitvoer
Uitvoer is een bestand nio2.uit dat bestaat uit één regel.

Zo mogelijk is dat de gevraagde letterbrij.

Wanneer het niet mogelijk is om een letterbrij van de aangegeven grootte te maken staat er een

foutmelding:

< L is te klein om bij dit codewoord een geldige letterbrij te maken

> L is te groot om bij dit codewoord een geldige letterbrij te maken.

Voorbeelden

Voorbeeldnr.

Invoer nio2.in

Uitvoer nio2.uit

1

bal

9

balbalbal

2

haast

6

3

uilebal

120

4

bal

11

lblabbaqalq

5

droom

27

rdadadroxmocpronogomocdmqzx

Punten voor deze opgave

Voor het correct ontdekken of een letterbrij wel of niet te maken is kun je 20 punten krijgen. Het maken van een geldige letterbrij bij het codewoord levert je 40 punten op.

Onderdeel 2B

Zoals je aan voorbeeld 1 al kunt zien is het mogelijk om een geldige letterbrij te maken die toch niet echt veel verstopt. Als je voor de extra punten van deze opgave in aanmerking wilt komen moet je programma aan de voorwaarden die hieronder worden uitgewerkt voldoen: Een zo laag mogelijke open-neer-score en een zo hoog mogelijke afstandsscore. Deze voorwaarden worden los van elkaar beoordeeld.

Aanvullende voorwaarde 1: Een zo laag mogelijke op-en-neer-score.

Een letterbrij doet bij voorkeur nogal willekeurig aan. Om te kijken hoe jouw letterbrij eruit ziet berekenen we de op-en-neer-score van je letterbrij. Deze score bereken je als volgt:

inf3.jpg

Het aantal paren in de categorie Op noem je O.
Het aantal paren in de categorie Neer noem je N.
Het aantal paren in de categorie Gelijk noem je G.
De op-en-neer-score van je letterbrij is (O-N)2+G2

Je kunt in totaal 25 punten voor deze opgave verdienen als de op-en-neer-score van je letterbrij bij de gegeven invoer minimaal is.

Er is een programma ons.exe beschikbaar waarmee je de op-en-neer-score van een bestand kunt bepalen. Open een commandovenster en geef als opdracht ons nio2.uit en je ziet de score op het scherm weergegeven.

Voorbeelden:

nio2.uit

Op-en-neer-score

balbalbal

4

lblabbaqalq

2

rdadadroxmocpronogomocdmqzx

4

Aanvullende voorwaarde 2: Een zo hoog mogelijke afstandsscore.

Een letterbrij bevat het codewoord, maar bij voorkeur herken je dat er niet zo makkelijk in. Op de volgende manier kun je de afstandsscore van een codewoord in een letterbrij bepalen. Ga na welke letters niet meer dan twee keer in de letterbrij voorkomen. Laat deze letters uit de letterbrij weg. Wat je overhoudt noemen we de goedeletterzin. Nu ga je het codewoord vergelijken met elk van de deelzinnen van de goedeletterzin: je legt het codewoord naast de goedeletterzin, vergelijkt codewoord en deelzin en telt het aantal verschillen. Daarna schuif je het codewoord telkens één plaats op en tel je telkens opnieuw de verschillen (Zie het voorbeeld hieronder).

Voorbeeld berekening afstandsscore:

Letterbrij: lblabbaqalq

Codewoord: bal

Goedeletterzin: lblabbaal

Goedeletterzin Deelzin/codewoord Verschillen

Goedeletterzin

Deelzin/codewoord

Verschillen

lblabbaal

1b1-ba1

2

bla-ba1

2

lab-ba1

2

abb-ba1

2

bba-ba1

2

baa-ba1

1

aal-ba1

1

Het kleinste verschil noem je A.

Het aantal keren dat dit kleinste verschil voorkomt noem je N. De afstandsscore van codewoord en letterbrij is nu 10A+1 – N. Je kunt voor deze opgave 15 punten verdienen als de afstandsscore van de door jou gevonden letterbrij bij het gegeven codewoord maximaal is.

Er is een programma afsc.exe beschikbaar waarmee je de afstandsscore van een bestand kunt bepalen. Open een commandovenster en geef als opdracht afsc nio2.in nio2.uit en je ziet de score op het scherm weergegeven.

Voorbeelden:

nio1.in

nio2.uit

Afstandsscore

bal

9

balbalbal

7

bal

11

lblabbaqalq

98

droom

27

rdadadroxmocpronogomocdmqzx

996