Przygotowanie do jednolitego egzaminu państwowego. Informacja i jej kodowanie

Ćwiczenia:

1) Do zakodowania liter A, B, C, D postanowiono użyć dwucyfrowych kolejnych liczb binarnych (od 00 do 11odpowiednio). Jeśli zakodujesz w ten sposób sekwencję symboli GBAV i zapiszesz wynikokazuje się, że w systemie szesnastkowym:
1) 132 16 2) D2 16 3) 3102 16 4) 2D 16

Rozwiązanie i odpowiedź:

Z warunku odpowiednio:
A - 00
B-01
B-10
G - 11
GBAB = 11010010 - przekonwertuj ten zapis binarny na system szesnastkowy i uzyskaj D2
Odpowiedź: 2

2) Do zakodowania liter A, B, C, D postanowiono zastosować dwucyfrowe kolejne liczby binarne (odpowiednio od 00 do 11). Jeśli zakodujesz w ten sposób ciąg znaków GBVA i zapiszesz wynik w kodzie szesnastkowym, otrzymasz:

1) 138 16 2) DBCA 16 3) D8 16 4) 3120 16

Rozwiązanie i odpowiedź:

Zgodnie z warunkiem:
A = 00
B = 01
B = 10
G = 11
Oznacza:
GBVA = 11011000 w formacie binarnym. Konwertuj na szesnastkowy i uzyskaj D8
Odpowiedź: 3

3) Dla 5 liter alfabetu łacińskiego określone są ich kody binarne (dla niektórych liter - z dwóch bitów, dla niektórych - z trzech). Kody te przedstawiono w tabeli:
a b c d e
000 110 01 001 10
Określ, który zestaw liter jest kodowany przez ciąg binarny 1100000100110
1) źle 2) źle 3) bacde 4) bacdb

Rozwiązanie i odpowiedź:

Pierwszą literą jest b, ponieważ kod binarny to 110
Druga litera to a, ponieważ kod binarny to 000
Trzecia litera to c, ponieważ kod binarny to 01
Czwarta litera to d, ponieważ kod binarny to 001
Piąta litera to e, ponieważ kod binarny to 10
Wynik: bacde, co odpowiada opcji nr 3.
Odpowiedź: 3

4) Do kodowania liter A, B, C, D stosuje się odpowiednio czterobitowe kolejne liczby binarne od 1000 do 1011. Jeśli zakodujesz w ten sposób ciąg znaków BGAV i zapiszesz wynik w kodzie ósemkowym, otrzymasz:
1) 175423 2) 115612 3) 62577 4) 12376

Rozwiązanie i odpowiedź:

Zgodnie z warunkiem:
A = 1000
B = 1001
B = 1010
G = 1011
BGAV = 1001101110001010, teraz musisz przekonwertować tę liczbę z binarnego na ósemkowy i uzyskać odpowiedź.
1001101110001010 2 = 115612 8

Odpowiedź: 2

5)

Do kodowania liter A, B, C, D stosuje się trzybitowe kolejne liczby binarne zaczynające się od 1 (odpowiednio od 100 do 111). Jeśli zakodujesz w ten sposób ciąg znaków CDAB i napiszesz wynik w kodzie szesnastkowym, otrzymasz:
1) A52 16 2) 4С8 16 3) 15D 16 4) DE5 16

Rozwiązanie i odpowiedź:

Według warunku: odpowiednio
A = 100
B=101
C=110
D=111
CDAB = 110111100101, zamień liczbę binarną na szesnastkową:
110111100101 2 = DE5 16
Odpowiedź: 4

6) Do kodowania liter K, L, M, N stosuje się odpowiednio czterobitowe kolejne liczby binarne od 1000 do 1011. Jeśli zakodujesz w ten sposób ciąg znaków KMLN i napiszesz wynik w kodzie ósemkowym, otrzymasz:
1) 84613 8 2) 105233 8 3) 12345 8 4) 776325 8

Rozwiązanie i odpowiedź:

Według warunku: odpowiednio
K = 1000
L = 1001
M = 1010
N=1011
KMLN = 1000101010011011, przelicz na liczbę ósemkową:

1000101010011011 2 = 105233 8

Odpowiedź: 2

7) Dla 5 liter alfabetu łacińskiego określone są ich kody binarne (dla niektórych liter - z dwóch bitów, dla niektórych - z trzech). Kody te przedstawiono w tabeli:

A b c d e
100 110 011 01 10
Określ, który zestaw liter jest zakodowany przez ciąg binarny 1000110110110, jeśli wiesz, że wszystkie litery w ciągu są różne:
1) cbade 2) acdeb 3) acbed 4) bacde

Rozwiązanie i odpowiedź:

Zapiszmy kod binarny w postaci bitów: Metodą brute-force możliwe opcje aby litery się nie powtarzały.
Okazuje się: 100 011 01 10 110
Stąd: Acdeb
Odpowiedź: 2

8) Dla 6 liter alfabetu łacińskiego określono ich kody binarne (dla niektórych liter dwa bity, dla niektórych trzy). Kody te przedstawiono w tabeli:
A B C D E F
00 100 10 011 11 101
Określ, który ciąg 6 liter jest kodowany przez ciąg binarny 011111000101100.
1) DEFBAC 2) ABDEFC 3) DECAFB 4) EFCABD

Rozwiązanie i odpowiedź:

Rozwiążmy metodą brute-force, ponieważ litery w odpowiedziach się nie powtarzają, co oznacza, że ​​kody nie powinny się powtarzać:

Otrzymujemy:
011 11 10 00 101 100
Odpowiednio: DECAFB
Odpowiedź: 3

