Fakulteta za raˇ cunalniˇ stvo in informatiko Fakulteta za matematiko in fiziko

(1)

Fakulteta za raˇ cunalniˇ stvo in informatiko Fakulteta za matematiko in fiziko

Marija Marolt

Spoznavanje algoritmov s projektnim uˇ cenjem

DIPLOMSKO DELO

INTERDISCIPLINARNI UNIVERZITETNI ˇSTUDIJSKI PROGRAM PRVE STOPNJE

RA ˇCUNALNIˇSTVO IN MATEMATIKA

Mentor : prof. dr. Janez Demˇsar

Ljubljana, 2021

(2)

tatov diplomske naloge je potrebno pisno privoljenje avtorja, fakultete ter mentorja.

Besedilo je oblikovano z urejevalnikom besedil L^ATEX.

(3)

Vrsta naloge: Diplomska naloga na univerzitetnem programu prve stopnje Interdisciplinarni ˇstudij raˇcunalniˇstva in matematike

Mentor: prof. dr. Janez Demˇsar

Opis:

Uˇcenje algoritmov je zabavnejˇse, ˇce poteka prek reˇsevanja problemov, ki se povezujejo v ˇsirˇso zgodbo. Sestavite zaporedje zgodb, katerih reˇsevanje bo zahtevalo implementacijo osnovnih algoritmov na nivoju nekoliko bolj nadar- jenih in zagnanih srednjeˇsolcev. Algoritmi naj si sledijo v nekem smiselnem vrstnem redu. Naloge postavite na spletno stran, prek katere bodo uˇcenci dobivali podatke in oddajali odgovore.

(4)

(5)

Povzetek Abstract

1 Uvod 1

2 Teoretiˇcna izhodiˇsˇca 3

2.1 Pouˇcevanje raˇcunalniˇstva . . . 4

2.2 Raˇcunalniˇsko miˇsljenje . . . 5

2.3 Metafore pri programiranju . . . 7

2.4 Aktivno uˇcenje . . . 9

2.5 Projektno uˇcenje . . . 11

2.6 Poigritev . . . 12

2.7 Obravnavani algoritmi in podatkovne strukture . . . 13

3 Spletna stran Tatovi umetnin 17 3.1 Razvoj spletne strani . . . 17

3.2 Uporaba spletne strani . . . 18

4 Opisi nalog 25 4.1 Sumljiva kustosa visoke postave . . . 27

4.2 Nered v kleti . . . 29

4.3 Kako izuriti robota . . . 32

4.4 Sreˇca v nesreˇci . . . 33

(6)

4.7 Aˇzurni podatki . . . 39

4.8 Nenavadna delitev dela . . . 41

4.9 Ali ima kdo privilegije? . . . 44

4.10 Na sledi . . . 45

4.11 Kje se mafijci sreˇcujejo . . . 48

4.12 Kraj sreˇcevanja . . . 51

4.13 Ali verjeti mafijcu . . . 53

4.14 Korak bliˇzje k reˇsitvi . . . 56

4.15 Mafijec je govoril resnico . . . 59

4.16 Dvojni agenti . . . 61

4.17 Zdaj gre zares . . . 64

5 Sklepne ugotovitve 69

Literatura 71

(7)

kratica angleˇsko slovensko PBL project-based learning projektno uˇcenje MDA mechanics, dynamics and mehanika, dinamika in

aesthetics estetika

HTML Hyper Text Markup jezik za oznaˇcevanje

Language nadbesedila

LIFO last in – first out zadnji noter – prvi ven FIFO first in – first out prvi noter – prvi ven

(8)

(9)

Naslov: Spoznavanje algoritmov s projektnim uˇcenjem Avtor: Marija Marolt

Na spletu in v fiziˇcni obliki najdemo veliko nalog za utrjevanje programiranja. V tem delu pa smo ˇzeleli oblikovati naloge, povezane v ˇsirˇso zgodbo, da bi tako vzbudili dodatno zanimanje in poveˇcali motivacijo za reˇsevanje.

Obravnavani problemi si sledijo v smiselnem vrstnem redu, se med sabo povezujejo in stopnjujejo. Zahtevajo implementacijo osnovnih algoritmov in podatkovnih struktur, primernih za bolj zavzete srednjeˇsolce.

Nastala je zbirka sedemnajstih nalog povezanih v detektivsko zgodbo. Pri vsaki od njih so za reˇsevanje na voljo posebne funkcije, ki usmerjajo uˇcenca pri iskanju reˇsitve. Na koncu sledi razlaga, s katero umestimo reˇsen problem na podroˇcje algoritmov.

Naloge so postavljene na spletno stran, ki na podlagi vpisanega imena uporabnika generira unikatne podatke, prikazuje navodila nalog in preverja vpisane odgovore.

Kljuˇcne besede: algoritmi, podatkovne strukture, projektno uˇcenje, pouˇcevanje raˇcunalniˇstva, spletna stran.

(10)

(11)

Title: Teaching algorithms using project based learning Author: Marija Marolt

There are many collections of programming exercises. In this work, we de- cided to create one in which individual tasks represent pieces of a larger story in order to make solving them more interesting and exciting. The tasks are arranged in coherent, progressing sequence, from more basic algorithms to advanced one. The level is assumed to be suitable for a talented secondary school student.

We created a collection of seventeen tasks and weaved them into a de- tective story. In each, the student is given several functions that provide the necessary data. After solving the task, we explain the algorithmic back- ground.

Tasks are published on web site, which, based on user name generates unique data, displays task instructions and checks the correctness of answers.

Keywords: algorithms, data structures, project based learning, teaching computer science, web page.

(12)

(13)

Uvod

V zadnjih letih naraˇsˇca zanimanje za pouˇcevanje raˇcunalniˇstva v osnovnih in srednjih ˇsolah. Kljuˇcnega pomena je pri tem znanje programiranja. Le-tega se ne moremo nauˇciti na tradicionalen naˇcin, saj potrebujemo izkuˇsnje in razmisleke. Da uˇcence spodbudimo k uˇcenju z razumevanjem, lahko uporabimo katero od oblik aktivnega uˇcenja. [21] Izbrana oblika aktivnega uˇcenja v tem delu je projektno uˇcenje. Temelji na kreativnem miˇsljenju pri odkrivanju ter uporabi novega znanja. Skozi reˇsevanje vsakdanjih problemov uˇcenci pridobijo teoretiˇcno in praktiˇcno znanje. [4, 1]

Tema nalog oziroma namen njihovega reˇsevanja je usvajanje novih algoritmov in podatkovnih struktur. Ti so pomembni za ustvarjanje in razumevanje delovanja uˇcinkovitih raˇcunalniˇskih programov. [6]

Sestavili smo spletno stran z nalogami za uˇcenje algoritmov in podatkovnih struktur. Namenjena je uˇcencem z osnovnim znanjem programiranja, ki ˇzelijo nove koncepte usvojiti z drugaˇcnim, bolj samostojnim, zanimivim naˇcinom uˇcenja. Vkljuˇcene naloge se med sabo povezujejo in tvorijo zgodbo.

Za utrjevanje konceptov programiranja obstaja kopica nalog dostopnih na spletu ali v tiskani obliki, kot so Project Euler, HackerRank in druge. Kot primer dobre prakse lahko vzamemo tudi Advent of Code, za katero je znaˇcilno, da objavljene naloge povezuje zgodba. Vsi ti viri so namenjeni predvsem utr- jevanju ˇze pridobljenega znanja. Naˇs cilj je zato oblikovati naloge namenjene

1

(14)

samemu uˇcenju novih konceptov. V ta namen je osnovnoˇsolcem za podroˇcje raˇcunalniˇstva na voljo portal Vidra - Raˇcunalniˇstvo brez raˇcunalnika. Za viˇsji nivo znanja se lahko obrnemo na Computer Science Field Guide. A slednji le v manjˇsi meri pokriva vsebine algoritmov in podatkovnih struktur, kar je bil naˇs interes pri pripravi nalog.

V nadaljevanju je v 2. poglavju utemeljena izbira pristopa k pouˇcevanju.

Opisana so teoretiˇcna izhodiˇsˇca, ki so vodila k izbiri projektnega uˇcenja kot uˇcne metode. Pri tem se osredotoˇcimo na motivacijo uˇcencev pri uˇcenju, spodbujanje uˇcenja z razumevanjem in aktivnega sodelovanja. To ˇzelimo doseˇci s stopnjevanjem teˇzavnosti nalog, zanimivo zgodbo, ki le te povezuje, lestvico napredka, moˇznostjo namiga in drugimi elementi. V naslednjem poglavju je sprva predstavljeno delovanje in uporaba narejene spletne strani. Opisane so znaˇcilnosti uporabljenih orodij in tehnologij ter zgradba datoteˇcnega sistema spletne aplikacije. Sledijo podrobni opisi posameznih nalog v 4. poglavju. Podamo njihovo navodilo, reˇsitev, razlago reˇsitve ter algoritmiˇcno in didaktiˇcno ozadje.

(15)

Teoretiˇ cna izhodiˇ sˇ ca

Na zasnovani spletni strani uˇcenci samostojno reˇsujejo programerske naloge.

Reˇsevanje ni ˇcasovno ali prostorsko omejeno. Uˇcitelj lahko daje nasvete in usmeritve, vendar njegova prisotnost ni obvezna. Uˇcenci skozi zgodbo in s pomoˇcjo ponujenih funkcij sami razvijejo algoritem, ki reˇsi dani problem. S tem pridobijo veˇsˇcine reˇsevanja problemov, istoˇcasno pa to deluje motivacijsko. Problem je izmiˇsljen, a temelji na realistiˇcnih okoliˇsˇcinah in omejitvah. Uporabljen je kot metafora za sploˇsen raˇcunalniˇski koncept, za katerega ˇzelimo, da ga uˇcenci usvojijo. Kljuˇcnega pomena je razumevanje in ne uˇcenje na pamet ali implementacija znanih reˇsitev. Spletna stran omogoˇca reˇsevanje nalog z uˇcenˇcevim tempom, kar nudi nadzor nad lastnim uˇcenjem in poslediˇcno veˇcjo motiviranost ter boljˇso uspeˇsnost. K temu prispeva tudi moˇznost prilagoditve teˇzavnosti oziroma pomoˇci z odkrivanjem namigov. Za reˇsitev doloˇcene naloge je praviloma potrebno reˇsiti predhodne naloge. Od preskakovanja nalog odvraˇca tudi vrstica napredka, ki prikazuje deleˇz pravil- nih reˇsitev.

V tem poglavju je predstavljenih nekaj znaˇcilnosti pouˇcevanja raˇcunalniˇstva ter raˇcunalniˇskega miˇsljenja. Opisani so tudi glavni postopki, ki so uporabljeni pri snovanju tega dela.

3

(16)

2.1 Pouˇ cevanje raˇ cunalniˇ stva

