BEBRO konkurso užduotys 2018

 

Surask sklandytuvą

Taškai: 9

Jonė ir Kajus žaidžia lauke su sklandytuvo modeliu. Vaikai susitarė, kad Jonė paleis sklandytuvą nuo kalvos, o Kajus paims jį, kai sklandytuvas nusileis ant žolės. Tačiau žolė nešienauta ir nutūpusį lėktuvą galima matyti tik nuo kalvos. Vaikai sugalvojo signalinių ženklų kodus, kuriais Jonė ant kalvos parodo, kur nusileido lėktuvas:

Kairėn

Dešinėn

Link kalvos

Tolyn nuo kalvos

  

  

Deja, šis kodas turi trūkumą: kai komandos siunčiamos be pauzės, galima skirtingai suprasti tą pačią komandų seką. Pavyzdžiui, jei rodomos šios komandos:

tai gali reikšti: Kairėn, Link kalvos, Kairėn arba: Kairėn, Dešinėn, Kairėn, Kairėn.

Vaikai pabandė patikslinti savo kodą. Tik vienas iš jų sugalvotų kodų leidžia vienareikšmiškai suprasti komandų seką. Kuris?

 

Kairėn

Dešinėn

Link kalvos

Tolyn nuo kalvos

A.

B.

C.

D.

Paaiškinimas

Informacija, siunčiama tarp kompiuterių laidiniu ar bevieliu tinklu, naudoja greitas signalų sekas. Kiekvienas signalas turi dvi būsenas (įjungta arba išjungta), kaip ir vaikai naudoja du signalus (pakeltas arba nuleistas ženklas). Tik kompiuteriuose šis procesas vyksta sudėtingiau.

Būdas, kuriuo pranešimai arba komandos pakeičiamos į signalus, vadinamas (dvejetainiu) kodu. Šiuo atveju yra kintamo ilgio kodas, nes vienam pranešimui ar komandai naudojamų signalų skaičius yra nevienodas.

Svarbu, kad koduoto pranešimo gavėjas galėtų išversti signalus į pradinį pranešimą be klaidų. Kitaip tariant, reikia būti atsargiam, kuriant tokį kodą. Tinkamai sukurti kodai turi būti vienareikšmiškai iškoduojami.

Vienas iš tokių kodų yra prefiksinis kodas, kuris ypatingas tuo, kad jame nėra tokio žodžio, kuris visas būtų kito to paties kodo žodžio pradžia. Pavyzdžiui:

Kairėn

Dešinėn

Link kalvos

Tolyn nuo kalvos

  

  

Prefiksiniai kodai gali būti labai trumpi ir lengvai iškoduojami. Jie naudojami ne tik komunikacijoje, bet ir glaudinimo algoritmuose (bei įvairiose Bebro užduotyse).

Raktiniai žodžiai: kodas, kintamo ilgio kodas, prefiksinis kodas.

Atsakymas

Pirmiausia atmetami netinkami atsakymai.

Atsakymas B nepateikia gero kodo, nes seka Kairėn, Dešinėn išreiškiama taip pat, kaip komanda Link kalvos:

+

Atsakymas D nepateikia gero kodo, nes seka Kairėn, Link kalvos išreiškiama taip pat, kaip komanda Tolyn nuo kalvos.

+ =   

Sunkiau įžvelgti, kad atsakymas A nepateikia gero kodo. Čia komandų seka Kairėn, Link kalvos išreiškiame tokia pačia komandų seka, kaip ir Dešinėn, Dešinėn:

+  =  +

Kodėl atsakymas C yra teisingas? Kaip galima įsitikinti, kad nėra dviejų skirtingų signalų, išreiškiamų ta pačia seka? Pastebėkime, kad atsakymo C keturios komandos koduojamos skirtingu signalinio ženklo nuleidimų skaičiumi (nulis nuleidimų, vienas nuleidimas, du nuleidimai ir trys nuleidimai), einančių po vieno signalinio ženklo pakėlimo. Taigi kai tik Kajus pamato pakeltą signalinį ženklą, jis žino, kad pradedamas rodyti naujas kodas. Iškoduojant žinutę, jis turi suskaičiuoti nuleidimų skaičių tarp pakėlimų.

Interaktyvi užduotis

 

 
Informacija atnaujinta 2017-11-13 16:52:39