9) Do kodowania liter A, B, C, D stosuje się czterobitowe kolejne liczby binarne zaczynające się od 1 (odpowiednio od 1001 do 1100). Jeśli zakodujesz w ten sposób ciąg znaków CADB i napiszesz wynik w kodzie szesnastkowym, otrzymasz:
1) AF52 16 2) 4CB8 16 3) F15D 16 4) V9SA 16

Rozwiązanie i odpowiedź: odpowiednio..
A-1001
B-1010
C-1011
D - 1100
Oznacza to: CADB = 1011100111001010, przekonwertujmy 1011100111001010 z postaci binarnej na szesnastkową:
1011 1001 1100 1010 2 = B9CA 16 , co odpowiada czwartej opcji.
Odpowiedź: 4

10)
A B C D
00 11 010 011
Jeśli zakodujesz w ten sposób ciąg znaków VGAGBV i zapiszesz wynik w kodzie szesnastkowym, otrzymasz:
1) CDADBC 16 2) A7C4 16 3) 412710 16 4) 4S7A 16

Rozwiązanie i odpowiedź:

VGAGBV = 0100110001111010, przelicz na szesnastkowy:
0100 1100 0111 1010 2 = 4C7A 16

Odpowiedź: 4

11) Do zakodowania wiadomości składającej się wyłącznie z liter A, B, C i D stosuje się kod binarny o nierównej długości:
A B C D
00 11 010 011
Jeśli zakodujesz w ten sposób ciąg znaków GAVBVG i napiszesz wynik w kodzie szesnastkowym, otrzymasz:
1) 62D3 16 2) 3D26 16 3) 31326 16 4) 62133 16

Rozwiązanie i odpowiedź:
GAVBVG = 0110001011010011 2 - Konwertuj na system szesnastkowy:
0110 0010 1101 0011 2 = 62D3 16

Odpowiedź: 1

12) Aby zakodować wiadomość składającą się wyłącznie z liter A, B, C i D, o nierównej długości

kod binarny:
A B C D
00 11 010 011
Jeśli zakodujesz w ten sposób sekwencję znaków GBVAVG i wynik zapiszesz w formacie szesnastkowym

kod, okaże się:
1) 71013 16 2) DBCACD 16 3) 31A7 16 4) 7A13 16

Rozwiązanie i odpowiedź:
GBVAVG = 0111101000010011 2 - konwertuj na format szesnastkowy.
0111 1010 0001 0011 2 = 7A13 16
Odpowiedź: 4

13) Do zakodowania wiadomości składającej się wyłącznie z liter A, B, C i D stosuje się kod binarny o nierównej długości:
A B C D
00 11 010 011
Jeśli zakodujesz w ten sposób ciąg znaków GAVBGV i napiszesz wynik w kodzie szesnastkowym, otrzymasz:
1) DACBDC 16 2) AD26 16 3) 621310 16 4) 62DA 16
Rozwiązanie i odpowiedź: odpowiednio..

GAVBGV = 0110001011011010 2 , przekonwertuj na postać szesnastkową:
0110 0010 1101 1010 2 = 62DA 16
Odpowiedź: 4

14) Aby zakodować wiadomość składającą się wyłącznie z liter A, B, C, D i E, stosuje się kod binarny o różnej długości:
A B C D E
000 11 01 001 10
Który (tylko jeden!) z czterech odebranych komunikatów został przesłany bez błędów i można go odszyfrować:
1) 110000010011110
2) 110000011011110
3) 110001001001110
4) 110000001011110

Rozwiązanie i odpowiedź:

Weźmy pierwszy kod:
11 000 001 001 11 10 = BADDBE
Drugi kod:
11 000 001 10 11 110 = z błędem na końcu.
Trzeci kod:
11 000 10 01 001 110 = z błędem na końcu.
Czwarty kod:
11 000 000 10 11 110 = z błędem na końcu.
Odpowiedź: 1

15)

kodowanie: A-00, B-11, B-010, G-011. Komunikat: VAGBGV jest przesyłany kanałem komunikacyjnym. Zakoduj wiadomość

z tym kodem. Konwertuj wynikową sekwencję binarną na postać szesnastkową.
1) AD34 2) 43DA 3) 101334 4) CADBCD
Rozwiązanie i odpowiedź:

VAGBGV = 0100001111011010 2 , zamień na szesnastkowy:
0100 0011 1101 1010 2 = 43DA 16
Odpowiedź: 2

16) Do przesłania komunikatu kanałem komunikacyjnym składającym się wyłącznie z liter A, B, C, D zdecydowano się zastosować kod o nierównej długości: A=1, B=01, B=001. Jak należy zakodować literę G, aby długość kodu była minimalna, a zakodowany komunikat można było jednoznacznie podzielić na litery?
1) 0001 2) 000 3) 11 4) 101
Rozwiązanie i odpowiedź:
Aby wiadomość została odszyfrowana wymagane jest, aby żaden kod nie był początkiem innego, dłuższego kodu.

Opcje 1, 3 i 4 nie są odpowiednie, są początkiem innych kodów.
Opcja 2 nie jest początkiem innych kodów.
Odpowiedź: 2

17) Do przesłania komunikatu kanałem komunikacyjnym składającym się wyłącznie z liter A, B, C, D zdecydowano się zastosować kod o nieparzystej długości: A=0, B=100, C=101. Jak należy zakodować literę G, aby długość kodu była minimalna, a zakodowany komunikat można było jednoznacznie podzielić na litery?

1) 1 2) 11 3) 01 4) 010

Podobnie jak w zadaniu numer 16.

Odpowiedź: 2

18) Czarno-biały obraz rastrowy kodowane linia po linii, zaczynając od lewego górnego rogu i kończąc w prawym dolnym rogu. Podczas kodowania 1 oznacza kolor czarny, a 0 oznacza kolor biały.