”Pouˇcevanje (oziroma, mogoˇce bolj natanˇcno, uˇcenje) raˇcunalniˇskega programiranja je problem“. [21] ˇStevilni uˇcenci imajo z njim teˇzave in ob koncu izobraˇzevanja obˇcutek, da je njihovo znanje ˇsibko.

Uˇcenci se uˇcijo na razliˇcne naˇcine in uˇcitelji prav tako pouˇcujejo na razliˇcne naˇcine. Zato obstaja veˇc vrst uˇcenja; vsako ima svoje prednosti in pomanjkljivosti.

Solsko uˇˇ cenje je posebna vrsta uˇcenja, ki se od spontanega vsakodnevnega uˇcenja loˇci po intenziteti in vsebini uˇcne motiviranosti. ˇCe je denimo uˇcenec motiviran za uˇcenje na doloˇcenem podroˇcju ali v dejavnosti, ki si jo sam izbere ali pa je zaˇzelena v kontekstu njegovega socialnega okolja, to ˇse ne pomeni, da bo ta uˇcenec kljub svojim potencialom enako motiviran tudi za uˇcenje v ˇsoli. V ˇsoli si uˇcenec ˇsolskih predmetov in uˇcnih vsebin ne izbira sam, tudi si ne doloˇca sam tempa uˇcenja, za sodelovanje v tem procesu si ne izbira ne vrstnikov (soˇsolcev) ne odraslih (uˇciteljev, starˇsev), se pa ne glede na naˇsteto od njega zahteva kakovostno znanje, ki ga lahko doseˇze le, ˇce je za uˇcenje dobro motiviran [22].

Uˇcencu ne moremo

”dati“ motivacije, saj je ta pravzaprav

”ˇze v njem“ [22].

Lahko pa jo z razliˇcnimi metodami in pristopi spodbudimo ali v nasprotnem primeru celo pripomoremo k njenemu zniˇzevanju.

Dolˇznost uˇcitelja je podajanje znanja uˇcencem. A to ni njegova edina naloga. Predvsem mora znati uˇcence motivirati. [21] Uˇcenci morajo ceniti rezultate uˇcenja in hkrati priˇcakovati uspeh. Potrebno je zagotoviti, da uˇcenci vedno ˇcutijo, da imajo nadzor nad svojo usodo, nad uspehom in neuspehom.

Tisti, ki imajo obˇcutek, da obvladajo svoje uˇcenje in z njim gradijo svoje znanje, so pri uˇcenju bolj samozavestni in zato tudi dejansko uspeˇsnejˇsi. [22]

”Motivacija je kljuˇcni dejavnik dinamike uˇcnega procesa: le motivirani uˇcenci uˇcenje zaˇcnejo, se uˇcijo (spraˇsujejo, posluˇsajo, sodelujejo, preizkuˇsajo, berejo, razmiˇsljajo, primerjajo, doˇzivljajo, vrednotijo, ustvarjajo . . . ) in pri uˇcenju vztrajajo, vse dokler ne konˇcajo uˇcnih nalog ali ne doseˇzejo zastavlje- nih uˇcnih ciljev.” [22] Pomembna je tako samo organizacija uˇcenja kot tudi

(17)

podpora in usmerjanje pri uˇcenju. Motivacija ni nujno povezana z uˇcnimi doseˇzki oziroma uˇcno uspeˇsnostjo, ima pa moˇcan vpliv na samo uˇcenje. To se kaˇze v ˇcasu in naporu posveˇcenem uˇcenju, uˇcni strategiji ter razpoloˇzenju.

Bolj motivirani uˇcenci se uˇcijo dlje, z razumevanjem ter laˇzje ostajajo zbrani in pozitivni.

Uˇcenje delimo uˇcenje na pamet ter uˇcenje z razumevanjem (prviˇc sta delitev opisala Marton in S¨alj¨o [24]). Uˇcenje na pamet je povezano z oce- njevanjem, ki zahteva dobesedno ponovitev. Na drugi strani, se uˇcenje z razumevanjem osredotoˇca na znanje, ki se uporablja v novih situacijah. Eno ni vedno boljˇse od drugega. Katerega izbrati oziroma spodbujati, je odvisno od okoliˇsˇcin. ˇCeprav se prednost daje uˇcenju z razumevanjem, je v neka- terih primerih edino moˇzno ali bolj primerno uˇcenje na pamet (na primer pri uˇcenju abecede). [21] V naˇsem primeru si bomo prizadevali za uˇcenje z razumevanjem, saj je slednje povezano z bolj aktivnim sodelovanjem uˇcencev pri uˇcenju. Tako doseˇzemo veˇcjo motiviranost in vkljuˇcenost v uˇcenje. Ak- tivnega sodelovanja je pri klasiˇcnem pouˇcevanju zelo malo, zato je smiselno uporabiti njegove alternative. Uporabimo katero od oblik aktivnega uˇcenja, njemu primerno uˇcno okolje in aktivnosti. V nadaljevanju si bomo pogledali nekaj vrst uˇcenja, na katere se opira to delo.

2.2 Raˇ cunalniˇ sko miˇ sljenje

Raˇcunalniˇstva ne smemo enaˇciti z raˇcunalniˇskim programiranjem. Razmiˇsljati kot raˇcunalniˇcar je veliko veˇc kot znati sprogramirati raˇcunalnik: pomeni znati razmiˇsljati na veˇc nivojih abstrakcije [27].

Raˇcunalniˇsko miˇsljenje se opira na zmoˇznosti in omejitve raˇcunalniˇskih procesov. Pri tem se ne ozira ali jih izvaja ˇclovek ali stroj. [27] Za reˇsevanje doloˇcenega problema se moramo vpraˇsati: Kako zahtevna je reˇsitev problema? Katera je najboljˇsa reˇsitev? Raˇcunalniˇstvo temelji na trdnih teme- ljih, da lahko odgovori na taka vpraˇsanja. Zahtevnost problema je pogojena z zmoˇznostmi stroja - raˇcunalniˇske naprave, ki bo izraˇcunala reˇsitev. V obzir

(18)

moramo vzeti nabor ukazov, omejitve njihovih virov in njihovo okolje.

Pouˇcevanje raˇcunalniˇskega miˇsljenja spodbudi uˇcence k uˇcenju opisova- nja problema, iskanja njegovih bistvenih delov, razdelitev le-teh v manjˇse logiˇcne korake, ki sestavljajo algoritem za reˇsevanje problema ter vrednotenje celotnega procesa. Te veˇsˇcine se lahko aplicirajo na poljubna podroˇcja, toda bistvenega pomena so pri razvoju digitalnih sistemov in reˇsevanju problemov z ozirom na zmogljivost raˇcunalnikov.

Obstaja veliko definicij raˇcunalniˇskega miˇsljenja. Veˇcina zajema teh ˇsest veˇsˇcin reˇsevanja problemov: algoritmiˇcno miˇsljenje, abstrakcija, dekompo- zicija, posploˇsitev in prepoznavanje vzorcev, vrednotenje ter logika. Algo- ritmiˇcno miˇsljenje je proces kreiranja algoritmov – konˇcnega ˇstevila korakov, ki reˇsijo doloˇcen problem. Prepoznavanje bistva problema je abstrakcija. De- kompozicija je razdelitev problema na manjˇse dele, ki jih je laˇzje razreˇsiti.

Posploˇsitev vzame reˇsitev nekega problema in jo preoblikuje tako, da jo lahko uporabimo pri drugih problemih. Prepoznavanje vzorcev je pomemben del tega procesa: ko prepoznamo podobnosti pri dveh problemih, ju lahko reˇsimo na podoben naˇcin. Vrednotenje je razpoznavanje moˇznih reˇsitev problema in presojanje, katero je boljˇse uporabiti, v katerih situacijah deluje in v katerih ne ter kako jo je moˇzno izboljˇsati. Pri reˇsevanju problemov je pomembno logiˇcno sklepanje, ko skuˇsamo na podlagi ˇze usvojenega znanja postaviti nova pravila [7].

Pri reˇsevanju problemov v raˇcunalniˇstvu z razliˇcnimi domenami lahko ob uporabi prej naˇstetih veˇsˇcin oblikujemo algoritem, ki vsem najde reˇsitev.

Kot primer vzemimo razprˇsene tabele. Te, ne glede na vhodne podatke, na izhodu vrnejo na videz nakljuˇcno enakomerno razporejene podatke. Nji- hove aplikacije najdemo v pridobivanju podatkov, digitalnem podpisovanju in porazdeljeni izmenjavi datotek. [9]

Usvajanje veˇsˇcin raˇcunalniˇskega miˇsljenja pripomore k razvoju edinstve- nih naˇcinov oblikovanja in reˇsevanja problemov. Ti koristijo ne samo pri problemih s podroˇcja raˇcunalniˇstva, temveˇc tudi ˇstevilnih drugih znanosti, od matematike, naravoslovja, ekonomije do umetnosti in druˇzboslovja. [28]

(19)

2.3 Metafore pri programiranju

Poznamo razliˇcne opredelitve metafore [15]. Za naˇse potrebe si poglejmo de- finicijo v Slovarju slovenskega knjiˇznega jezika.

”Metafora je besedna figura, za katero je znaˇcilno poimenovanje doloˇcenega pojava z izrazom, ki oznaˇcuje v navadni rabi kak drug podoben pojav.“ [30] Pri uporabi metafore ustva- rimo abstrakcijo, ki skrije doloˇcene informacije o pojavu. Lahko bi zajeli vse informacije in pojav poimenovali z ”nemetaforiˇcnim”terminom. A se za prvo moˇznost odloˇcimo, ˇce ˇzelimo zmanjˇsati zahtevnost in olajˇsati pogovor o zadevi. [10]

V raˇcunalniˇstvu se sreˇcujemo s ˇstevilnimi metaforiˇcnimi poimenovanji. [15]

Datoteke na namizju so shranjene v razliˇcne mape/direktorije, bliˇznjica nas hitreje pripelje do cilja, na zaˇcetnem meniju preberemo in izberemo katero od moˇznosti. Njihova vloga je povezana s samimi osnovami raˇcunalniˇstva.

Raˇcunalniˇstvo je veda, ki sama ustvarja svojo vsebino. Programski jeziki in podatkovne strukture so ustvarjeni in nato uporabljeni za kreiranje in preuˇcevanje drugih. Na drugi strani imamo znanstvenike naravoslovnih ved, ki naredijo in uporabijo orodja za preuˇcevanje narave in ne orodij samih.

Raˇcunalniˇcarji naredijo raˇcunalnike in programske jezike, jih preuˇcujejo in z ponovno uporabo abstrakcije kreirajo nove. Metafore v raˇcunalniˇstvu zago- tavljajo ogrodje za raziskovanje obstojeˇcih, nastajajoˇcih, vˇcasih tudi vsiljenih podobnosti na svojem podroˇcju. [10]

Metafore je pri pouˇcevanju smiselno uporabljati na vseh ravneh izobrazbe.

[15, 14] Igrajo pomembno vlogo pri izobraˇzevanju ne le uporabnikov, temveˇc tudi razvijalcev programske opreme. Za uporabnike vzemimo primer spletne trgovine. Ko kupec zagleda gumb ”Dodaj v koˇsarico”, dobi obˇcutek, da je nakupovanje na spletni strani primerljivo z nakupovanjem v fiziˇcni trgovini.

S poznavanjem obiˇcajnega nakupovanja lahko sklepa, da mora naprej izbrati izdelke za nakup (jih dati v nakupovalno koˇsarico), nato pa jih plaˇcati (za- kljuˇciti nakup). Kupec lahko predvideva, da bo nekje lahko dostopen gumb za sklenitev nakupa. Na to ga napelje ravno uporaba metaforiˇcnega poime- novanja na spletu. Zaradi podobnosti z obiˇcajnih nakupovanjem zna opra-

(20)

viti spletni nakup brez dodatnih pojasnil. To je glavni razlog, da je takˇsna zgradba spletnih strani smiselna. Za uporabnike so podobnosti med vrstama nakupovanja samoumevne, medtem ko so za razvijalce vsiljene. Uporabnike nove programske opreme bi lahko primerjali z otroki. Enako velja za pro- gramerje, ki se prviˇc sreˇcajo s programiranjem ali se uˇcijo novega jezika.

Nanaˇsamo se na otrokovo kognitivno prilagoditev okolji, ki zajema projek- cijo in prilagajanje. Poglejmo si primer igre z hiˇso in lutkami, kjer projicira shemo iz realnosti na igraˇce. Otrok shemo iz realnosti prilagodi svojim potre- bam. To je razvidno iz sesalnih navad otroka. Sprva ga nagon vodi k noˇsenju stvari v usta, dokler ne postane njegov vid bolj izostren. Takrat zaˇcne stvari nositi v svoje vidno polje in ne veˇc v usta. Kvaliteta metafore je odvisna od koliˇcine potrebne prilagoditve – ˇcim manj prilagajanja je potrebnega, tem boljˇsa je metafora. Pri spletnem nakupovanju se izkaˇze, da prilagajanja ni veliko. Treba je le znati uporabiti miˇsko za klik na gumb. Zato ta koncept veˇcini ljudi ne predstavlja teˇzav. Druga pomembna uporaba metafor v raˇcunalniˇstvu je pri razvoju novih produktov in orodij, kot so raˇcunalniˇske naprave, algoritmi in podatkovne strukture. Njihov razvoj traja dlje, saj zahtevajo nov pristop k problemu in ne samo izpeljave iz obstojeˇcega znanja.

Pri tem je v obzir treba vzeti ciljnega uporabnika. Metafore lahko poma- gajo programerjem pri znanstvenem raziskovanju. Nanaˇsajo se na orodja in metode, ki naˇcrtno opisujejo podobnosti z raˇcunskim svetom, z namenom analize in preuˇcevanja. [10]

Pri rabi metafor je potrebno paziti na razlike v razumevanju med razliˇcnimi kulturami. [13] Kot primer vzemimo ameriˇski poˇstni nabiralnik z zastavico.

Slednja je dvignjena natanko tedaj, ko je v nabiralniku poˇsta za prevzem.

To se prenese na elektronsko poˇsto, ki prikaˇze zastavico, ko imamo nepre- gledano prejeto poˇsto. V kulturah, ki se z njim niso sreˇcale, bo ta oznaˇcba nenaravna. Uporabniku ne bo mogel takoj sklepati, kaj to pomeni. Metafore lahko tudi zastarijo. Poimenovanje za gradnik izbire (angl. radio button) je iz ˇcasov, ko so mnoˇziˇcno uporabljali radie. Ti so imeli gumbe, pri katerih je bil lahko hkrati priˇzgan le en. Danes ta primerjava ni veˇc smiselna in intu-

(21)

itivna. Pozorni moramo biti tudi na napaˇcno aplikacijo metafore. Pojava, ki ju primerjamo, se nikoli popolnoma ne ujemata. Zato obstaja nevarnost aplikacije lastnosti, ki se ne skladajo. [14] Primer pomanjkljive metafore je tabela za ponazoritev 2D tabele (angl. array). Ce ˇˇ zelimo pregledati vse elemente, se zdi na podlagi metafore enakovredno ali jih beremo po stolpcih ali po vrsticah. V praksi ni tako, saj je zaradi naˇcina, na katerega je tabela shranjena v pomnilniku in na katerega procesor dostopa do njega, eden od naˇcinov lahko veliko hitrejˇsi od drugega. [15, 14]

Napredek v raˇcunalniˇstvu je olajˇsan z uporabo abstrakcije na vse viˇsjem nivoju, ki prikrije dejansko kompleksnost problema. ˇStevilne od teh abstrak- cij so zgrajene na osnovi metafor. [10] Vendar metafore ne morejo nadome- stiti poznavanja osnovne strukture za tiste, ki si ˇzelijo poglobljenega znanja in popolnega razumevanja. [26]

Odnos uˇciteljev do rabe metafor pri pouˇcevanju je razliˇcen. Nekateri jih uporabljajo ali si celo izmislijo svoje. Nekateri pa jih uporabljajo nezave- dno oziroma zavraˇcajo njihovo uporabo. Izvirne metafore, ki jih pripravi uˇcitelj, se lahko izkaˇzejo za odliˇcne, saj so narejene z obzirom na dotiˇcno snov in uˇcence. Hkrati izkoristijo in pokaˇzejo znanje uˇcitelja. [29] Na podlagi razliˇcnih raziskav so ugotovili, so bile razlage s pomoˇcjo metafor veliko bolj uspeˇsne kot tiste brez njih. [14] Z metaforami je pogosto povezano globlje razumevanje novo osvojenega znanja za veˇcino uˇcencev.

2.4 Aktivno uˇ cenje

Konstruktivizem je teorija znanja, ki temelji na ideji, da je uˇcenje aktiven proces lastne konstrukcije spoznanj. Sloni torej na lastnih izkuˇsnjah in in- terpretacijah. Uˇcenje bi zato moralo temeljiti predvsem na posameznikovi lastni aktivnosti. [11]

Aktivno uˇcenje bi lahko povzeli po modrosti filozofa Konfucija:

”Prebral sem in sem pozabil. Videl sem in sem si zapomnil. Naredil sem in znam!“. [23]

Po Silbermanu [19] aktivno uˇcenje zajema samostojno razmiˇsljanje, iskanje

(22)

primerov in opravljanje nalog, kjer je potrebno uporabiti novo znanje. Bolj aktivni ko so uˇcenci, boljˇse je njihovo razumevanje nauˇcenega. Poleg po- sluˇsanja razlage morajo brati, pisati, razpravljati ali biti vpleteni v reˇsevanje problemov. [2]

Aktivno uˇcenje podpira razliˇcne uˇcne metode. Skupno jim je, da v ospredje postavljajo pristope za dosego globljega znanja vsakega uˇcenca.

Uˇciteljeva vloga je predvsem usmerjati uˇcence pri interaktivnem procesu uˇcenja. V dani situaciji mora izbrati najboljˇso metodo pouˇcevanja. [11] Bo- nwell [2] predlaga vodene aktivnosti, pri katerih uˇcenci nekaj delajo in o tem razmiˇsljajo. Te se lahko vkljuˇci tudi v del klasiˇcnega predavanja. Uˇcitelj, na primer, naredi dva ali tri kratke dvominutne odmore, med katerimi uˇcenci primerjajo in popravijo svoje zapiske. Aktivnost lahko vkljuˇcuje sodelovanje uˇcencev, razpravo, igre, slikovno gradivo, simulacijo ali pa je izvedena samostojno kot na primer reˇsevanje doloˇcenega problema.

Pri aktivnem uˇcenju vsak uˇcenec gradi na podlagi svojega obstojeˇcega znanja, zato razliˇcno predznanje ni tako velika teˇzava kot pri, na primer, frontalnem pouku. [19]

Na sploˇsno je uˇciteljeva naloga ustvarjanje spodbudnega okolja za aktivno sodelovanje uˇcencev. Pri aktivnosti jih vodi in spodbuja. Pri razpravi po- sluˇsa, spraˇsuje in povzema. [19] Teˇzava, s katero se sreˇcujejo, je pomanjkanje dostopnih nalog na osnovi aktivnega uˇcenja, koliˇcina ˇcasa, potrebnega za samostojno pripravo le-teh, pa je velika. Reˇsitev so lahko naloge, ki jih uˇcenci pripravijo sami. [17] Druge ovire pri vpeljevanju metod aktivnega uˇcenja so zahtevno vkljuˇcevanje v uˇcni naˇcrt, podaljˇsan ˇcas priprave, teˇzka izvedba pri velikem ˇstevilu uˇcencev in pomanjkanje materialov, opreme ali sredstev.

Najveˇcja pa je verjetno strah pred odzivom uˇcencev in pred pomanjkanjem kontrole. Uˇcitelj ne ve, ali bodo uˇcenci dobro razumeli snov, usvojili potrebne veˇsˇcine. [2]

Aktivno uˇcenje poveˇca pozornost uˇcencev pri samem uˇcenju. [17] Free- manova raziskava aktivnemu uˇcenju pripisuje boljˇse rezultate kot obiˇcajni frontalni razlagi. [16] Tomaˇz Kranjc ugotavlja, da tako uˇcenje prinese viˇsjo

(23)

raven znanja. [23] Aktivni pouk ni edina pot ali bliˇznjica k znanju. Je naˇcin, ki prispeva k poveˇcanju motivacije, k boljˇsemu razumevanju in pozitivnem odnosu do uˇcenja.

2.5 Projektno uˇ cenje

Projektno uˇcenje (angl. project-based learning, PBL) je uˇcna metoda, po kateri uˇcenci pridobijo znanje z aktivnim sodelovanjem pri reˇsevanju problemov iz vsakdanjega ˇzivljenja. Usvojijo teoretiˇcno in praktiˇcno znanje. Hkrati razvijejo veˇsˇcine sodelovanja, komuniciranja in dela v skupini. Poudarek je na kreativnem miˇsljenju pri odkrivanju ter uporabi novega znanja. [4, 1]

Obiˇcajen projekt se od projektnega uˇcenja loˇcuje v trajanju, zahtevnosti in namenu oziroma smislu uporabe. Projekt je obiˇcajno krajˇsi in miselno manj zahteven. Izvede se ga po obravnavanju snovi kot utrjevanje/nadgraditev. Nasprotno od tega je projektno uˇcenje del samega uˇcnega procesa – metoda za pridobivanje potrebnega znanja in veˇsˇcin. Traja dlje ˇcasa in je miselno zahtevnejˇse. [1]

Projektno uˇcenje se niti ˇcasovno niti vsebinsko niti organizacijsko pa tudi ˇcasovno in prostorsko ne omejuje na pogoje, v katerih je organiziran ˇsolski pouk. [8] Poteka lahko kot individualno ali skupinsko delo. Traja lahko veˇc ˇsolskih ur, veˇc dni, tednov ali celo mesecev.

