2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Pranešimai vėliavėlėmis

Taškai: 6

Vėliavų mieste bebrai bendrauja vėliavėlėmis. Sutarta, kad vėliavėlės turi dvi būsenas: horizontali ir vertikali.

1 būsena: horizontali
 
2 būsena: vertikali
 


Matome, kaip nuosekliai keičiant vėliavėlės būsenas gaunamos penkios skirtingos raidės: P, Q, R, S, T. .

 

P

Q

R

S

T

 

Bebrė Agota siunčia pranešimą:

Kurią raidžių seką išsiuntė Agota?

1. TSQ
2. RPQSR
3. RPSP
4. QPPTP

 

Paaiškinimas

Seniau vėliavėlės buvo naudojamos jūreivystėje pranešimams perduoti (vadinamoji semaforo komunikavimo sistema). Siunčiant tokius pranešimus naudojamas kodas turi būti vienareikšmis. Šiuo atveju kodas – tai sistema, kai vėliavėlių būsenų vienareikšmiais rinkiniais koduojama kiekviena raidė. Vienas vienareikšmio kodo kūrimo būdas – priešdėlių naudojimas. Tai reiškia, kad nei vienos raidės kodas negali būti bet kurios kitos raidės prefiksu (priešdėliu).
Šioje užduotyje raidžių kodai turi prefiksus, nes P raidės kodas yra S raidės kodo prefiksas, Q raidės kodas – raidžių R ir T prefiksas, R raidės kodas – T prefiksas.
Šioje užduotyje kodas yra daugiaprasmis ir pranešimas gali būti koduojamas įvairiai:
QPPQPPQP, QSSP, QPPTP, TSP, RPQSP, RPTP ir t. t. Tokiais atvejais pranešimai gali būti klaidingai suprantami.
Jei visų koduojamų objektų kodai vienodo ilgio, nelieka priešdėlių problemos.
Kodavimą ir dekodavimą nagrinėja informacijos teorija – viena iš informatikos sričių.

Atsakymas

4. QPPTP