Номер 5

Известно, что Т кодируется 111, О — 0, П — 100. Например, ПОП было бы закодировано так: 1000100 (полужирным выделено вхождение буквы П). А, например, вот такая последовательность 1110100 декодировалась бы однозначно в слово ТОП.

Нам надо придумать наименьший возможный код для буквы С, при котором декодирование было бы однозначным. Что означает слово "однозначность" в данном контексте?

К примеру, давайте обозначим букву С за 1. Наименьший возможный? Да, потому что меньше 1 символа не бывает. Но есть ли однозначность? 

1. Рассмотрим слово 111. С одной стороны, это — буква Т. С другой стороны, если С — это 1, то 111 можно декодировать, как ССС. То есть, одно и то же слово, записанное в двоичном коде, можно декодировать двумя способами, при этом непонятно, какой из них верный. Значит, если сделать кодом буквы С цифру 1, то такое кодирование не будет однозначным.
2. Значит, нельзя кодировать букву С кодами, состоящими из одной цифры (0 — уже занято О, 1 — не подходит). Попробуем двумя. Вариантов — четыре: 00, 10, 11, 01. При этом сходу очевидно, что вариант С=00 не подходит, так как в этом случае слово 00 может восприниматься либо как буква С, либо как две буквы О. Поэтому остаётся три варианта: 10, 11, 01.
3. Попробуем закодировать букву С кодом 10. С какой потенциально буквой у С есть общая часть? С П (С=10, П=100, есть общая часть 10). Давайте тогда и рассмотрим тогда слово 100, связанное с буквой П. 
   С одной стороны, 100 может быть декодировано просто буквой П (ведь П и есть 100).
   С другой стороны, 100 можно декодировать буквами СО (С=10, О=0). 
   Таким образом, имеется неоднозначность. Значит, С нельзя кодировать кодом 10.
4. Закодируем букву С кодом 11. В этом случае буква С очень похожа на букву Т (С=11, Т=111). Рассмотрим последовательность 111111.
   С одной стороны, 111111 можно декодировать, как ТТ.
   С другой стороны, 111111 декодируется, как ССС.
   Таким образом, имеется неоднозначность. Значит, С нельзя кодировать кодом 11.
5. Закодируем букву С кодом 01. В этом случае буква С очень похожа на перевёрнутый код буквы П (П=100, С=01). Рассмотрим последовательность 0100.
   С одной стороны, 0100 можно представить, как СОО.
   С другой стороны, 0100 декодируется, как ОП.
   Таким образом, имеется неоднозначность. Значит, С нельзя кодировать кодом 01.
6. Таким образом, все двузначные коды не подошли. Значит, надо брать трёхзначные.
7. Варианты у нас следующие: 000, 001, 010, 100, 011, 101, 110, 111. При этом 111 и 100 уже заняты буквами Т и П соответственно. Вариант 000 очевидно не подходит по соображениям обозначенным в п.2 (равен трём буквам О). 
8. Остаётся: 001, 010, 011, 101, 110. Заметьте — мы сразу упорядочили коды по возрастанию, как это требуется в условии задачи (если вдруг подойдут несколько кодов — нужно выбрать наименьший).
9. Начнём с 001. Он очевидным образом похож на букву П (П=100, С=001). Возьмём последовательность 00100.
   С одной стороны, 00100 можно декодировать, как СОО.
   С другой стороны, 00100 представим, как ООП.
   Таким образом, имеется неоднозначность. Значит, С нельзя кодировать кодом 001.
10. Рассмотрим код 010.  Он похож на букву П (П=100, С=010). Возьмём последовательность 0100.
    С одной стороны, 0100 можно декодировать, как СО.
    С другой стороны, 0100 представим, как ОП.
    Таким образом, имеется неоднозначность. Значит, С нельзя кодировать кодом 010.
11. Рассмотрим код 011.  В нём уже две единицы, значит, если и есть неоднозначность, то она обязана быть с буквой Т (111). Возьмём последовательность 011100.
    С одной стороны, 011100 можно декодировать, как СП.
    С другой стороны, 011100 представим, как ОТОО.
    Таким образом, имеется неоднозначность. Значит, С нельзя кодировать кодом 011.
12. Рассмотрим код 101. Он похож на несколько кодов, но если начать перебирать возможные несостыковки, то мы их не найдём. На основе этого делаем вывод, что этот код и будет являться ответом.

Ответ: код буквы С, которых сохраняет однозначость кодирования/декодирования, — 101.

 

Номер 6

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1) Строится двоичная запись числа N.

2) К этой записи до­пи­сы­ва­ют­ся спра­ва ещё два раз­ря­да по сле­ду­ю­ще­му пра­ви­лу:

а) скла­ды­ва­ют­ся все цифры дво­ич­ной за­пи­си, и оста­ток от де­ле­ния суммы на 2 до­пи­сы­ва­ет­ся в конец числа (спра­ва). На­при­мер, за­пись 11100 пре­об­ра­зу­ет­ся в за­пись 111001;

б) над этой за­пи­сью про­из­во­дят­ся те же дей­ствия — спра­ва до­пи­сы­ва­ет­ся оста­ток от де­ле­ния суммы цифр на 2.

