2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Šifro „nulaužimas“

Taškai: 12

Prefikso šifre raidės yra koduojamos kintamo ilgio skaitmenų kodu. Keliamas reikalavimas, kad joks kodas neprasidėtų kitu kodu. Pavyzdžiui, jei raidė A yra koduojama 12, tai raidė B gali būti koduojama 2, nes 12 neprasideda 2, bet negali būti koduojama 121. Raidė C gali būti koduojama 11, nes abu kodai – 12 ir 2 – neprasideda 11, bet C negali būti koduojama nei 21 (nes 2 jau yra raidės B kodas), nei 121 (nes kodą 12 turi A).

Žvalgai gavo informaciją, kad perduotas skaitmeninis pranešimas reiškia žodį BEBRAS. Išsiaiškinkite, kaip koduojamos raidės, ir padarykite tarpus tarp skaitmenų taip, kad kiekviena seka, atskirta tarpais, būtų raidės kodas. Koduotas pranešimas yra toks:12112233321.

Paaiškinimas

Prefikso šifras šiame uždavinyje yra kintamo ilgio kodo pavyzdys, kuriame raidės yra paverčiamos kodais, turinčiais savybę, kad nė vienas iš jų neprasideda kitos raidės kodu. Ši prefikso kodų savybė užtikrina vienareikšmį pranešimo dekodavimą, nes nėra būtinybės naudoti tarpų  tarp kodų.

Su kintamo ilgio kodais yra susijusi informacijos suspaudimo problema, sprendžiama siekiant kuo trumpesnio perduodamo pranešimo. Šiuo tikslu gali būti naudojamas Hufmano kodavimo (David A. Huffman) algoritmas, pasižymintis duomenų nepraradimo ir suspaudimo savybėmis. Šio algoritmo rezultatas yra kintamo ilgio kodo lentelė, nurodanti, kaip optimaliai koduoti raides. Algoritmu įvertinamas pasikartojimų skaičius ir atitinkamai formuojami svoriai (pagal simbolių pasikartojimų skaičių).

https://en.wikipedia.org/wiki/Prefix_code

https://en.wikipedia.org/wiki/Huffman_coding

Raktiniai žodžiai: kriptografija, prefiksas, kodavimas.

Atsakymas

Teisingas atsakymas yra

1 21 1 22 33 321

Pradėkime nuo pradžių. Raidės B kodas negali būti didesnis negu 2 (121, 1211, 12112,...), nes raidė B turi pasikartoti, o tokių pasikartojimų nėra koduotame pranešime. Jei raidė B būtų koduojama 12, tada raidė E turėtų būti koduojama 1, o tai neatitinka reikalavimo, nes raidės B kodas prasidėtų E kodu. Taigi raidės B kodas turi būti 1.

Raidė E yra po B, todėl ji gali būti koduojama 2, 21 arba 211223332. E negali būti koduojama 2, nes tada gautume kodą BEBB. Ji negali būti 211223332, nes tada gautume žodį BEB. Taigi E kodas yra 21.

Kol kas žinome, kad 1_21_1 koduoja BEB, taigi belieka padėti tarpus tarp 2233321.

Kadangi raidė S yra žodžio pabaigoje, tai ji negali būti 1 arba 21, nes šiuos kodus naudoja B ir E. Taigi raidė S gali būti 321, 3321, 33321,233321 arba 2233321. S negali būti koduojama 2233321, nes tada gautume žodį BEBS. Ji taip pat negali būti 233321, nes tada liktų tik vienas skaitmuo raidėms R ir A koduoti. Kodas 33321 taip pat negalimas, nes liktų 22, o vienodi skaitmenys 2 ir 2 turėtų koduoti skirtingas raides R ir A. Jei S būtų 3321, tada raidės RA turėtų būti koduojamos 223. Tačiau R negali būti koduojama 22, o A negali būti 3, nes S prasideda 3. Taigi S kodas turi būti 321, o RA koduojama 2233. Panašiai nagrinėdami gauname, kad R kodas turi būti 22, o A kodas yra 33.

Interaktyvi užduotis