Naloga uˇcitelja je pripraviti gradivo in navodila projekta. Uˇcitelj nato pomaga pri uˇcenju oziroma izvajanju. Spodbuja in usmerja uˇcence. Slednji pa se ob tej pomoˇci samostojno uˇcijo. Imajo glavno vlago pri izvajanju aktivnosti. Zbirajo in preuˇcujejo informacije, analizirajo opaˇzanja in poroˇcajo o rezultatih. [8, 4]

Tema je vzeta iz vsakdanjega ˇzivljenja. Cilji so praktiˇcni. Uˇcencem predstavlja smiselno situacijo. Vsebina obiˇcajno povezuje razliˇcna strokovna po- droˇcja. Pri naˇcrtovanju se upoˇsteva interese uˇcencev, njihovih potreb in sposobnosti. Idejna zasnova projekta je skupna. Zaˇzeleno je, da uˇcenci po- dajo pobudo, saj jo bodo tako praviloma bolj zavzeto obravnavali. [8, 25]

(24)

Poznamo veˇc tipov projektnega uˇcenja [8]:

• projekt konstruktivnega tipa (izdelava izdelka, izvedba dogodka),

• projekt usvajanja in ovrednotenja (spoznavanje in ovrednotenje pojava, metode, glasbe, filma, razstave ipd.),

• projekt problemskega tipa (reˇsevanje problema),

• projekt uˇcenja (osvajanje spretnosti, veˇsˇcine, sposobnosti ali znanja).

Pri projektnem uˇcenju moramo biti pripravljeni na doloˇcene teˇzave. Prva je zanemarjanje sistematiˇcnosti uˇcnih vsebin. Obseg usvojenega znanja je manjˇsi. Za doloˇcena podroˇcja ni najbolj uˇcinkovita metoda uˇcenja, posebno pri pridobivanju teoretiˇcnih znanj. Te probleme lahko poskuˇsamo zmanjˇsati z dobrim naˇcrtovanjem. [8]

2.6 Poigritev

Poigritev (angl. gamification) je definirana kot

”prenos zakonitosti, pravil in elementov igre iz igre v resniˇcno ˇzivljenje“ [12]. Osredotoˇcili se bomo na uporabe poigritve pri pouˇcevanju. Poigritev spremeni celoten uˇcni proces v igro. V obstojeˇce uˇcne naˇcrte vpelje pravila in elemente igre. S tem dodatno motivira uˇcence in jih spodbudi k sodelovanju. Primer takih elementov so zbiranje toˇck, zgodba/tema, lestvica najboljˇsih, vrstica napredka, ˇcasovne omejitve in stopnje teˇzavnosti. V resnici poigritev ni omejena samo na izobraˇzevalne aktivnosti. Uporablja se vse od fitnes aplikacij do LinkedIn profilov, saj poveˇcuje interes in uporabo. [3]

Igro lahko opiˇsemo kot zabavno, izmiˇsljeno, nepredvidljivo. Doloˇcena je s pravili, omejena s ˇcasom in prostorom ter njen konˇcni rezultat ni nekaj uporabnega. Za igre, ki se uporabljajo v izobraˇzevanju, je znaˇcilno, da so zgrajene na podlagi uˇcnih naˇcrtov. Poveˇcajo vkljuˇcenost uˇcenca, prilago- dijo situacijo posamezniku in omogoˇcijo korektno ocenjevanje. Hkrati uˇcijo posameznika veˇsˇcin 21. stoletja. [3]

(25)

Za boljˇse razumevanje strukture igre in njenih elementov uporabimo MDA model (angl. MDA framework). Z njim loˇcimo tri tipe elementov igre: mehanika, dinamika in estetika. Mehanika opiˇse komponente na nivoju podatkov in algoritmov. To so npr. zvezdice, lestvica najboljˇsih, toˇcke, stopnje, po- vratne informacije, virtualne dobrine, vrstica napredka, avatarji in skupine.

Dinamika opisuje obnaˇsanje komponent mehanike v ˇcasu igranja. To so npr.

ˇcasovna omejenost, obnaˇsanje nasprotnikov, deljenje informacij v skupini, ustvarjanje pogojev, ki spodbujajo sodelovanje igralcev, sistem pridobivanja dobrin igre. Estetika spodbuja ˇzelene ˇcustvene odzive igralca med igranjem.

S tega vidika igro opiˇsemo kot npr. izziv, fantazijo, pripoved, raziskovanje, socialni sistem, razvedrilo. [5, 20]

Kljub temu, da poigritev v veˇcini primerov izboljˇsa uˇcenje, moramo biti pozorni na nekaj njenih pasti. Spodbujanje tekmovalnosti lahko na nekatere vpliva negativno. V doloˇcenih kontekstih uporaba poigritve ni primerna. [18]

2.7 Obravnavani algoritmi in podatkovne strukture

Privzeli smo, da uˇcenci pred reˇsevanjem nalog poznajo osnovne algoritme in podatkovne strukture, kot so seznami in slovarji.¹ Privzemamo tudi pozna- vanje sintakse in semantike programskega jezika.

Na podlagi omenjenega predznanja smo izbrali algoritme in podatkovne strukture, za katere ˇzelimo, da jih uˇcenci utrjujejo. Med njih spadajo algoritmi za urejanje in iskanje elementov strukture, algoritmi za iskanje in dodajanje elementov v binarnem neuravnoteˇzenem drevesu, spoznavanje vr-

1V izogib dvoumnosti bomo v besedilu, kjer ne bo eksplicitno napisano (ali iz konte- ksta oˇcitno) drugaˇce, uporabljali terminologijo iz programskega jezika Python. Tako se izrazseznam (v Pythonu: list) nanaˇsa na strukturo, ki jo sicer navadno imenujemotabela (array) z dinamiˇcnim spreminjanjem velikosti, podobno kot, na primer, vector v stan- dardni knjiˇznici C++. Izraz slovar (dictionary) pa se v tem delu nanaˇsa na Pythonovo implementacijo slovarja z razprˇseno tabelo.

(26)

ste in sklada ter algoritmov za iskanje najkrajˇse poti med dvema toˇckama v grafu. Spodnja tabela kaˇze, kateri koncepti se pojavljajo v posameznih nalogah.

naloge algoritmi in podatkovne strukture 1, 2 urejanje: zlivanje, mehurˇcno urejanje 3 iskanje: linearno iskanje, bisekcija

4, 5, 6, 7, 8, 9 drevesa: binarna, uravnoteˇzena/neuravnoteˇzena, iskanje, dodajanje

13 vrsta

14 sklad

15, 16 algoritmi na grafih: iskanje najkrajˇse poti

Urejanje. Ker obstaja veliko razliˇcnih algoritmov urejanja, ki jih ni teˇzko razumeti, prav tako pa analiza njihove ˇcasovne zahtevnosti navadno ni zahtevna, so algoritmi urejanja pogosto eni od prvih algoritmov, predstavljeni v okviru predmetov s tega podroˇcja, saj sluˇzijo kot primer za dokazovanje pra- vilnosti, analizo ˇcasovne zahtevnosti, doloˇcanje najmanjˇse teoretiˇcno moˇzne ˇcasovne zahtevnosti in podobno.

V nalogah v tem delu si ogledamo dva algoritma urejanja. Prvi je urejanje z zlivanjem (angl. merge sort). Tu se osredotoˇcimo zgolj na postopek zlivanja dveh urejenih seznamov, ki ju je potrebno s postopnim primerjanjem elementov na prvem mestu zdruˇziti v en sam urejen seznam.

Drugi algoritem je mehurˇcno urejanje (angl. bubble sort). Pri njem primerjamo po dva sosednja elementa. ˇCe sta v napaˇcnem vrstnem redu po velikosti, ju zamenjamo. Ta algoritem smo izbrali, ker ga je preprosto odkriti in sprogramirati, istoˇcasno pa ga je bilo preprosto naravno vkljuˇciti v zgodbo.

Iskanje. Prvi algoritem iskanja, ki ga spoznajo uˇcenci, je linearno iskanje (angl. linear search). Uvidijo, da ga je zelo preprosto implementirati, vendar je poˇcasen na veliki mnoˇzici podatkov. V naslednji nalogi jih pripeljemo do binarnega iskanja (angl. binary search). Uˇcenci spoznajo, da je ta naˇcin

(27)

iskanja hitrejˇsi.

Drevesa. Drevesa uvedemo kot strukturo, namenjeno binarnemu iskanju, ki pa za razliko od urejenih seznamov omogoˇca tudi dodajanje in brisanje elementov v konstantnem ˇcasu. Ker bisekcija zaˇcne iskanje s srednjim ele- mentom seznama, je ta v korenu drevesa; njegova neposredna naslednika sta srednja elementa leve in desne polovice seznama in tako naprej.

Uˇcence z eno od nalog pripeljemo do zavedanja o problemu neuravnoteˇzenih dreves, ne uˇcimo pa jih razliˇcnih definicij uravnoteˇzenosti in razliˇcnih obra- tov za ohranjanje uravnoteˇzenosti, saj je programiranje teh postopkov zanje ˇse preteˇzko.

Vrsta in sklad. Vrsto in sklad uvedemo tako, da pokaˇzemo, da vˇcasih po podatkih ne iˇsˇcemo, paˇc pa nam je pomemben njihov vrstni red. Drevesa nam pri tem ne bodo pomagala, zato se vrnemo k seznamom. Zato pripravimo dve nalogi, ki kombinirata sklade in vrste.

Algoritmi na grafih. Algoritmi na grafih so pogosto zakljuˇcna tema predmetov s podroˇcja algoritmov. V nalogah predstavimo algoritem za iskanje najkrajˇse poti. V prvi nalogi uˇcenci delajo z neuravnoteˇzenim grafom, tako da je v bistvu dovolj implementirati iskanje v ˇsirino. V drugi nalogi so pove- zavam predpisane dolˇzine. Podana je tudi maksimalna dolˇzina celotne povezave, tako da lahko uˇcenci sprogramirajo bodisi Dijkstrov algoritem bodisi nekakˇsno omejeno razliˇcico iskanja v ˇsirino.

(28)

(29)

Spletna stran Tatovi umetnin

Razvoj spletne strani ni predstavljal bistva te diplomske naloge, zato ga bomo opisali le na kratko. Sledil bo opis njene uporabe.

3.1 Razvoj spletne strani

Streˇzniˇski del spletne stran je napisan v programskem jeziku Python, zaradi interaktivnosti pa smo na doloˇcene strani dodali kodo v jeziku Javascript.

Za implementacijo streˇznika smo uporabili knjiˇznico Flask. V HTML smo zapisali le nekaj osnovnih strani, navodila nalog pa smo zaradi preprostosti pisali v jeziku Markdown; zapis v tem jeziku prevedemo v HTML z ustrezno knjiˇznico in ga vstavimo v pripravljeno predlogo.

Za razvoj smo uporabljali okolje PyCharm, namenjeno razvoju v programskem jeziku Python. PyCharm omogoˇca tudi dostop do ukazne vrstice in preprostejˇse delo z repozitorijem git.

Spodaj je prikazana struktura programske kode spletne strani.

data/

naloge/

resitve/

seznami/

explanations/

17

(30)

static/

icons/

img/

javascript.js style.css tasks/

templates/

konec.html naloga.html prijava.html uvod.html main.py

requirements.txt

Seznam Pythonovih knjiˇznic, ki so potrebne za delovanje spletne aplikacije, je zapisan v requirements.txt. Datoteka main.py inicializira aplikacijo in zdruˇzi vse njene komponente v delujoˇco celoto. Vse predloge HTML so shranjene v direktoriju templates. Direktorij tasks vsebuje datoteke z navodili posameznih nalog v jeziku Markdown. Datoteke z razlagami posameznih nalog, prav tako v jeziku Markdown, pa so zapisane vexplanations.

Izgled strani dopolnjujejo datoteke v direktoriju static. style.css doloˇca slogovno oblikovanje. Interaktivnost omogoˇca javascript.js. Vse slike so shranjene v podmapi imgin vse ikone v podmapi icons.

Spletna stran ne shranjuje podatkov o uporabnikih, tako da na streˇzniku ni podatkovne baze. Edina funkcija streˇznika je prikazovanje spletnih strani in generiranje unikatnih podatkov, pri ˇcemer kot seme za generator na- kljuˇcnih ˇstevil sluˇzi uporabnikovo ime.

3.2 Uporaba spletne strani

Uporabnik se za reˇsevanje nalog prijavi z uporabniˇskim imenom, kot je vidno na sliki 3.1. Ime sluˇzi kot seme za generator nakljuˇcnih ˇstevil, ki ga

(31)

potrebujemo za sestavljanje unikatnih podatkov. Ime se shrani v piˇskotek, tako da ga ob naslednji prijavi ni potrebno vnaˇsati. Gesla ni, prav tako se ime ne shrani na streˇzniku.

Uporabnik je nato preusmerjen na uvodno stran.

Slika 3.1: Prijavna stran, posnetek zaslona.

Uvodna stran (Slika 3.2) vsebuje prolog zgodbe, ki povezuje naloge med sabo. Za njim je povezava do datoteke zip s potrebnimi podatki, sestavljenimi za tega uporabnika, in funkcijami za reˇsevanje. Uporabnik si jo prenese na svoj raˇcunalnik in razˇsiri. V eno od teh map shranjuje tudi svoje reˇsitve. V zadnjem odstavku uvoda je povezava do strani z navodilom prve naloge.

Opis naloge je sestavljen iz naslova, nadaljevanja zgodbe, predloˇzenih funkcij, vnosnega polja za odgovor ter lestvice napredka (Slika 3.3). Naslov je poudarjen in zapisan veˇcje, da vzbudi zanimanje in napoveduje nadaljevanje zgodbe.

Sledi navodilo naloge (Slika 3.4). Z odebeljenimi kljuˇcnimi besedami opiˇse ozadje zgodbe in kaj priˇcakuje od uˇcenca.

V naslednjem razdelku so zapisane vse funkcije, ki jih uporabnik lahko uporabi. Kot je razvidno iz slike 3.5, je zraven tega polja ikona za namig. ˇCe kliknemo nanjo, se prikaˇze pojavno okno z nasvetom za reˇsevanje (Slika 3.6).

(32)

Slika 3.2: Uvodna stran, posnetek zaslona.

Slika 3.3: Naslov naloge, posnetek zaslona.

Okno zapremo s klikom na kriˇzec ali s klikom izven samega okna.

Sledita vnosno polje za odgovor in gumb za njegovo preverjanje. Vidimo ju na sliki 3.7. Vnosnih polij je pri doloˇcenih nalogah veˇc.

Ob oddaji napaˇcnega odgovora se prikaˇze pojavno okno, kot ga kaˇze slika 3.8. Tudi to okno zapremo s klikom na kriˇzec ali s klikom izven okna.

(33)

Slika 3.4: Navodilo naloge, posnetek zaslona.

Slika 3.5: Podane funkcije naloge, posnetek zaslona.

Ce naloga ne zahteva odgovora, ni vnosnega polja. Nadomeˇsˇˇ ca ga gumb za nadaljevanje z naslednjo nalogo, kot vidimo na sliki 3.9

V primeru, da oddamo pravilen odgovor ali kliknemo na gumb za nadaljevanje (pri drugi in sedmi nalogi, kjer odgovor ni potreben) se pojavi razdelek z razlago in povezavo do naslednje naloge (Slika 3.10).

(34)

Slika 3.6: Pojavno okno namiga, posnetek zaslona.

Slika 3.7: Vnos odgovora naloge, posnetek zaslona.

Na koncu strani z nalogo je indikator napredka (Slike 3.7, 3.9 in 3.10), ki grafiˇcno in ˇstevilˇcno prikazuje procent opravljenih nalog.

Ob oddaji pravilne reˇsitve zadnje naloge nas povezava pripelje do konˇcne strani. Vidimo jo na sliki 3.11. Tu izvemo zakljuˇcek zgodbe in prejmemo ˇcestitke za uspeˇsno reˇsevanje.

(35)

Slika 3.8: Pojavno okno ob napaˇcnem odgovoru, posnetek zaslona.

Slika 3.9: Nadaljevanje brez odgovora, posnetek zaslona.

(36)

Slika 3.10: Razlaga naloge, posnetek zaslona.

Slika 3.11: Zakljuˇcna stran, posnetek zaslona.

(37)

Opisi nalog

Tabela 4.1 kaˇze, kateri koncepti so obravnavani v posamiˇcnih nalogah.

V nadaljevanju je vsaka naloga opisana podrobneje. Zgodba naloge razloˇzi problem. Pojasni njegovo vpetost v celotno dogajanje. Navede funkcije, ki so nam na voljo za reˇsevanje, ter namige, s katerimi si lahko pomagamo.

Razlaga objasni pot do reˇsitve. Ponazori, kako naj uˇcenec razmiˇslja in kaj ga pri tem vodi. Reˇsitev je zapisana v obliki programske kode. Algoritmiˇcno in didaktiˇcno ozadje nam pove, kaj je uˇcni cilj naloge in kako navodilo uˇcenca usmeri, da razmiˇslja v pravo smer.

Od besedil v tem poglavju uˇcenec vidi opis naloge in funkcij, namig in razlago reˇsitve.

Veliko nalog uporablja iste funkcije. Spodnje besedilo smo skrajˇsali tako, da smo takˇsno funkcijo opisali le prviˇc, v naslednjih nalogah pa se sklicujemo na prejˇsnji opis. Na spletni strani pa uˇcenec pri vsaki nalogi vidi opise vseh za nalogo relevantnih funkcij, tudi tistih, ki jih je ˇze uporabljal.

V objavljenih reˇsitvah smo se izogibali trikov, specifiˇcnih za programski jezik Python in naprednih konceptov, ki jih programer na tem nivoju najbrˇz ˇse ne obvlada. Tipiˇcen primer je iskanje tistega kljuˇca v slovarju, ki mu je prirejena najveˇcja vrednost; profesionalni programer v Pythonu tu uporabi max(d, key=d.get) (pri ˇcemer je d slovar), zaˇcetnik pa tak klic teˇzko ra- zume, saj jed.gettu vezana metoda slovarja. Paˇc pa smo uporabili nekatere

25

(38)

Sumljivakustosavisokepostavezlivanje,urejanjezzlivanjem

Neredvkletimehurˇcnourejanje

Kakoizuritirobotalinearnoiskanje

Sreˇcavnesreˇcibisekcija

Skomsenesmemohecatistrukturadrevesa,iskanjekorenadrevesa

Zgovornimafijciiskanjeelementavdrevesu

Aˇzurnipodatkidodajanjeelementavdrevo

Nenavadnadelitevdelaneuravnoteˇzenodrevo

Aliimakdoprivilegije?preiskovanjeneuravnoteˇzenegadrevesa,iskanjevglobino

Naslediˇcasovnazahtevnostiskanjavdrevesu

Kjesemafijcisreˇcujejorazprˇsenetabele,unikatnapredstavitevelementa,iskanjedvojnikov

Krajsreˇcevanjarazprˇsenetabele,iskanjenajpogostejˇsevrednosti

Aliverjetimafijcurazprˇsenetabele,iskanjedesetihnajpogostejˇsihvrednosti

Korakbliˇzjekreˇsitvisklad

Mafijecjegovorilresnicovrsta

Dvojniagentigrafzenakovrednimipovezavami,iskanjenajkrajˇsepotimeddvemavozliˇsˇcema

Zdajgrezaresgrafzneenakovrednimipovezavami,iskanjenajkrajˇsepotimeddvemavozliˇsˇcema

Tabela4.1:Naslovinaloginvnjihuporabljenihalgoritmiinpodatkovnestrukture

(39)

prikladne funkcije in podatkovne strukture iz vdelanih knjiˇznic (na primer slovar s privzetimi vrednostmi collections.defaultdict). Pri reˇsevanju kasnejˇsih nalog so skoraj neizbeˇzne tudi rekurzivne funkcije.

4.1 Sumljiva kustosa visoke postave

Kot vidiˇs, je stavba sestavljena iz dveh delov, ki ju povezuje glavni vhod z veˇzo. Novo razstavo so otvorili v najviˇsjem, tretjem nadstropju desnega dela stavbe. Ukradli pa so dve sliki, eno iz drugega nadstropja v desnem delu in eno iz pritliˇcja v levem delu. Policisti, ki so zasliˇsali obiskovalce, poroˇcajo, da sta najbrˇz imela prste vmes dva od zaposlenih. Veˇc ljudi je namreˇc omenilo, da so opazili usluˇzbenca muzeja, visoke postave, ki se mu je nekam mudilo, le da eni govorijo o temnolasem in drugi o svetlolasem ˇcloveku. Policisti so ˇze zbrali vse zaposlene iz levega in desnega dela v dve vrsti, ki so ju uredili po velikosti od najveˇcjega do najmanjˇsega. Tvoja naloga je zasliˇsati usluˇzbence in iz dveh, ki sta verjetno sodelovala z roparji, izvleˇci kaj uporabnega.

Razpoloˇzljive funkcije:

• visina_levega() in visina_desnega() vrneta viˇsino prve osebe, ki ˇcaka v levi oziroma desni vrsti.

• poklici_levega() in poklici_desnega() pokliˇceta osebo iz leve oz.

desne vrste. Funkcija vrneta niz z imenom in priimkom te osebe.

(Po tem oseba ne stoji veˇc v vrsti in funkciji visina_levega() in visina_desnega()vraˇcata imeni naslednjih oseb).

• zaslisi(ime) zasliˇsi osebo s podanim imenom. ˇCe zasliˇsiˇs katero od dveh oseb, ki je (ˇce so naˇsi sumi pravilni) sodelovala pri ropu, bo funkcija vrnila niz z izjavo, sicer pa vrneNone.

Dodatni namig: Zasliˇsevanje jemlje ˇcas. Razmisli, kako se lotiti dela tako, da zasliˇsiˇs ˇcim manj zaposlenih.