Dla zwartości wynik zapisano w systemie liczb ósemkowych. Wybierz poprawny wpis kodu.
1) 57414 2) 53414 3) 53412 4) 53012

Rozwiązanie i odpowiedź:
Po zakodowaniu otrzymujemy taki kod:

101011100001010 2 , przekonwertuj ten kod na ósemkowy:
101 011 100 001 010 2 = 53412 8

Odpowiedź: 3

19) Aby przesłać wiadomość kanałem komunikacyjnym składającym się wyłącznie ze znaków A, B, C i D, znak po znaku

kodowanie: A-0, B-11, B-100, G-011. Komunikat przekazywany jest kanałem komunikacyjnym: GBAVAVG. Zakoduj wiadomość

z tym kodem. Konwertuj wynikową sekwencję binarną na kod ósemkowy.
1) DBACACD 2) 75043 3) 7A23 4) 3304043
Rozwiązanie i odpowiedź: Odpowiednio:
GBAVAVG = 0111101000100011 2 , przekonwertuj na system ósemkowy.
0 111 101 000 100 011 2 = 75043 8, pierwsze zero nie jest znaczące.
Odpowiedź: 2

20) Do przesyłania danych kanałem komunikacyjnym używany jest kod 5-bitowy. Wiadomość zawiera tylko

litery A, B i C, które są zakodowane następującymi słowami kodowymi:

A - 11010, B - 00110, C - 10101.

Podczas transmisji mogą wystąpić zakłócenia. Możesz jednak spróbować poprawić niektóre błędy. Dowolne dwa z tych trzech słów kodowych różnią się od siebie co najmniej w trzech pozycjach. Dlatego też, jeśli podczas przesyłania słowa wystąpił błąd w co najwyżej jednej pozycji, można zgadnąć, która litera została przesłana. (Mówią, że „kod koryguje jeden błąd.”) Na przykład, jeśli odebrane zostanie słowo kodowe 10110, uważa się, że przesłana została litera B (różnica od słowa kodowego dla B jest tylko w jednym miejscu; w przypadku innych słów kodowych tam jest więcej różnic.) Jeśli otrzymano Jeśli słowo kodowe różni się od słów kodowych liter A, B, C na więcej niż jednej pozycji, uważa się, że wystąpił błąd (jest to oznaczone przez „x”).

Otrzymano wiadomość 00111 11110 11000 10111. Odszyfruj tę wiadomość - wybierz właściwą opcję.

1) BAAx
2) BAAW
3)xxx
4) xAAx

Rozwiązanie:
1) 00111 = B, ponieważ w ostatniej cyfrze jest 1 błąd.
2) 11110 = A, ponieważ w trzeciej cyfrze jest 1 błąd.
3) 11000 = A, ponieważ w czwartej cyfrze jest 1 błąd.
4) 10111 = B, ponieważ w czwartej cyfrze jest 1 błąd

00111 11110 11000 10111 = BAAW.
Odpowiedź: 2

Na podstawie: opcje demonstracyjne Jednolity egzamin państwowy z informatyki na rok 2015, http://wiki.vspu.ru/

Aby zakodować pewną sekwencję składającą się z liter A, B, C, D i D, stosuje się niejednolity kod binarny, który umożliwia jednoznaczne zdekodowanie powstałej sekwencji binarnej. Oto kod: A - 0; B - 100; B - 1010; G - 111; D - 110. Należy skrócić długość słowa kodowego dla jednej z liter, tak aby kod nadal mógł być jednoznacznie zdekodowany. Kody pozostałych liter nie powinny się zmieniać. Jak można to zrobić?

Aby zrozumieć, czego się od nas wymaga, przyjrzyjmy się każdemu słowu w tym zadaniu. Kodowanie, sekwencja to słowa znane i dobrze rozumiane przez nas wszystkich i doskonale rozumiemy, co one oznaczają. A teraz, po wyliczeniu liter, mamy do czynienia z wyrażeniem NIENAWIDZONY kod binarny, który nie jest znany każdemu. Nierównomierne kodowanie binarne to kodowanie, w którym znaki określonego alfabetu podstawowego są kodowane poprzez kombinacje znaków alfabetu binarnego (tj. 0 i 1), a długość kodów i, w związku z tym, czas transmisji pojedynczego kodu mogą różnić się. Ta idea kodowania binarnego jest podstawą Kodeksu Huffmana, w którym znak, który występuje najczęściej w sekwencji, otrzymuje bardzo mały kod, a znak, który pojawia się najrzadziej, przeciwnie, otrzymuje bardzo długi kod, zmniejszając w ten sposób ilość informacji.

Załóżmy, że mamy ciąg „tor here ter”, dla którego w obecnej formie na każdy znak przypada jeden bajt. Oznacza to, że cały ciąg zajmuje 11*8 = 88 bitów pamięci. Po zakodowaniu ciąg zajmie 27 bitów.

Aby otrzymać kod dla każdego znaku ciągu „tor here ter” w oparciu o jego częstotliwość, musimy zbudować drzewo (wykres) tak, aby każdy liść tego drzewa zawierał znak. Drzewo będzie zbudowane od liści do korzenia, w tym sensie, że postacie o niższej częstotliwości będą dalej od korzenia niż postacie o wyższej częstotliwości.

Do budowy drzewa wykorzystamy nieco zmodyfikowaną kolejkę priorytetów - w pierwszej kolejności zostaną z niej usunięte elementy o najniższym priorytecie, a nie najwyższym. Jest to konieczne, aby zbudować drzewo od liści po korzenie.

Obliczmy więc częstotliwość występowania symboli T R spacja O U E

Po obliczeniu częstotliwości utworzymy dla każdego znaku węzły drzewa binarnego i dodamy je do kolejki, stosując jako priorytet częstotliwość:

Teraz pobieramy dwa pierwsze elementy z kolejki i łączymy je, tworząc nowy węzeł drzewa, w którym obaj będą dziećmi, a priorytet nowego węzła będzie równy sumie ich priorytetów. Następnie dodamy powstały nowy węzeł z powrotem do kolejki.

Powtarzamy te same kroki i na koniec otrzymujemy:

Po połączeniu gałęzi w jedno drzewo, Ty i ja otrzymamy następujące kody dla naszych symboli

T - 00; R - 10; spacja -01; O - 1110; U - 110; E - 1111 możesz przeczytać bardziej szczegółowo

Zadanie 1 egzaminu Unified State Exam:

Aby zakodować pewną sekwencję składającą się z liter A, B, C, D i D, stosuje się niejednolity kod binarny, który umożliwia jednoznaczne zdekodowanie powstałej sekwencji binarnej. Oto kod: A - 0; B - 100; B - 1010; G - 111; D - 110. Należy skrócić długość słowa kodowego dla jednej z liter, tak aby kod nadal mógł być jednoznacznie zdekodowany. Kody pozostałych liter nie powinny się zmieniać. Jak można to zrobić?

nie mniej niż cztery i nie więcej niż pięć sygnały (kropki i kreski)?

Rozwiązanie.

Mamy alfabet składający się z dwóch liter: kropki i myślnika. Z dwóch liter możesz ułożyć 2 4 słowa czteroliterowe i 2 5 słów pięcioliterowych.

Odpowiednio liczba zakodowanych znaków będzie równa liczbie różnych słów i będzie 16 + 32 = 48.

Odpowiedź: 48

Źródło: Wersja demonstracyjna egzaminu Unified State Exam 2013 z informatyki.

Alfabet Morse'a umożliwia kodowanie znaków do komunikacji radiowej poprzez określenie kombinacji kropek i myślników. Ile różnych znaków (cyfr, liter, znaków interpunkcyjnych itp.) można zakodować przy użyciu alfabetu Morse’a nie mniej niż trzy i nie więcej niż cztery sygnały (kropki i kreski)?

Rozwiązanie.

W tym zadaniu możemy użyć nie mniej niż 3 i nie więcej niż 4 sygnałów, co oznacza, że ​​liczba różnych symboli wynosi N = 2 4 +2 3 = 24.

Prawidłowa odpowiedź: 24.

Odpowiedź: 24

Alfabet Morse'a umożliwia kodowanie znaków do komunikacji radiowej poprzez określenie kombinacji kropek i myślników. Ile różnych znaków (cyfr, liter, znaków interpunkcyjnych itp.) można zakodować przy użyciu alfabetu Morse'a o długości co najmniej dwóch i maksymalnie czterech sygnałów (kropek i kresek)?

Rozwiązanie.

Informacja uzyskana z jednego znaku alfabetu Morse'a jest równa jednemu bitowi, ponieważ są tylko dwa znaki. Jeśli są dwa znaki, to w celu obliczenia liczby możliwe kombinacje z tych symboli na n pozycjach, musisz podnieść 2 do potęgi n.

W tym zadaniu możemy użyć nie mniej niż 2 i nie więcej niż 4 sygnałów, co oznacza, że ​​liczba różnych symboli wynosi N = 2 4 + 2 3 + 2 2 = 28.

Prawidłowa odpowiedź: 28.

Odpowiedź: 28

Alfabet Morse'a umożliwia kodowanie znaków do komunikacji radiowej poprzez określenie kombinacji kropek i myślników. Ile różnych znaków (cyfr, liter, znaków interpunkcyjnych itp.) można zakodować przy użyciu alfabetu Morse'a o długości co najmniej dwóch i maksymalnie pięciu sygnałów (kropek i kresek)?

Rozwiązanie.

M=2 (kropka i myślnik), „co najmniej dwa i nie więcej niż pięć sygnałów” oznacza, że ​​należy określić liczbę wszystkich słów 5, 4, 3 i 2-literowych w alfabecie binarnym.

Odpowiedź: 60

Alfabet Morse'a umożliwia kodowanie znaków do komunikacji radiowej poprzez określenie kombinacji kropek i myślników. Ile różnych znaków (cyfr, liter, znaków interpunkcyjnych itp.) można zakodować przy użyciu alfabetu Morse'a składającego się z nie więcej niż pięciu sygnałów (kropek i kresek)?

Rozwiązanie.

Używając dwóch symboli alfabetu (kropki i myślnika) możesz utworzyć 2 5 słów pięcioliterowych, 2 4 słowa czteroliterowe, 2 3 słowa trzyliterowe, 2 2 słowa dwuliterowe i 2 1 pojedyncze symbole. Zatem liczba zakodowanych znaków wynosi 32 + 16 + 8 + 4 + 2 = 62.

Odpowiedź: 62

Alfabet Morse'a umożliwia kodowanie znaków do komunikacji radiowej poprzez określenie kombinacji kropek i myślników. Ile różnych znaków (cyfr, liter, znaków interpunkcyjnych itp.) można zakodować przy użyciu alfabetu Morse'a o długości czterech lub pięciu sygnałów (kropek i kresek)?

Rozwiązanie.

Zatem istnieje 2 4 = 16 czteroliterowych symboli słów i 2 5 = 32 pięcioliterowych symboli słów. W sumie można zakodować 48 wiadomości.

Odpowiedź: 48

Alfabet Morse'a umożliwia kodowanie znaków do komunikacji radiowej poprzez określenie kombinacji kropek i myślników. Ile różnych znaków (cyfr, liter, znaków interpunkcyjnych itp.) można zakodować przy użyciu alfabetu Morse’a nie mniej niż trzy i nie więcej niż pięć sygnały (kropki i kreski)?

