Код10 класс

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

Open Ended

Два подхода к измерению информации:

Multiple Choice

Каждая цифра машинного двоичного кода несет количество информации, равное:

• 1 байт

• 1 Кбайт  

• 1 бит  

• 8 бит

Формула Хартли определяет количество информации в зависимости от количества возможных вариантов:

N=2ⁱ, где

N — это количество вариантов,

i — это количество бит, не обходимых для кодирования.

Итак, если в нашем алфавите будет присутствовать только 32 символа, то каждый из них займет только 5 бит.

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

Open Ended

Какие кодировочные таблицы вы знаете?

Первая широко используемая кодировочная таблица была создана в США и называлась ASCII, что в переводе означало American standard code for information interchange. Как вы видите, в таблице присутствуют не только латинские буквы, но и цифры, и даже действия. Каждому символу отводится 7 бит, а значит, всего было закодировано 128 символов.

Но так как этого количества было недостаточно, стали создаваться другие таблицы, в которых можно было закодировать и другие символы. Например, таблица Windows-1251, которая, по сути, являлась изменением таблицы ASCII, в которую добавили буквы кириллицы. Таких таблиц было создано множество: MS-DOS, КОИ-8, ISO, Mac и другие

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

Поэтому была разработана международная таблица кодировки Unicode, включающая в себя как символы английского, русского, немецкого, арабского и других языков. На каждый символ в такой таблице отводится 16 бит, то есть она позволяет кодировать 65536 символов. Однако использование такой таблицы сильно «утяжеляет» текст.

Поэтому существуют различные алгоритмы неравномерной кодировки текста, например, алгоритм Хаффмана.

Идея алгоритма Хаффмана основана на частоте появления символа в последовательности. Символ, который встречается в последовательности чаще всего, получает новый очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код.

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, Н, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Г  — 110, И  — 01, Т  — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова БАРАБАН?

 

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А  — 010, Б  — 00, Г  — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

На предприятии каждой изготовленной детали присваивается серийный номер, состоящий из 377 символов. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 23155 серийных номеров требуется более 5536 Кбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

На предприятии каждой изготовленной детали присваивается серийный номер, состоящий из 377 символов. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 23155 серийных номеров требуется более 5536 Кбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

Ответ 33

На складе каждой упаковке товара присваивают уникальный идентификатор, который может содержать десятичные цифры, 26 латинских букв (без учёта регистра) и символы из 476-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 5000 идентификаторов отведено не более 1 Мбайт памяти. Определите максимально возможную длину идентификатора. В ответе запишите только целое число.

На складе каждой упаковке товара присваивают уникальный идентификатор, который может содержать десятичные цифры, 26 латинских букв (без учёта регистра) и символы из 476-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 5000 идентификаторов отведено не более 1 Мбайт памяти. Определите максимально возможную длину идентификатора. В ответе запишите только целое число.

​Ответ 185

При регистрации в компьютерной системе каждому пользователю присваивается идентификатор фиксированной длины, состоящий из двух частей. Первая часть включает в себя 20 заглавных латинских букв; каждый символ кодируется отдельно с использованием минимально возможного количества бит. Вторая часть – целое число от 0001 до 3000, для его кодирования используется минимальное число бит. Для кодирования полного идентификатора выделяется целое число байт. Кроме того, для каждого пользователя хранятся дополнительные сведения (также целое число байт, одинаковое для каждого пользователя). Определите, сколько байт занимают дополнительные сведения, если известно, что данные о 50 пользователях занимают 2500 байт.

В ответе запишите только целое число – количество байт.

При регистрации в компьютерной системе каждому пользователю присваивается идентификатор фиксированной длины, состоящий из двух частей. Первая часть включает в себя 20 заглавных латинских букв; каждый символ кодируется отдельно с использованием минимально возможного количества бит. Вторая часть – целое число от 0001 до 3000, для его кодирования используется минимальное число бит. Для кодирования полного идентификатора выделяется целое число байт. Кроме того, для каждого пользователя хранятся дополнительные сведения (также целое число байт, одинаковое для каждого пользователя). Определите, сколько байт занимают дополнительные сведения, если известно, что данные о 50 пользователях занимают 2500 байт.

В ответе запишите только целое число – количество байт.

Ответ 36