(40)

Razlaga. Imamo dve po velikosti urejeni vrsti zaposlenih v galeriji. Dokler ne dobimo dveh koristnih izjav, ˇzelimo zasliˇsevati usluˇzbence. Da jih bomo dobili ˇcim prej, jih kliˇcemo na zasliˇsanje po vrsti od najviˇsjih do najmanjˇsih.

Najviˇsja oseba med vsemi je prvi iz leve vrste ali tisti na ˇcelu desne. Viˇsji med njima je namreˇc viˇsji od vseh v svoji vrsti ter viˇsji od prvega druge vrste in poslediˇcno vseh za njim. Ko najviˇsjega zasliˇsimo, ta zapusti vrsto. Nato ponavljamo postopek za izbiro naslednjega.

Funkcija zaslisi(ime) vrne rezultat po 0,5 sekunde, zato jo je smiselno uporabiti ˇcim manjkrat. Reˇsitev bi naˇceloma lahko dobili tudi z za- sliˇsevanjem vseh zaposlenih po nakljuˇcnem vrstnem redu, vendar nas dolgo ˇcakanje na rezultat od tega odvrne.

Zaposleni v galeriji predstavljajo elemente seznama. Vrednosti elementov so viˇsine zaposlenih. Imamo dva seznama, enega z zaposlenimi levega dela stavbe in enega zaposlenimi desnega dela. Seznama sta urejena, saj so jih policaji razvrstili po viˇsini. ˇZelimo iskati od najviˇsjega izmed vseh zaposlenih, kar je enako iskanju po celotnem urejenem seznamu. Za pridobitev slednjega, moramo obstojeˇca seznama zdruˇziti. To bomo najhitreje naredili z zlivanjem (angl. merge). Primerjamo prvi vrednosti podseznamov in ustrezno premaknemo v konˇcni seznam. Pri zaposlenih sta prva iz vrste najviˇsja.

Na zasliˇsanje pokliˇcemo viˇsjega izmed njiju. Ta postopek ponavljamo, dokler ne najdemo obeh osumljenih, ki nekaj skrivata.

Primer reˇsitve:

krivcev = 0

while krivcev < 2:

if visina_levega() > visina_desnega():

oseba = poklici_levega() else:

oseba = poklici_desnega() izjava = zaslisi(oseba)

(41)

if izjava != None:

print(izjava) krivcev += 1

Algoritmiˇcno in didaktiˇcno ozadje. Z nalogo ˇzelimo prikazati korak urejanja z zlivanjem, torej pojasniti princip zlivanja elementov dveh tabel. Elemente ˇzelimo pridobivati po vrsti od najveˇcjega do najmanjˇsega, saj iˇsˇcemo enega od veˇcjih elementov. Pri tem se sklicujemo na dve predhodno urejeni tabeli. Uˇcenec ugotovi, ali je naˇsel iskani element, s pomoˇcjo funkcije zaslisi(ime). Njen klic traja pol sekunde, zato bi bilo pregledovanje vseh elementov prepoˇcasno. Cilj je torej poiskati algoritem, ki minimizira ˇstevilo klicev te funkcije. K uporabi zlivanja ga prisilimo z omejitvijo pridobivanja in ugotavljanja velikosti le najveˇcjih elementov danih dveh tabel.

Uˇcenec mora ugotoviti, da se mu najbolj splaˇca klicati osumljence na zasliˇsanje od najviˇsjega do najniˇzjega, ob ˇcemer odkrije princip zlivanja (ali pa se spomni nanj, ˇce ga ˇze pozna). Pridobi viˇsini oseb na ˇcelu leve in desne urejene vrste. Pokliˇce ter zasliˇsi viˇsjega izmed njiju. Postopek nadaljuje, dokler ne najde obeh krivcev.

4.2 Nered v kleti

V kleti imajo spravljene vse dokumente o nakupu, prodaji in vrednosti ume- tniˇskih del. Zagotovo bi bilo koristno, da jih pregledamo, a kaj, ko so totalno neurejeni. Dokumenti, ki bi bili zanimivi za nas, so spravljeni v ˇskatlah na zgornji polici, do katerih lahko prideˇs le, ˇce splezaˇs po lestvi. Sicer so ravno ta teden kupili robota za delo v arhivu, vendar ga ˇse nihˇce ni nauˇcil urejati ˇskatel po vrsti, od tistih z najstarejˇsim datumom, do tistih z najnovejˇsim.

Vem, da je programiranje ena tvojih moˇcnih strani. Ali misliˇs, da bi znal to reˇsiti? Brez urejenih ˇskatel bomo namreˇc imeli kasneje teˇzave.

(42)

• premik_desno() inpremik_levo() premakneta robota k sosednji polici s ˇskatlo. Vrneta True, ˇce je premik moˇzen in False, ˇce ni.

• vrni_datum_trenutne()robot prebere datum ˇskatle, pri kateri se nahaja. Vrne datum v obliki nizayyyymmdd.

• zamenjaj_trenutno_z_levo()inzamenjaj_trenutno_z_desno()robot zamenja trenutno ˇskatlo s sosednjo. ˇCe to izvede uspeˇsno, vrne True, sicer vrne False.

Dodatni namig: Poskusi med vsakim sprehodom od zaˇcetka do konca police ˇcim bolj izboljˇsati vrstni red ˇskatel.

Razlaga. Dokumente moramo urediti po vrsti, da bomo kasneje laˇzje iskali po njih. Kakˇsen naˇcin urejanja uporabiti, sugerirajo moˇzne funkcije robota.

Zamenjamo lahko samo trenutno ˇskatlo s sosednjima, kar je natanˇcno za- manjava, ki jo uporabljamo pri urejanju z mehurˇcki oziroma mehurˇcnem urejanju (angl. bubble sort). Sprehajamo se ˇcez seznam in zamenjamo sosednji ˇskatli, ˇce sta v napaˇcnem ˇcasovnem vrstnem redu. To ugotovimo tako, da si zapomnimo datum prejˇsnje in ga primerjamo z datumom trenutne. Da smo bolj uˇcinkoviti, urejamo pri prehajanju od leve proti desni in nazaj (urejanje s stresanjem, angl. shaker sort). Na zaˇcetku in koncu vrste preverimo ali so ˇskatle urejene oziroma ali pri zadnjem sprehodu nismo naredili nobene zamenjave. ˇCe ta pogoj drˇzi, konˇcamo.

Primer reˇsitve: Urejanje z mehurˇcki lahko sprogramiramo tako.

urejene = False while not urejene:

# Urejanje z leve proti desni urejene = True

datum_leve = vrni_datum_trenutne() while premik_desno():

datum_trenutne = vrni_datum_trenutne()

(43)

if datum_trenutne < datum_leve:

zamenjaj_trenutno_z_levo() else:

datum_leve = datum_trenutne while premik_levo():

pass

Ce ˇˇ zelimo postopek nekoliko pospeˇsiti, pa urejemo ˇse med vraˇcanjem nazaj na levo stran in tako dobimo urejanje s stresanjem.

urejene = False while not urejene:

# Urejanje z leve proti desni urejene = True

datum_leve = vrni_datum_trenutne() while premik_desno():

datum_trenutne = vrni_datum_trenutne() if datum_trenutne < datum_leve:

zamenjaj_trenutno_z_levo() else:

datum_leve = datum_trenutne

# Urejanje z desne proti levi

datum_desne = vrni_datum_trenutne() while premik_levo():

datum_trenutne = vrni_datum_trenutne() if datum_trenutne > datum_desne:

zamenjaj_trenutno_z_desno() urejene = True

else:

datum_desne = datum_trenutne

(44)

Algoritmiˇcno in didaktiˇcno ozadje. V tej nalogi ˇzelimo ponazoriti delovanje iskanja z mehurˇcki v tabeli. Prav tako pojasnimo, da nam urejeni podatki v tabeli olajˇsajo iskanje, kar se bo pokazalo v naslednjih nalogah. Na- loga od uˇcenca zahteva, da uredi elemente tabele. Pri tem ima na voljo le zamenjave sosednjih elementov s funkcijamazamenjaj_trenutno_z_levo()in zamenjaj_trenutno_z_desno(). Poleg tega je s funkcijamapremik_desno() inpremik_levo() omejen na premikanje po tabeli zaporedno.

Uˇcenec mora na podlagi omejitev in funkcij, ki so mu na voljo, nare- diti postopek za urejanje. Operaciji, ki sta mu na voljo, ga prisilita odkriti urejanje z mehurˇcki. Sprehaja se po tabeli in zamenjuje sosednji ˇskatli, ˇce sta v napaˇcnem vrstnem redu, dokler ˇskatle niso urejene od najstarejˇse do najnovejˇse.

4.3 Kako izuriti robota

Ali veˇs za tisti ˇstevilki, ki sta nam jo povedala zaposlena? Mislim, da gre v resnici za datuma. Tako so oznaˇcene ˇskatle spodaj v arhivu. O, ne . . . Spet se bo treba igrati s tistim robotom, da ju najdemo. Ali lahko to prepustim tebi?

• stevilo_skatel()vrne ˇstevilo ˇskatel v arhivu.

• hitro_preveri_ito(i, d, m, l)preveri ali je datumi-te zaporedne ˇskatle sestavljen iz dneva d, meseca m in leta l. Vrne razliko v dnevih med datumom i-te ˇskatle in podanim datumom.

Dodatni namig: Preveri vse ˇskatle. Tako zagotovo ne boˇs zgreˇsil prave.

Razlaga. Uporabimo ˇcim bolj preprost algoritem za iskanje, na primer linearno iskanje (angl. linear search). Pregledujemo ˇskatle od prve do zadnje, dokler ne pridemo do tiste, katere datum je enak iskanemu. Ker je preverjanje ujemanja datumov s funkcijo hitro_preveri_ito(i, d, m, l) relativno

(45)

hitro, smo s tem postopkom zadovoljni, ˇceprav je v obiˇcajnih okoliˇsˇcinah prepoˇcasen.

Primer reˇsitve:

d, m, l = 8, 11, 2015 # Podatek iz reˇsitve 1. naloge i = 0

while hitro_preveri_ito(i, d, m, l) != 0:

i += 1

print(vsebina(i))

Algoritmiˇcno in didaktiˇcno ozadje. S to nalogo ˇzelimo pokazati, da obstajajo enostavni algoritmi za iskanje elementov v tabeli – tudi zato, da kasneje vidimo, da ti algoritmi niso nujno dovolj hitri. Z enostavnimi algoritmi imamo v mislih tiste, ki so intuitivni in jih je preprosto implementirati.

Pri tem se ni potrebno ozirati na njihovo ˇcasovno in prostorsko zahtevnost in na dejstvo, da so ˇskatle urejene. Cilj naloge je prikazati, da je taka reˇsitev sprejemljiva, ker imamo relativno majhno ˇstevilo ˇskatel in relativno hitro funkcijo, s katero izvajamo poizvedbe. S tem namenom smo slednjo poime- novalihitro_preveri_ito.

