Задание 10. Кодирование информации

Задание 10. Кодирование информации

За­да­ние 10 № 000. Аз­бу­ка Морзе поз­во­ля­ет ко­ди­ро­вать сим­во­лы для со­об­ще­ний по ра­дио­свя­зи, за­да­вая ком­би­на­цию точек и тире. Сколь­ко раз­лич­ных сим­во­лов (цифр, букв, зна­ков пунк­ту­а­ции и т. д.) можно за­ко­ди­ро­вать, ис­поль­зуя код аз­бу­ки Морзе дли­ной не менее четырёх и не более пяти сиг­на­лов (точек и тире)?

По­яс­не­ние.

Мы имеем ал­фа­вит из двух букв: точка и тире. Из двух букв можно со­ста­вить 24 четырёхбук­вен­ных слова и 25 пя­ти­бук­вен­ных слов.

Со­от­вет­ствен­но, ко­ли­че­ство за­ко­ди­ро­ван­ных сим­во­лов будет равно ко­ли­че­ству раз­лич­ных слов, а их 16 + 32 = 48.  Ответ 48

За­да­ние 10 № 000. Алек­сей со­став­ля­ет таб­ли­цу ко­до­вых слов для пе­ре­да­чи со­об­ще­ний, каж­до­му со­об­ще­нию со­от­вет­ству­ет своё ко­до­вое слово. В ка­че­стве ко­до­вых слов Алек­сей ис­поль­зу­ет 5-бук­вен­ные слова, в ко­то­рых есть толь­ко буквы A, B, C, X, причём буква X может по­явить­ся на пер­вом месте или не по­явить­ся вовсе. Сколь­ко раз­лич­ных ко­до­вых слов может ис­поль­зо­вать Алек­сей?

По­яс­не­ние.

На пер­вой по­зи­ции в слове могут быть все че­ты­ре буквы А, В, С и Х, а со вто­рой по пятую — 3. Зна­чит всего можно со­ста­вить 4 · 3 · 3 · 3 · 3 = 324 слова.  Ответ: 324.

За­да­ние 10 № 000. Игорь со­став­ля­ет таб­ли­цу ко­до­вых слов для пе­ре­да­чи со­об­ще­ний, каж­до­му со­об­ще­нию со­от­вет­ству­ет своё ко­до­вое слово. В ка­че­стве ко­до­вых слов Игорь ис­поль­зу­ет 5-бук­вен­ные слова, в ко­то­рых есть толь­ко буквы A, B, C, X, причём буква X по­яв­ля­ет­ся ровно 1 раз. Каж­дая из дру­гих до­пу­сти­мых букв может встре­чать­ся в ко­до­вом слове любое ко­ли­че­ство раз или не встре­чать­ся со­всем. Сколь­ко раз­лич­ных ко­до­вых слов может ис­поль­зо­вать Игорь?

По­яс­не­ние.

Пусть Х стоит в слове на пер­вом месте. Тогда на каж­дое из остав­ших­ся 4 мест можно по­ста­вить не­за­ви­си­мо одну из 3 букв. То есть всего 3 · 3 · 3 · 3 = 81 ва­ри­ант.

Таким об­ра­зом Х можно по оче­ре­ди по­ста­вить на все 5 мест, в каж­дом слу­чае по­лу­чая 81 ва­ри­ант.

Итого по­лу­ча­ет­ся 81 · 5 = 405 слов. Ответ: 405.

За­да­ние 10 № 000. Шах­мат­ная доска со­сто­ит 8 столб­цов и 8 строк. Какое ми­ни­маль­ное ко­ли­че­ство бит по­тре­бу­ет­ся для ко­ди­ро­ва­ния ко­ор­ди­нат од­но­го шах­мат­но­го поля?

По­яс­не­ние.

Если в ал­фа­ви­те сим­во­лов, то ко­ли­че­ство всех воз­мож­ных «слов» (со­об­ще­ний) дли­ной равно .

Всего кле­ток . В ал­фа­ви­те 2 сим­во­ла(так как «бит»), то есть . Оста­лось найти ., сле­до­ва­тель­но, .  Ответ 6.

За­да­ние 10 № 000. Какое ми­ни­маль­ное ко­ли­че­ство бит по­тре­бу­ет­ся для ко­ди­ро­ва­ния по­ло­жи­тель­ных чисел, мень­ших 60?

По­яс­не­ние.

