7. Peosõnum

Kobras Ann saadab salakoodide abil sõpradele sõnumeid. Praegu korraldab ta salajast pidu ja soovib saata oma sõpradele sissepääsuks vajaliku parooli 3124.

Ta uuristas ühe oma sõbra jaoks parooli viiele pulgale, aga pulkade järjekord läks sassi:

Küsimus

Millises järjekorras peaksid pulgad olema, ülevalt alla?

[Lohistamine]

Vastus

Õige vastus on

Vastuse selgitus

Iga pulk kirjeldab kompaktselt ühte kahendesituses kirja pandud sõnumi rida. Iga pulga esimene number näitab, kas rida algab valge või sinise ruuduga (0 tähistab valget ja 1 sinist). Kooloni järel tulevad numbrid näitavad, mitu ühte värvi ruutu kummastki vahelduvast värvist järgneb.

Näiteks ülesande joonisel algab esimene rida sinise ruuduga (1). Koolonile järgneb arv, mis näitab seda värvi ruutude arvu (3 sinist ruutu). Sellele järgneb 2 valget ruutu, siis 1 sinine ruut, siis 2 valget ruutu jne:

Seega peaks esimesel (ülemisel) pulgal olema järgmine kood:

Sõnumi teine rida algab valge ruuduga, seega teise pulga esimene number on 0. On 2 valget ruutu, millele järgneb 1 sinine ruut, 1 valge ruut, 2 sinist ruutu jne:

Seega on sellele vastav kood:

Samamoodi saab sõnumi ridadele vastavusse seada kolm ülejäänud pulka.

See on informaatika

Ülesanne toob sisse järjest mitu andmete kodeerimisega seotud mõistet:

• kõigepealt arvu esitamine pildina;
• seejärel pildi kodeerimine rastrina;
• lõpuks rastri edastamine sarikodeerimise abil.

Andmete töötlemise puhul on tavaline, et meil on sama informatsiooni esitamiseks mitu viisi ja vaja on teisendada andmeid ühest esitusest teise.

Selles ülesandes sisse toodud sarikodeerimine (run-length encoding, RLE) on kadudeta pakkimise väga lihtne vorm. Sarikodeerimise algoritmi rakendatakse jadadele, kus samu väärtusi esineb tihti mitu korda järjest. Selline jada kodeeritakse nii, et iga väärtus salvestatakse ainult üks kord, ning selle järele kirjutatakse selle esinemiskordade arv. Enamikel juhtudel tuleb väljundi suurus niimoodi sisendi suurusest väiksem, aga halvimal juhul võib see olla ka suurem.

Selles ülesandes on väärtuste salvestamisest loobutud, eeldades, et iga järgnev kordade arv vastab väärtusele, mis on eelmise väärtuse vastand. (Kas suudad leida näitejoonise, kus Ann sellise lähenemise tõttu raskustesse satub? Kas sellised joonised võivad esineda paroolide esitustena?)

Ülesande lahendamiseks on vaja üldistamise ja algoritmilise mõtlemise oskust. Esmalt peab tuletama sarikodeerimise algoritmi, võrreldes vastavaid ridu tabelis ja pulkadel. Seejärel peab rakendama seda algoritmi joonise ridadele ja saama kätte vastavad sõnumid.

Kodeeritud tulemusest joonise taastamine ja seejärel esituse sümbolite või numbrite kättesaamine ei ole inimese jaoks liiga raske. Kuid mida pikem on lause, seda rohkem aega ja jõudu on selleks vaja. Niisuguste ülesannete automatiseerimiseks arvutil tuleb välja mõtelda ja arvutile öelda, mida teha tuleb. Selleks ongi vaja arendada oma arvutusliku ja algoritmilise mõtlemise oskust.

Veebilehed

• Sarikodeerimine: https://en.wikipedia.org/wiki/Run-length_encoding
• Andmete pakkimine: https://en.wikipedia.org/wiki/Data_compression
• Andmete esitamine: https://computersciencewiki.org/index.php/Data_representation, https://www.khanacademy.org/computing/ap-computer-science-principles/computers-101/digital-data-representation/a/digital-data-introduction
• Algoritmid: https://en.wikipedia.org/wiki/Algorithm, https://www.khanacademy.org/computing/computer-science/algorithms
• Krüptograafia: https://en.wikipedia.org/wiki/Cryptography, https://www.wikihow.com/Create-Secret-Codes-and-Ciphers
• Krüptograafilise kunsti ja käsitöö projektid algkooliõpilastele: https://www.melissaanddoug.com/blogpost?postId=6-secret-codes-for-kids