Uˇcenec mora spoznati, da je vsak algoritem za iskanje po tabeli prime- ren, ˇce nimamo ˇcasovnih in prostorskih omejitev ter nimamo nujno urejenih elementov. Zato poiˇsˇce ˇcim bolj preprosto in enostavno reˇsitev na primer zaporedno oziroma linearno iskanje. Ne ozira se na dejstvo, da so ˇskatle urejene. Po vrsti od prve do zadnje preverja ˇskatle, dokler ne najde prave.

4.4 Sreˇ ca v nesreˇ ci

Hitremu robotu se je spraznila baterija . . . Ne moremo ˇcakati, da se napolni, zato si pri iskanju indeksa ˇskatle pomagaj s starejˇsim, poˇcasnejˇsim robotom.

Ta ˇskatla se nahaja v tistem delu skladiˇsˇca, ki si ga prej uredil.

(46)

• stevilo_skatel()vrne ˇstevilo ˇskatel v arhivu.

• preveri_ito(i, d, m, l) preveri ali je datum i-te zaporedne ˇskatle sestavljen iz dneva d, meseca m in leta —l—. Vrne razliko v dnevih med datumom i-te ˇskatle in podanim datumom.

Dodatni namig: Preverjanje datuma s tem robotom je poˇcasno. Poizkusi to funkcijo uporabiti ˇcim manjkrat. Mogoˇce lahko sedaj izkoristiˇs, da so ˇskatle urejene.

Razlaga. Sedaj iˇsˇcemo drug naˇcin iskanja, saj bi linearno iskanje trajalo predolgo. Izkoristimo dejstvo, da je seznam urejen. Najprej preverimo ˇskatlo na sredini. ˇCe se ujema z iskanim datumom, konˇcamo. ˇCe je njen datum ka- snejˇsi, nadaljujemo z iskanjem v levem delu seznama - iˇsˇcemo med ˇskatlami od zaˇcetne do trenutne (brez nje), v nasprotnem primeru pa v desnem. Po- stopek ponavljamo, dokler ne najdemo reˇsitve. ˇCe ˇskatel ne bi prej uredili, sedaj ne bi mogli uporabiti tega algoritma, ki mu pravimo bisekcija (angl.

bisection).

Primer reˇsitve:

d, m, l = 4, 4, 2018 # del resitve 1. naloge

levo = 0 # indeks prve ˇskatle na intervalu, ki nas zanima desno = stevilo_skatel() # indeks prve ˇskatle po intervalu while desno > levo:

sredina = (levo + desno) // 2

razlika = preveri_ito(sredina, d, m, l) if razlika == 0:

print(vsebina(sredina)) break

elif razlika < 0:

(47)

levo = sredina + 1 else:

desno = sredina

Algoritmiˇcno in didaktiˇcno ozadje. namen naloge je pokazati, da obstajajo hitrejˇsi naˇcini iskanja od zaporednega, linearnega iskanja. Pri iskanju minimiziramo ˇstevilo poizvedb, to je, dostopov do tabele. V tej nalogi uˇcenec izvaja poizvedbe s funkcijo preveri_ito. Da minimizira ˇstevilo klicev te funkcije in tako odkrije boljˇsi algoritem, ga prisilimo tako, da upoˇcasnimo to funkcijo: pri poˇcasnejˇsem robotu, o katerem govori naloga, klic funkcije traja dve sekundi, torej bi zaporedno iskanje trajalo predolgo.

Uˇcenec mora odkriti, da se mu splaˇca izkoristiti dejstvo, da so ˇskatle urejene. Odkriti mora torej iskanje z bisekcijo: najprej mora preveriti ˇskatlo na sredini. ˇCe se ujema z iskanim datumom, je iskanje konˇcano, sicer pa iskanje nadaljujemo na levi ali desni polovici seznama, glede na to, ali je datum na srednji ˇskatle prepozen ali preveˇc zgoden.

4.5 S kom se ne smemo hecati

Prebral sem dokumente, ki si jih naˇsel v ˇskatlah. Na prvi pogled niso niˇc drugaˇcni od ostalih, govorijo o srednje vrednih slikah. Zanimivo pa je, da za nobeno od njih ne poznamo zadnjega lastnika. To namiguje, da so bile ukradene in prodane na ˇcrnem trgu. Pred leti so imeli podoben primer, ko smo osumili najbolj znano mafijo umetnin pri nas, a nismo zbrali dovolj dokazov, da jih obsodimo. Sigurno si ˇze sliˇsal za njih . . . Prav oni so krivi za veˇc kot polovico vseh kraj slik po Evropi in Afriki. Malo prej sem izvedel, da je eden od naˇsih policistov pod krinko, Jane Romero, priˇsel do podatkov o ˇclanih in njihovih nadrejenih. Za zaˇcetek poskusimo ugotoviti vsaj, kdo je glavni. Spodaj vpiˇsi njegovo ime in priimek.

(48)

• grdo_poglej(ime_mafijca)vrne 3 imena - nadrejenega in oba podrejena zasliˇsanega mafijca. ˇCe kdo od omenjenih ne obstaja, na tistem mestu vrne None.

Dodatni namig: Razmisli, kako loˇciˇs ˇsefa od ostalih mafijcev.

Razlaga. Clani mafije so med sabo povezani v strukturo drevesa. Vsakˇ ima najveˇc dva podrejena, oziroma, vsako vozliˇsˇce ima najveˇc dva otroka - povezavi do podrejenih vozliˇsˇc. ˇSef je nadrejen vsem ostalim in edini, ki nima nadrejenega. V drevesu predstavlja koren. Poznamo neko vozliˇsˇce in funkcijo, ki vrne vozliˇsˇca povezana z njim. Od nakljuˇcnega vozliˇsˇca do korena pridemo s preverjanjem nadrejenih. ˇCe trenutni mafijec nima nadrejenega, smo naˇsli ˇsefa. V nasprotnem primeru nadaljujemo preverjanje z njegovim nadrejenim.

Primer reˇsitve:

mafijec = "Jane Romero"

while True:

nadrejeni, _, _ = grdo_poglej(mafijec) if nadrejeni != None:

mafijec = nadrejeni else:

break

print("ˇSef je", mafijec)

Algoritmiˇcno in didaktiˇcno ozadje. V tej nalogi ˇzelimo predstaviti strukturo drevesa, povezanega grafa, ki nima ciklov. Uˇcenec drevo prei- skuje s funkcijogrdo_poglej(ime_mafijca). Funkcija vraˇca sosede danega vozliˇsˇca. Ker v zaˇcetku pozna le en element, ga s tem ga prisili v preiskovanje elementov po povezavah navzgor.

(49)

Uˇcenec mora izkoristiti podatek, da so mafijci povezani v strukturo drevesa. Ugotoviti mora, da je od doloˇcenega mafijca lahko pride le do njegovih sosedov. To so natanko njegov nadrejeni in dva podrejena. Ugotoviti mora, da je ˇsef tista oseba, ki nima nadrejenega. Ko se uˇcenec tega zaveda, lahko od nakljuˇcnega mafijca pride do njega. Preveriti mora, ali ima dani mafijec nadrejenega. ˇCe ga ima, nadaljuje s preiskovanjem le-tega, sicer je naˇsel reˇsitev.

Naloga predstavlja tudi prvi program, v katerem se moramo sprehajati po drevesu. To je za zaˇcetnika namreˇc lahko kar zahtevno opravilo.

4.6 Zgovorni mafijci

Danes sem od kolega izvedel nekaj zelo zanimivega. Ta podatek se je ostalim zdel nepomemben, nam pa lahko zelo koristi. Vsak mafijec vedno proda le eno sliko, da ne postane sumljiv. Po tem zaupa prodajanje vseh slik, ki so cenejˇse od te slike, enemu od dveh podrejenih, prodajo vseh draˇzjih pa drugemu. ˇCe mafijca samo grdo pogledaˇs, ti bo izdal ime svojega nadrejenega in obeh podrejenih. ˇCe pa mu zagroziˇs z zaporom, ti takoj pove ˇse ime slike, ki jo je prodal sam, ter ime prve cenejˇse in prve draˇzje slike, ki ju je za tem moral zaupati podrejenim. Podatkov imamo veliko, dokazov pa praktiˇcno niˇc, zato jim ne moremo niˇc. Za vsako sliko lahko pogledamo v register in najdemo tudi oceno, koliko je vredna. Obratno pa ne gre, razen ˇce si pomagamo s podatki, ki nam jih dajo mafijci. Imaˇs dovolj podatkov, da bi lahko naˇsel imena desetih ukradenih slik, za katere poznamo le njihovo vrednost?

• grdo_poglej(ime_mafijca): glej nalogo 4.5.

• zagrozi_z_zaporom(ime_mafijca) vrne 3 imena slik - ime tiste, ki jo je prodal mafijec ter prve cenejˇse in prve draˇzje, ki sta ju prodala njegova podrejena. ˇCe kateri od njih ni prodal nobene slike, na tistem mestu vrne None.

• vrednost_slike(ime_slike)vrne vrednost slike s podanim imenom.

(50)

• vrednost(i)vrne vrednost slike, katere ime iˇsˇcemo, za i od 0 do 9.

Dodatni namig: Ali obstaja kakˇsna povezava med zaporedjem prodanih slik in hierarhijo mafijcev? Ugotovi, komu bo mafijec zaupal prodajo prve naslednje slike, ko bo eno sliko ˇze prodal.

Razlaga. Pri natanˇcnem branju opazimo, da se imena mafijcev in slik, ki jih dobimo pri klicu funkcij grdo_poglej(ime_mafijca) in

zagrozi_z_zaporom(ime_mafijca) z istim parametrom, ujemajo. Prvi podrejeni namreˇc proda ravno prvo cenejˇso sliko, drugi poskrbi za prodajo prve draˇzje. Sedaj vemo, kdo od mafijcev proda katero sliko, njeno vrednost pa lahko pridobimo s klicem funkcijevrednost_slike(ime_slike). V drevesni strukturi imajo vozliˇsˇca poleg imena mafijca lahko tudi ime prodane slike ter njeno vrednost. Ugotovimo, da imamo opravka z binarnim iskalnim drevesom: ˇce je vsakemu vozliˇsˇcu prirejena neka vrednost, je vrednost njegovega levega otroka (ˇce ta obstaja) vedno manjˇsa in vrednost desnega vedno veˇcja.

Iskanje v takem drevesu ni zahtevno. Zaˇcnemo v korenu, s ˇsefom. Pri- merjamo njegovo vrednost z iskano. ˇCe sta enaki, smo naˇsli reˇsitev. ˇCe je vrednost manjˇsa, nadaljujemo z iskanjem pri prvem podrejenem, sicer pri drugem. ˇCe pridemo do mafijca, ki ni prodal slike, iskana slika ne obstaja ali smo se zmotili pri postopku.

Primer reˇsitve:

def poisci_sliko(oseba, cena):

while oseba != None:

ime_trenutne, _, _ = zagrozi_z_zaporom(oseba) cena_trenutne = vrednost_slike(ime_trenutne) _, levi, desni = grdo_poglej(oseba)

if cena_trenutne == cena:

return ime_trenutne elif cena < cena_trenutne:

oseba = levi

(51)

else:

oseba = desni

return "slika ne obstaja / ni bila prodana"

sef = "Bart Roberts" # Podatek iz reˇsitve 5. naloge for i in range(10):

print(poisci_sliko(sef, vrednost(i)))

Algoritmiˇcno in didaktiˇcno ozadje. S to nalogo ˇzelimo pokazati, kako poteka iskanje v dvojiˇskem iskalnem drevesu. Vpeljemo novo drevo slik, ki se natanko ujema z nekim vpetim drevesom mafijcev iz prejˇsnje naloge. Namen naloge je najti iskani element z ustreznim pomikanjem po obeh drevesih hkrati. Funkcija zagrozi_z_zaporom(ime_mafijca)namreˇc vraˇca trenutni element ter podrejena elementa v drevesu slik, kot vhod pa zahteva vrednost ujemajoˇcega se elementa v drevesu mafijcev.

V tej nalogi mora uˇcenec najprej ugotoviti, da se povezave med slikami in mafijci ujemajo. Odkrije, da gre za urejeni dvojiˇski drevesi. Prvo cenejˇso prodana sliko doloˇcenega mafijca je prodal njegov prvi podrejeni, prvo draˇzjo sliko pa drugi. Nato mora za iskanje posamezne slike izkoristiti urejenost njihovih vrednosti. Zaˇceti mora s ˇsefom. Preveri vrednost njegove prodane slike. ˇCe se ujema z iskano, zakljuˇci. ˇCe je vrednost viˇsja od iskane, nadaljuje s preiskovanjem prvega podrejenega, sicer s preiskovanjem drugega.

4.7 Aˇ zurni podatki

Ravnokar smo dobili informacije o novih desetih krajah. Sedaj, ko poznamo delovanje mafijcev, lahko iz imena ukradenih slik ugotovimo, kdo bo sodeloval pri prodaji. Raziˇsˇci in si zapomni, kdo jih bo prodal. To nam bo zelo koristilo pri nadaljnjem raziskovanju.

(52)

• zagrozi_z_zaporom(ime_mafijca): glej nalogo 4.6.

• vrednost_slike(ime_slike): glej nalogo 4.6.

• shrani_sliko(ime_mafijca, ime_slike, cena_slike)zabeleˇzi, kdo od mafijcev bo prodal novo sliko. ˇCe kasneje pokliˇcemozagrozi_z_zaporom za tega mafijca, bo vrnila ime te slike. ˇCe si ˇzelimo zapomniti napaˇcnega prodajalca, funkcija vrneFalse, sicer vrne True.

• vrednost_in_ime(i) vrne par imena in vrednosti slike, ki jo ˇzelimo shraniti, za i od 0 do 9.

Dodatni namig: Premisli, kateremu mafijcu bo zaupana prodaja dane slike. Kdo jo bo komu predal?

Razlaga. V obstojeˇce drevo ˇzelimo dodati nova vozliˇsˇca – na novo ukradene slike. Vemo, da vsak mafijec proda le eno sliko, naslednje pa preda podrejenemu. ˇCe je slika cenejˇsa od njegove, jo preda prvemu podrejenemu, sicer drugemu. Tako bo prodaja zaupana prvemu mafijcu, ki ˇse ni prodal nobene. Najprej ˇzelimo poiskati tega mafijca. Uporabimo enak postopek, kot v prejˇsnji nalogi. Ko ga najdemo, s funkcijo shrani_sliko(ime_mafijca, ime_slike, cena_slike) k njemu shranimo ustrezno novo ukradeno sliko.

Ce vseh slik ne bomo ustrezno shranili, bomo imeli zaradi neposodobljenegaˇ drevesa teˇzave pri naslednjih nalogah.

Primer reˇsitve:

def komu_dodam(cena):

mafijec = "Bart Roberts" # resitev 5. naloge ime_slike, _, _ = zagrozi_z_zaporom(mafijec) cena_trenutne = vrednost_slike(ime_slike) while cena_trenutne != None:

_, ime_cenejse, ime_drazje = zagrozi_z_zaporom(mafijec) _, levi, desni = grdo_poglej(mafijec)

if cena < cena_trenutne:

cena_trenutne = vrednost_slike(ime_cenejse)

(53)

mafijec = levi else:

cena_trenutne = vrednost_slike(ime_drazje) mafijec = desni

return mafijec for i in range(10):

ime, vrednost = ime_in_vrednost(i)

shrani_sliko(komu_dodam(vrednost), ime, vrednost)

Algoritmiˇcno in didaktiˇcno ozadje. Namen naloge je prikazati dodajanje elementa v dvojiˇsko iskalno drevo. Uˇcenec mora poiskati ustrezno mesto v drevesu ter uporabiti funkcijo shrani_sliko(ime_mafijca,ime_slike, cena_slike). Slednja ustvari element in ga doda na mesto v drevesu slik, ki se ujema z mestom podanega elementa v drevesu mafijcev. To naredi samo v primeru, ko je mesto ustrezno. Uˇcenec bo posodobljeno drevo potreboval pri naslednjih nalogah. Zato je pred nadaljevanjem prisiljen k reˇsevanju te naloge.

Uˇcenec mora ugotoviti, da je postopek dodajanja v drevo podoben iskanju. Torej si lahko pomaga z reˇsitvijo prejˇsnje naloge. Zaˇcne, kot da bi poskuˇsal najti element z vrednostjo, ki ga mora dodati. Ustavi se, ko prviˇc pride do mafijca, ki ni prodal nobene slike. K njemu shrani dano sliko in njej pripadajoˇco vrednost.

4.8 Nenavadna delitev dela

Nekaj se mi zdi ˇcudno pri teh mafijcih. . . Nekateri si lepo porazdelijo delo, nekateri pa vedno prevzamejo delo sodelavcem. Primerjajmo, koliko slik proda vsak od mafijcev na doloˇcenem poloˇzaju. Kaj nam to pove o ukradenih slikah?

Zanima me, pri koliko prodajah omenjenih slik je posredoval vsak od mafijcev 3. reda (tistih, ki imajo nad seboj enega mafijca, nad katerim pa je samo

(54)

ˇse vrhovni ˇsef )? In pri koliko prodajah omenjenih slik je posredoval vsak od mafijcev 4. reda (tistih, ki so pod mafijci 3. reda)?

• ime(i) vrne ime slike, ki jo ˇzelimo preveriti, za i od 0 do 19.

Dodatni namig: Nariˇsi si strukturo mafijcev in oznaˇci mafijce 3. in 4.

reda. Kdaj boˇs pri iskanju dane slike naletel nanje?

Razlaga. Priˇcakujemo, da bo natanko eden od mafijcev doloˇcenega reda sodeloval pri prodaji posamezne slike. Mafijci namreˇc vedno zaupajo prodajo podrejenemu in nikoli sodelavcu istega reda. Lahko pa se zgodi, da je sliko prodal mafijec viˇsjega reda (na primer drugega) in nihˇce od mafijcev 3. reda ni sodeloval pri prodaji.

Najprej v slovar shranimo vse mafijce doloˇcenega reda in vrednost, ki bo predstavljala ˇstevilo posredovanj, inicializiramo na 0. Nato zaˇcnemo z iskanjem tistih, ki so prodali podane slike, vendar se ustavimo na tretjem oziroma ˇcetrtem nivoju in ustreznemu mafijcu, ki sodeluje pri prodaji slike priˇstejemo ena.

Primer reˇsitve:

def prodane_slike_reda(st_reda):

prodajalci = {}

for i in range(20):

cena = vrednost_slike(ime(i))

mafijec = "Bart Roberts" # resitev 5. naloge ime_slike, _, _ = zagrozi_z_zaporom(mafijec) cena_trenutne = vrednost_slike(ime_slike) for j in range(st_reda - 1):

(55)

_, ime_cenejse, ime_drazje = \ zagrozi_z_zaporom(mafijec)

_, levi, desni = grdo_poglej(mafijec) if cena == cena_trenutne:

break # slika ni priˇsla do te globine if cena > cena_trenutne:

cena_trenutne = vrednost_slike(ime_drazje) mafijec = levi

else:

cena_trenutne = vrednost_slike(ime_cenejse) mafijec = desni

else: # ˇce se zanka ni konˇcala z break if mafijec not in prodajalci:

prodajalci[mafijec] = 0 prodajalci[mafijec] += 1 return prodajalci

print(prodane_slike_reda(3)) print(prodane_slike_reda(4))

Algoritmiˇcno in didaktiˇcno ozadje. S to nalogo ˇzelimo pokazati, da drevo mafijcev ni uravnoteˇzeno. Bolj natanˇcno, levo poddrevo korena je iz- rojeno, desno poddrevo pa je skoraj uravnoteˇzeno. Podamo deset elementov levega in deset elementov desnega poddrevesa. Z primerjavo porazdeljeno- sti najdenih elementov na levi in desni strani pokaˇzemo razliko med urav- noteˇzenim in izrojenim drevesom. V naslednjih nalogah bo vidno, kako to vpliva na iskanje po drevesu. K neuravnoteˇzeni strukturi napeljuje tudi sam naslov naloge.

Uˇcenec iz porazdelitve najdenih slik v levem in desnem poddrevesu ugotovi, kakˇsna je struktura vsakega od poddreves. Pri iskanju danih slik si zapomni, kateri od mafijcev tretjega in ˇcetrtega reda so nad njimi v uje-

(56)

majoˇcem se drevesu mafijcev. Ugotovi, da je ˇstevilo najdenih elementov v desnem poddrevesu pribliˇzno enakomerno porazdeljeno, v levem poddrevesu pa zgoˇsˇceno na eno vejo.

4.9 Ali ima kdo privilegije?

Vidim, da si polovica mafijcev dokaj enakomerno razdeli prodajo, druga polovica pa vedno zaupa le enim in istim mafijcev. Da preverimo ali ima kdo privilegiran poloˇzaj, je potrebno pregledati vse prodane slike in ne le nekaj nakljuˇcnih. Prodajo koliko slik je ˇsef zaupal vsakemu od svojih dveh podrejenih?

Dodatni namig: Razdeli problem na manjˇse probleme enakega tipa. Tak postopek ponavljaj, dokler nisi sposoben reˇsiti podproblemov.

Razlaga. Pregledati moramo celotno drevo slik. Oblikujmo funkcijo, ki ji podamo mafijca in preˇsteje vse prodane slike njega in njegovih podrejenih.

Vhodni parameter je torej ime mafijca, izhod pa je ˇstevilo slik. Najprej se vpraˇsajmo ali dani mafijec sploh obstaja oziroma ali ni prodal nobene slike in v tem primeru vrnemo 0. V nasprotnem primeru vrnemo seˇstevek slik njegovega prvega in drugega podrejenega ter enice, ki predstavlja sliko trenutnega mafijca.