сколько бит нужно отвести на кодирование положительного двузначного числа

Сколько бит нужно отвести на кодирование двузначного десятеричного числа? 1. 6 2. 7 3. 8 4. 9

Если не прогуливать занятия, то вероятность сдать сессии на «хорошо» и «отлично» равна 0,7. Найдите энтропию системы.

Ответы

Формально, количество бит для представления значений определяется двоичным логарифмом от числа значений. Здесь число десятичных цифр равно 10, значит, число возможных значений равно 10. Осталось вычислить log₂10 — получится приблизительно 3,322 бита.

Иными словами, спросите себя: в какую степень нужно возвести число 2 чтобы получить 10? Правильный ответ: число 2 в степени 3,322 приблизительно равно 10.

Если вам трудно воспринять тот факт, что число бит оказалось нецелым числом, округлите в большую сторону — получится 4 бита. Но тогда и вопрос нужно было начать словами: «Какое минимальное количество бит потребуется, чтобы. »

Нецелое число бит может иметь практический смысл в вычислениях. Например, у вас есть цветное изображение, где каждый пиксель представлен смешением красного, зелёного и синего сигнала, причём для каждого сигнала возможны 10 значений яркости. Сколько бит потребуется для представления одного пикселя? Умножаем 3,322 бита на 3 сигнала — получим 9,966 бит на пиксель. На практике вы будете использовать для представления пикселя не менее 10 бит, округлив до целого числа бит.

Но было бы неправильно сказать, что для пикселя требуется как минимум 12 бит, потому что якобы для 10 значений яркости сигнала нужно целых 4 бита.

Источник

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

У Александра Романовича 12345 клонов. Каждому клону присвоен свой номер. Какое минимальное количество бит потребуется для кодирования номера одного клона?

Бит может принимать 2 значения, для кодирования номера потребуется такое количество бит, чтобы можно было закодировать 12345 символов.