Полученная таким об­ра­зом за­пись (в ней на два раз­ря­да боль­ше, чем в за­пи­си ис­ход­но­го числа N) яв­ля­ет­ся дво­ич­ной за­пи­сью ис­ко­мо­го числа R.

Ука­жи­те ми­ни­маль­ное число R, ко­то­рое пре­вы­ша­ет 43 и может яв­лять­ся ре­зуль­та­том ра­бо­ты ал­го­рит­ма. В от­ве­те это число за­пи­ши­те в де­ся­тич­ной си­сте­ме.

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

Если в числе было нечётное ко­ли­че­ство еди­ниц, то в конец до­пи­шет­ся 10. Если чётное, то 00. Таким об­ра­зом, нужно найти пер­вое число, боль­шее 43, у ко­то­ро­го в дво­ич­ной за­пи­си чётное ко­ли­че­ство еди­ниц, а на конце 10 или 00. Имеем:

4410 = 1011002,

4510 = 1011012,

4610 = 1011102.

Ответ: 46.

 

Номер 9

чтобы закодировать 256 различных цветов, нам потребуется 8 бит. Значит, один пиксель в данном изображении будет занимать 8 бит.

Вспомним, сколько у нас всего пикселей? — 2¹². Если 1 пиксель занимает 8 бит, то 2¹² пикселей будут занимать 2¹²x8 = 2¹²x2³ = 2¹⁵ бит.

Нас просят дать ответ в Кбайтах. Значит, надо перевести из бит в Кбайты. Давайте вспомним соотношения между величинами:

• 1 байт   = 8 бит = 2³ бит
• 1 Кбайт = 1024 байта = 2¹⁰ байт
• 1 Кбайт = 8x1024 бит = 2³ x 2¹⁰ = 2¹³ бит

Значит, информационный объём («размер») данного изображения составляет 4 Кбайта.
А у нас сколько? 2¹⁵ бит. Сколько это Кбайт? Надо поделить на то, сколько занимает 1 Кбайт бит: 2¹⁵ / 2¹³ = 2² = 4 Кбайт. Значит, информационный объём («размер») данного изображения составляет 4 Кбайта.

 

Номер 10

Буква П появляется 1 раз. Где она потенциально может быть? На первом месте, на втором, на третьем, на четвёртом или на пятом. Давайте по-отдельности посчитаем количество слов, когда буква П стоит в соответствующих местах.

Начнём со случая, когда П стоит на первом месте.

1. В этом случае 2 буква может быть любая из двух оставшихся — И или Р. То есть, всего два варианта.
2. 3 буква может быть также любой из оставшихся — тоже 2 варианта.
3. Для каждого варианта второй буквы есть ровно два варианта 3-ей, поэтому всего вариантов 2 и 3 букв будет 2x2=4.
4. Добавляем четвёртую букву — тоже 2 возможных варианта.
5. Для каждого из 4-х вариантов 2 и 3 букв есть ровно 2 варианта 4-ой.
6. Значит, вариантов 2, 3 и 4 букв 4x2=8 шт.
7. Добавляем 5-ую букву. По тем же соображениям кол-во вариантов будет: 8x2 = 16 вариантов.

Итого: когда П находится на первом месте, количество вариантов слов — 16.

Ровно по тем же соображениям будет 16 вариантов, когда П стоит на втором месте. Аналогично — на третьем, четвёртом и пятом. Значит, всего будет 16+16+16+16+16=80 вариантов.

Ответ: 80 различных слов.

 

Номер 12

За­пи­шем тре­тий байт IP-ад­ре­са и ад­ре­са сети в дво­ич­ной си­сте­ме счис­ле­ния:

208₁₀ = 11010000₂

192₁₀ = 11000000₂

Видим, что два пер­вых слева бита маски − еди­ни­цы, а тре­тий бит может быть как нулем, так и еди­ни­цей. Для того, чтобы зна­че­ние было наи­боль­шим, этот бит дол­жен быть равен еди­ни­це. По­лу­ча­ем, что тре­тий слева байт маски равен 11100000₂ = 224₁₀

Ответ: 224.

 

Номер 13

Со­глас­но усло­вию, в но­ме­ре могут быть ис­поль­зо­ва­ны 12 букв. Из­вест­но, что с по­мо­щью N бит можно за­ко­ди­ро­вать 2N раз­лич­ных ва­ри­ан­тов. По­сколь­ку 2³ < 12 < 2⁴, то для за­пи­си каж­до­го из 12 сим­во­лов не­об­хо­ди­мо 4 бита.

Для хра­не­ния всех 15 сим­во­лов па­ро­ля нужно 4 · 15 = 60 бит, а т. к. для за­пи­си ис­поль­зу­ет­ся целое число байт, то берём бли­жай­шее не мень­шее зна­че­ние, крат­ное вось­ми, это число 64 = 8 · 8 бит (8 байт).

Пусть ко­ли­че­ство па­мя­ти, от­ве­ден­ное под до­пол­ни­тель­ные све­де­ния равно x, тогда:

20 * (8+x) = 400

x = 12

Ответ: 12.