Uzdevums

Izmēģini savus spēkus, atrisinot uzdevumu! Tieši šāda veida uzdevumi Tevi sagaida arī šī gada Bebr[a]s konkursā.

Divi bebri dzīvo abpus mežam. Viņi sazinās, izmantojot divu krāsu salūtu. Katra ziņa ir vārdu virkne un bebri ir izdomājuši kodus pieciem vārdiem:

Vārds Kods
Baļķis
Koks
Akmenis
Upe
Pārtika

Piemēram, lai nosūtītu ziņu “pārtika, baļķis, pārtika”, bebram jāšauj sekojošs salūts:

 Uzdevums: Cik atšķirīgu nozīmju var būt šai salūtu virknei?

Atbilžu varianti:

A: 1
B: 2
C: 3
D: 4

Sākumā izvēlies atbildi

Apsveicu ar pareizo atbildi! :)

Diemžēl atbilde nav pareiza :(

Atbilde

Pareizā atbilde: D (4).

Ziņojumam var būt jebkura no šīm nozīmēm:

1. Baļķis, Akmens, Pārtika, Upe.
2. Baļķis, Baļķis, Baļķis, Upe.
3. Akmens, Koks, Upe.
4. Akmens, Pārtika, Baļķis, Upe.

Lai pārliecinātos, ka vairāk iespēju nav, tās var sistemātiski saskaitīt:
- Sāc ar pirmo salūtu. Tas nav ziņojums, tāpēc to var uzskatīt par 0.
- Pirmie divi salūti var nozīmēt tikai "Baļķis". Tātad tos var uzskatīt par 1 variantu.
- Trešais salūts - tas var būt daļa no kāda īsāka jauna koda vai noslēgt vārdu “akmens”. 
- Ceturtais salūts ir interesants. Tas var pievienot vārdu “baļķis” pirmajiem diviem salūtiem vai arī vārdu “pārtika” pirmajiem trīs salūtiem. Tātad mēs varam saskaitīt divus skaitļus pie otrā un trešā salūta un pierakstīt tos pie ceturtā. 
- Tā mēs varam turpināt un izmantot šo pašu metodi, virzoties uz priekšu pa salūtu virkni. Vienmēr skatāmies vienu, divus un trīs salūtus atpakaļ. Ja šie īsākie ziņojumi var tikt pagarināti, veidojot vārdu, mēs to atzīmējam ar bultu. Pēc tam atliek tikai saskaitīt skaitļus, ko bultas “atved” uz salūtu, ko šajā brīdī apskatām.
- Pie pēdējā salūta mēs iegūsim sarakstu ar visiem iespējamajiem variantiem.

Sistemātiska pieeja, veidojot risinājumu soli pa solim un izmantojot iepriekšējos soļus, tiek saukta par dinamisko programmēšanu. Tā procesu padara daudz vienkāršāku - iedomājies, cik grūti būtu šo uzdevumu atrisināt, mēģinot uzreiz ieraudzīt visas iespējamās variācijas!

Kā tas ir saistīts ar informātiku?

Visa digitālā informācija tiek attēlota izmantojot bināro kodu. Tas nozīmē - tā sastāv tikai no bitiem: 0 un 1. Garākas kombinācijas no 0 un 1 (kā šajā uzdevumā - vārdi) ļauj tās interpretēt dažādos veidos. Tomēr mums ir svarīgi izvairīties no tā, ka ziņojumi var tikt pārprasti.

Vairums kodu izmanto vienādu daudzumu bitu katram vārdam, tāpēc katram ziņojumam var būt tikai viena nozīme. Tomēr daži vārdi tiek izmantoti ļoti bieži, bet citi - reti, tāpēc šāda veida kods rada nevajadzīgi garus ziņojumus.

Tāpēc ir lietderīgi, ja biežāk lietotiem vārdiem, piemēram, “Pārtika” tiek izmantots īsāks kods, bet retāk izmantotiem, piemēram, “Akmens” - garāks kods. Protams, lai izvairītos no pārpratumiem, ir jārīkojas gudrāk, nekā bebriem. Izmantojot priedēkļa kodu (prefix code), ziņojumiem būs tikai viena iespējamā interpretācija. Šo metodi (bieži lietotu datu apjoma saīsināšanu) lieto dati kompresijā.

Šāda veida uzdevumi tiek izmantoti starptautiskajā informātikas konkursā skolēniem Bebr[a]s.

Uzzini vairāk par konkursu Bebr[a]s