8. Kus nad elavad?

Koprad Alar, Siim ja Erik seisavad kollasel ruudul oma kooli ees, näoga näidatud suunas.

Teel koju teeb igaüks neist teatavates kohtades pöörded.

Alar teeb kaks vasakpööret.

Siim teeb ühe vasakpöörde ja selle järel ühe parempöörde.

Erik teeb ühe vasakpöörde.

Iga kobras elab erinevas majas. Koprad liiguvad ainult horisontaalselt või vertikaalselt, aga mitte diagonaalselt. Koprad ei saa astuda hallidele ruutudele.

Küsimus

Millises majas iga kobras elab?

[Raadionupud]

A. Alar majas 4, Siim majas 2, Erik majas 5

B. Alar majas 3, Siim majas 2, Erik majas 1

C. Alar majas 4, Siim majas 2, Erik majas 1

D. Alar majas 3, Siim majas 2, Erik majas 4

Vastus

Õige vastus on D.

Vastuse selgitus

Vastused A ja C on valed, sest majani 4 jõudmiseks tuleb kas pöörata üks kord vasakule või pöörata üks kord vasakule ja teine kord paremale või pöörata rohkem kui kaks korda. Seepärast ei saa Alar elada majas 4.

Vastus B on vale, sest majani 1 jõudmiseks tuleb pöörata kaks korda vasakule ja seejärel üks kord paremale. Seetõttu ei saa Erik elada majas 1.

Õige vastuseni jõudmiseks võib panna tähele, et maja 3 on ainuke maja, kuhu Alar jõuda saab. Siim saab jõuda majani 2 või 4, aga ta ei saa elada samas majas nagu Erik. Erik saab jõuda ainult majani 4.

See on informaatika

Kujutada ette mingi tegevuse mõju pole tavaliselt liiga raske: kui on teada, et kobras on liikunud ruudustikul vasakule, vasakule ja paremale, siis on lihtne järgida tema liikumisi, eeldusel, et "vasakule" ja "paremale" on selgelt defineeritud tegevused, näiteks liikumine ühe ruudu võrra ruudustikus kopra hetkesuunaga määratud suunas. Ülesandes aga esitatakse raskem probleem, mis on informaatikas siiski üsna tavaline: antud on mõned tulemused või vihjed ning vaja on kindlaks teha, mis juhtus minevikus. Mitmel juhul on meil teada andmed (või isegi palju andmeid) ning me püüame aru saada, mis liiki protsessis need tekkinud on. Üldiselt võib samade andmetega kokku sobida mitu protsessi: näiteks on teada, et Siim pööras vasakule ja paremale, aga selle tingimusega on kooskõlas kaks erinevat maja (2 ja 4).

Veebilehed

• https://en.wikipedia.org/wiki/Grid_plan

9. Võitja ja kaotaja

Koprad korraldasid maleturniiri. Nad on juba pidanud mõned mängud. Alloleval pildil on tõmmatud kõik nooled võitjatest kaotajateni. Näiteks Bruno võitis Aivit ja Aivi võitis Danielit.

Et kobrastel ei olnud kõigi mängude pidamiseks aega, otsustasid nad võitja määrata uue reegli abil. Reegel on selline: kui Bruno võitis Aivit ja Aivi võitis Danielit, siis see tähendab, et Bruno võitis Danielit. Turniiri võitja on see, kes võitis selle reegli järgi iga ülejäänud kobrast.

Kuid tulemusi polnud võitja määramiseks piisavalt. Seetõttu otsustasid nad mängida veel neli mängu. Tulemused olid:

Küsimus

Kes võitis turniiri?

[Raadionupud]

A. Gregor

B. Ilmar

C. Calvin

D. Elma

Vastus

Õige vastus on B. Ilmar.

Vastuse selgitus

Vastavalt reeglitele peab selleks, et turniiril oleks võitja, saama liikuda igast ülejäänud osalejast mööda nooli tagurpidi ühe ja sama osalejani. See tähendab, et täpselt ühel osalejal puuduvad sissetulevad nooled.

Kui selliseid osalejaid oleks rohkem kui üks, nagu esialgsel joonisel, siis on võitja määramiseks vaja rohkem mänge. Kui selliseid osalejaid üldse pole, siis ei saa reeglit rakendada.

