Вспомним некоторые известные нам факты:
 Множество символов, с помощью которых записывается текст, называется алфавитом. Число символов в алфавите – это его мощность. Формула определения количества информации: N=2 i , где N – мощность алфавита (количество символов), i – количество бит (информационный вес символа). В алфавит мощностью 256 символов можно поместить практически все необходимые символы. Такой алфавит называется достаточным. Т.к. 256 = 28, то вес 1 символа – 8 бит. Единице измерения 8 бит присвоили название 1 байт: 1 байт = 8 бит. Двоичный код каждого символа в компьютерном тексте занимает 1 байт памяти. |
Задачи: 1) Алфавит содержит 32 буквы. Какое количество информации несет одна буква? Дано: Мощность алфавита N = 32
Решение: 1. 32 = 2 5, значит вес одного символа i = 5 бит. Ответ: одна буква несет 5 бит информации. 2) Сообщение, записанное буквами из 16 символьного алфавита, содержит 10 символов. Какой объем информации в битах оно несет? Дано: Мощность алфавита N = 16 текст состоит из 10 символов.
Решение: 1. 16 = 2 4 2. Всего символов 10, значит объем информации 10 * 4 = 40 бит. Ответ: сообщение несет 40 бит информации (8 байт). 3) Информационное сообщение объемом 300 бит содержит 100 символов. Какова мощность алфавита? Дано: Объем сообщения = 300 бит текст состоит из 100 символов
Решение: 1. Определим вес одного символа: 300 / 100 = 3 бита. 2. Мощность алфавита определяем по формуле: 2 3 = 8 Ответ: мощность алфавита N = 8. |
Единицы измерения информации.
В 1 бит можно записать один двоичный
символ.
1 байт = 8 бит.
В кодировке ASCII в один байт можно записать один
256 символьный код.
В кодировке UNICODE один 256 символьный код занимает в
памяти два байта.
1 килобайт = 1024 байт
1 мегабайт = 1024 килобайт
1
гигабайт = 1024 мегабайт
1 терабайт = 1024 гигабайт
Формула Хартли 2 i = N где i– количество информации в битах, N –
неопределенность
Таблица степеней двойки, которая показывает сколько информации можно
закодировать с помощью i – бит
i
0 1 2 3 4 5 6 7 8 9 10
N=2 i
1 2 4 8 16 32 64 128 256 512 1024
Чтобы вычислить информационный объем
сообщения надо количество символов умножить на число бит, которое требуется для
хранения одного символа
Например: двоичный текст 01010111 занимает в памяти
8 бит
Этот же текст в кодировке ASCII занимает 8 байт или 64 бита
Этот
же текст в кодировке UNICODE занимает 16 байт или 128 бит.
Не забывайте, что
пробелы надо тоже считать за символы поскольку они также набираются на
клавиатуре и хранятся в памяти.
Мощность алфавита – это количество символов
в алфавите или неопределенность из формулы Хартли.
Информационный вес одного
символа – это значение i из формулы Хартли.
Отсюда можно сделать вывод, что
не существует алфавита, состоящего из одного символа, поскольку тогда
информационный вес этого символа был бы равен 0.
Источник: http:// festival. 1september.ru/ articles/ 604157/
Символ это совокупность бит, определяем битовую скорость
В статье поговорим про то, что такое бит и символ. И решим задачу на нахождение битовой скорости, если известна символьная скорость.
p, blockquote 1,0,0,0,0 —>
p, blockquote 2,0,1,0,0 —>
Бит (единица информации) это минимальный объем информации, который представляется одним из двух значений: 0 или 1.
p, blockquote 3,0,0,0,0 —>
Символ – это сгруппированная совокупность битов, предназначенная для одновременной передачи. В один символ помещается несколько бит информации.
p, blockquote 4,0,0,0,0 —>
Число возможных значений символа: М=2^k т.е. сколько разных значений символ может принимать. где k – количество бит в символе.
p, blockquote 5,1,0,0,0 —>
Если символ содержит только один бит, то такой способ передачи называют бинарным, либо двоичным. Различают соответственно битовую (бит/с) и символьную скорость (сим./с). Символьную скорость также называют скоростью манипуляции, измеряемой в бодах. Бод – единица измерения символьной скорости: 1 Бод = 1сим./с
p, blockquote 6,0,0,0,0 —>
ЗАДАЧА: Найти битовую скорость.
p, blockquote 7,0,0,1,0 —>
В таблице представлено несколько видов модуляций. Второй столбик (Алфавит), говорит о том, сколько значений символов можно принимать. Дана символьная скорость, нужно найти битовую.
p, blockquote 8,0,0,0,0 —>
- 2-ФМн, символьная скорость 1200 бод. Вопрос, сколько у нас бит на символ приходится? У одного бита два возможных состояния 1 и 0. Мы одним битом можем закодировать символ целиком. Если в одном символе содержится один бит, символьная и битовая скорости будут равны, т.е. 1200 бит/с.
- 4-ФМн, здесь в одном символе содержится? Сколькими битами мы можем закодировать 4 состояния? Можно проверять так, 2 в какой степени даст 4? Во 2 ! Соответственно скорость будет равна 200 . (100*2)
- 8-ФМн, 2 в какой степени дает 8? в 3! Следовательно, 3*300=900 бит/с.
- 16-КАМ, 4 бит на символ, 4*600=2400.
Про виды модуляций вы можете почитать в статье про амплитудную и фазовую манипуляцию.
Набор символов знаковой системы (алфавит) можно рассматривать как различные возможные состояния (события).
Тогда, если считать, что появление символов в сообщении равновероятно, количество возможных событийN можно вычислить как N=2i
Количество информации в сообщении I можно подсчитать умножив количество символов K на информационный вес одного символа i
Итак, мы имеем формулы, необходимые для определения количества информации в алфавитном подходе:
Если к этим задачам добавить задачи на соотношение величин, записанных в разных единицах измерения, с использованием представления величин в виде степеней двойки мы получим 9 типов задач.
Рассмотрим задачи на все типы. Договоримся, что при переходе от одних единиц измерения информации к другим будем строить цепочку значений. Тогда уменьшается вероятность вычислительной ошибки.
Задача 1. Получено сообщение, информационный объем которого равен 32 битам. чему равен этот объем в байтах?
Решение: В одном байте 8 бит. 32:8=4
Ответ: 4 байта.
Задача 2. Объем информацинного сообщения 12582912 битов выразить в килобайтах и мегабайтах.
Решение: Поскольку 1Кбайт=1024 байт=1024*8 бит, то 12582912:(1024*8)=1536 Кбайт и
поскольку 1Мбайт=1024 Кбайт, то 1536:1024=1,5 Мбайт
Ответ:1536Кбайт и 1,5Мбайт.
Задача 3. Компьютер имеет оперативную память 512 Мб. Количество соответствующих этой величине бит больше:
1) 10 000 000 000бит 2) 8 000 000 000бит 3) 6 000 000 000бит 4) 4 000 000 000бит Решение: 512*1024*1024*8 бит=4294967296 бит.
Ответ: 4.
Задача 4. Определить количество битов в двух мегабайтах, используя для чисел только степени 2.
Решение: Поскольку 1байт=8битам=23битам, а 1Мбайт=210Кбайт=220байт=223бит. Отсюда, 2Мбайт=224бит.
Ответ: 224бит.
Задача 5. Сколько мегабайт информации содержит сообщение объемом 223бит?
Решение: Поскольку 1байт=8битам=23битам, то
223бит=223*223*23бит=210210байт=210Кбайт=1Мбайт.
Ответ: 1Мбайт
Задача 6. Один символ алфавита “весит” 4 бита. Сколько символов в этом алфавите?
Решение:
Дано:
| i=4 | По формуле N=2i находим N=24, N=16 |
| Найти: N – ? |
Ответ: 16
Задача 7. Каждый символ алфавита записан с помощью 8 цифр двоичного кода. Сколько символов в этом алфавите?
Решение:
Дано:
| i=8 | По формуле N=2i находим N=28, N=256 |
| Найти:N – ? |
Ответ: 256
Задача 8. Алфавит русского языка иногда оценивают в 32 буквы. Каков информационный вес одной буквы такого сокращенного русского алфавита?
Решение:
Дано:
| N=32 | По формуле N=2i находим 32=2i, 25=2i,i=5 |
| Найти: i– ? |
Ответ: 5
Задача 9. Алфавит состоит из 100 символов. Какое количество информации несет один символ этого алфавита?
Решение:
Дано:
| N=100 | По формуле N=2i находим 32=2i, 25=2i,i=5 |
| Найти: i– ? |
Ответ: 5
Задача 10. У племени “чичевоков” в алфавите 24 буквы и 8 цифр. Знаков препинания и арифметических знаков нет. Какое минимальное количество двоичных разрядов им необходимо для кодирования всех символов? Учтите, что слова надо отделять друг от друга!
Решение:
Дано:
| N=24+8=32 | По формуле N=2i находим 32=2i, 25=2i,i=5 |
| Найти: i– ? |
Ответ: 5
Задача 11. Книга, набранная с помощью компьютера, содержит 150 страниц. На каждой странице — 40 строк, в каждой строке — 60 символов. Каков объем информации в книге? Ответ дайте в килобайтах и мегабайтах
Решение:
Дано:
| K=360000 | Определим количество символов в книге 150*40*60=360000. Один символ занимает один байт. По формуле I=K*iнаходим I=360000байт 360000:1024=351Кбайт=0,4Мбайт |
| Найти: I– ? |
Ответ: 351Кбайт или 0,4Мбайт
Задача 12. Информационный объем текста книги, набранной на компьютере с использованием кодировки Unicode, — 128 килобайт. Определить количество символов в тексте книги.
Решение:
Дано:
| I=128Кбайт,i=2байт | В кодировке Unicode один символ занимает 2 байта. Из формулыI=K*i выразимK=I/i,K=128*1024:2=65536 |
| Найти: K– ? |
Ответ: 65536
Задача 13.Информационное сообщение объемом 1,5 Кб содержит 3072 символа. Определить информационный вес одного символа использованного алфавита
Решение:
Дано:
| I=1,5Кбайт,K=3072 | Из формулы I=K*i выразимi=I/K,i=1,5*1024*8:3072=4 |
| Найти: i– ? |
Ответ: 4
Задача 14.Сообщение, записанное буквами из 64-символьного алфавита, содержит 20 символов. Какой объем информации оно несет?
Решение:
Дано:
| N=64, K=20 | По формуле N=2i находим 64=2i, 26=2i,i=6. По формуле I=K*i I=20*6=120 |
| Найти: I– ? |
Ответ: 120бит
Задача 15. Сколько символов содержит сообщение, записанное с помощью 16-символьного алфавита, если его объем составил 1/16 часть мегабайта?
Решение:
Дано:
| N=16, I=1/16 Мбайт | По формуле N=2i находим 16=2i, 24=2i,i=4. Из формулы I=K*i выразим K=I/i, K=(1/16)*1024*1024*8/4=131072 |
| Найти: K– ? |
Ответ: 131072
Задача 16. Объем сообщения, содержащего 2048 символов,составил 1/512 часть мегабайта. Каков размер алфавита, с помощью которого записано сообщение?
Решение:
Дано:
| K=2048,I=1/512 Мбайт | Из формулы I=K*i выразим i=I/K, i=(1/512)*1024*1024*8/2048=8. По формулеN=2iнаходим N=28=256 |
| Найти: N– ? |
Ответ: 256
Задачи для самостоятельного решения:
- Каждый символ алфавита записывается с помощью 4 цифр двоичного кода. Сколько символов в этом алфавите?
- Алфавит для записи сообщений состоит из 32 символов, каков информационный вес одного символа? Не забудьте указать единицу измерения.
- Информационный объем текста, набранного на компьюте¬ре с использованием кодировки Unicode (каждый символ кодируется 16 битами), — 4 Кб. Определить количество символов в тексте.
- Объем информационного сообщения составляет 8192 бита. Выразить его в килобайтах.
- Сколько бит информации содержит сообщение объемом 4 Мб? Ответ дать в степенях 2.
- Сообщение, записанное буквами из 256-символьного ал¬фавита, содержит 256 символов. Какой объем информации оно несет в килобайтах?
- Сколько существует различных звуковых сигналов, состоящих из последовательностей коротких и длинных звонков. Длина каждого сигнала — 6 звонков.
- Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 20 до 100%, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатом наблюдений.
- Скорость передачи данных через ADSL-соединение равна 512000 бит/с. Через данное соединение передают файл размером 1500 Кб. Определите время передачи файла в секундах.
- Определите скорость работы модема, если за 256 с он может передать растровое изображение размером 640х480 пикселей. На каждый пиксель приходится 3 байта. А если в палитре 16 миллионов цветов?
Тема определения количества информации на основе алфавитного подхода используется в заданиях А1, А2, А3, А13, В5 контрольно-измерительных материалов ЕГЭ.
Здравствуйте! С вами Елена TeachYOU, и сегодня мы разберем задачи 11 из ЕГЭ по информатике. Задачи несложные, но почему-то у многих учеников с ними возникают проблемы.
Что такое равномерное кодирование
Для того, чтобы работать с какими-то объектами с помощью компьютера, необходимо их закодировать. Так как подавляющее большинство современных ЭВМ использует двоичную логику, разумно кодировать объекты с использованием двоичного кодирования.
Двоичное кодирование можно разделить на равномерное (когда кодовые слова, или коды, имеют одинаковую длину), и неравномерное (когда длина кодовых слов разная). Тема неравномерного кодирования поднимается в 4 задании ЕГЭ, можете посмотреть материал по нему в этой статье. Там разобраны примеры с разными вариантами кодирования. Если вам все еще непонятно, чем равномерное кодирование отличается от неравномерного, то перед тем, как читать материал по 11 заданию дальше, советую сначала просмотреть материал по ссылке выше.
Перевод битов в байты и далее
Прежде чем двигаться дальше, напомню правила перевода между единицами измерения информации. Основное:
- 1 байт = 8 бит
- 1 Кбайт = 1024 байт = 2^10 байт = 2^13 бит
- 1 Мбайт = 1024 Кбайт = 2^10 Кбайт = 2^23 бит
1. Сначала переводим 5 Мбайт в Кбайты, домножая на 1024: 5 Мбайт = 5 * 1024 Кбайт.
2. Затем переводим Кбайты в байты домножением на 1024: 5 * 1024 Кбайт = 5 * 1024 * 1024 байт.
3. Для перевода в биты домножаем на 8: 5 * 1024 * 1024 байт = 5 * 1024 * 1024 * 4 бит.
Переведем 24576 бит в килобайты:
1. Делим на 8, чтобы перевести в байты: 24576 / 8 = 3072 (байт).
2. Делим на 1024, чтобы перейти к Кбайтам: 3072 / 1024 = 3 (Кбайт).
Что нужно знать про равномерное двоичное кодирование
Кодирование равномерное => все кодовые слова имеют одинаковую, минимально возможную, длину. Кодирование двоичное => кодовые слова состоят только из 0 и 1.
Сколько объектов можно закодировать, используя кодовые слова имеют длины i ?
Например, буква А может кодироваться кодовым словом 01101. В нем пять знаков (0 или 1). Говорят, что кодовое слово 01101 состоит из пяти бит. Бит – это ячейка, принимающая значение 0 или 1 (тире или точка, вкл или выкл и пр.).
Тогда кодовое слово 0110 состоит из 4 бит, слово 110011 – из 6 бит и т.д.
Посмотрим, сколько разных кодовых слов можно составить, если брать кодовые слова определенной длины (здесь нам поможет теория по теме “Комбинаторика” для 8 номера).
- Кодовые слова длины 1 – это 0 и 1. Их два (каждое занимает 1 бит).
- Кодовые слова длины 2 – это 00, 01, 10 и 11. Их четыре (каждое занимает 2 бит).
- Кодовые слова длины 3 я перечислять не буду. Их количество равно 2*2*2 = 2^3 = 8 (если непонятно, загляните в материал по комбинаторике). Каждое кодовое слово занимает 3 бита.
- ….
- Кодовые слова длины i – их 2^i. Каждое занимает i бит.
Получается, что, если для кодирования мы выберем кодовые слова длины i (i-битные), то сможем закодировать 2^i объектов.
Если в сообщении используется N символов, сколько бит нужно для кодирования каждого символа?
Количество i-битных кодовых слов равно 2^i.
Похоже, что, нужно подобрать такое i, чтобы N = 2^i.
Но на практике не всегда число N является степенью двойки. Поэтому для кодирования N объектов нужно взять такое минимальное i, чтобы выполнялось условие N <= 2^i.
Например:
- N = 14: 14 <= 16 = 2^4. Получается, что при кодировании 14 объектов с использованием равномерного двоичного кодирования на каждый объект будет приходиться 4 бита.
- N = 250: 250 <= 256 = 2^8 => 8 бит на объект.
- N = 2050: 2050 <= 4096 = 2^12 => 12 бит на объект.
Рассмотрим задачи 11 из ЕГЭ
Задача 1 (номер 1964 с компегэ)
При регистрации в компьютерной системе каждому объекту сопоставляется идентификатор, состоящий из 15 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом объекте отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно идентификатора, для каждого объекта в системе хранятся дополнительные сведения, для чего отведено 24 байта на один объект.
Определите объём памяти (в байтах), необходимый для хранения сведений о 20 объектах. В ответе запишите только целое число – количество байт.
Из задачи следует, что нужно сохранить данные о 20 объектах. Для каждого из них хранится идентификатор (его информационный вес нужно вычислить) и дополнительные сведения (известны, 24 байта на один объект).
Начнем с вычисления количества байт, которое занимает один идентификатор.
Длина идентификатора 15 символов, а мощность алфавита равна восьми. Вспоминаем основную формулу информатики: N = 2^i, где N – количество кодируемых равномерным кодированием объектов, i – количество бит, которое приходится на один объект. N = 8 (нужно закодировать все символы из набора, поэтому N = мощности алфавита). Из 8 = 2^i находим i=3 бита. Каждый символ кодируется 3 битами, а идентификатор состоит из 15 символов. Получается, на один идентификатор приходится 15 * 3 = 45 бит = 5,625 байт.
Обращаем внимание, что в задаче говорится, что для хранения сведений о каждом объекте отведено одинаковое и минимально возможное целое число байт. Необходимо округлить 5,625 байт до целого значения. Но в большую или меньшую сторону?
Если округлим в меньшую, то получим 5 байт = 40 бит. Но для хранения идентификатора нужно 45 бит! 45 бит не помещаются в “коробочку” из 5 байт. Значит, нужно округлять в большую. Итого, на идентификатор приходится 6 байт.
Для вычисления информационного объема, необходимого для хранения сведений об одном объекте, найдем сумму байт, приходящихся на идентификатор и на дополнительные сведения:
6 + 24 = 30 (байт) – на 1 объект.
Вычислим объем информации для хранения сведений о 20 объектах:
30 (байт) * 20 (объектов) = 600 (байт).
Задача 2 (номер 212 с компегэ)
Для регистрации на сайте необходимо продумать пароль, состоящий из 9 символов. Он может содержать десятичные цифры, строчные или заглавные буквы латинского алфавита (алфавит содержит 26 букв) и символы из перечисленных: «.», «$», «#», «@», «%», «&». В базе данных для хранения сведения о каждом пользователе отведено одинаковое и минимальное возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственного пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт одинаковое для каждого пользователя. Для хранения сведений о двадцати пользователях потребовалось 500 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе. В ответе запишите только целое число – количество байт.
Сайт хранит данные о 20 пользователях. Они занимают 500 байт. Для каждого пользователя хранятся пароль (его информационный объем нужно вычислить) и дополнительные сведения (эту величину нужно найти и взять в качестве ответа).
Начнем с поиска количества байт, приходящихся на одного пользователя:
500 (байт) / 20 (польз.) = 25 (байт на 1 польз.)
Разберемся с паролем. Мощность алфавита символов, которые используются для его записи:
N = 10 (цифр) + 26 (строчных букв) + 26 (заглавных букв) + 6 (символов «.», «$», «#», «@», «%», «&») = 68 (символов).
Сколькими битами можно закодировать каждый из 78 символов при использовании равномерного кодирования?
68 <= 2^i, i = 7 (бит).
Тогда пароль занимает
7 (бит) * 9 (символов) = 63 (бит) = 8 (байт).
Для одного пользователя хранится пароль (8 байт) и доп. сведения. Всего на пользователя приходится 25 байт. Тогда доп. сведения занимают
25 – 8 = 17 (байт).
Задача 3 (номер 463 с компегэ)
Очень люблю эту задачу авторства Евгения Джобса за нацеленность на понимание темы
Автомобильный номер состоит из одиннадцати букв русского алфавита A, B,C, E, H, K, M, O, P, T, X и десятичных цифр от 0 до 9. Каждый номер состоит из двух букв, затем идет 3 цифры и еще одна буква. Например, АВ901С.
В системе каждый такой номер кодируется посимвольно, при этом каждая буква и каждая цифра кодируются одинаковым минимально возможным количеством бит.
Укажите, сколько бит на один номер можно сэкономить, если кодировать с помощью одинакового минимально возможного количества бит каждую из трех групп – первые две буквы, три цифры и последняя буква.
В этой задаче есть “до” и “после”.
“До”: каждая буква и каждая цифра кодируются отдельно.
“После”: кодируются отдельно первые две буквы, три цифры и последняя буква.
Разберемся, сколько бит занимал автомобильный номер при выборе способа кодирования “до”.
- Буквы: N = 11 <= 16 = 2^4 => i = 4.
- Цифры: N = 10 <= 16 = 2^4 => i = 4.
- Весь номер состоит их трех цифр и трех букв, это 3 (буквы) * 4 (бита) + 3 (цифры) * 4 (бита) = 24 (бит на один номер)
Как кодируем номер “после”?
- Первые две буквы. Букв 11. Количество пар букв (АА, АВ, … , ХХ) равно 11*11 = 121. Нашли объекты – это пары букв. Их количество N = 121 <= 128 = 2^7 => i=7 бит. Раньше каждую букву мы кодировали 4 битами и две буквы занимали 8 бит. А теперь 7. Э – экономия!
- Три цифры. Цифр 10. Количество троек цифр (000, 001, … , 999) равно 10*10*10 = 1000. В этом случае кодируемые объекты – это тройки цифр. N = 1000 <= 1024 = 2^10 => i = 10 бит. “До” каждую цифру кодировали 4 битами, три цифры занимали 12 бит. А сейчас 10. И здесь сэкономили.
- Последняя буква. N = 11 <= 16 = 2^4 => i=4. Тут ничего не изменилось: “до” кодировали объекты-буквы и здесь поступили так же.
- Количество бит на номер “после”: 7 + 10 + 4 = 21 (бит).
Итого сэкономили 24 – 21 = 3 (бита).
Какие еще задачи посмотреть, чтобы закрепить материал?
Сайт kompege.ru покорил мое сердце, и теперь я считаю себя его амбассадором)
Если вы только знакомитесь с 11 номерами, решайте любые задачи (на сайте компегэ их можно отсортировать по сложности, начните с простых).
Для более продвинутых настоятельно советую прорешать задачи из списка ниже, так как в каждой есть свои тонкости.
Номера 11: 4468, 4323, 2119, 5433.
