Статья "Решение задания А9 ЕГЭ по информатике быстро и легко"
статья по информатике и икт (11 класс) по теме
В статье приведен способ решения задач на кодирование, который позволяет быстро и легко решать трудные задачи типа А9 из ЕГЭ по информатике
Скачать:
Вложение | Размер |
---|---|
![]() | 17.32 КБ |
Предварительный просмотр:
Решение задания А9 ЕГЭ по информатике быстро и легко.
Чтобы легко решать задачи на декодирование в случае использования неравномерного кода, надо знать следующее:
Код — система условных знаков
Кодирование — процесс представления информации (сообщения) в виде кода, то есть переход от представления информации в одной символьной системе к представлению в другой символьной системе (например, с русского языка в двоичный код).
Декодирование — процесс обратного преобразования кода к форме исходной символьной системы, т.е. получение исходного сообщения. Например: перевод из двоичного кода в письменный текст на русском языке.
Кодирование может быть равномерное и неравномерное, при равномерном кодировании все символы кодируются кодами равной длины, при неравномерном кодировании разные символы могут кодироваться кодами с разным количеством символов. Это осложняет декодирование.
При использовании неравномерного кода надо знать, что «сообщение допускает однозначное разбиение, если выполняется условие Фано: никакой код символа не является началом кода другого символа (в этом случае сообщение нужно раскодировать с начала) или обратное условие Фано: никакой код символа не является окончанием кода другого символа (в этом случае сообщение нужно раскодировать с конца).»
Рассмотрим задание, аналогичное заданию А9 ЕГЭ:
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00, Б – 010, В –101, Г – 011, Д – 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Д – 11
2) это невозможно
3) для буквы Г –01
4) для буквы Б –01
Разберем, как будет работать декодирующее устройство, и представим для большей наглядности алгоритм его работы в виде графа.
Поскольку в нашем задании используется код не длиннее трех символом, то построим граф работы декодирующего устройства в виде графа, у которого будет 3 уровня. Вершины нашего графа – это символы двоичного кода, а ветви – это возможные переходы к следующему символу, то есть те символы, которые могут следовать за символом на уровне, выше текущего.
Первый символ может иметь значение 0 или 1, и от каждого значения построим ветку.
Граф нашей задачи представлен на рисунке 1
1 символ двоичного кода | 0 | 1 | |||||||||
2 символ двоичного кода | 0 | 1 | 0 | 1 | |||||||
«А» | В | ||||||||||
3 символ двоичного кода | 0 | 1 | 0 | 1 | |||||||
«Б» | «Г» | «Д» | «Не используется» |
Рис.1.
Код буквы А – 00, код Б – 010, код Г – 011, код В -10, код Д – 110, а код – 111 – не используется.
Учтем условие Фано и проанализируем граф. Из графа видно, что 01 – не может быть кодом каких-либо букв, так как он является началом для букв Б и Г, а код для буквы Д можно сократить до 11.
Ответ нашей задачи 1.
По теме: методические разработки, презентации и конспекты
![](/sites/default/files/pictures/2015/02/03/picture-31764-1422973310.jpg)
Задания вступительного экзамена по информатике в лицей для одаренных детей при СевКавГТУ 2009 год
Эти задания вступительного экзамена по информатике в лицей для одаренных детей при Северо-Кавказском Государственном техническом университете были подготовлены мной в 2009 году....
![](/sites/default/files/pictures/2016/09/25/picture-22628-1474832993.jpg)
Мастер класс "Быстрый счет-легко и просто"
Математика является одной из важнейших наук на земле и именно с ней человек встречается каждый день в своей жизни. Счет в уме является самым древним и простым способом вычисления. Знание упроще...
Задания школьной олимпиады по информатике 10 класс
представлены задания школьного этапа олимпиады по информатике для 10 класса...
![](/sites/default/files/pictures/2013/11/10/picture-339640-1384076569.jpg)
Решение задач по теме «Второй закон Ньютона». Составление практического задания к компьютерной модели «Движение тел на легком блоке».
Решение задач по теме «Второй закон Ньютона».Составление практического задания к компьютерной модели «Движение тел на легком блоке».(Использование компьютерных технологий на уроках ф...
Решаем задания, сдаем ГИА по Информатике и ИКТ.
Подготовка обучающихся Госудорственной ( итоговой ) аттестации 2014 года (в новой форме) по ИНФОРМАТИКЕ и ИКТ, осваивших основное общеобразовательные программы....
Решаем задания, сдаем ГИА по Информатике и ИКТ.
Подготовка обучающихся Госудорственной ( итоговой ) аттестации 2014 года (в новой форме) по ИНФОРМАТИКЕ и ИКТ, осваивших основное общеобразовательные программы....
![](/sites/default/files/pictures/2014/05/01/picture-443690-1398931678.jpg)
Теоретические тестовые задания по физкультуре по разделам "Баскетбол", "Волейбол", "Легкая атлетика.Бег на длинные дистанции"
Тестовые задания предназначены для учащихся 6-8 классов по состоянию здоровья освобожденных от практических занятий. Выполнены в виде билетов и включают в себя вопросы по трем темам школьной программы...