Esimesel joonisel on ainult Gregor, Ilmar, Calvin ja Elma võimalikud võitjad.

Lisades neli viimast noolt, näeme, et Gregor ei saa olla võitja, sest ta kaotas Ilmarile. Calvin kaotas Gregorile ja Elma kaotas Henrile. Seega on Ilmar ainuke osaleja, kes võib olla võitja.

Alltoodud jooniselt näeme, et Ilmar tõepoolest võitis kõiki ülejäänud kopraid.

See on informaatika

Suunatud graaf on viis, kuidas esitada (mittesümmeetrilisi) seoseid objektide paaride vahel: objekte kujutavad tipud ning objektist A viib nool objektini B siis, kui A on seoses B-ga.

Selles ülesandes on vaadeldavaks seoseks "võitja": mõned seosed tulevad tegelikult peetud kohtumistest, teised aga tekstis antud reeglist, mis ütleb, et võitmisseos on transitiivne. Spordis see tavaliselt nii ei ole. Spordimatše ongi huvitav jälgida just sellepärast et kui Bruno võidab Aivit ja Aivi võidab Danielit, siis see veel ei garanteeri, et Bruno võidab Danielit reaalses matšis. Ülesande olukord on aga tavaline informaatikas: mõnesid objekte ei saa vahetult ei võrrelda, aga siiski peame moodustama järjestuse, kus on võrreldud iga objektipaari.

Loomulikult võib selliseid järjestusi olla rohkem kui üks. Näiteks võivad meil olla tegevused või programmid, mis üksteisest sõltuvad: kingade jalgapanemiseks peab enne jalga panema sokid ning mantli selgapanemiseks peab enne selga panema särgi... aga kindlasti saad leida mitu erinevat viisi, kuidas oma riietumistegevused õigesti järjestada!

Veebilehed

• https://en.wikipedia.org/wiki/Directed_graph
• https://en.wikipedia.org/wiki/Transitive_relation
• https://en.wikipedia.org/wiki/Topological_sorting

10. Programmide interpreteerimine

Järgmised käsud kirjeldavad kolmnurkade joonistamist:

joonista(üles, 1, 2)

joonista(alla, 2, 1)

Pärast kujundi joonistamist asud samas kohas nagu alghetkel. Kui programmis on mitu käsku, täidetakse need järjest.

Meil on 4 programmi

1. joonista(alla, 2, 1); joonista(üles, 1, 2)

2. joonista(alla, 1, 2); joonista(üles, 2, 1)

3. joonista(alla, 2, 1); joonista(üles, 2, 1)

4. joonista(alla, 2, 1); joonista(üles, 1, 1)

Küsimus

Sea programmidele vastavusse pildid, mida need programmid joonistavad.

[Vastavusse seadmine]

A.

B.

C.

D.

Vastus

1. programm vastab joonisele B. Kõigepealt joonistatakse "lame" kolmnurk tipuga allapoole ja seejärel "terav" kolmnurk tipuga ülespoole.

2. programm vastab joonisele A. Kõigepealt joonistatakse "terav" kolmnurk tipuga allapoole ja seejärel "lame" kolmnurk tipuga ülespoole.

3. programm vastab joonisele C. Joonistatakse kaks "lamedat" kolmnurka, üks tipuga ülespoole ja teine tipuga allapoole.

4. programm vastab joonisele D. Kõigepealt joonistatakse "lame" kolmnurk tipuga allapoole ja seejärel väiksem "terav" kolmnurk tipuga ülespoole.

See on informaatika

Programmeerimises kasutame tavaliselt käske korduvalt, tehes neis väikesi muudatusi. Ülesandes on defineeritud joonistamisfunktsioon, millele on võimalik ette anda kolm parameetrit ja saadav joonis sõltub nende parameetrite väärtustest.

Meie (funktsiooni kasutaja) jaoks pole oluline, kuidas joonistamine töötab, me ei tea midagi selle "kehast" ehk sisemistest käskudest. Me ainult "kutsume" seda funktsiooni mitu korda erinevate väärtustega ja saame niimoodi joonistada erinevaid kolmnurki.

11. Kodukohvik

Bruno oli koolivaheajal kaks nädalat emal abiks nende kodukohvikus.

Iga tööpäeva õhtul märkis ta üles kassas oleva raha kogusumma ja sai sellise graafiku:

Mõlema reede õhtul võttis ta kassast kogu raha välja ja andis emale.

Küsimus

Mitu eurot oli kohviku suurim päevane sissetulek?

[Tekstikast, täisarv]

Vastus

Õige vastus on 40€.

Vastuse selgitus

Kohviku käibest parema ülevaate saamiseks toome graafikul välja eraldi kassajäägi hommikul ja õhtul:

Veel selgem on asi, kui jätame graafikult välja hommikuse jäägi ja keskendume päeval lisandunud summale:

Nüüd on ilmne, et kõige suurema summa, 40€, teenis kohvik teise nädala esmaspäeval.

See on informaatika

See ülesanne illustreerib, kuidas andmete esitusviis võib nende põhjal mõnele küsimusele vastamise teha kas lihtsamaks või keerulisemaks. Kui graafiku aluseks olevad andmed on arvutustabelis või andmebaasis, saab esituse parandamiseks vajaliku teisenduse lasta ära teha arvutil. Mida rohkem on andmeid, seda suurem on sellisest automaatsest parandamisest saadav kasu.

12. Sõnade otsing tekstis

Järgnevas tekstis esineb sõna "beaver" viis korda:

Sõnade otsimisel ja asendamisel tekstitöötlusprogrammis võib lisaks sõnadele endile arvestada ka nende vormingut.

Küsimus

Mitu sõna "beaver" esinemist leitakse järgmise käsuga?

[Raadionupud]

A. 0

B. 3

C. 4

D. 5

Vastus

Õige vastus on C. 4.

Vastuse selgitus

Kuna otsingutingimuseks on valitud lisaks sõnale "beaver" ka vorming "Italic" ehk kaldkiri, leitakse 4 esinemist:

See on informaatika

Tekstitöötlusprogrammi võimaluste tundmine ja nende kasutamine oma töö hõlbustamiseks on loomulikult informaatika!

13. Parooli meeldejätmine

Kobras Pfiffikus tahab moodustada parooli, mida tema suudab meeles pidada, aga mida keegi teine ei suuda lihtsasti ära arvata. Seetõttu kasutab ta parooli moodustamiseks erilist meetodit.

Kobras Pfiffikus armastab järgmist lauset:

Mulle meeldib puder mille valmistas kokk Wilhelm

Seepärast võtab ta selle lause oma parooli aluseks:

M5m7p5m5v9k4W7

Küsimus

Millise parooli saab samal meetodil moodustada sellisest lausest:

Minu robotiringi juhendaja on magister Hanna

[Tekstikast, vastuse pikkus 13 tähemärki]

Vastus

Õige vastus on M4r11j9o2m8H5.

Vastuse selgitus

Kobras kasutab parooli moodustamiseks spetsiaalset meetodit. Selles meetodis võetakse igast sõnast esimene täht ja kirjutatakse selle järele sõna pikkus (tähtede arv sõnas).

Mulle → M5

meeldib → m7

puder → p5

mille → m5

valmistas → v9

kokk → k4

Wilhelm → W7

Kasutades sama meetodit, saame moodustada parooli ka uue lause põhjal:

Minu → M4

robotiringi → r11

juhendaja → j9

on → o2

magister → m8

Hanna → H5

Seega uue lause parool on M4r11j9o2m8H5.

Paneme tähele, et antud näites on tähed M ja W suurtähed. Kui mingi täht on suurtäht lauses, siis on ta suurtäht ka paroolis. Seepärast peavad vastuses samuti M ja H olema suurtähed.

See on informaatika

Andmete turvalisus on informaatikas üks võtmeteemasid. Kõige lihtsam ja tavalisem lähenemine andmete ja arvutile juurdepääsu kaitsmisele on paroolide kasutamine.

Parool peab olema kergesti meeldejäetav, sest parooli üleskirjutamine on riskantne. Kuid parool peab olema teiste jaoks raskesti äraarvatav ning ei tohiks olla ilmne või seotud kasutaja isikuandmetega.

14. Koodi lugemine tagurpidi

Minu arvuti loeb programme ridahaaval ülevalt alla.

Meil on selline programm:

A ← 2
Kirjuta A
A ← A*2
Kirjuta A
A ← A*2
Kirjuta A
A ← 100

Märk ← tähendab "salvesta paremal poolel arvutatud väärtus muutujasse"; märk * tähendab korrutamist.

Kui see programm käima panna, siis kirjutab arvuti:

2
4
8

Täna aga paistab, et minu arvutis on viirus, sest arvuti käitub imelikult. Ta loeb programme tagurpidi, alustades viimasest reast ja liikudes ülespoole.

