11. Количество информации и комбинаторика —Каталог задач по ЕГЭ - Информатика

Главная
Каталог задач
Каталог заданий по ЕГЭ - Информатика
Количество информации и комбинаторика

Тема 11. Количество информации и комбинаторика

11.01 Количество информации и комбинаторика

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела количество информации и комбинаторика

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#63193

Система мониторинга формирует и отправляет специальные сообщения, в которые могут входить только следующие символы: латинские буквы ( $26$ заглавных и $26$ строчных), цифры от $0$ до $9$ , пробел. Количество символов в сообщении может быть любым.

При передаче сообщения используется равномерное посимвольное кодирование: каждый символ кодируется одинаковым минимально возможным количеством битов. Сообщение в целом кодируется минимально возможным количеством байтов. Кроме того, к каждому сообщению добавляется заголовок, содержащий целое число байтов, одинаковое для всех сообщений.

Система отправила $7$ сообщений: два сообщения по $30$ символов каждое, два сообщения по $50$ символов и три сообщения по $70$ символов. При этом всего было передано $400$ байт.

Сколько байтов содержит заголовок сообщения? В ответе запишите только целое число — количество байтов.

Показать ответ и решение

Начнем с подсчета количество всех символов:

$26 + 26 + 10 + 1 = 63$ символа. Значит вес $1$ символа будет $i 2 = 63$ .

$i = 6$ бит на $1$ символ.

Примем, что $m −$ вес заголовка, а $I−$ вес всех сообщений.

$I1−$ вес первого одного сообщения.

$I2−$ вес второго одного сообщения.

$I3−$ вес третьего одного сообщения.

Тогда получаем:

(| 30 ⋅ 6 ||| I1 = -----≈ 23 байта. ||| 8 |||{ 50 ⋅ 6 | I2 = 8 ≈ 38 байт. |||| ||| ||( 70 ⋅ 6 I3 = 8 ≈ 53 байта.

Общая формула будет выглядеть следующим образом:

$I = 2 ⋅ (I1 + m ) + 2 ⋅ (I2 + m ) + 3 ⋅ (I3 + m ) = 400$

Отсюда выразим $m$ :

$m = 400-−--2 ⋅ 23-−-2-⋅ 38-−-3-⋅ 53 = 119-= 17 7 7$ байт.

Ответ: 17

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#56312

В некоторой стране автомобильный номер длиной $6$ символов составляется из заглавных букв (всего используется $23$ буквы) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер — одинаковым и минимально возможным целым количеством байт. Определите объем памяти в байтах, необходимый для хранения $20$ автомобильных номеров.

Показать ответ и решение

Алфавит, доступный для автомобильного номера, состоит из $33$ символов (буквы и цифры), значит, чтобы закодировать один символ понадобится $6$ бит ( $25 < 33 <= 26$ ). Тогда для всего номера необходимо отвести $6⋅6 = 36$ бит $≈ 5$ байт.
Для хранения $20$ номеров понадобится $5 ⋅20 = 100$ байт.

Ответ: 100

Ошибка.
Попробуйте повторить позже

Задача 3#43649

В велокроссе участвуют $37$ спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Какой объём памяти будет использован устройством, когда промежуточный финиш прошли $16$ велосипедиста? (Ответ дайте в Байтах)

Показать ответ и решение

Всего участвует $37$ спортсменов, значит, на информацию об одном спортсмене понадобится выделить $6$ бит (поскольку $25 < 37 < 26$ . На информацию о $16$ велосипедистах потребуется $16 ⋅6$ бит, или же $12$ байт.

Ответ: 12

Ошибка.
Попробуйте повторить позже

Задача 4#43648

В соревнованиях по плаванию участвуют $167$ спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Какой объём памяти будет использован устройством, когда промежуточный финиш прошли $104$ пловца? (Ответ дайте в битах)

Показать ответ и решение

Всего участвует $167$ спортсменов, значит, на информацию об одном спортсмене понадобится выделить $8$ бит (поскольку $27 < 167 < 28$ . На информацию о $104$ пловцах потребуется $104 ⋅8 = 832$ бит.

Ответ: 832

Ошибка.
Попробуйте повторить позже

Задача 5#39289

В велокроссе участвуют $193$ спортсмена. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем в байтах сообщения, записанного устройством, после того как промежуточный финиш прошли $100$ велосипедистов?

Показать ответ и решение

Всего участвует $193$ спортсмена, значит, на информацию об одном спортсмене понадобится выделить $8$ бит (поскольку $193 < 28$ . На информацию о $100$ велосипедистах потребуется $100⋅8 = 800$ бит, или же $100$ байт.

Ответ: 100

Ошибка.
Попробуйте повторить позже

Задача 6#39288

В написании пробника участвуют $3000$ марафонцев. Куратор фиксирует прохождение каждым из марафонцев регистрации на написание пробника, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого марафонца. Какой объём памяти потребуется выделить куратору на своем ноутбуке, чтобы зарегистрировать всех марафонцев на написание пробника? Ответ дайте в Кбайтах. В ответ запишите только целую часть числа.

Показать ответ и решение

Так как с помощью $i$ бит можно закодировать $N = 2i$ чисел, то для регистрации $N = 3000$ номеров потребуется $12$ бит, так как $211 = 2048 < 3000 ≤ 212 = 4096$ . Значит, для регистрации всех марафонцев куратору потребуется выделить $3000⋅12 = 36000$ бит, то есть $36000∕8 = 4500$ байт, то есть $4500∕1024 ≈ 4.4$ Кбайт памяти. В ответ записываем число $4$ .

Ответ: 4

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#37488

В велокроссе участвуют $617$ спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем в байтах сообщения, записанного устройством, после того как промежуточный финиш прошли $212$ велосипедистов?

Показать ответ и решение

Всего участвует $617$ спортсменов, значит, на информацию об одном спортсмене понадобится выделить $10$ бит (поскольку $29 < 617 < 210$ . На информацию о $212$ велосипедистах потребуется $212 ⋅10$ бит, или же $265$ байт.

Ответ: 265

Ошибка.
Попробуйте повторить позже

Задача 8#37487

В велокроссе участвуют $98$ спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Какой объём памяти будет использован устройством, когда промежуточный финиш прошли $92$ велосипедиста? (Ответ дайте в битах)

Показать ответ и решение

Всего участвовало $98$ спортсменов. $26 < 98 < 27$ , значит, чтобы записать одного участника, хватит $7$ бит. Финиш прошли $92$ велосипедиста, то есть было потрачено $7 ⋅92 = 644$ бит.

Ответ: 644

Ошибка.
Попробуйте повторить позже

Задача 9#33599

При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из $258$ символов и содержащий только десятичные цифры и символы из $4500$ -символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.

Определите объём памяти (в Кбайт), необходимый для хранения $32768$ идентификаторов. В ответе запишите только целое число – количество Кбайт.

Показать ответ и решение

На каждый символ индетификатора занимает: $log2(4500+ 10) = 13$ бит

Каждый идентификатор занимает: $(Р азм ер одного сим вола)⋅(К оличество символов в иден ти фик&#$

Каждый идентификатор занимает: $13 ⋅258 = 3354$ бит или же $3354∕8 = 420$ байт.

Общий объем для памяти для всех идентификаторов в Кбайт: $420⋅32768= 13440 210$ Кбайт.

Ответ: 13440

Ошибка.
Попробуйте повторить позже

Задача 10#30255

Праздник, на котором было $19$ человек и еще Петя ( $20$ -й), подходит к концу, поэтому ребятам пришло время расходиться. Все начали прощаться друг с другом. Петя счёл интересным кодировать каждое прощание. Всего он определил три вида прощаний: мальчик с мальчиком, девочка с девочкой, девочка с мальчиком. Определите, сколько байт потребовалось Пете для кодирования этой информации. Каждое прощание кодируется минимально возможным количеством бит.

Показать ответ и решение

Есть всего три вида прощаний, поэтому для кодирования каждого из них нужно минимум 2 бит, так как $21 < 3 <= 22$ . Приглашено 19 человек. Петя является 20-тым. Тогда всего прощаний между 20 людьми равно количеству ребер в полном графе на 20 вершинах, то есть равно $20⋅19∕2 = 190$ Значит, на все кодирование всех прощаний требуется $190⋅2 = 380$ бит $= 48$ байт.

Ответ: 48

Ошибка.
Попробуйте повторить позже

Задача 11#30254

Оказалось, Ваня кроме камней принёс с собой сейф, чтобы подарить его Пете. Именинник был рад такому подарку и решил незамедлительно придумать надежный пароль. Естественно, все придуманные варианты Петя захотел закодировать.

Петя попросил одну часть ребят придумать первые $4$ символа пароля, состоящие только из последних $15$ букв латинского алфавита в двух регистрах. Каждый символ кодируется минимально возможным количеством бит. Вся придуманная последовательность кодируется целым количеством байт.

Другую часть ребят Петя попросил придумать следующие $6$ цифр пароля, используя десятичные цифры и символы $∗,&,%, @$ . Каждый символ кодируется минимально возможным количеством бит. Вся придуманная последовательность кодируется целым количеством байт.

Для ещё большей надёжности Петя придумал последние два символа пароля сам. Для этого он использовал все $26$ букв латинского алфавита в нижнем регистре. Каждый символ кодируется минимально возможным количеством бит. Вся придуманная последовательность кодируется целым количеством байт.

В итоге получился $12$ -символьный пароль, состоящий из трёх разных частей. Но Пете он не понравился, поэтому совместными усилиями таким же способом был получен новый пароль. А потом ещё. И ещё немного. После шести попыток Пете понравился результат и пароль был наконец установлен, после чего ребята отправились есть праздничный торт.

Определите, сколько байт потребовалось Пете, чтобы закодировать информацию обо всех шести паролях.

Показать ответ и решение

Первая часть пароля. Используется 15 букв в двух регистрах, то есть 30 символов. Для кодирования такого количества необходимо минимум 5 бит на каждый символ, так как $24 < 30 <= 25$ . Тогда на 4 символа нужно $5 ⋅4 = 20$ бит $= 20∕8 = 3$ байт.

Вторая часть пароля. Используется 10 цифр и $∗,&, %,@$ , то есть 14 символов. Для кодирования такого количества необходимо минимум 4 бит на каждый символ, так как $23 < 14 <= 24$ . Тогда на 6 символов нужно $6 ⋅4 = 24$ бит $= 24∕8 = 3$ байт.

Третья часть пароля. Используется 26 букв в одном регистре, то есть 26 символов. Для кодирования такого количества необходимо минимум 5 бит на каждый символ, так как $24 < 26 <= 25$ . Тогда на 2 символа нужно $5 ⋅2 = 10$ бит $= 10∕8 = 2$ байт.

Следовательно, на один пароль потребуется $3+ 3+ 2 = 8$ байт. Тогда на 6 паролей необходимо $6⋅8 = 48$ байт.

Ответ: 48

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#30253

Другим ребятам на празднике понравилась игра Пети и Вани и они решили поиграть тоже. Петя изменил правила. Теперь изменить количество камней в куче стало возможно десятью способами, при этом игра состояла из шести ходов. Петя записывал дополнительные сведения о каждой игре, но забыл, сколько памяти для этого отводилось. Всего было проведено 20 игр, на которые было потрачено 420 байт (игры кодировались вместе с дополнительными сведениями).

Помогите вспомнить Пете, сколько байт нужно для хранения дополнительных сведений о каждой игре. Каждый ход кодируется минимально возможным количеством бит. Каждая игра кодируется минимально возможным количеством байт. Дополнительные сведения о каждой игре занимают одинаковое количество байт.

Показать ответ и решение

Существует 10 способов сделать ход. $23 < 10 <= 24$ , поэтому для кодирования каждого хода потребуется минимум 4 бит. Так как игра состоит из 6 ходов, то для кодирования данных об одной игре потребуется $6⋅4 = 24$ бит $= 24∕8 = 3$ байт. На 20 игр с дополнительными сведениями было отведено 420 байт. Значит, на одну игру с дополнительными сведениями требуется $420∕20 = 21$ байт. Тогда для кодирования дополнительных данных об одной игре потребуется $21− 3 = 18$ байт.

Ответ: 18

Ошибка.
Попробуйте повторить позже

Задача 13#30252

Наконец на день рождения пришёл Ваня. Он опоздал и был весьма удивлён выбору скучной игры с придумыванием слов, поэтому предложил другой вариант.

Ваня захватил с собой камни (обычное дело), поэтому начал с именинником играть в следующую игру. За ход можно изменить количество камней в куче одним из трёх способов. Одна игра состоит из восьми ходов. Конечно, Петя решил закодировать партии этой увлекательной игры. Каждый ход (то есть один из способов изменения количества камней в куче) кодируется минимально возможным количеством бит. Каждая игра кодируется минимально возможным количеством байт. Петя решил добавить дополнительные сведения к каждой игре, на которые уходит по 1 байт. Сколько байт потребуется для кодирования трёх игр с дополнительными сведениями о них?

Показать ответ и решение

Существует всего 3 способа сделать ход. $21 < 3 <= 22$ , поэтому для кодирования каждого хода потребуется минимум 2 бит. Так как игра состоит из 8 ходов, то для кодирования данных об одной игре потребуется $8⋅2 = 16$ бит $= 16∕8 = 2$ байт. Каждая игра с дополнительными сведениями занимает $2 + 1 = 3$ байт. Тогда для трёх игр потребуется $3⋅3 = 9$ байт.

Ответ: 9

Ошибка.
Попробуйте повторить позже

Задача 14#30251

Ребята на дне рождения решили поиграть в игру. Все должны были придумать как можно больше последовательностей длиной $9$ символов из букв $П, Е, Т, Я$ и цифр $1,8$ . Ребята написали $40$ последовательностей. Петя решил их все закодировать. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждая последовательность — одинаковым и минимально возможным целым количеством байт. Определите объем памяти в байтах, который потребуется Пете.

Показать ответ и решение

Всего можно использовать $6$ символов, для кодирования каждого нужно минимум $3$ бит, так как $22 < 6 <= 23.$ Тогда для $9$ символов потребуется $9⋅3 = 27$ бит $= 27∕8 = 4$ байт. Значит, для $40$ таких последовательностей потребуется $40 ⋅4 = 160$ байт.

Ответ: 160

Ошибка.
Попробуйте повторить позже

Задача 15#30250

Петя пригласил на день рождения 19 человек. Для каждого он придумал уникальный код, который записал с помощью минимального количества бит. Каков информационный объем в байтах сообщения о кодах первых 11 человек, пришедших на праздник?

Показать ответ и решение

На 19 человек нужно минимум 5 бит для каждого кода, так как $24 < 19 <= 25.$ Тогда для первых 11 человек потребуется $11 ⋅5 = 55$ бит $= 55∕8 = 7$ байт.

Ответ: 7

Ошибка.
Попробуйте повторить позже

Задача 16#29446

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из $34$ символов и содержащий только символы $X, Y,Z,W, F$ . Каждый такой пароль в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт, при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит.

Определите, сколько байт необходимо для хранения $15$ паролей. В ответе запишите только число.

Показать ответ и решение

Всего используется $5$ символов, найдём количество бит на символ: $5 ≤ 2i,i = 3$ бит. Значит, на пароль выделяется $3⋅834 = 13$ байт. Получаем ответ: $13⋅15 = 195$ .

Ответ: 195

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#29358

При регистрации в компьютерной системе каждому пользователю выдаётся пароль длиной $10$ символов, составленный из букв (только $21$ различная буква) и десятичных цифр.

Каждый такой номер в базе данных записывается минимально возможным и одинаковым целым количеством байт, при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит.

Определите объём памяти, отводимый этой программой для записи $81$ пароля. Ответ дайте в байтах.

Показать ответ и решение

Алфавит, доступный для пароля, состоит из $31$ символа, значит, чтобы закодировать один символ понадобится $5$ бит ( $24 < 31 <= 25$ ). Тогда для всего номера необходимо отвести $5⋅10 = 50$ бит $≈ 7$ байт.
Для хранения $81$ пароля требуется $81⋅7 = 567$ байт.

Ответ: 567

Ошибка.
Попробуйте повторить позже

Задача 18#28807

В некоторой стране каждой машине выдается автомобильный номер длиной $10$ символов, составленный из заглавных букв (используются только $33$ различных буквы) и десятичных цифр.

Каждый такой номер в базе данных записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит).

Определите объём памяти, отводимый этой программой для записи $100$ номеров. Ответ дайте в байтах.

Показать ответ и решение

Алфавит, доступный для автомобильного номера, состоит из $44$ символа (буквы и цифры), значит, чтобы закодировать один символ понадобится $6$ бит ( $25 < 44 <= 26$ ). Тогда для всего номера необходимо отвести $6⋅10 = 60$ бит $≈ 8$ байт.
Для хранения $100$ паролей понадобится $8⋅100 = 800$ байт.

Ответ: 800

Ошибка.
Попробуйте повторить позже

Задача 19#27993

В некоторой стране автомобильный номер длиной $5$ символов составляется из заглавных букв (всего используется $26$ букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер — одинаковым и минимально возможным целым количеством байт. Определите объем памяти в байтах, необходимый для хранения $100$ автомобильных номеров.

Показать ответ и решение

Всего используется 26 + 10 символов, найдём количество бит на символ: $36 ≤ 2i,i = 6$ . Значит, на пароль выделяется $5∗86 = 4$ байта. Получаем ответ: $100 ∗4 = 400$ .

Ответ: 400

Ошибка.
Попробуйте повторить позже

Задача 20#27454

В некоторой базе данных хранятся записи, содержащие информацию о некоторых датах. Каждая запись содержит три поля: номер года (число от $1$ до $2100$ ), номер месяца (число от $1$ до $12$ ) и номер дня в месяце (число от $1$ до $30$ ). Каждое поле записывается отдельно от других полей с использованием минимально возможного количества бит. Определите минимальное количество бит, необходимое для кодирования одной записи. Ответ дайте в битах.

Показать ответ и решение

Так как $2100 ≤ 212$ , то номер года кодируется с помощью $12$ бит.
Так как $12 ≤ 24$ , то номер месяца кодируется с помощью $4$ бит.
Так как $30 ≤ 25$ , то номер дня в месяце кодируется с помощью $5$ бит.
Тогда минимальное количество бит, необходимое для кодирования одной записи, равно $12+ 4 + 5 = 21$

Ответ: 21

Предыдущий раздел

Следующий раздел