Rozwiązanie.

Jeżeli w alfabecie występują symbole, to liczba wszystkich możliwych „słów” (wiadomości) o długości jest równa .

Musimy określić liczbę wszystkich trzy-, cztero- i pięcioliterowych słów w alfabecie binarnym:

Duplikuje zadanie 4988.

Odpowiedź: 56

Alfabet Morse'a umożliwia kodowanie znaków do komunikacji radiowej poprzez określenie kombinacji kropek i myślników. Ile różnych znaków (cyfr, liter, znaków interpunkcyjnych itp.) można zakodować przy użyciu alfabetu Morse’a nie mniej niż trzy i nie więcej niż 5 sygnały (kropki i kreski)?

Rozwiązanie.

Jeżeli w alfabecie występują symbole, to liczba wszystkich możliwych „słów” (wiadomości) o długości jest równa .

Musimy określić liczbę wszystkich pięcio-, cztero- i trzyliterowych słów w alfabecie binarnym:

Odpowiedź: 56

Alfabet Morse'a umożliwia kodowanie znaków do komunikacji radiowej poprzez określenie kombinacji kropek i myślników. Ile różnych znaków (cyfr, liter, znaków interpunkcyjnych itp.) można zakodować przy użyciu alfabetu Morse’a pięć Lub sześć sygnały (kropki i kreski)?

Rozwiązanie.

Jeśli w alfabecie znajdują się symbole, liczba wszystkich możliwych „słów” (wiadomości) o długości jest równa

W w tym przypadku M = 2 (kropka i myślnik), „pięć lub sześć sygnałów” oznacza, że ​​musisz określić liczbę wszystkich pięcio- i sześcioliterowych słów w alfabecie binarnym:

2 5 +2 6 = 32 + 64 = 96.

Odpowiedź: 96

Alfabet Morse'a umożliwia kodowanie znaków do komunikacji radiowej poprzez określenie kombinacji kropek i myślników. Ile różnych znaków (cyfr, liter, znaków interpunkcyjnych itp.) można zakodować przy użyciu alfabetu Morse'a o długości co najmniej czterech i maksymalnie sześciu sygnałów (kropek i kresek)?

Rozwiązanie.

Jeśli w alfabecie znajdują się symbole, liczba wszystkich możliwych „słów” (wiadomości) o długości jest równa

W tym przypadku M = 2 (kropka i myślnik), „co najmniej cztery i nie więcej niż sześć” oznacza, że ​​musisz określić liczbę wszystkich cztero, pięcio i sześcioliterowych słów w alfabecie binarnym:

2 4 + 2 5 + 2 6 = 16 + 32 + 64 = 112.

Odpowiedź: 112.

Odpowiedź: 112

Ile jest różnych sekwencji symboli plusa i minusa o długości dokładnie pięciu znaków?

Rozwiązanie.

Jeżeli w alfabecie występują symbole, to liczba wszystkich możliwych „słów” (wiadomości) o długości jest równa .

Przygotowanie do jednolitego egzaminu państwowego.

Informacja i jej kodowanie. Analiza zadań A9, A11.

Dzień dobry, studenci!

Zapraszam na lekcję online dotyczącą przygotowania do Unified State Exam z informatyki. Struktura lekcji jest logiczna i spójna. W oparciu o podstawowe pojęcia i formuły tematu lekcji zaczynamy analizować rozwiązywanie problemów, a następnie samodzielnie wykonujemy zadania standardowe i niestandardowe. Każda lekcja będzie zawierać zbędne informacje, które mogą nie zostać wykorzystane wprost w bieżącej lekcji, ale są ważne dla kolejnych.

Scenariusz pracy:

1. Opierać. Wprowadzenie podstawowych pojęć i formuł

2. Za ząb. Przekrój. Materiał zalecany jest do automatycznego, bezbłędnego odtwarzania w środku nocy.

3. Z teorii. Dodatkowy materiał z pokrewnych tematów z innych dyscyplin w ramach lekcji.

4. Zrób to sam. Zadania do przećwiczenia materiału z punktów 1 – 3.

5. Analiza zadań. Uporządkujmy to różne sposoby rozwiązywanie zadań z ujednoliconego egzaminu państwowego z demonstracyjnych maszyn współrzędnościowych z ubiegłych lat i prawdziwych egzaminów zunifikowanego stanu. Wyciąganie mikrowniosków (sekcja przekrojowa Uwaga!).

Podstawowe pojęcia:

ü Fragment (Dwójkowy cyfra) to jednostka miary ilości informacji równa ilości informacji zawartej w doświadczeniu, które ma dwa równie prawdopodobne wyniki.

ü Informacja- są to informacje o obiektach i zjawiskach otoczenia, ich właściwościach, zmniejszające niepewność i/lub niekompletność wiedzy.

ü Kodowanie informacji to proces jednoznacznego przekształcania informacji z jednego języka na inny. Niedwuznaczny proces, który oznacza posiadanie reguły/systemu reguł przekształcania informacji z powrotem do jej pierwotnej postaci. Dwuznaczny proces nie pozwalający na powrót do pierwotnej formy informacji, zniekształcając ją.

ü Dekodowanie informacji- Jest to proces przekształcania informacji odwrotnie do kodowania.

ü Jednolite kodowanie to kodowanie, w którym wszystkie znaki są kodowane kodami o tej samej długości.

ü Nierówne kodowanie to kodowanie, w którym różne znaki mogą być kodowane za pomocą kodów o różnej długości.

ü Alfabet to zbiór różnych znaków używanych do pisania wiadomości.

ü Głębokość kodowania kolorów to liczba bitów wymaganych do przechowywania i reprezentowania koloru podczas kodowania jednego piksela grafiki rastrowej.

Podstawowe formuły:

ü N = 2 I, Gdzie Nto liczba różnych znaków w alfabecie, Ito minimalna ilość informacji (bitów) wymagana do zakodowania jednego znaku alfabetu.

ü I = K · I, Gdzie I- jest to objętość informacji wiadomości w bitach (bajtach, KB...), K- jest to liczba znaków w wiadomości(dla wiadomości tekstowej K jest liczbą wszystkich znaków w wiadomości; np obraz graficzny: K to liczba pikseli w obrazie rastrowym; Dla plik dźwiękowy: we wzorze znajdują się dodatkowe czynniki, więcej szczegółów w innych lekcjach ), I- jest to liczba bitów potrzebnych do zakodowania jednego znaku(w terminologii graficznego kodowania informacji i jest głębokością kodowania kolorem).

Przy zębie:

Uwaga:! (Nota Bene, z łaciny „uważaj”)

1 bajt = 23 bity

1 KB = 210 bajtów = 213 bitów

1 MB = 210 KB = 220 bajtów = 223 bity

1 GB = 210 MB = 220 KB = 230 bajtów = 233 bity

Podobnie jak tabliczka mnożenia, musisz znać wartości potęg liczby 2. Uwaga: ponieważ na egzaminie z informatyki nie można korzystać z kalkulatora, uczymy się obliczać wyrażenia z potęgami liczby 2 bez uciekania się do skomplikowanych obliczeń z długimi liczbami.

Ćwiczenia. Obliczmy, ile bitów zawiera :

Rozwiązanie.

Pierwsza metoda (kategorycznie trudna):

https://pandia.ru/text/78/122/images/image003_19.png" szerokość="589" wysokość="184 src=">

W drugim sposobie rozwiązania dodajemy i odejmujemy jedynie wartości potęg liczby 2. Pamiętaj o podstawowych wzorach na przeliczanie potęg, które przydadzą się przy rozwiązywaniu wielu zadań Unified State Examination.

Z algebry:

https://pandia.ru/text/78/122/images/image005_15.png" szerokość="91 wysokość=41" wysokość="41">? W swojej odpowiedzi wskaż potęgę 2.

2) Ile MB mieści się w 4096 bajtach? W swojej odpowiedzi wskaż potęgę liczby 2.

Analiza zadań A9.

Poziom podstawowy.

Maksymalny wynik - 1.

Co sprawdza zadanie: Proces przekazywania informacji, źródło i odbiorca informacji. Sygnał, kodowanie i dekodowanie. Zniekształcenie informacji.

Ćwiczenia . KIM dla ujednoliconego egzaminu państwowego-2012.

Do zakodowania pewnego ciągu składającego się z liter A, B, C, D i D postanowiliśmy zastosować niejednorodny kod binarny, który pozwala jednoznacznie zdekodować ciąg binarny pojawiający się po stronie odbiorczej kanału komunikacyjnego. Stosowany kod: A-1, B-000, B-001, G-011. Proszę wskazać jakie słowo kodowe litera D musi być zakodowana. Długość tego słowa kodowego musi być możliwie najkrótsza. Kod musi spełniać właściwość jednoznacznego dekodowania.

Rozwiązanie .

1. Kod znaku jest nierówny. Ale dekodowanie wiadomości musi być jednoznaczne.

2. Sprawdźmy metodą brute-force, która z zaproponowanych opcji kodu dla symbolu D zostanie jednoznacznie zdekodowana.

· D - 00. Wtedy np. komunikat TAK (kod można rozszyfrować jako symbol B (kod 001). NIEPRAWIDŁOWY.

· D - 01. Wtedy np. komunikat TAK (kod można rozszyfrować jako symbol g (kod 011). NIEPRAWIDŁOWY.

· D - 11. Wtedy np. komunikat TAK (kod można zdekodować jako AAA (kod 1) lub AD (kod 1 i 11) NIEPOPRAWNY.

ü D-010. Jedyna prawdziwa opcja. Dowolny ciąg znaków przypisany przed lub po symbolu D zostanie jednoznacznie zdekodowany.

Uwaga:! Dekodując nierówny kod, należy wziąć pod uwagę wszystkie możliwe opcje.

Ćwiczenia . Źródło KIMi dla ujednoliconego egzaminu państwowego-2011.

Do przesłania komunikatu kanałem komunikacyjnym składającym się wyłącznie ze znaków A, B, C i D stosuje się nierówny (długość) kod: A-01, B-1, C-001. Jakim słowem kodowym należy zakodować symbol D, aby jego długość była minimalna, a kod umożliwiał jednoznaczny podział zakodowanego komunikatu na symbole.

Rozwiązanie .

1. Kod znaku jest nierówny. Ale dekodowanie wiadomości musi być jednoznaczne. W przeciwieństwie do poprzedniego zadania, jest tu warunek - długość kodu musi być minimum. Dlatego wypróbowując opcje, nie zatrzymuj się na pierwszym kodzie, który prowadzi do jednoznacznego dekodowania. Inny kod może spełniać ten sam warunek i być krótszy.

2. Przeanalizujmy opcje kodu dla symbolu D i wybierzmy tę, w której wiadomość zostanie jednoznacznie zdekodowana, a długość kodu będzie wynosić minimum.

· Oczywiście kod znaku musi zaczynać się od 0, in W przeciwnym razie wiadomość zostanie odszyfrowana niejednoznacznie. Załóżmy na przykład D-101. Wtedy wiadomość o jednym symbolu D (101) może zostać zdekodowana jako wiadomość VAI lub niech D-11. Wtedy wiadomość o jednym symbolu D (11) może zostać zdekodowana jako wiadomość BB

· Kod znaku musi zaczynać się od 0, aby umożliwić jednoznaczne zdekodowanie jakiejkolwiek wiadomości. Z dwóch opcji wybierz kod o krótszej długości.

ü D - 000.

3. Użyliśmy Stan Fano. Jego sformułowanie: aby wiadomość napisana kodem o nierównej długości mogła zostać jednoznacznie odszyfrowana, wymagane jest, aby żaden kod nie był początkiem innego (dłuższego) kodu.

Uwaga:! Rozwiązując problemy, zwracaj uwagę na wszystkie warunki zadania. W tym zadaniu istnieje ryzyko, że analiza zostanie przeprowadzona błędnie, dlatego zaleca się przejrzenie wszystkich opcji w celu ponownego sprawdzenia wybranego rozwiązania.

Ćwiczenia . Źródło KIMi dla ujednoliconego egzaminu państwowego-2011.

Do przesłania komunikatu kanałem komunikacyjnym składającym się wyłącznie ze znaków A, B, C i D stosuje się nierówny (długość) kod: A-00, B-11, B-010, G-011. Kanałem komunikacyjnym przesyłany jest komunikat: GBVAVG. Zakoduj wiadomość za pomocą tego kodu. Konwertuj wynikową sekwencję binarną na szesnastkowy system liczbowy. Jak będzie wyglądać ta wiadomość?

Rozwiązanie .

1. W przeciwieństwie do dwóch poprzednich zadań, tutaj musisz zastosować wiedzę na temat konwersji liczb z systemu binarnego na szesnastkowy (w przypadek ogólny do systemu liczbowego o podstawie będącej wielokrotnością potęgi 2 (czyli do systemu liczbowego o podstawie q=2n, gdzie n jest liczbą naturalną)).

2. Zamiast symboli wiadomości zapisz ich kody. Otrzymujemy binarny kod wiadomości:

GBVAVG: . Wyobraźmy sobie kod binarny w 16. alfabecie SS.

Pierwsza metoda konwersji z 2ss na system liczbowy o podstawie 2 N (nieporównywalnie wygodne):

Alfabet systemu liczbowego o podstawie 2n (są to symbole od 0 do 2n-1) powiązany jest z unikalnym kodem binarnym o długości n znaków.

Przy zębie:

2. metoda konwersja z 2ss na bazę 2n (uciążliwa i ryzykowna):

Etap 1. Konwersja kodu binarnego na 10 ss (przy użyciu rozszerzony wzór na zapis liczby):

Przy zębie:

DIV_ADBLOCK154">

4. Prawidłowa odpowiedź 3.

Zrób to sam.

Do zakodowania liter A, B, C, D, D, E postanowiliśmy zastosować następujący kod: A - 101, B - 1, C - 10, D - 110, D - 001, E - 0. Jeśli zakoduj w ten sposób ciąg znaków AEEGDBE i zapisz wynik w systemie ósemkowym, otrzymasz:

3) Do przesłania komunikatu kanałem komunikacyjnym składającym się wyłącznie z liter A, B, C, D zdecydowano się zastosować kod o nierównej długości: A=0, B=10, C=110. Jak należy zakodować literę G, aby długość kodu była minimalna, a zakodowany komunikat można było jednoznacznie podzielić na litery?

4) Do zakodowania wiadomości składającej się wyłącznie z liter A, B, C, D i E stosuje się kod binarny o różnej długości:

Który (tylko jeden!) z czterech odebranych komunikatów został przesłany bez błędów i można go odszyfrować:

5) Czarno-biały obraz rastrowy jest kodowany linia po linii, zaczynając od lewego górnego rogu i kończąc w prawym dolnym rogu. Podczas kodowania 1 oznacza kolor czarny, a 0 oznacza kolor biały.

Dla zwartości wynik zapisano w systemie liczb ósemkowych. Wybierz poprawny wpis kodu.

Proszę opisać sposób rozwiązania tego zadania. Materiał zawarty w tej lekcji jest wystarczający, aby ją ukończyć. Testujemy, jak nie można odtworzyć rozwiązania, ale znaleźć je w nowej sytuacji.

Analiza zadań A11.

Podwyższony poziom.

Maksymalny wynik - 1.

Co sprawdza zadanie: Dyskretna (cyfrowa) reprezentacja informacji tekstowych, graficznych, audio i wideo. Jednostki miary ilości informacji.

Ćwiczenia . KIM dla ujednoliconego egzaminu państwowego-2012.

Aby zarejestrować się na stronie internetowej określonego kraju, użytkownik musi utworzyć hasło. Długość hasła wynosi dokładnie 11 znaków. Używane znaki to cyfry dziesiętne i 12 różnych liter lokalnego alfabetu, a wszystkie litery są używane w dwóch stylach: zarówno małych, jak i wielkich (wielkość liter ma znaczenie!).

Do przechowywania każdego takiego hasła na komputerze przydzielana jest minimalna możliwa i identyczna liczba całkowita bajtów, przy czym stosowane jest kodowanie znak po znaku, a wszystkie znaki są kodowane przy użyciu tej samej i minimalnej możliwej liczby bitów.

Określ ilość pamięci wymaganą do przechowywania 60 haseł.

Rozwiązanie .

Opracowujemy rozwiązanie problemu od końca.

If to ilość informacji w przeszukiwanym pliku.

IF = I1 hasło× K, gdzie hasło I1 to ilość informacji wymagana do przechowywania 1 hasła, K to liczba haseł (60).

I1 hasło = I × L, i - liczba bitów do zakodowania jednego znaku hasła, L - długość hasła (11).

I = dziennik2 N, gdzie N to liczba różnych znaków, które można zastosować w haśle (tzn. alfabetu).

