Uvod
- O učbeniku
Predstavitev informacij
Tehnologije znanja
Objektno usmerjeno programiranje

Licenca

To delo je na voljo pod pogoji slovenske licence Creative Commons 2.5:

priznanje avtorstva - nekomercialno - deljenje pod enakimi pogoji.

Celotna licenca je na voljo na spletu na naslovu http://creativecommons.org/licenses/by-nc-sa/2.5/si/. V skladu s to licenco je dovoljeno vsakemu uporabniku delo razmnoževati, distribuirati, javno priobčevati, dajati v najem in tudi predelovati, vendar samo v nekomercialne namene in ob pogoju, da navede avtorja oziroma avtorje in izdajatelja tega dela. Če uporabnik delo predela, kar pomeni, da ga spremeni, preoblikuje, prevede ali uporabi to delo v svojem delu, lahko predelavo dela ponudi na voljo le pod pogoji, ki so enaki pogojem iz te licence oziroma pod enako licenco.

Rešitev

Niz »znanost«, predstavljen s pomočjo standarda ASCII: $$ \underbrace{0111\ 1010}_{z} \ \underbrace{0110\ 1110}_{n} \ \underbrace{0110\ 0001}_{a} \ \underbrace{0110\ 1110}_{n} \ \underbrace{0110\ 1111}_{o} \ \underbrace{0111\ 0011}_{s} \ \underbrace{0111\ 0100}_{t} \ $$
Niz »Ljubljana«, predstavljen s pomočjo standarda ASCII: $$ \underbrace{0100\ 1100}_{L} \ \underbrace{0110\ 1010}_{j} \ \underbrace{0111\ 0101}_{u} \ \underbrace{0110\ 0010}_{b} \ \underbrace{0110\ 1100}_{l} \ \underbrace{0110\ 1010}_{j} \ \underbrace{0110\ 0001}_{a} \ \underbrace{0110\ 1110}_{n} \ \underbrace{0110\ 0001}_{a} \ $$
Niz »358«, predstavljen s pomočjo standarda ASCII: $$ \underbrace{0011\ 0011}_{3} \ \underbrace{0011\ 0101}_{5} \ \underbrace{0011\ 1000}_{8} \ $$ Če bi »358« predstavili kot dvojiško številko $1\ 0110\ 0110$, bi potrebovali 9 bitov, namesto gornje predstavitve, kjer »358« predstavimo kot besedilo in za to potrebujemo 3 × 8 bitov = 24 bitov.
Niz »Zdravo, kako si?«, predstavljen s pomočjo standarda ASCII: $$ \underbrace{0101\ 1010}_{Z} \ \underbrace{0110\ 0100}_{d} \ \underbrace{0111\ 0010}_{r} \ \underbrace{0110\ 0001}_{a} \ \underbrace{0111\ 0110}_{v} \ \underbrace{0110\ 1111}_{o} \ \underbrace{0010\ 1100}_{,} \ \underbrace{0010\ 0000}_{\text{presledek}} \\ \underbrace{0110\ 1011}_{k} \ \underbrace{0110\ 0001}_{a} \ \underbrace{0110\ 1011}_{k} \ \underbrace{0110\ 1111}_{o} \ \underbrace{0010\ 0000}_{\text{presledek}} \ \underbrace{0111\ 0011}_{s} \ \underbrace{0110\ 1001}_{i} \ \underbrace{0011\ 1111}_{?} \ $$

Rešitev

Največje število, ki ga lahko predstavimo z uporabo 32 bitov, je 4.294.967.295 (okrog 4,3 milijarde). To je največje nepredznačeno celo število, ki ga lahko 32-bitni računalnik preprosto predstavi v programskih jezikih, kot je na primer programski jezik C.
Desetiška vednost dvojiškega števila $00000000\ 00010000\ 11111111\ 11111111$ je 1.114.111.
Vse trenutne znake Unicode lahko predstavimo s 17 biti. Največje število, ki ga lahko predstavimo s 16 biti, je 65.536, kar pa ni dovolj. Če uporabimo 17 bitov, bo največje število 131.072, kar je več kot 120.000. Zato za predstavitev vseh trenutnih znakov Unicode potrebujemo 17 bitov.

Rešitev

Niz »banana«, predstavljen s pomočjo standarda ASCII, zavzame 6 × 8 bitov, kar je skupaj 48 bitov. Z predstavitev vsake črke potrebujemo 8 bitov oziroma 1 bajt: $$ \underbrace{0110\ 0010}_{b} \ \underbrace{0110\ 0001}_{a} \ \underbrace{0110\ 1110}_{n} \ \underbrace{0110\ 0001}_{a} \ \underbrace{0110\ 1110}_{n} \ \underbrace{0110\ 0001}_{a} \ $$

