Информация и информационные процессы

1. Информация и информационные процессы

Задания 10 и 13

2. 10 (базовый уровень, время – 4 мин)

Тема: Анализ последовательностей,
системы счисления

3. Задача 1

Сколько существует различных символьных
последовательностей длины 5 в
четырёхбуквенном алфавите {A, C, G, T},
которые содержат ровно две буквы A?

4. Решение

• А на первом месте: АА***
А*А**
А**А* А***А
(звёздочка – любой символ из набора {C, G, T})
• в каждом наборе есть 3 позиции, каждую из которых можно
заполнить 3-мя способами, т.е. 33 = 27
• всего 4 набора, значит 4 · 27 = 108
• А на втором месте : *АА**
*А*А*
*А**А
• они дают 3 · 27 = 81
• А на третьем месте: **АА*
**А*А
2 · 27 = 54
• один набор, где сочетание АА стоит в конце: ***АА
• они дают 27
• Итого (4 + 3 + 2 + 1) · 27 = 270
• ответ: 270

5. Задача 2

Сколько слов длины 5, начинающихся с
гласной буквы, можно составить из букв Е, Г,
Э? Каждая буква может входить в слово
несколько раз. Слова не обязательно должны
быть осмысленными словами русского языка.

6. Решение

• первая буква слова может быть выбрана двумя способами
(Е или Э), остальные – тремя
• общее число различных слов равно 2*3*3*3*3 = 162
• ответ: 162.

7. Задача 3

Все 4-буквенные слова, составленные из букв
К, Л, Р, Т, записаны в алфавитном порядке и
пронумерованы. Вот начало списка:
1. КККК
2. КККЛ
3. КККР
4. КККТ
……
Запишите слово, которое стоит на 67-м месте
от начала списка

8. Решение

• Замена: К 0, Л 1, Р 2, Т 3;
• Тогда
1. КККК
0000
2. КККЛ
0001
3. КККР
0002
4. КККТ
0003
• Значит, под номером 67 стоит число 66
• 6610 = 10024
• Обратная замена (цифр на буквы): ЛККР.
• Ответ: ЛККР.

9. Задача 4

Все 5-буквенные слова, составленные из букв
А, О, У, записаны в обратном алфавитном
порядке. Вот начало списка:
1. УУУУУ
2. УУУУО
3. УУУУА
4. УУУОУ
……
Запишите слово, которое стоит на 240-м месте
от начала списка.

10. Решение

• Замена: У → 0, О → 1, А → 2;
• Тогда
1. УУУУУ 0000
2. УУУУО 0001
3. УУУУА 0002
4. УУУОУ 0010
• Значит, под номером 240 стоит число 239
• 23910 = 22212 3
• Обратная замена (цифр на буквы): АААОА.
• Ответ: АААОА.

11. 13 (повышенный уровень, время – 3 мин)

Тема: Вычисление информационного объема
сообщения

12. Задача 1

При регистрации в компьютерной системе каждому
пользователю выдаётся пароль, состоящий из 15
символов и содержащий только символы Ш, К, О, Л, А
(таким образом, используется 5 различных символов).
Каждый такой пароль в компьютерной системе
записывается минимально возможным и одинаковым
целым количеством байт (при этом используют
посимвольное кодирование и все символы
кодируются одинаковым и минимально возможным
количеством бит). Укажите объём памяти в байтах,
отводимый этой системой для записи 30 паролей. В
ответе запишите только число, слово «байт» писать не
нужно

13. Решение

в пароле можно использовать 5 символов, значит 5 < 23 бит
т.е 3 бита – 1 символ
15 символов пароля: 15 3 = 45 бит
45 : 8 ≈ 5, … ≈ 6 байт
30 паролей: 6 30 = 180 байт
ответ: 180.

14. Задача 2

Для регистрации на сайте некоторой страны
пользователю требуется придумать пароль. Длина пароля –
ровно 11 символов. В качестве символов используются
десятичные цифры и 12 различных букв местного алфавита,
причём все буквы используются в двух начертаниях: как
строчные, так и заглавные (регистр буквы имеет значение!).
Под хранение каждого такого пароля на компьютере
отводится минимально возможное и одинаковое целое
количество байтов, при этом используется посимвольное
кодирование и все символы кодируются одинаковым и
минимально возможным количеством битов.
Определите объём памяти в байтах, который занимает
хранение 60 паролей.

15. Решение

• 10 цифр (0..9) + 12 заглавных букв местного алфавита + 12
строчных букв, всего 10 + 12 + 12 = символа
• Один символ – 6 бит памяти (34 < 26)
• 11 символов: 11 6 = 66 бит
• 66 : 8 = 8,25 ≈9; то есть один пароль занимает 9 байт
• тогда 60 паролей занимают 9 60 = 540 байт
• ответ: 540

16. Задача 3

Объем сообщения, содержащего 4096 символов,
равен 1/512 части Мбайта. Какова мощность алфавита,
с помощью которого записано это сообщение?

17. Решение

• в сообщении было 4096 = 212 символов
• объем сообщения: 1/512 Мбайта = 223 / 512 бита = 223 / 29 бита =
214 бита
• 1 символ: 214 бита / 212 символов = 22 бита на символ = 4 бита на
символ
• 4 бита на символ позволяют закодировать 24 = 16 разных
символов
• мощность алфавита – 16 символов
• Ответ: 16

18. Задача 4

В зоопарке 32 обезьяны живут в двух вольерах, А и Б.
Одна из обезьян заболела. Сообщение «Заболевшая
обезьяна живет в вольере А» содержит 4 бита
информации. Сколько обезьян живут в вольере Б?

19. Решение

• информация в 4 бита соответствует выбору одного из 16 (24)
вариантов
• поэтому в вольере А живет 1/16 часть всех обезьян
• всего обезьян – 32
• значит, в вольере А 32/16 = 2 обезьяны
• тогда в вольере Б: 32 – 2 = 30 обезьян
• ответ – 30.

20. Задача 5

В школьной базе данных хранятся записи, содержащие
информацию об учениках:
<Фамилия> – 16 символов: русские буквы (первая
прописная, остальные строчные),
<Имя> – 12 символов: русские буквы (первая
прописная, остальные строчные),
<Отчество> – 16 символов: русские буквы (первая
прописная, остальные строчные),
<Год рождения> – числа от 1992 до 2003.
Каждое поле записывается с использованием
минимально возможного количества бит. Определите
минимальное количество байт, необходимое для
кодирования одной записи, если буквы е и ё считаются
совпадающими.?

21. Решение

• Определяем для каждого из четырех полей и складываем;
• первые буквы имени, отчества и фамилии – всегда заглавные,
поэтому можно хранить их в виде строчных и делать заглавными
только при выводе на экран
• алфавит состоит из 32 символов (русские строчные буквы, «е» и
«ё» совпадают, пробелы не нужны)
• для кодирования каждого символа 32-символьного алфавита
нужно 5 бит (32 = 25)
• поэтому для хранения имени, отчества и фамилии нужно
(16 + 12 + 16)•5=220 бит
• для года рождения есть 12 вариантов, поэтому для него – 4 бита
(24 = 16 ≥ 12)
• всего требуется 224 бита или 28 байт
• Ответ – 28 .