Õpilastele näidatakse binaarotsingu ideed. Idee põhineb inimrobotite harjutusel.
| Looja | Mikko Muilu |
| Õppeaine | Matemaatika, arvutiteadus |
| Kestus | 45 minutit |
| Pedagoogiline lähenemine | Fenomenipõhine õpe Probleemipõhine õpe |
| Pädevus | Õpilased saavad teada, mida tähendab algoritm. Õpilased saavad teada, et teatud arvude leidmiseks on erinevaid viise ja mõned viisid on tunduvalt kiiremad kui teised. Õpilased õpivad lihtsaid algoritmi põhimõtteid. Õpilased õpivad programmeerimisega seotud if-lauset praktikas kasutama |
| Vanuserühm | Õpilased vanuses 9-12 aastat |
| Tarkvara ja materjalid | Pliiats ja paber |
Kirjeldus
Tegevus vajab paarisarv õpilasi. Nad on jagatud paarideks. Üks paaris olev isik leiab kokkulepitud vahemikust numbri. Teine inimene proovib arvu ära arvata, esitades küsimusi. Isik, kes valis numbri, saab neile küsimustele vastata ainult “jah” või “ei”. Kuidas on kiireim viis soovitud numbri leidmiseks?
Sissejuhatus
Õpilastele selgitatakse algoritmide põhimõtet (lisa 1) ja seda, kuidas algoritmid järgivad teatud juhiseid, et pakkuda alati lahendust olenemata neile antud andmetest. Õpilastele võib meelde tuletada inimroboti harjutust ja soovitada hoolikalt järgida antud juhiseid.
Ülesanne 1
Õpetaja jagab õpilased paaridesse. Esimene on otsija ja teine vastaja. Vastaja valib numbri vahemikus 1 kuni 50 ja kirjutab selle paberile. Kui need on tehtud, hakkab otsija küsimusi esitama ja vastaja saab vastata ainult “jah” või “ei”. Alguses võib keegi küsida üksikute numbrite kohta (“Kas see on kaks?”, “Kas see on kolm?”). Kui nad ei leia võimalust komplekti kitsendada, esitades selliseid küsimusi nagu “Kas see on suurem kui 10”, saab neid õiges suunas juhtida. Harjutuse ideed selgitatakse allolevas videos.
Arutelu: Mitu oletust kulus õige numbri leidmiseks? Milline taktika õpilastel oli? Kuidas muutuks erineva taktikaga arvamiste arv, kui arv oleks vahemikus 1 kuni 1000?
Õpetaja selgitab kahendotsingu põhimõtet: Kui otsinguvahemik on vahemikus 1 kuni 1000, on kõigepealt oluline uurida, kas arv on suurem kui 500 (otsingu keskel). Pärast seda jagatakse ülejäänud komplekt pooleks sarnase küsimusega ja jätkatakse seda seni, kuni soovitud arv on saavutatud.
https://youtu.be/vV7TR6_moug
Ülesanne 2
Alustame vahemikust 1 kuni 1 000. Õpilane harjutab kahendotsingut ja soovi korral saab proovida teist viisi numbri leidmiseks. Õpilased loevad kokku, mitu arvamist on õige arvu leidmiseks vaja. Mis juhtub, kui vahemik on 1 kuni 10 000? Aga ühest miljonini või ühest miljardini?
Arutelu:
Mida märkasid õpilased arvamiste arvu juures? Miks arvamiste arv väga kiiresti ei kasvanud? Mitu oletust oli vaja ühe kuni ühe miljoni vahelise arvu leidmiseks? Saate rääkida vanematele õpilastele astmefunktsioonist (2^x) ja sellest, kui kiiresti see kasvab. Iga otsing lõikab öeldud numbri pooleks, muutes soovitud numbri leidmise lihtsamaks. Teisisõnu, kui arv kahekordistub, on teil vaja ainult ühte küsimust. Allolev pilt selgitab kahe astendamist. Arv 2 korrutatakse iseendaga nii palju kordi, kui on märgitud eksponendis. Pilt selgitab ka edukaks binaarseks otsinguks vajalike oletuste arvu. Kui arvuvahemik on 128, on õige arvu leidmiseks vaja kuni seitset küsimust (2 korrutatuna endaga seitse korda võrdub 128-ga). Kahe aste näitab soovitud arvu leidmiseks vajalike küsimuste maksimaalset arvu
Ülesanne 3
Kui aega on, saavad õpilased ka praktikas proovida, kas varem tehtud väide on ka tegelikult mõttekas või mitte.
Lisa 1
Algoritmid on juhiste komplektid, mis võimaldavad soovitud tulemust saavutada. Põhimõtteliselt võivad need juhised olla mis tahes juhised, näiteks need, mida näeme kokaraamatutes. Tavaliselt viitame aga algoritmide arutamisel sageli matemaatilistele juhistele või juhistele, mis on mõeldud arvutile mõistmiseks. Binaarne otsing, mida me siin kasutame, on otsingualgoritm. Infotehnoloogias, aga ka näiteks reklaamide internetti kasutavatele inimestele suunamisel kasutatakse palju otsingu- ja järjestamisalgoritme.