13 бит: \(2^ <13>= 8192 — не подходит, слишком мало символов можно закодировать.

14 бит: \(2^ <14>= 16384 \geq 12345\) — подходит, можно закодировать достаточное количество символов.

Значит для кодирования номера одного клона потребуется 14 бит.

В лотерее разыгрывается 500 билетов. Какое минимальное количество бит потребуется для кодирования номера одного билета?

Бит может принимать 2 значения, для кодирования номера потребуется такое количество бит, чтобы можно было закодировать 500 символов.

8 бит: \(2^8 = 256 — не подходит, слишком мало символов можно закодировать.

9 бит: \(2^9 = 512 \geq 500\) — подходит, можно закодировать достаточное количество символов.

Значит для кодирования номера одного билета потребуется 9 бит.

В базе данных есть 30000 записей. Какое минимальное количество бит потребуется для кодирования номера одной записи?

Бит может принимать 2 значения, для кодирования номера потребуется такое количество бит, чтобы можно было закодировать 30000 символов.

14 бит: \(2^ <14>= 16384 — не подходит, слишком мало символов можно закодировать.

15 бит: \(2^ <15>= 32768 \geq 30000\) — подходит, можно закодировать достаточное количество символов.

Значит для кодирования номера одной записи потребуется 15 бит.

В магазине продаётся 24 рубашки разных цветов. Какое минимальное количество бит потребуется для кодирования цвета одной рубашки?

Бит может принимать 2 значения, для кодирования цвета потребуется такое количество бит, чтобы можно было закодировать 24 символа.

4 бит: \(2^4 = 16 — не подходит, слишком мало символов можно закодировать.

5 бит: \(2^5 = 32 \geq 24\) — подходит, можно закодировать достаточное количество символов.

Значит для кодирования цвета одной рубашки потребуется 5 бит.

Калькулятор может хранить числа от 0 до 1000 включительно. Какое минимальное количество бит потребуется для кодирования одного из этих чисел?

Бит может принимать 2 значения, для кодирования одного из чисел потребуется такое количество бит, чтобы можно было закодировать 1001 символ (ведь от 0 до 1000 включительно всего 1001 число).

9 бит: \(2^9 = 512 — не подходит, слишком мало символов можно закодировать.

10 бит: \(2^ <10>= 1024 \geq 1001\) — подходит, можно закодировать достаточное количество символов.

Значит для кодирования одного из чисел потребуется 10 бит.

Друг записал 70 чисел, неподходящих врагам. Какое минимальное количество бит потребуется для кодирования одного из этих чисел?

Бит может принимать 2 значения, для кодирования одного из чисел потребуется такое количество бит, чтобы можно было закодировать 70 символов.

6 бит: \(2^6 = 64 — не подходит, слишком мало символов можно закодировать.

7 бит: \(2^7 = 128 \geq 70\) — подходит, можно закодировать достаточное количество символов.

Значит для кодирования одного из чисел потребуется 7 бит.

Марафонцы решили совместить два алфавита и закодировать буквы получившегося алфавита. В первом из них 26 различных букв, а во втором 20 различных букв. Какое минимальное количество бит потребуется для кодирования одной из букв получившегося алфавита?

После совмещения алфавитов, в новом получилось 26 + 20 = 46 различных букв. Бит может принимать 2 значения, для кодирования одного из чисел потребуется такое количество бит, чтобы можно было закодировать 46 символов.

5 бит: \(2^5 = 32 — не подходит, слишком мало символов можно закодировать.

6 бит: \(2^6 = 64 \geq 46\) — подходит, можно закодировать достаточное количество символов.

Значит для кодирования одного из чисел потребуется 6 бит.

Источник

Кодирование положительных целых чисел

Положительные целые числа кодиру­ются согласно правилам двоичной арифметики. Числа в диапазоне от 0 до 255 записываются одним байтом. Порядок пре­образования числа в двоичную форму рас­смотрим на примере числа 99.

1. Число раскладывается в ряд по степе­ням двойки (128, 64, 32,16, 8, 4, 2 и 1),
например:

2. Слагаемые записываются с помощью степенных выражений:

99 = 2 6 + 2 5 + 2 1 + 2°

3. Показатели степеней указывают на то, какой бит в байте должен быть включён (равен 1). То есть в нашем примере включены должны быть биты: шестой, пятый, первый и нуле­вой. Номера битов в байте отсчитыва­ются от 0 до 7, а сами биты обознача­ются от А₀ до А₇. (Здесь буква «А» обозначает слово «адрес».)

Числа в диапазоне от 0 до 65535 записы­ваются двумя байтами. Пара взаимосвя­занных байтов (16 бит) в информатике на­зывается словом. Его информационным значением являются 65 536 (2 16 ) различи­мых состояний.

Для записи более крупных целых положи­тельных чисел используют двойное слово(32 бита) или учетверённое слово(64 бита). Так, например, учетверённым словом можно записать целые числа в диапазоне от 0 до 18 446 744 073 709 551 615.

Кодирование целых чисел со знаком

· информационным содержанием байта становятся 255 различимых чисел вместо 256 (то есть одно значение куда-то пропадает);

· мы получаем два различимых нуля: «плюс ноль» и «минус ноль» (вот куда пропало недостающее значение). Эти обстоятельства «сбивают» работу вычислительных систем и не позволяют использовать простое двоичное представ­ление для записи целых чисел со знаком. Для таких чисел придумана специальная форма записи, которая называется двоич­ной дополнительной арифметикой.Запись числа в этой форме осуществляется в три приёма.

1. Сначала записывается целое число без знака (как будто оно положительное).

2. Если число отрицательное, то оно ин­вертируется (каждый бит числа меняется на противоположный).

3. Затем инверсное число дополняется (значение младшего бита увеличивается на единицу).

Интересно отметить, что старший бит байта указывает на знак числа. Если он равен нулю, то число положительное, а если он равен 1, то отрицательное.

Кодирование действительных чисел

Запись действительного числа в двоич-ной форме выполняется в несколько эта­пов. Рассмотрим для примера запись числа 29,125.

1. Сначала число преобразуется в двоичную форму. При этом целая и дробная части преобразуются порознь, а потом объединяются.

29, 125

Для перевода чисел из системы исчисления с основой p в систему исчисления с основой q с использованием арифметики старой системы исчисления с основой p нужно:

· для перевода целой части:

последовательно число, записанное в системе основой делить на основу новой системы исчисления, выделяя остатки. Последние записанные в обратном порядке, будут образовывать число в новой системе исчисления;

· для перевода дробной части:

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

3. Записываем действительное число по правилам двоичной дополнительной арифметики. Первый байт последова­тельности выражает порядок со зна­ком. Его старший бит указывает на знак порядка. Следующие байты по­следовательности выражают мантис­су со знаком. Самый левый бит ука­зывает на знак мантиссы.

Кодирование текстов

Для текстов применяется цифровое (табличное) кодирование. Имеется некая таблица, связывающая символ определён­ного языка с его порядковым номером в этой таблице. Понятно, что результат ко­дирования зависит от того, какая именно таблица кодирования была использована, а таблицы эти могут быть очень и очень раз­ными. Они закреплены международными, национальными и корпоративными стан­дартами.

ТАБЛИЦА КОДИРОВАНИЯ ASCII

Наибольшее распространение в мире имеет система кодирования ASCII. Её название расшифровывается как American Standard Code for Information Interchange — стан­дартный код внутреннего информацион­ного обмена США. Её ввёл в действие На­циональный институт стандартов США (ANSI, American National Standard Institute). Строго говоря, таблица ASCII предна­значена не для восьмиразрядного, а для семиразрядного кодирования 128 различ­ных символов. Этого достаточно для пред­ставления строчных и прописных букв ан­глийского алфавита, знаков препинания, цифр и знаков математических действий. В таблице ещё остаётся 32 кода (от 0 до 31), которые не представляются никакими символами, почему их иногда называют непечатаемыми знаками. Они служат для управления техническими устройствами.

Так, например, код 10 вызывает на печа­тающем устройстве протяжку бумаги на одну строку и называется кодом подачи строки, а код 13 вызывает возврат печата­ющей головки в крайнее левое положение и называется кодом возврата каретки. Соответственно, пара этих кодов (10, 13), переданная принтеру, вызывает печать но­вой строки документа.

СХЕМЫ 8-РАЗРЯДНОГО КОДИРОВАНИЯ

При 8-разрядном кодировании на запись символа отводится байт, имеющий 256 различимых состояний. Это позволяет коди­ровать двуязычные символьные наборы. Как правило, одним из языков является английский, а вторым — какой-либо наци­ональный европейский (русский, немец­кий, французский, испанский и другие). Англоязычную часть размещают в нижней части таблицы (коды от 0 до 127), а нацио­нальную часть — в верхней (коды от 128 до 255). Нижнюю часть делают совпадающей с таблицей ASCII, а верхнюю часть государства, международные организации и отдельные корпорации закрепляют в собственных стандартах.

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

Источник

ГДЗ по информатике 10 класс учебник Босова параграф 2

1. Что такое неопределённость знания о результате какого-либо события? Приведите пример.

Неопределенность знания о результате некоторого события (броса­ние монеты или игрального кубика, вытаскивание жребия и др.) — это количество возможных результатов.

2. В чём состоит суть содержательного подхода к определению количества информации? Что такое бит с точки зрения содержательного подхода?

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

Сообщение, уменьшающее неопределенность знания в два раза, несет 1 бит информации. Как пример содержит знание: да или нет

3. Паролем для приложения служит трёхзначное число в шестнадцатеричной системе счисления. Возможные варианты пароля: 189 101 654 FFE 123 А41 880 391 110 125 Ответ на какой вопрос (см. ниже) содержит 1 бит информации?

1) Это число записано в двоичной системе счисления?

2) Это число записано в четверичной системе счисления?

3) Это число может быть записано в восьмеричной системе счисления?

4) Это число может быть записано в десятичной системе счисления?

5) Это число может быть записано в шестнадцатеричной системе счисления?

4. При угадывании целого числа в некотором диапазоне было получено 5 бит информации. Каковы наибольшее и наименьшее числа этого диапазона?

Это бит в пятой степени. 2^5 = 32, если берем целые неотрицательные числа, то диапазон определен от 0 до 31, наименьшее и наибольшие числа

5. Какое максимальное количество вопросов достаточно задать вашему собеседнику, чтобы точно определить день и месяц его рождения?

Два вопроса: Какой месяц? Какой день месяца?

6. В чём состоит суть алфавитного подхода к измерению информации? Что такое бит с точки зрения алфавитного подхода?

Алфавитный подход позволяет вычислить количество информации, содержащейся в тексте, сложив информационные объёмы каждого символа, при этом содержание текста не учитывается.

7. Закодируйте фразу «ALL IN GOOD TIME» кодом Бодо и восьмиразрядным компьютерным кодом. Сравните полученные информационные объёмы текста.

010000010100110001001100 0100100101001110 01000111010011110100111101000100 01010100

(I=K*i, K=104 символов, i= 8 бит,I= 104*8=832)

8. Какие единицы используются для измерения объёма информации, хранящейся на компьютере?

Бит, байт, килобайт, мегабайт, гигабайт, терабайт.

9. Объём сообщения, содержащего 11 264 символа, равен 11 Кбайт. Определите максимальную мощность алфавита, который мог быть использован для кодирования этого сообщения? Какова минимальная мощность алфавита, использование которого привело к такому же информационному объёму закодированного сообщения?

90112 = 11264 * i => i = 8

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

Надо найти минимальное b, чтобы N было больше 750.

Значит, минимальное кол-во бит, при помощи которого можно записать коды 750 учащихся b = 10.

Соответственно информационный объем сообщения о кодах 180 учащихся = 180 * 10 = 1800 бит = (1800 / 8) байт = 225 байт

11. В школьной базе данных каждый ученик получил идентификатор, состоящий ровно из б символов. В качестве символов используются все заглавные буквы русского алфавита, кроме «Ё», «Ы», «Ъ» и «Ь», а также все десятичные цифры за исключением цифры 0. Каждый такой идентификатор в информационной системе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Определите объём памяти, необходимый для хранения в этой системе 180 идентификаторов учащихся начальных классов. Ответ выразите в килобайтах.

Общее количество символов для записи идентификатора = 29+9=38
Для кодирования одного символа необходимо log(2)38 ≈ 6 бит.
Для записи одного идентификатора требуется 6*6 бит = 36 бит = 36/8 байт ≈ 5 байт
Для хранения 180 идентификаторов потребуется 5*180 байт = 900 байт = 900/1024 Кбайт ≈ 0,9 Кбайт

12. В ходе телевизионного шоу проводится СМС-голосование: каждый телезритель отдаёт свой голос за одного из 12 артистов-участников шоу, отправляя сообщение с его номером. Голос каждого телезрителя, отданный за того или иного участника, кодируется одинаковым и минимально возможным количеством бит и сохраняется для подведения итогов. За время телевизионного шоу в голосовании приняли участие 163 840 зрителей. Определите объём сохранённой информации о голосовании и выразите его в килобайтах.

13. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 6 символов и содержащий только символы из шестибуквенного набора А, В, С, D, Е, F. Для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей и все символы кодируются одинаковым и минимально возможным количеством бит. Кроме собственно пароля для каждого пользователя в системе хранятся дополнительные сведения, занимающие 15 байт. Определите объём памяти в байтах, необходимый для хранения сведений о 120 пользователях.

2^2 = 4; 2^3 = 8. Значит 3 бит памяти достаточно для кодировки 1 символа.

Всего символов 6. 6*3 = 18. 18/8 = 3 (округляем до целого) байт нужно для сохранения пароля.

3+15 = 18 байт для кодировки информации про 1 пользователя

Источник

Сколько бит нужно отвести на кодирование положительного двузначного числа

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

· с помощью K бит можно закодировать Q=2 k различных вариантов (чисел)

· таблица степеней двойки, она же показывает, сколько вариантов Q можно закодировать с помощью K бит:

· при измерении количества информации принимается, что в одном байте 8 бит, а в одном килобайте (1 Кбайт) – 1024 байта, в мегабайте (1 Мбайт) – 1024 Кбайта [i]

· чтобы найти информационный объем сообщения (текста) I, нужно умножить количество символов (отсчетов) N на число бит на символ (отсчет) K: I=N*K

· две строчки текста не могут занимать 100 Кбайт в памяти

· мощность алфавита M – это количество символов в этом алфавите

· если алфавит имеет мощность M, то количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) равно Q=M N ; для двоичного кодирования (мощность алфавита M – 2 символа) получаем известную формулу: Q=2 N

Пример задания:

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

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

Определите объём памяти, который занимает хранение 60 паролей.

1) 540 байт 2) 60 0 байт 3) 66 0 б ай т 4) 720 байт