Küsimus

Mida minu viirusega arvuti kirjutas, kui see programm käima pandi?

[Raadionupud]

A.

8
4
2

B.

100
50
25

C.

2
4
8
100

D.

100
200
400

Vastus

Õige vastus on D.

Vastuse selgitus

Kõigepealt järjestame read ümber, et saaksime neid lugeda ülevalt alla:

A ← 100
Kirjuta A
A ← A*2
Kirjuta A
A ← A*2
Kirjuta A
A ← 2

Esimene täidetav käsk on seega A ← 100 ja teine käsk Kirjuta A. Seetõttu peab esimene kirjutatav arv olema 100.

Kui programmi ridu lugeda teises järjekorras, siis see ei tähenda, et käskudes sooritatakse teisi arvutusi. Käsk A ← A*2 ei tähenda tagurpidi lugedes käsku A ← A/2. Kui programm sisaldab ainult 2-ga korrutamise käske, siis peavad väärtused kasvama. Seega järgmised väärtused ei saa olla 50 ja 25.

See on informaatika

Arvutiprogrammide lugemine on oluline oskus, sest me peame teadma, kuidas arvuti programmi ja seal olevaid käske täidab. Igal käsul on programmis õige koht, et programm töötaks õigesti. Programmeerijad peavad teadma, kuidas tulemused muutuvad, kui programmis käskude asukoht või järjestus muutub.

15. Vanglast põgenemine

Kaks vangi, Jass ja Jonn kavatsevad alustada vanglast põgenemist esmaspäeval, 1. veebruaril. Vabadusse pääsemiseks tuleb neil kummalgi enne veebruari lõppu valmis kaevata käik, mis suundub 2 meetrit allapoole ja siis 30 meetrit edasi.

Tabelis on näidatud, mitu meetrit saavad nad igal nädalapäeval kaevata. Nädalalõpul nad kaevata ei saa.

	Esmaspäev	Teisipäev	Kolmapäev	Neljapäev	Reede
Jass	2	0	2	0	2
Jonn	0	4	0	4	0

Küsimus

Kellel on võimalik veebruari lõpus põgeneda?

[Raadionupud]

A. Mitte kummalgi

B. Ainult Jassil

C. Ainult Jonnil

D. Mõlemal vangil

Vastus

Õige vastus on C.

Vastuse selgitus

Jooniselt on näha, et nad peavad kaevama ruumi põrandast 2 meetrit allapoole maa sisse ja seejärel 30 meetrit horisontaalselt, seega on neil edukaks põgenemiseks vaja kaevata 30+2=32 meetrit.

Põhiline on siin kuu "veebruar", sest veebruaris on 28 või 29 päeva.

Jass saab kaevata kolmel päeval nädalas ehk 2+2+2=6 meetrit nädalas. Et veebruaris on täpselt 4 nädalat, siis ta saab kuuga kaevata 6*4=24 meetrit. Isegi kui oleks veel üks esmaspäev 29. veebruaril, siis saaks ta kaevata 24+2=26 meetrit, ning kummalgi juhul ta välja ei pääse.

Jonn saab kaevata kahel päeval nädalas, kokku 4+4=8 meetrit, ja nelja nädala jooksul 8*4=32 meetrit. Seega saab tema edukalt põgeneda.

See on informaatika

Informaatikas saab andmeid ja informatsiooni esitada paljudel viisidel (näiteks skeem vahemaade kohta, tekst ja joonis aja kohta). Vaja on aru saada ja osata mõelda erinevatel viisidel: "teisendada" informatsiooni. Selle ülesande lahendamiseks peame korraga mõtlema, arvutama ja kiiresti arutlema 3 minuti jooksul.

Selles ülesandes võib vangide vajaminevate kaevamistööde esitamiseks kasutada lihtsaid graafikuid ning nädala kaevamistööde esitamiseks histogrammi ja tabelit.

Ülesande lahendamise võti on panna see informatsioon kokku ja leida, kui palju tööd kumbki vang nädala jooksul teha suudab. Seejärel arvestada, et 1. veebruar on esmaspäev ning et veebruaris võib olla 28 või 29 päeva. Märgime, et andmepõhiste arvutuste puhul on informaatikas vaja pöörata erilist tähelepanu andmete muutumisulatusele.

Copyright © 2020 Bebras – International Challenge on Informatics and Computational Thinking.
Licensed under Creative Commons Attribution-ShareAlike 4.0 International License.

Flag icons by GoSquared.