Niz »banana« stisnemo s postopkom Huffmanovega kodiranja tako, da posamezne črke predstavimo z manj kot 8 biti. S pomočjo Huffmanovega drevesa lahko ustvarimo naslednje krajše kode:

a = 0
b = 10
n = 11

Z uporabo teh kod, lahko besedilo »banana« predstavimo z 9 biti: $$ \underbrace{10}_{b} \ \underbrace{0}_{a} \ \underbrace{11}_{n} \ \underbrace{0}_{a} \ \underbrace{11}_{n} \ \underbrace{0}_{a} \ $$

Rešitev

Ker vemo, da Huffmanova koda $01001101011010100100110$ vsebuje naslednje znake: $d(1)$, $k(1)$, $b(2)$, $r(2)$ in $a(5)$, lahko ustvarimo Huffmanovo drevo, na primer:

Paziti moramo v toliko, da bo morda potrebno izdelati več Huffmanovih dreves, saj lahko zamenjamo mesti $d(1)$ in $k(1)$ oziroma $b(2)$ in $r(2)$ ter tako dobimo različne krajše kode črk.

Recimo, da sledimo Huffmanovemu drevesu in dobimo naslednje krajše kode črk:

a = 0
r = 11
b = 100
d = 1010
k = 1011

Skrivno besedo odkrijemo tako, da Huffmanovo kodo $01001101011010100100110$ razbijemo na krajše kode črk: $$ \underbrace{0}_{a} \ \underbrace{100}_{b} \ \underbrace{11}_{r} \ \underbrace{0}_{a} \ \underbrace{1011}_{k} \ \underbrace{0}_{a} \ \underbrace{1010}_{d} \ \underbrace{0}_{a} \ \underbrace{100}_{b} \ \underbrace{11}_{r} \ \underbrace{0}_{a} \ $$ Skrivna beseda je torej »abrakadabra«.

Rešitev

Ker vemo, da Huffmanova koda $11100010011010111000$ vsebuje naslednje znake: $j(1)$, $n(1)$, $d(2)$, $p(2)$ in $e(3)$, lahko ustvarimo Huffmanovo drevo, na primer:

Paziti moramo v toliko, da bo morda potrebno izdelati več Huffmanovih dreves, saj lahko zamenjamo mesti $j(1)$ in $n(1)$ oziroma $d(2)$ in $p(2)$ ter tako dobimo različne krajše kode črk.

Recimo, da sledimo Huffmanovemu drevesu in dobimo naslednje krajše kode črk:

d = 00
e = 10
p = 11
j = 010
n = 011

Skrivno besedo odkrijemo tako, da Huffmanovo kodo $11100010011010111000$ razbijemo na krajše kode črk: $$ \underbrace{11}_{p} \ \underbrace{10}_{e} \ \underbrace{00}_{d} \ \underbrace{10}_{e} \ \underbrace{011}_{n} \ \underbrace{010}_{j} \ \underbrace{11}_{p} \ \underbrace{10}_{e} \ \underbrace{00}_{d} \ $$ Skrivna beseda je torej »pedenjped«.

Naloge

S pomočjo standarda ASCII:

Predstavi niz »znanost«.
Predstavi niz »Ljubljana« (ne pozabi, da se ta niz začne z veliko začetnico »L«).
Predstavi niz »358« (ne pozabi, da gre za tri znake, čeprav izgledajo kot številka).
Predstavi niz »Zdravo, kako si?« (v ASCII tabeli poišči kode za vejico, presledek in vprašaj).

Koliko je pravzaprav 32 bitov?

Katero je največje število, ki ga lahko predstavimo z 32 biti? Odgovor naj bo v desetiški in v dvojiški obliki.
Največje število, ki predstavlja določen znak Unicode, je število $00000000\ 00010000\ 11111111\ 11111111$ in ni največje možno 32-bitno število. Kakšna je destiška vrednost tega števila?
Kolikšno bi bilo najmanjše število bitov, ki bi jih potrebovali za predstavitev poljubnega znaka Unicode, glede na to, da trenutno obstaja približno 120.000 znakov Unicode?

Koliko bitov potrebujemo za predstavitev besede »banana« v nestisnjeni obliki in koliko bitov, če to besedo stisnemo s Huffmanovim kodiranjem?

Pomagaj si s Huffmanovim drevesom.

Huffmanova koda $01001101011010100100110$ vsebuje naslednje znake: $d(1)$, $k(1)$, $b(2)$, $r(2)$ in $a(5)$. S pomočjo znanja o Huffmanovem kodiranju odkrij skrivno besedo.

Huffmanova koda $11100010011010111000$ vsebuje naslednje znake: $j(1)$, $n(1)$, $d(2)$, $p(2)$ in $e(3)$. S pomočjo znanja o Huffmanovem kodiranju odkrij skrivno besedo.