Если в ал­фа­ви­те сим­во­лов, то ко­ли­че­ство всех воз­мож­ных «слов» (со­об­ще­ний) дли­ной равно . По­ло­жи­тель­ных чисел, мень­ших 60, 59 штук . В ал­фа­ви­те 2 сим­во­ла (так как «бит»), то есть Оста­лось найти . Сде­ла­ем это под­бо­ром. При , , при , .  Ответ 6.

За­да­ние 10 № 000. Двое иг­ра­ют в «кре­сти­ки-но­ли­ки» на поле 4 на 4 клет­ки. Какое ко­ли­че­ство ин­фор­ма­ции (в битах) по­лу­чил вто­рой игрок, узнав ход пер­во­го иг­ро­ка?

По­яс­не­ние.

Если в ал­фа­ви­те сим­во­лов, то ко­ли­че­ство всех воз­мож­ных «слов» (со­об­ще­ний) дли­ной равно

В дан­ном слу­чае, ко­ли­че­ство воз­мож­ных ва­ри­ан­тов сде­лать пер­вый ход равно 16 ().

, где N — ко­ли­че­ство бит. Ответ 4.

За­да­ние 10 № 000. В кор­зи­не лежат 8 чер­ных шаров и 24 белых. Сколь­ко бит ин­фор­ма­ции несет со­об­ще­ние о том, что до­ста­ли чер­ный шар?

По­яс­не­ние. Фор­му­ла Ше­нон­на: где x — ко­ли­че­ство ин­фор­ма­ции в со­об­ще­нии о со­бы­тии P, p — ве­ро­ят­ность со­бы­тия P.

Ве­ро­ят­ность до­стать из кор­зи­ны чер­ный шар

Вос­поль­зо­вав­шись фор­му­лой Ше­нон­на, по­лу­ча­ем, что

За­да­ние 10 № 000. В ко­роб­ке лежат 64 цвет­ных ка­ран­да­ша. Со­об­ще­ние о том, что до­ста­ли белый ка­ран­даш, несет 4 бита ин­фор­ма­ции. Сколь­ко белых ка­ран­да­шей было в ко­роб­ке?

По­яс­не­ние.

Фор­му­ла Ше­нон­на: где x — ко­ли­че­ство ин­фор­ма­ции в со­об­ще­нии о со­бы­тии P, p — ве­ро­ят­ность со­бы­тия P.

Ве­ро­ят­ность до­стать из ко­роб­ки белый ка­ран­даш

Вос­поль­зо­вав­шись фор­му­лой Ше­нон­на, по­лу­ча­ем, что

Сле­до­ва­тель­но,

За­да­ние 10 № 000. За чет­верть Ва­си­лий Пуп­кин по­лу­чил 20 оце­нок. Со­об­ще­ние о том, что он вчера по­лу­чил чет­вер­ку, несет 2 бита ин­фор­ма­ции. Сколь­ко чет­ве­рок по­лу­чил Ва­си­лий за чет­верть?

По­яс­не­ние.

Фор­му­ла Шен­но­на: где x — ко­ли­че­ство ин­фор­ма­ции в со­об­ще­нии о со­бы­тии P, p — ве­ро­ят­ность со­бы­тия P.

Ве­ро­ят­ность того, что Ва­си­лий по­лу­чил чет­вер­ку

Вос­поль­зо­вав­шись фор­му­лой Ше­нон­на, по­лу­ча­ем, что

Сле­до­ва­тель­но,

За­да­ние 10 № 000. В кор­зи­не лежат чер­ные и белые шары. Среди них 18 чер­ных шаров. Со­об­ще­ние о том, что до­ста­ли белый шар, несет 2 бита ин­фор­ма­ции. Сколь­ко всего шаров в кор­зи­не?

По­яс­не­ние.

Фор­му­ла Ше­нон­на: где x — ко­ли­че­ство ин­фор­ма­ции в со­об­ще­нии о со­бы­тии P, p — ве­ро­ят­ность со­бы­тия P.

Ве­ро­ят­ность до­стать из кор­зи­ны белый шар

Вос­поль­зо­вав­шись фор­му­лой Ше­нон­на, по­лу­ча­ем, что

  Сле­до­ва­тель­но,

За­да­ние 10 № 000. В за­кры­том ящике на­хо­дит­ся 32 ка­ран­да­ша, не­ко­то­рые из них си­не­го цвета. На­у­гад вы­ни­ма­ет­ся один ка­ран­даш. Со­об­ще­ние «этот ка­ран­даш – НЕ синий» несёт 4 бита ин­фор­ма­ции. Сколь­ко синих ка­ран­да­шей в ящике?

По­яс­не­ние. Фор­му­ла Ше­нон­на: где x — ко­ли­че­ство ин­фор­ма­ции в со­об­ще­нии о со­бы­тии P, p — ве­ро­ят­ность со­бы­тия P.

Ве­ро­ят­ность того, что до­ста­ли НЕ синий где — число синих ка­ран­да­шей.

Вос­поль­зо­вав­шись фор­му­лой Ше­нон­на, по­лу­ча­ем, что

Сле­до­ва­тель­но,

За­да­ние 10 № 000. Для пе­ре­да­чи сиг­на­лов на флоте ис­поль­зу­ют­ся спе­ци­аль­ные сиг­наль­ные флаги, вы­ве­ши­ва­е­мые в одну линию (по­сле­до­ва­тель­ность важна). Какое ко­ли­че­ство раз­лич­ных сиг­на­лов может пе­ре­дать ко­рабль при по­мо­щи че­ты­рех сиг­наль­ных фла­гов, если на ко­раб­ле име­ют­ся флаги трех раз­лич­ных видов (фла­гов каж­до­го вида не­огра­ни­чен­ное ко­ли­че­ство)?

По­яс­не­ние.

Если в ал­фа­ви­те сим­во­лов, то ко­ли­че­ство всех воз­мож­ных «слов» (со­об­ще­ний) дли­ной равно .

N=4, M=3. Сле­до­ва­тель­но,

За­да­ние 10 № 000. Не­ко­то­рое сиг­наль­ное устрой­ство за одну се­кун­ду пе­ре­да­ет один из трех сиг­на­лов. Сколь­ко раз­лич­ных со­об­ще­ний дли­ной в пять се­кунд можно пе­ре­дать при по­мо­щи этого устрой­ства?

По­яс­не­ние.

Если в ал­фа­ви­те сим­во­лов, то ко­ли­че­ство всех воз­мож­ных «слов» (со­об­ще­ний) дли­ной равно .

N=5, M=3. Сле­до­ва­тель­но,

За­да­ние 10 № 000. Не­ко­то­рый ал­фа­вит со­дер­жит 4 раз­лич­ных сим­во­ла. Сколь­ко трех­бук­вен­ных слов можно со­ста­вить из сим­во­лов этого ал­фа­ви­та, если сим­во­лы в слове могут по­вто­рять­ся?

По­яс­не­ние.

Если в ал­фа­ви­те сим­во­лов, то ко­ли­че­ство всех воз­мож­ных «слов» (со­об­ще­ний) дли­ной равно .  N=3, M=4. Сле­до­ва­тель­но,

За­да­ние 10 № 000. Све­то­вое табло со­сто­ит из лам­по­чек. Каж­дая лам­поч­ка может на­хо­дить­ся в одном из трех со­сто­я­ний («вклю­че­но», «вы­клю­че­но» или «ми­га­ет»). Какое наи­мень­шее ко­ли­че­ство лам­по­чек долж­но на­хо­дить­ся на табло, чтобы с его по­мо­щью можно было пе­ре­дать 18 раз­лич­ных сиг­на­лов?

По­яс­не­ние.

Q=18. N — ко­ли­че­ство лам­по­чек, M=3 («вклю­че­но», «вы­клю­че­но» или «ми­га­ет»). , . Нужно найти наи­мень­шее целое N.

Проще всего ис­поль­зо­вать метод под­бо­ра: при по­лу­ча­ем , но уже при имеем .  Ответ: 3.

За­да­ние 10 № 000. Све­то­вое табло со­сто­ит из цвет­ных ин­ди­ка­то­ров. Каж­дый ин­ди­ка­тор может окра­ши­вать­ся в че­ты­ре цвета: белый, чер­ный, жел­тый и крас­ный. Какое наи­мень­шее ко­ли­че­ство лам­по­чек долж­но на­хо­дить­ся на табло, чтобы с его по­мо­щью можно было пе­ре­дать 300 раз­лич­ных сиг­на­лов?

По­яс­не­ние.

Если в ал­фа­ви­те сим­во­лов, то ко­ли­че­ство всех воз­мож­ных «слов» (со­об­ще­ний) дли­ной равно .  M=4 (белый, чер­ный, жел­тый и крас­ный).

Проще всего ис­поль­зо­вать метод под­бо­ра: при по­лу­ча­ем но уже при имеем .

