Решение заданий ЕГЭ по информатике 5 и 10


Чтобы посмотреть презентацию с оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов:

Подготовка к ЕГЭучитель информатикиМБОУ СОШ №1 г. Азова Баламутова Ирина Александровна2015 г. Кодирование и декодирование информации. (Задания 5) Кодирование данных, комбинаторика, системы счисления (Задания 10) СодержАние темы ” Кодирование и декодированиеинформации.”ТеорияЗадача 1Задача 2Задача 3Задача 4Задачи для тренировкиТема: Кодирование данных, комбинаторика, системы счисленияТеорияЗадача 1Задача 2Задача 3Задача 4Задача 5Задачи для тренировкиСписок литературыПОЛЕЗНЫЕ САЙТЫ ДЛЯ ПОДГОТОВКИ К ЕГЭ2 декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;условие Фано – это достаточное, но не необходимое условие однозначного декодированиятеория3 Кодирование – это перевод информации с одного языка на другой. Кодирование может быть равномерное и неравномерное.При равномерном кодировании все символы кодируются кодами равной длины.При неравномерном кодировании разные символы могут кодироваться кодами разной длины.4теория По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?555551) А:0, Б:10, В:110, Г:1112) А:0, Б:10, В:01, Г:113) А:1, Б:01, В:011, Г:0014) А:00, Б:01, В:10, Г:11Задача 15 сначала выберем коды, в которых ни одно кодовое слово не совпадет с началом другого (такие коды называю префиксными)для кода 2 условие «а» не выполняется, так как кодовое слово буквы В (01) начинается с кодового слова буквы А (0)для кода 3 условие «а» не выполняется, так как кодовое слово буквы В (011) начинается с кодового слова буквы Б (01)для кодов 1 и 4 условие выполняется, их рассматриваем дальшесчитаем общее количество битов в сообщении для кода 1:16∙1 + 8·2 + 4∙3 + 4∙3 = 56 битовсчитаем общее количество битов в сообщении для кода 4:16∙2 + 8·2 + 4∙2 + 4∙2 = 64 битакод 1 даёт наименьшую длину сообщения, поэтому выбираем егоОтвет: 1.6Решение задачи 1 Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110.Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?1) 7 2) 8 3) 9 4) 107Задача 2 Решение (способ 1, исключение вариантов):условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового словапоскольку уже есть кодовое слово 0, ни одно другое кодовое слово не может начинаться с 0 поскольку есть код 110, запрещены кодовые слова 1, 11; кроме того, ни одно другое кодовое слово не может начинаться с 110таким образом, нужно выбрать еще два кодовых слова, для которых выполняются эти ограничения.Есть одно допустимое кодовое слово из двух символов: 10 если выбрать кодовое слово 10 для буквы В, то остаётся одно допустимое трёхсимвольное кодовое слово – 111, которое можно выбрать для буквы Г8Решение задача 2 выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов.Если же не выбрать В – 10, то есть три допустимых трёхсимвольных кодовых слова: 100, 101 и 110; при выборе любых двух их них для букв В и Г получаем суммарную длину кодовых слов 10, что больше 9; поэтому выбираем вариант 3 (9 символов) Ответ: 3. Решение задча 2 (продолжение) 9 АБ10100Решение (способ 2, построение дерева):условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева которые не имеют потомков;построим дерево для заданных кодовых слов А – 0 и Б – 110:10Задача 2 штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» листья для кодовых слов букв В (10) и Г (111)АБ10100ВГвыбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символовОтвет: 3. Задача 2 способ 2, построение дерева продолжение11 По каналу связи передаются сообщения, содержащие только 4 буквы П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. 12Задача 3 ОТ101000П1Решение (способ 2, построение дерева):условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева, то есть в узлах, которые не имеют потомков;построим дерево для заданных кодовых слов О – 0, Т – 111 и П – 100:13Решение задачи 3 Штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» лист для кодового слова буквы С: 101 или 110; из них минимальное значение имеет код 101Решение задачи 3(продолжение) 14 15Штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» лист для кодового слова буквы С: 101 или 110; из них минимальное значение имеет код 101.ОТ101000П1СВыбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символовОтвет: 101. Решение задачи 3 (продолжение)15 Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.                         BD9AA5 2) BDA9B5 3) BDA9D5 4)DB9DAB 16Задача 4 «вытянем» растровое изображение в цепочку: сначала первая (верхняя) строка, потом – вторая, и т.д.:в этой полоске 24 ячейки, черные заполним единицами, а белые – нулями:поскольку каждая цифра в шестнадцатеричной системе раскладывается ровно в 4 двоичных цифры, разобьем полоску на тетрады – группы из четырех ячеек (в данном случае все равно, откуда начинать разбивку, поскольку в полоске целое число тетрад – 6):переводя тетрады в шестнадцатеричную систему, получаем последовательно цифры B (11), D(13), A(10), 9, D(13) и 5, то есть, цепочку BDA9D5поэтому правильный ответ – 3.17Решение задачи 4                         1 строка2 строка3 строка4 строка1011110110101001110101011 строка2 строка3 строка4 строка10111101101010011101010118Решение задачи 4 (продолжение) За­да­ние 5 № 7746. Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв А, Б, В, Г и Д, ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код, поз­во­ля­ю­щий од­но­знач­но де­ко­ди­ро­вать по­лу­чен­ную дво­ич­ную по­сле­до­ва­тель­ность. Вот этот код: А — 1; Б — 0100; В — 000; Г — 011; Д — 0101. Тре­бу­ет­ся со­кра­тить для одной из букв длину ко­до­во­го слова так, чтобы код по-преж­не­му можно было де­ко­ди­ро­вать од­но­знач­но. Коды осталь­ных букв ме­нять­ся не долж­ны. Каким из ука­зан­ных спо­со­бов это можно сде­лать? 1) для буквы Г — 112) для буквы В — 003) для буквы Г — 014) это не­воз­мож­ноОтвет:19 задачи для самостоятельного решения2
Задание 5 № 1104. Для кодирования букв X, Е, Л, О, Д решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с со­хра­не­ни­ем одного незначащего нуля в случае одноразрядного представления). Если закодировать последовательность букв ЛЕДОХОД таким способом и результат записать шестнадцатеричным кодом, то получится 1) 999С2) 32541453) 123F 4) 2143034 Ответ:20 ответы За­да­ние 5 № 1104ХЕЛОД0123400011011100Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: ЛЕ­ДО­ХОД — 1001100110011100. Те­перь разобьём это пред­став­ле­ние на четвёрки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел cна­ча­ла в де­ся­тич­ный код, затем в шест­на­дца­те­рич­ный. 1001 1001 1001 1100 — 9 9 9 12 — 999С.Пра­виль­ный ответ ука­зан под но­ме­ром 1.21 Задание 5 № 7193 Для пе­ре­да­чи по ка­на­лу связи со­об­ще­ния, со­сто­я­ще­го толь­ко из сим­во­лов А, Б, В и Г, ис­поль­зу­ет­ся не­рав­но­мер­ный (по длине) код: А – 0; Б – 100; В – 101. Каким ко­до­вым сло­вом нужно ко­ди­ро­вать сим­вол Г, чтобы длина его была ми­ни­маль­ной, а код при этом до­пус­кал од­но­знач­ное раз­би­е­ние ко­ди­ро­ван­но­го со­об­ще­ния на сим­во­лы? 1) 12) 113) 01 Решение4) 010 http://inf.reshuege.ru/test?theme=232 Ответ:222
Задание 5 № 9293.23 Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Л использовали кодовое слово 1, для буквы М – кодовое слово 01. Какова наи­мень­шая возможная суммарная длина всех пяти кодовых слов?Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.Ответ:4Решение http://inf.reshuege.ru/test?theme=23123
24Задачидля тренировки видеоурок ссылкассылкаhttps://www.youtube.com/watch?v=BoBnzjwLsnU Тема: Кодирование данных, комбинаторика, системы счисления(Задания 10)25 Что нужно знать:русский алфавит принципы работы с числами, записанными в позиционных системах счисленияесли слово состоит из L букв, причем есть n1 вариантов выбора первой буквы, n2 вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение N = n1 · n2 · … · nLесли слово состоит из L букв, причем каждая буква может быть выбрана n способами, то число возможных слов вычисляется как N = nL26теория Вася составляет 5-буквенные слова, в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?27Задача 1 Буква С может стоять на одном из пяти мест: С****, *С***, **С**, ***С* и ****С, где * обозначает любой из оставшихся трёх символов в каждом случае в остальных четырёх позициях может быть любая из трёх букв Л, О, Н, поэтому при заданном расположении буквы С имеем 34 = 81 вариант всего вариантов 5 · 81 = 405.Ответ: 405.28решение Сколько существует различных символьных последовательностей длины 5 в четырёхбуквенном алфавите {A, C, G, T}, которые содержат ровно две буквы A?29Задача 2 Решение (вариант 1, перебор):рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А:АА*** А*А** А**А* А***АЗдесь звёздочка обозначает любой символ из набора {C, G, T}, то есть один из трёх символов. Итак, в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 33 = 27 всего 4 шаблона, они дают 4 · 27 = 108 комбинаций30решение теперь рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три:*АА** *А*А* *А**Аони дают 3 · 27 = 81 комбинациюдва шаблона, где первая по счёту буква А стоит на третьей позиции:**АА* **А*А они дают 2 · 27 = 54 комбинации и один шаблон, где сочетание АА стоит в конце ***АА они дают 27 комбинаций всего получаем (4 + 3 + 2 + 1) · 27 = 270 комбинаций Ответ: 270.Решение (продолжение)31 Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:КККК2. КККЛ3. КККР4. КККТ……Запишите слово, которое стоит на 67-м месте от начала списка. 32Задача 3 Самый простой вариант решения этой задачи – использование систем счисления; действительно, здесь расстановка слов в алфавитном порядке равносильна расстановке по возрастанию чисел, записанных в четверичной системе счисления (основание системы счисления равно количеству используемых букв).Выполним замену К0, Л1, Р2, Т3; поскольку нумерация слов начинается с единицы, а первое число КККК0000 равно 0, под номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = 10024 Выполнив обратную замену (цифр на буквы), получаем слово ЛККР.Ответ: ЛККР.33Решение 34Задача 4 За­да­ние 10 № 6777. Сколь­ко слов длины 5 можно со­ста­вить из букв Е, Г, Э? Каж­дая буква может вхо­дить в слово не­сколь­ко раз. 35РешениеЕсли в алфавите M символов, то количество всех возможных «слов» (сообщений) длиной N равно Q = MN. В нашем слу­чае N = 5, M = 3. Сле­до­ва­тель­но, Q = 35 = 243. Ответ: 243. 36Задача 5 Задание 10 № 4797. В закрытом ящике находится 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике? 37 Формула Шенонна:     где x — количество информации в сообщении о событии P, p — вероятность события P. вероятность того, что до­ста­ли НЕ синий  где   — число синих ка­ран­да­шей.Воспользовавшись формулой Шенонна, получаем, чтоУ=30Решение 38Задачидля тренировки самоподготовка видеоурок ссылкассылкаhttps://www.youtube.com/watch?v=BoBnzjwLsnU СПИСОК ЛИТЕРАТУРАhttp://kpolyakov.narod.ru/ Крылов С.С., Чуркина Т.Е. ЕГЭ 2015. Информатика и ИКТ. Типовые экзаменационные варианты.  — М.: «Национальное образование», 2015. Лещинер В.Р. ЕГЭ 2015. Информатика. Типовые тестовые задания. — М.: Экзамен, 2015.Евич Л.Н., Кулабухов С.Ю. Информатика и ИКТ. Подготовка к ЕГЭ-2015. — Ростов-на-Дону: Легион, 2014. Ушаков Д.М., Якушкин П.А. Информатика. Самое полное издание типовых вариантов заданий ЕГЭ 2014. — М.: Астрель, 2014. Евич Л.Н., Кулабухов С.Ю. Информатика и ИКТ. Подготовка к ЕГЭ-2015. — Ростов-на-Дону: Легион, 2014. Островская Е.М., Самылкина Н.Н. ЕГЭ 2015. Информатика. Сдаём без проблем! — М.: Эксмо, 2014. Самылкина Н.Н., Островская Е.М. ЕГЭ 2015. Информатика. Тематические тренировочные задания. — М.: Эксмо, 2014.Зорина Е.М., Зорин М.В. ЕГЭ 2015. Информатика. Сборник заданий. — М.: «Эксмо», 2015.39 Полезные сайты для ПОДГОТОВКИ К ЕГЭ!40Информатика - это просто http://easyinformatics.ru/Видеоразбор задачи ЕГЭ-2013  http://www.агейчев.рф/ege.htmlОбразовательный портал для подготовки к экзаменам http://inf.reshuege.ru/?redir=1ЕГЭ по информатике 2013 http://infoegehelp.ru/40

Приложенные файлы

  • pptx EGE_5_i_10
    Размер файла: 976 kB Загрузок: 128