Лабораторная работа №1 Информация и формы ее представления. Понятие количества информации 1
жүктеу/скачать 80,27 Kb.
|
Лаб СРС 1 Информация
1.3 Примеры выполнение работыПример 1 В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 70 велосипедистов? 1) 70 бит 2) 70 байт 3) 490 бит 4) 119 байт Решение: Велосипедистов было 119, у них 119 разных номеров, то есть, нам нужно закодировать 119 вариантов По таблице степеней двойки находим, что для этого нужно минимум 7 бит (при этом можно закодировать 128 вариантов, то есть, еще есть запас); итак, 7 бит на один отсчет Когда 70 велосипедистов прошли промежуточный финиш, в память устройства записано 70 отсчетов Поэтому в сообщении 70*7 = 490 бит информации (ответ 3). Обратить внимание при решении: - может быть дано число, которое есть в условии (неверные ответы 70 бит, 70 байт, 119 байт), чтобы сбить случайное угадывание - может быть в ответах указано правильное число, но другие единицы измерения (мог быть вариант 490 байт) - можно не заметить, что требуется определить объем только 70 отсчетов, а не всех 119 (мог быть вариант 119*7=833 бита) Пример 2 Объем сообщения, содержащего 4096 символов, равен 1/512 части Мбайта. Какова мощность алфавита, с помощью которого записано это сообщение? 1) 8 2) 16 3) 4096 4) 16384 Подсказка: Большие числа. Что делать? Обычно (хотя и не всегда) задачи, в условии которых даны большие числа, решаются достаточно просто, если выделить в этих числах степени двойки. На эту мысль должны сразу наталкивать такие числа как 128 = 27, 256 = 28, 512 = 29 , 1024 = 210, 2048 = 211, 4096 = 212 , 8192 = 213, 16384 = 214, 65536 = 216 и т.п. Нужно помнить, что соотношение между единицами измерения количества информации также представляют собой степени двойки: 1 байт = 8 бит = 23 бит, 1 Кбайт = 1024 байта = 210 байта = 210 · 23 бит = 213 бит, 1 Мбайт = 1024 Кбайта = 210 Кбайта = 210 · 210 байта = 220 байта = 220 · 23 бит = 223 бит. Правила выполнения операций со степенями: при умножении степени при одинаковых основаниях складываются … а при делении – вычитаются: Решение (вариант 1): В сообщении было 4096 = 212 символов Объем сообщения 1/512 Мбайта = 223 / 512 бита = 223 / 29 бита = 214 бита (= 16384 бита!) Место, отведенное на 1 символ: 214 бита / 212 символов = 22 бита на символ = 4 бита на символ 4 бита на символ позволяют закодировать 24 = 16 разных символов Поэтому мощность алфавита – 16 символов Правильный ответ – 2. Обратить внимание при решении: - может быть дано число, которое есть в условии и получится неверный ответ - 4096 - можно увидев «правильное» число в ходе вычислений не довести расчет до конца и получится неверный ответ - 16384 - можно легко запутаться, если выполнять вычисления «в лоб», не через степени двойки Решение (вариант 2): Объем сообщения 1/512 Мбайт = 1024/512 Кбайт = 2 Кбайт = 2048 байт На 1 символ приходится 2048 байт / 4096 = 1/2 байта = 4 бита 4 бита на символ позволяют закодировать 24 = 16 разных символов Поэтому мощность алфавита – 16 символов Правильный ответ – 2. Обратить внимание при решении: - не всегда удобно работать с дробными числами (1/2 байта) - метод разработан специально для этой задачи, где он хорошо работает; в других задачах может не работать Пример 3 В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян – альбинос (вся белая). Сообщение «Обезьяна-альбинос живет в вольере А» содержит 4 бита информации. Сколько обезьян живут в вольере Б? 1) 4 2) 16 3) 28 4) 30 Решение (вариант 1): Информация в 4 бита соответствует выбору одного из 16 вариантов, … … поэтому в вольере А живет 1/16 часть всех обезьян (это самый важный момент!) Всего обезьян – 32, поэтому в вольере А живет 32/16 = 2 обезьяны Поэтому в вольере Б живут все оставшиеся 32 – 2 = 30 обезьян Правильный ответ – 4. Обратить внимание при решении: - можно дать неверный ответ 1 (4 обезьяны) сбивает случайное угадывание «в лоб», по исходным данным - можно сделать неверный вывод о том, что в вольере А живет 4 обезьяны (столько же, сколько бит информации мы получили), следовательно, в вольере Б живут оставшиеся 28 обезьян (неверный ответ 3) - после п. 1 можно сделать (неверный) вывод о том, что в вольере А живет 16 обезьян, следовательно, в вольере Б – тоже 16 (неверный ответ 2) Решение (вариант 2, использование формулы Шеннона): Обезьяна-альбинос может жить в вольере А (событие 1) или в вольере Б (событие 2) По формуле Шеннона количество информации в сообщении о произошедшем событии с номером равно , где – вероятность этого события; таким образом, получаем вероятность того, что обезьяна-альбинос живет в вольере А: . У нас не было никакой предварительной информации о том, где живет альбинос, поэтому можно считать, что вероятность определяется количеством обезьян в вольере – если вероятность равна 1/16, то в вольере живет 1/16 часть всех обезьян: 32/16 = 2 обезьяны Поэтому в вольере Б живут все оставшиеся 32 – 2 = 30 обезьян Правильный ответ – 4. Пример 4 В корзине лежат 32 клубка шерсти, из них 4 красных. Сколько бит информации несет сообщение о том, что достали клубок красной шерсти? 1) 2 2) 3 3) 4 4) 32 Решение (вариант 1): Красные клубки шерсти составляют 1/8 от всех, … Поэтому сообщение о том, что первый вынутый клубок шерсти – красный, соответствует выбору одного из 8 вариантов Выбор 1 из 8 вариантов – это информация в 3 бита (по таблице степеней двойки) Правильный ответ – 2. Решение (вариант 2, использование формулы Шеннона): Красные клубки шерсти составляют 1/8 от всех, поэтому вероятность того, что первый вынутый клубок шерсти – красный, равна 1/8 По формуле Шеннона находим количество информации в битах: бита. Правильный ответ – 2. Пример 5 В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 20 автомобильных номеров. 1) 20 байт 2) 105 байт 3) 120 байт 4) 140 байт Решение: Всего используется 26 букв + 10 цифр = 36 символов Для кодирования 36 вариантов необходимо использовать 6 бит, так как , т.е. пяти бит не хватит (они позволяют кодировать только 32 варианта), а шести уже достаточно Таким образом, на каждый символ нужно 6 бит (минимально возможное количество бит) Полный номер содержит 7 символов, каждый по 6 бит, поэтому на номер требуется бита По условию каждый номер кодируется целым числом байт (в каждом байте – 8 бит), поэтому требуется 6 байт на номер ( ), пяти байтов не хватает, а шесть – минимально возможное количество На 20 номеров нужно выделить байт Правильный ответ – 3. Обратить внимание при решении: - может быть неверный ответ 1 (20 байт) сбивает случайное угадывание «в лоб», по исходным данным - можно не обратить внимание на то, что каждый номер кодируется целым числом БАЙТ, получаем неверный ответ 2 ( бит = 105 байт) - можно по невнимательности считать, что каждый СИМВОЛ кодируется целым числом байт, получаем 7 байт на символ и всего 140 байт (неверный ответ 4) - можно «забыть» про цифры, получим всего 26 символов, 5 бит на символ, 35 бит (5 полных байт) на каждый номер и неверный ответ 100 байт (на 20 номеров) Пример 6 Какое наименьшее число символов должно быть в алфавите, чтобы при помощи всевозможных трехбуквенных слов, состоящих из символов данного алфавита, можно было передать не менее 9 различных сообщений? 1) 1 2) 2 3) 3 4) 4 Решение: Здесь используется только одна формула: если алфавит имеет мощность M, то количество всех возможных «слов» длиной N равно В данном случае нужно закодировать 9 сигналов ( ) с помощью трехбуквенных слов ( ) Таким образом, нужно найти наименьшее целое M, такое что (куб числа не меньше 9) Проще всего использовать метод подбора: при получаем (с помощью трех двоичных сигналов можно закодировать только 8 вариантов), но уже при имеем , поэтому нужно брать Таким образом, правильный ответ – 3. Возможные проблемы: - нас интересуют только трехбуквенные слова (одно- и двухбуквенные слова учитывать не нужно) Пример 7 Каждая ячейка памяти компьютера, работающего в троичной системе счисления, может принимать три различных значения (-1, 0, 1). Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина? Решение: Непривычность этой задачи состоит в том, что используется троичная система Фактически мы имеем дело с языком, алфавит которого содержит M=3 различных символа Поэтому количество всех возможных «слов» длиной N равно Для получаем Таким образом, правильный ответ – 81. Обратить внимание при решении: - если не осознать, что используется троичная (а не двоичная!) система, можно «по инерции» получить неправильный ответ Пример 8 В базе данных хранятся записи, содержащие информацию о студентах: - <Фамилия> – 16 символов: русские буквы (первая прописная, остальные строчные), - <Имя> – 12 символов: русские буквы (первая прописная, остальные строчные), - <Отчество> – 16 символов: русские буквы (первая прописная, остальные строчные), - <Год рождения> – числа от 1992 до 2003. Каждое поле записывается с использованием минимально возможного количества бит. Определите минимальное количество байт, необходимое для кодирования одной записи, если буквы е и ё считаются совпадающими. 1) 28 2) 29 3) 46 4) 56 Решение: Очевидно, что нужно определить минимально возможные размеры в битах для каждого из четырех полей и сложить их; Важно! известно, что первые буквы имени, отчества и фамилии – всегда заглавные, поэтому можно хранить их в виде строчных и делать заглавными только при выводе на экран (но нас это уже не волнует) Таким образом, для символьных полей достаточно использовать алфавит из 32 символов (русские строчные буквы, «е» и «ё» совпадают, пробелы не нужны) Для кодирования каждого символа 32-символьного алфавита нужно 5 бит (32 = 25555), поэтому для хранения имени, отчества и фамилии нужно (16 + 12 + 16)•5=220 бит Для года рождения есть 12 вариантов, поэтому для него нужно отвести 4 бита (24 = 16 ≥ 12) Таким образом, всего требуется 224 бита или 28 байт Правильный ответ – 1. жүктеу/скачать 80,27 Kb. Достарыңызбен бөлісу:
|