1) согласно условию, в пароле можно использовать 10 цифр (0..9) + 12 заглавных букв местного алфавита + 12 строчных букв, всего 10 + 12 + 12 = 34 символа

2) для кодирования 34 символов нужно выделить 6 бит памяти (5 бит не хватает, они позволяют закодировать только 2 5 = 32 варианта)

3) для хранения всех 11 символов пароля нужно 11 × 6 = 66 бит

4) поскольку пароль должен занимать целое число байт, берем ближайшее большее (точнее, не меньшее) значение, которое кратно 8: это 72 = 9 × 8; то есть один пароль занимает 9 байт

5) тогда 60 паролей занимают 9 × 60 = 540 байт

· часто забывают, что пароль должен занимать ЦЕЛОЕ число байт

Ещё пример задания:

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

1) 70 бит 2) 70 байт 3) 490 бит 4) 119 байт

7) велосипедистов было 119, у них 119 разных номеров, то есть, нам нужно закодировать 119 вариантов

8) по таблице степеней двойки находим, что для этого нужно минимум 7 бит (при этом можно закодировать 128 вариантов, то есть, еще есть запас); итак, 7 бит на один отсчет

9) когда 70 велосипедистов прошли промежуточный финиш, в память устройства записано 70 отсчетов

10) поэтому в сообщении 70*7 = 490 бит информации (ответ 3).

· дано число, которое есть в условии (неверные ответы 70 бит, 70 байт, 119 байт), чтобы сбить случайное угадывание

· указано правильное число, но другие единицы измерения (мог быть вариант 490 байт)

· расчет на невнимательное чтение условия: можно не заметить, что требуется определить объем только 70 отсчетов, а не всех 119 (мог быть вариант 119*7=833 бита)

Еще пример задания:

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

1) 8 2) 16 3) 4096 4) 16384

Большие числа. Что делать?

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

Нужно помнить, что соотношение между единицами измерения количества информации также представляют собой степени двойки:

1 байт = 8 бит = 2 3 бит,

1 Кбайт = 1024 байта = 2 10 байта

= 2 10 · 2 3 бит = 2 13 бит,

1 Мбайт = 1024 Кбайта = 2 10 Кбайта

= 2 10 · 2 10 байта = 2 20 байта

= 2 20 · 2 3 бит = 2 23 бит.

Правила выполнения операций со степенями:

· при умножении степени при одинаковых основаниях складываются

· … а при делении – вычитаются:

1) в сообщении было 4096 = 2 12 символов

1/512 Мбайта = 2 23 / 512 бита = 2 23 / 2 9 бита = 2 14 бита (= 16384 бита!)

3) место, отведенное на 1 символ:

2 14 бита / 2 12 символов = 2 2 бита на символ = 4 бита на символ

4) 4 бита на символ позволяют закодировать 2 4 = 16 разных символов

5) поэтому мощность алфавита – 16 символов

6) правильный ответ – 2.

· дано число, которое есть в условии (неверный ответ 4096), чтобы сбить случайное угадывание

· расчет на то, что увидев «правильное» число в ходе вычислений, учащийся не будет доводить расчет до конца (неверный ответ 16384)

· легко запутаться, если выполнять вычисления «в лоб», не через степени двойки

Решение (вариант 2, предложен В.Я. Лаздиным):

1 /512 Мбайт = 1024 /512 Кбайт = 2 Кбайт = 2048 байт

2) на 1 символ приходится 2048 байт / 4096 = 1/2 байта = 4 бита

3) 4 бита на символ позволяют закодировать 2 4 = 16 разных символов

4) поэтому мощность алфавита – 16 символов

5) правильный ответ – 2.

· не всегда удобно работать с дробными числами (1/2 байта)

· метод разработан специально для этой задачи, где он хорошо работает; в других задачах может быть не так гладко

Еще пример задания:

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

1) 4 2) 16 3) 28 4) 30

1) информация в 4 бита соответствует выбору одного из 16 вариантов, …

2) … поэтому в вольере А живет 1/16 часть всех обезьян (это самый важный момент!)

3) всего обезьян – 32, поэтому в вольере А живет

4) поэтому в вольере Б живут все оставшиеся

· неверный ответ 1 (4 обезьяны) сбивает случайное угадывание «в лоб», по исходным данным

· можно сделать неверный вывод о том, что в вольере А живет 4 обезьяны (столько же, сколько бит информации мы получили), следовательно, в вольере Б живут оставшиеся 28 обезьян (неверный ответ 3)

· после п. 1 можно сделать (неверный) вывод о том, что в вольере А живет 16 обезьян, следовательно, в вольере Б – тоже 16 (неверный ответ 2)

1) обезьяна-альбинос может жить в вольере А (событие 1) или в вольере Б (событие 2)

2) по формуле Шеннона количество информации в сообщении о произошедшем событии с номером i равно

3) у нас не было никакой предварительной информации о том, где живет альбинос, поэтому можно считать, что вероятность определяется количеством обезьян в вольере – если вероятность равна 1/16, то в вольере живет 1/16 часть всех обезьян:

6) поэтому в вольере Б живут все оставшиеся

7) правильный ответ – 4.

Еще пример задания:

В корзине лежат 32 клубка шерсти, из них 4 красных. Сколько бит информации несет сообщение о том, что достали клубок красной шерсти?