За­да­ние 10 № 000. На све­то­вой па­не­ли в ряд рас­по­ло­же­ны 7 лам­по­чек. Каж­дая из пер­вых двух лам­по­чек может го­реть крас­ным, жёлтым или зелёным цве­том. Каж­дая из осталь­ных пяти лам­по­чек может го­реть одним из двух цве­тов - крас­ным или белым. Сколь­ко раз­лич­ных сиг­на­лов можно пе­ре­дать с по­мо­щью па­не­ли (все лам­поч­ки долж­ны го­реть, по­ря­док цве­тов имеет зна­че­ние)?

По­яс­не­ние.

Если в ал­фа­ви­те сим­во­лов, то ко­ли­че­ство всех воз­мож­ных «слов» (со­об­ще­ний) дли­ной равно .  Для пер­вых двух лам­по­чек можно со­ста­вить раз­лич­ных сиг­на­лов. Для остав­ших­ся пяти можно со­ста­вить раз­лич­ных сиг­на­лов. Сле­до­ва­тель­но, с по­мо­щью всей па­не­ли можно пе­ре­дать 9·32 = 288 раз­лич­ных сиг­на­лов.  Ответ 288.

За­да­ние 10 № 000. Для пе­ре­да­чи ава­рий­ных сиг­на­лов до­го­во­ри­лись ис­поль­зо­вать спе­ци­аль­ные цвет­ные сиг­наль­ные ра­ке­ты, за­пус­ка­е­мые по­сле­до­ва­тель­но. Одна по­сле­до­ва­тель­ность ракет — один сиг­нал; в каком по­ряд­ке идут цвета — су­ще­ствен­но. Какое ко­ли­че­ство раз­лич­ных сиг­на­лов можно пе­ре­дать при по­мо­щи за­пус­ка ровно четырёх таких сиг­наль­ных ракет, если в за­па­се име­ют­ся ра­ке­ты пяти раз­лич­ных цве­тов (ракет каж­до­го вида не­огра­ни­чен­ное ко­ли­че­ство, цвет ракет в по­сле­до­ва­тель­но­сти может по­вто­рять­ся)?

По­яс­не­ние.

Если в ал­фа­ви­те сим­во­лов, то ко­ли­че­ство всех воз­мож­ных «слов» (со­об­ще­ний) дли­ной равно .  N=4, M=5. Сле­до­ва­тель­но,

За­да­ние 10 № 000. Сколь­ко слов длины 5 можно со­ста­вить из букв Е, Г, Э? Каж­дая буква может вхо­дить в слово не­сколь­ко раз.

По­яс­не­ние.

Если в ал­фа­ви­те M сим­во­лов, то ко­ли­че­ство всех воз­мож­ных «слов» (со­об­ще­ний) дли­ной N равно Q = MN. В нашем слу­чае N = 5, M = 3. Сле­до­ва­тель­но, Q = 35 = 243.  Ответ: 243.

За­да­ние 10 № 000. Сколь­ко cуще­ству­ет раз­лич­ных сим­воль­ных по­сле­до­ва­тель­но­стей длины от од­но­го до трёх в четырёхбук­вен­ном ал­фа­ви­те {A, C, G, T}?

По­яс­не­ние.

Если в ал­фа­ви­те M сим­во­лов, то ко­ли­че­ство всех воз­мож­ных «слов» (со­об­ще­ний) дли­ной N равно Q = MN. В нашем слу­чае M = 4, а N = 1, 2 или 3. Сле­до­ва­тель­но Q = 41 + 42 + 43 = 4 + 16 + 64 = 84.  Ответ: 84.

За­да­ние 10 № 000. Рас­смат­ри­ва­ют­ся сим­воль­ные по­сле­до­ва­тель­но­сти длины 6 в пя­ти­бук­вен­ном ал­фа­ви­те {К, А, Т, Е, Р}. Сколь­ко су­ще­ству­ет таких по­сле­до­ва­тель­но­стей, ко­то­рые на­чи­на­ют­ся с буквы Р и за­кан­чи­ва­ют­ся бук­вой К?

По­яс­не­ние.

Если в ал­фа­ви­те M сим­во­лов, то ко­ли­че­ство всех воз­мож­ных «слов» (со­об­ще­ний) дли­ной N равно Q = MN. Пер­вая и по­след­няя буквы слова фик­си­ро­ва­ны, зна­чит, за­да­ча сво­дит­ся к на­хож­де­нию ко­ли­че­ства воз­мож­ных слов дли­ной 4 в пя­ти­бук­вен­ном ал­фа­ви­те. Их число равно 54 = 625.  Ответ: 625.