Wykonajmy wszystkie operacje od dołu do góry, biorąc pod uwagę warunki zadania:

1. N = 10 + 12 + 12 = 34 znaki (10 cyfr, 12 małych i 12 wielkich liter)

2. i = log2N lub N = 2i
i = log234 lub 34 = 2i
5 bitów< i < 6 бит
i = 6 bitów.
Spełniamy warunek zadania: stosowane jest kodowanie znak po znaku i wszystkie znaki są kodowane z taką samą i minimalną możliwą liczbą bitów.

3. Hasło I1 = 6 bitów × 11 = 66 bitów.
Przejdźmy do warunku problemowego: do przechowywania każdego takiego hasła na komputerze przydzielana jest minimalna możliwa i identyczna liczba całkowita bajtów. Zaokrąglij 66 bitów do całkowitej liczby bajtów.
Następnie I1 hasła = 72 bity = 9 bajtów.

4. Iph = 9 bajtów × 60 = 540 bajtów.

Uwaga! W tym zadaniu liczba znaków w alfabecie nie jest wielokrotnością potęgi 2 i uciekamy się do zaokrąglania w górę do całkowitej liczby bitów.

Ćwiczenia . Prace diagnostyczne w informatyce od MIOO. 29 listopada 2010.

Program generuje N-znakowe hasła w następujący sposób: jako znaki używane są cyfry oraz małe i wielkie litery łacińskie w dowolnej kolejności (w alfabecie łacińskim jest 26 znaków). Wszystkie znaki są kodowane przy użyciu tej samej minimalnej możliwej liczby bitów i zapisywane na dysku. Program wygenerował 128 haseł i zapisał je w pliku z rzędu, bez dodatkowych znaków. Rozmiar powstałego pliku wynosił 1,5 KB.

Jaka jest długość hasła (N)?

Rozwiązanie .

Uwaga! To i poprzednie zadanie różnią się tym, że wymagana wartość poprzedniego zadania jest podaną wartością bieżącego zadania i odwrotnie.

1. M to liczba znaków, które można wykorzystać do utworzenia hasła.
M = 10 + 26 + 26 = 56 znaków (10 cyfr, 26 małych i wielkich liter).
Przejdźmy do sformułowania problemu: Wszystkie znaki są kodowane przy użyciu tej samej minimalnej możliwej liczby bitów i zapisywane na dysku.
i = log2M lub M = 2i
i = log256 lub 56 = 2i, 7 bitów< i < 8 бит
Ponieważ „Wszystkie znaki są kodowane przy użyciu tej samej minimalnej możliwej liczby bitów”, wówczas i = 8 bitów.

2. Iф = I1 hasło×K, gdzie Iф to objętość informacji wymaganego pliku (1,5 KB), I1 hasło to objętość informacji wymagana do przechowywania 1 hasła, K to liczba haseł (128).
I1 hasła = i × N, i to liczba bitów potrzebnych do zakodowania jednego znaku hasła, N to długość hasła (nieznana).
Iф = ja × N × K
N=

Uwaga! Zwróć uwagę na wygodę obliczeń w potęgach 2. Ćwicz tę umiejętność stale. Na początku wykładu miałeś 2 zadania na ten temat.
Jestem pewien, że zauważyłeś ważne sformułowanie w zadaniu: „Program wygenerował 128 haseł i zapisał je do pliku po kolei, bez dodatkowych znaków”. Jeżeli zostałaby określona liczba dodatkowych znaków pomiędzy hasłami używanymi podczas nagrywania, należałoby to wziąć pod uwagę. Ważne jest, aby dokładnie zapoznać się z warunkami zlecenia.

Zrób to sam.

6) W kolarstwie przełajowym uczestniczy 987 sportowców. Specjalne urządzenie rejestruje przebieg mety pośredniej przez każdego uczestnika, zapisując jego liczbę przy użyciu minimalnej możliwej liczby bitów, jednakowej dla każdego zawodnika. Jaka jest objętość informacyjna komunikatu zarejestrowanego przez urządzenie po ukończeniu mety pośredniej przez 60 kolarzy?

7) W niektórych krajach 7-znakowa tablica rejestracyjna składa się z wielkich liter (używa się tylko 22 różnych liter) i cyfr dziesiętnych w dowolnej kolejności. Każdy taki numer w program komputerowy jest zapisywany z minimalną możliwą i tą samą całkowitą liczbą bajtów (w tym przypadku stosowane jest kodowanie znak po znaku i wszystkie znaki są kodowane z tą samą i minimalną możliwą liczbą bitów). Określ ilość pamięci przydzielonej przez ten program do zapisania 50 liczb.

8) Każda komórka pola 8x8 jest kodowana przy użyciu minimalnej możliwej i tej samej liczby bitów. Rozwiązanie problemu rycerza przechodzącego przez pole zapisuje się jako ciąg kodów odwiedzanych komórek. Jaka jest ilość informacji po wykonaniu 11 ruchów? (Zapis rozwiązania rozpoczyna się od początkowej pozycji rycerza).

Sprawdziliśmy pierwszą lekcję z 14. Zaczynamy zbierać mozaikę zadań i wiedzy z egzaminu Unified State Exam ze wszystkich kursów informatyki i matematyki.

Następna lekcja poświęcona będzie kontynuacji nauki tematu i analizie zadań B1, B4, B10. Jednak wstępna analiza zadań, które otrzymałeś na tej lekcji, będzie obowiązkowa. Wykonując zadania, pamiętaj o zastosowaniu rozwiązań. Postępuj zgodnie z formatem rozwiązania, który przedstawiłem w skrypcie lekcji.

Ten, kto idzie, opanuje drogę.

Z poważaniem, Ekaterina Vadimovna.