1) красные клубки шерсти составляют 1/8 от всех, …

2) поэтому сообщение о том, что первый вынутый клубок шерсти – красный, соответствует выбору одного из 8 вариантов

3) выбор 1 из 8 вариантов – это информация в 3 бита (по таблице степеней двойки)

4) правильный ответ – 2.

Решение (вариант 2, использование формулы Шеннона):

1) красные клубки шерсти составляют 1/8 от всех, поэтому вероятность p_k того, что первый вынутый клубок шерсти – красный, равна 1/8

2) по формуле Шеннона находим количество информации в битах:

3) правильный ответ – 2.

Еще пример задания:

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

1) 20 байт 2) 105 байт 3) 120 байт 4) 140 байт

1) всего используется 26 букв + 10 цифр = 36 символов

3) таким образом, на каждый символ нужно 6 бит (минимально возможное количество бит)

4) полный номер содержит 7 символов, каждый по 6 бит, поэтому на номер требуется 6*7=42 бита

5) по условию каждый номер кодируется целым числом байт (в каждом байте – 8 бит), поэтому требуется 6 байт на номер (5*8=40

6) на 20 номеров нужно выделить 20*6=120 байт

7) правильный ответ – 3.

· неверный ответ 1 (20 байт) сбивает случайное угадывание «в лоб», по исходным данным

· если не обратить внимание на то, что каждый номер кодируется целым числом БАЙТ, получаем неверный ответ 2 (20*42=105*8 бит = 105 байт)

· если по невнимательности считать, что каждый СИМВОЛ кодируется целым числом байт, получаем 7 байт на символ и всего 140 байт (неверный ответ 4)

· если «забыть» про цифры, получим всего 26 символов, 5 бит на символ, 35 бит (5 полных байт) на каждый номер и неверный ответ 100 байт (на 20 номеров)

Еще пример задания:

Какое наименьшее число символов должно быть в алфавите, чтобы при помощи всевозможных трехбуквенных слов, состоящих из символов данного алфавита, можно было передать не менее 9 различных сообщений?

1) здесь используется только одна формула: если алфавит имеет мощность M, то количество всех возможных «слов» длиной N равно Q=M N

2) в данном случае нужно закодировать 9 сигналов (Q>=9) с помощью трехбуквенных слов (N=3)

3) таким образом, нужно найти наименьшее целое M, такое что Q=M 3 >= 9 (куб числа не меньше 9)

5) таким образом, правильный ответ – 3.

· нас интересуют только трехбуквенные слова (одно- и двухбуквенные слова учитывать не нужно)

Еще пример задания:

Каждая ячейка памяти компьютера, работающего в троичной системе счисления, может принимать три различных значения (-1, 0, 1). Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина?

1) непривычность этой задачи состоит в том, что используется троичная система

2) фактически мы имеем дело с языком, алфавит которого содержит M=3 различных символа

3) поэтому количество всех возможных «слов» длиной N равно Q=3 N

4) для N= 4 получаем Q=3 4 =81

5) таким образом, правильный ответ – 81.

· если не осознать, что используется троичная (а не двоичная!) система, можно «по инерции» получить неправильный ответ

Еще пример задания:

В школьной базе данных хранятся записи, содержащие информацию об учениках:

– 16 символов: русские буквы (первая прописная, остальные строчные),

– 12 символов: русские буквы (первая прописная, остальные строчные),

– 16 символов: русские буквы (первая прописная, остальные строчные),

– числа от 1992 до 2003.

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

1) 28 2) 2 9 3) 46 4) 56

1) очевидно, что нужно определить минимально возможные размеры в битах для каждого из четырех полей и сложить их;

2) важно! известно, что первые буквы имени, отчества и фамилии – всегда заглавные, поэтому можно хранить их в виде строчных и делать заглавными только при выводе на экран (но нас это уже не волнует)

3) таким образом, для символьных полей достаточно использовать алфавит из 32 символов (русские строчные буквы, «е» и «ё» совпадают, пробелы не нужны)

4) для кодирования каждого символа 32-символьного алфавита нужно 5 бит (32 = 2 555 5 ), поэтому для хранения имени, отчества и фамилии нужно (16 + 12 + 16)•5=220 бит

5) для года рождения есть 12 вариантов, поэтому для него нужно отвести 4 бита (2 4 = 16 ≥ 12)

6) таким образом, всего требуется 224 бита или 28 байт

Источник