Сообщение было закодировано с помощью кодовой таблицы в ней любые два кодовых
Обновлено: 05.07.2024
Текст, кодированный с помощью двухбайтной кодировки Unicode, занял 4096 байт памяти.
Петя проанализировал этот текст и понял, что в нем используются далеко не все символы, доступные при кодировании в Unicode. Он составил таблицу символов, состоящую только из тех символов, которые хотя бы раз встречаются в тексте, и закодировал текст с ее использованием, кодируя каждый символ минимально возможным одинаковым для всех символов количеством бит. В результате получился файл, размером 2304 байта.
Вася более внимательно посмотрел на текст и обнаружил, что его можно разделить на две равные половины. Причем в первой половине текста используется ровно четверть от общего количества символов в кодовой таблице, которую построил Петя, а во второй половине текста встречаются все символы из кодовой страницы Пети. Тогда Вася решил создать для первой половины текста новую кодовую таблицу и закодировать первую половину текста, кодируя каждый символ минимально возможным одинаковым количеством бит, используя свою таблицу, а вторую половину оставить кодированной по Петиной таблице. В результате Вася получил файл, состоящий из двух половинок, закодированный с использованием двух таблиц кодов символов. Какой размер в байтах получился у этого файла? Файлы, кодированные с использованием всех указанных в задаче таблиц, не содержат никакой дополнительной информации, кроме собственно кодируемого текста. В ответе укажите целое число.
вобщем логика такова:
1) хитрый петя составил новую табличку и файл занял 2304 байта, так как юникод символ состоит из 2 байт (16 бит) составим соотношение для выяснения размера кода символа в его таблице:
4096/2304 = 16/х, отсюда
х = 9, т. е. для кодирования символа в таблице хитрого пети отводится 9 бит и всего можно накодировать 512 разных символов
2) неменее хитрый вася решил так - половина текста при 9 бит символе - 2304/9*2 = 128 симолов, он закодировал по новой таблице, для чего ему понадобилось 7 бит на символ, т. к 2 в 7 степени есть 128 а это и есть четверть от полного набора петиной таблицы.
теперь файл стал занимать 2304/2 + 7*128 = 1152 + 896 = 2048 байт,
таков размер итогового файла!
Кодирование – это перевод информации, представленной символами первичного алфавита, в последовательность кодов.
Декодирование (операция, обратная кодированию) – перевод кодов в набор символов первичного алфавита.
Кодирование может быть равномерное и неравномерное. При равномерном кодировании каждый символ исходного алфавита заменяется кодом одинаковой длины. При неравномерном кодировании разные символы исходного алфавита могут заменяться кодами разной длины.
Равномерное кодирование всегда однозначно декодируемо.
Для неравномерных кодов существует следующее достаточное (но не необходимое) условие однозначного декодирования:
Кодирование в различных системах счисления
Для кодирования букв О, В, Д, П, А решили использовать двоичное представление
чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ВОДОПАД таким способом и результат записать восьмеричным кодом, то получится
Представим коды указанных букв в двоичном коде, добавив незначащий нуль для одноразрядных чисел:
Закодируем последовательность букв: ВОДОПАД — 010010001110010.
Разобьём это представление на тройки справа налево и переведём каждую тройку в восьмеричное число.
010 010 001 110 010 — 22162.
Правильный ответ указан под номером 1.
Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется посимвольное кодирование: А-10, Б-11, В-110, Г-0. Через канал связи передаётся сообщение: ВАГБААГВ. Закодируйте сообщение данным кодом. Полученное двоичное число переведите в шестнадцатеричный вид.
Закодируем последовательность букв: ВАГБААГВ — 1101001110100110. Разобьем это представление на четвёрки справа налево и переведём каждую четверку в шестнадцатеричное число:
1101 0011 1010 01102 = D3A616
Правильный ответ указан под номером 1.
Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
Определите, какой набор букв закодирован двоичной строкой 1000110110110, если известно, что все буквы в последовательности – разные:
Мы видим, что условия Фано и обратное условие Фано не выполняются, значит код можно раскодировать неоднозначно.
Значит, будем перебирать варианты, пока не получим подходящее слово :
1) 100 011 01 10 110
Первая буква определяется однозначно, её код 100: a.
Пусть вторая буква — с, тогда следующая буква — d, потом — e и b.
Такой вариант удовлетворяет условию, значит, окончательно получили ответ: acdeb.
Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами: А — 11010, Б — 10111, В — 01101.
Получено сообщение 11000 11101 10001 11111. Декодируйте это сообщение — выберите правильный вариант.
Декодируем каждое слово сообщения. Первое слово: 11000 отличается от буквы А только одной позицией. Второе слово: 11101 отличается от буквы В только одной позицией. Третье слово: 10001 отличается от любой буквы более чем одной позицией. Четвёртое слово: 11111 отличается от буквы Б только одной позицией.
Таким образом, ответ: АВхБ.
Однозначное кодирование
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:
Видим, что ближайший от корня дерева свободный лист (т.е. код с минимальной длиной) имеет код 000.
Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный префиксный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны.
Выберите правильный вариант ответа.
Примечание. Префиксный код — это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.
1) кодовое слово для буквы Е можно сократить до 01
2) кодовое слово для буквы К можно сократить до 1
3) кодовое слово для буквы Н можно сократить до 10
4) это невозможно
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:
Легко заметить, что если букву Н перенести в вершину 10, она останется листом. Т.е. кодовое слово для буквы Н можно сократить до 10.
Всем доброе время суток, сегодня мы рассмотрим второе задание ОГЭ по информатике 2021 года.
Валя шифрует русские слова (последовательности букв), записывая вместо каждой буквы её код:
Некоторые цепочки можно расшифровать не одним способом. Например, 00010101 может означать не только СКА, но и СНК. Даны три кодовые цепочки:
Найдите среди них ту, которая имеет только одну расшифровку, и запишите в ответе расшифрованное слово.
Рассмотрим верхнюю цепочку.
Она может начинаться с 10, 111, а может начинаться с 101, 111, здесь мы видим два варианта расшифровки, а значит эта строка нам не подходит.
Рассмотрим центральную цепочку.
Она по-любому начинается с 000, т.к. больше нет подходящих букв, начинающихся с больше одного нуля. Далее идёт 111, т.к. опять же нет букв, которые могут закодировать несколько единиц и на конце, таким образом, остается 10. Данная строка может быть раскодирована только одним способом, поэтому это наш потенциальный ответ.
Рассмотрим последнюю строчку.
Данная строка может начинаться с 100 и 111, а может с 10 и 01, соответственно данная строка нам не подходит.
Нашим правильным ответом является вторая строка, раскодируем её и получим слово СОН.
От разведчика была получена следующая шифрованная радиограмма, переданная с использованием азбуки Морзе:
При передаче радиограммы было потеряно разбиение на буквы, но известно, что в радиограмме использовались только следующие буквы:
Расшифруйте радиограмму. Запишите в ответе расшифрованную радиограмму.
В данном виде заданий нам требуется просто правильно подобрать буквы под шифр Морзе.
Видим, что начинается код с точки и двух тире, видим, что под данное условие подходит только буква А(*-), остальные буквы, которые начинаются с точки имеют на третьей позиции так же точку.
Далее у нас может быть Т(-) или Д(-**), в ситуациях, когда мы встаём перед выбором, мы делаем предположение, что это один из вариантов и пытаемся расшифровать слово, допустим, что дальше идёт буква Т(разгадано *--). В этом случае дальше у нас идёт буква Ж, т.к. только она начинается с нескольких точек подряд(*--***-). Последующую букву подобрать нельзя, т.к. нет ни одного символа с только одной или только двумя точками, это значит, что мы на второй букве ошиблись и нужно было брать Д, а не Т. Пока что у нас угадано АД(*--**).
Далее мы попадаем опять под выбор: А или Л, но А нам брать нельзя, т.к. эту позицию мы рассматривали и у нас нет символов, которые начинаются с одной или двух точек, это значит, что третьим символом у нас становиться Л. Угадано: АДЛ(*--***-**). Осталось угадать ––••–••–•––.
Далее нам нужен символ, который начинается с тире и потом можно опять поставить тире, под эти условия подходит только буква Т, Д не подходит по той причине, что после тире идёт точка. Угадано: АДЛТ(*--***-**-). Осталось угадать –••–••–•––.
Здесь уже идёт Д, так как если мы возьмём опять Т, то мы не найдём символ с двумя или одной точками в начале. Угадано: АДЛТД(*--***-**--**). Осталось: –••–•––.
Опять Д по тем же причинам, что и в предыдущем выборе. Угадано: АДЛТДД(*--***-**--**-**). Осталось: –•––.
Далее выбираем Т, т.к. больше нет букв с тире на третьей позиции. Угадано: АДЛТДДТ(*--***-**--**-**-). Осталось: •––.
Далее выбираем А, т.к. это единственная буква, которая начинается с *- и потом даёт возможность поставить еще тире за счёт буквы Т.
Вася шифрует русские слова, записывая вместо каждой буквы её номер в алфавите (без пробелов). Номера букв даны в таблице:
Только одна из них расшифровывается единственным способом. Найдите её и расшифруйте. То, что получилось, запишите в качестве ответа.
Рассмотрим первую строчку:
Начинаться может с буквы 8, т.к. буквы 81 нет, далее идут цифры разделяемые нулями а значит, что эти числа 10,20,30, иначе быть не может, иначе какой-то букве придётся начинаться с 0, а такого номера нет. Это строка имеет код 8 10 20 30 (ЖИТЬ) и является потенциально верным ответом.
После 8 может идти 1 12 или 11 2 или 11 21, вариантов много, соответственно нам не подходит этот вариант.
После 8 идёт 1 12 или 11 2, или 11 22, опять не подходит.
В начале 8, после идёт 1 5 или 15, дальше мы можем или соединять цифры в числа или оставлять одинарными значениями, что не подходит под условие задачи.
Текст, кодированный с помощью двухбайтной кодировки Unicode, занял 4096 байт памяти.
Петя проанализировал этот текст и понял, что в нем используются далеко не все символы, доступные при кодировании в Unicode. Он составил таблицу символов, состоящую только из тех символов, которые хотя бы раз встречаются в тексте, и закодировал текст с ее использованием, кодируя каждый символ минимально возможным одинаковым для всех символов количеством бит. В результате получился файл, размером 2304 байта.
Вася более внимательно посмотрел на текст и обнаружил, что его можно разделить на две равные половины. Причем в первой половине текста используется ровно четверть от общего количества символов в кодовой таблице, которую построил Петя, а во второй половине текста встречаются все символы из кодовой страницы Пети. Тогда Вася решил создать для первой половины текста новую кодовую таблицу и закодировать первую половину текста, кодируя каждый символ минимально возможным одинаковым количеством бит, используя свою таблицу, а вторую половину оставить кодированной по Петиной таблице. В результате Вася получил файл, состоящий из двух половинок, закодированный с использованием двух таблиц кодов символов. Какой размер в байтах получился у этого файла? Файлы, кодированные с использованием всех указанных в задаче таблиц, не содержат никакой дополнительной информации, кроме собственно кодируемого текста. В ответе укажите целое число.
вобщем логика такова:
1) хитрый петя составил новую табличку и файл занял 2304 байта, так как юникод символ состоит из 2 байт (16 бит) составим соотношение для выяснения размера кода символа в его таблице:
4096/2304 = 16/х, отсюда
х = 9, т. е. для кодирования символа в таблице хитрого пети отводится 9 бит и всего можно накодировать 512 разных символов
2) неменее хитрый вася решил так - половина текста при 9 бит символе - 2304/9*2 = 128 симолов, он закодировал по новой таблице, для чего ему понадобилось 7 бит на символ, т. к 2 в 7 степени есть 128 а это и есть четверть от полного набора петиной таблицы.
теперь файл стал занимать 2304/2 + 7*128 = 1152 + 896 = 2048 байт,
таков размер итогового файла!
Читайте также: