Keresés össze vissza

Ezen az órán a keresési algoritmusokkal foglalkoztunk. A feladat az, hogy megtanítsuk a gyerekeknek, hogy nagy mennyiségű adat között hogyan tudnak a számítógépek hatékonyan keresni.

A Tananyag szerint ilyenkor az “adatokat” a gyerekek szokták eljátszani, de mivel csak hatan voltak (színházba ment az egyik osztály), kicsit másképpen kezdtük. 9 matricás kártyát tettünk oly módon az asztalra, hogy a számok nem voltak láthatóak. A ragasztós állatos matricákat sokat használjuk az órákon. Jeleztük, hogy a rajtuk lévő számok 1 és 200 között vannak és próbálják megtalálni az általunk megadott számot. A jelentkező 4 cukorkát kapott és minden matrica felfordítás egy cukorkába került. A cukorkák elfogytak és nem lett meg a szám. A cukorkák ilyenkor a próbálkozásokat számolják. A keresési algoritmusok hatékonyságát a keresési próbálkozások számával szokták mérni.

Ilyenkor elbeszélgetünk arról, hogy mi a különbség a lineáris és a véletlenszerű keresés között, valamint, hogy ma legjobb és a legrosszabb eset a keresésnél.

Bináris keresés

Arra a kérdésre, hogy hogyan lehetne gyorsítani a keresést (hogy keresünk a számítógépen), valaki azt mondta, hogy mappákba rendezzük és valaki az ABC sorrendet is említette. Azt már mi mondtuk, hogy számokról van szó szám sorrendre lesz szükségünk. A bináris keresésnél ismét 9 kártyát tettünk először az asztalra sorrendben, mivel cukorka is maradt különösen értékelték. Kipróbáltuk később 15 kártyával is, megszámoltuk a minimum és maximum próbálkozásokat. Szerintem megértették. A bináris keresés lényege, hogy kiválasztunk egy tetszőleges matricát, majd mivel sorban vannak, ezért a balra vagy jobbra található összes kártya között már nem kell keresni. A maradék matricánál ugyanezt a módszert használjuk amíg már csak egy kártya marad.

Szótárazás

Ezt a módszert ezután egy szótárral is elpróbálják a gyerekek. Egy adott szót kell megkeresni egy angol-magyar szótárban úgy, hogy a bináris keresés módszerét használjuk.

A szótár kereséssel kicsit lassan haladtunk mivel már előbb megtalálták a szót, így nehezen vették rá magukat, hogy számolgassák az oldalakat (bár volt olyan csapat, aki ügyesebben haladt). El lehetne gondolkodni, hogy van-e valami jobb játék a szótárazás helyett.

Ezután megmutattuk a hash keresést is egy hagyományos telefonregiszter segítségével, ahol először betűk szerint keresünk, majd az adott oldalon már könnyű megtalálni a keresett nevet.

Mivel még maradt 5 perc a végén, a télapó büdös zoknija történet is sorra került (1024 csomag ajándékkal). Ez persze mindenkinek tetszett, részben ki is találták a megoldást.