Как решать задание 1 по информатике егэ – Как решать задание 1 ЕГЭ по информатике – разбор заданий

Задание 1 ЕГЭ по информатике 2019: практика и теория

Статьи

Среднее общее образование

Информатика

Предлагаем вашему вниманию разбор задания № 1 ЕГЭ 2019 года по информатике и ИКТ. Этот материал содержит пояснения и подробный алгоритм решения, а также рекомендации по использованию справочников и пособий, которые могут понадобиться при подготовке к ЕГЭ.

16 января 2019

Что нового?

В предстоящем ЕГЭ не появилось никаких изменений по сравнению с прошлым годом.

Возможно, вам также будут интересны демоверсии ЕГЭ по математике и физике.

О нововведениях в экзаменационных вариантах по другим предметам читайте в наших новостях.

ЕГЭ-2020. Информатика. Тематические тренировочные задания

Пособие содержит задания, максимально приближенные к реальным, используемым на ЕГЭ, но распределенные по темам в порядке их изучения в 10-11-х классах старшей школы. Работая с книгой, можно последовательно отработать каждую тему, устранить пробелы в знаниях, а также систематизировать изучаемый материал. Такая структура книги поможет эффективнее подготовиться к ЕГЭ.

Купить

Источник: сайт ФИПИ

Демо-КИМ ЕГЭ-2019 по информатике не претерпел никаких изменений по своей структуре по сравнению с 2018 годом. Это значимо упрощает работу педагога и, конечно, уже выстроенный (хочется на это рассчитывать) план подготовки к экзамену обучающегося.

Мы рассмотрим решение предлагаемого проекта (на момент написания статьи – пока еще ПРОЕКТА) КИМ ЕГЭ по информатике.

Часть 1

Ответами к заданиям 1–23 являются число, последовательность букв или цифр, которые следует записать в БЛАНК ОТВЕТОВ № 1 справа от номера соответствующего задания, начиная с первой клеточки, без пробелов, запятых и других дополнительных символов. Каждый символ пишите в отдельной клеточке в соответствии с приведёнными в бланке образцами.

Задание 1

Вычислите значение выражения 9E

16 — 9416.

В ответе запишите вычисленное значение в десятичной системе счисления.

Ответ: ___________________________.

Решение

Простая арифметика в шестнадцатеричной системе счисления:


Очевидно, что шестнадцатеричная цифра Е16 соответствует десятеричному значению 14. Разность исходных чисел дает значение А16. Решение, в принципе, уже найдено. Следуя условию, представим найденное решение в десятеричной системе счисления. Имеем: А16 = 1010.

Ответ: 10.

rosuchebnik.ru

Информатика ЕГЭ 1 задание разбор

1-е задание: «Системы счисления и представление информации в памяти ПК»
Уровень сложности — базовый,
Максимальный балл — 1,
Примерное время выполнения — 1 минута.

Разбор 1 задания ЕГЭ по информатике 2017 года ФИПИ вариант 1 (Крылов С.С., Чуркина Т.Е.):

Сколько единиц в двоичной записи шестнадцатеричного числа 2AC116?

Подобные задания для тренировки


Ответ: 6 ✍ Подробное решение
  • В шестнадцатеричной системе счисления числа от 10 до 15 представлены буквами латинского алфавита: A-10, B-11, C-12, D-13, E-14, F-15.
  • Необходимо вспомнить двоичные коды чисел от 1 до 15 (см. теорию выше на странице), так как для перевода 16-ричного числа в двоичную систему достаточно каждую цифру отдельно записать в виде четверки двоичных цифр (тетрады):

 2     A     C     1
0010  1010  1100  0001
  • в этой записи 6 единиц
  • Результат: 6

    📹 Видео


    1 задание. Демоверсия ЕГЭ 2018 информатика:

    Сколько существует целых чисел x, для которых выполняется неравенство 2A16<x<618

    ?
    В ответе укажите только количество чисел, сами числа писать не нужно.

    Подобные задания для тренировки


    Ответ: 6 ✍ Подробное решение
    • Переведем 2A16 в десятичную систему счисления:
    2A16 = 2*161+10*160 = 32 + 10 = 42
  • Переведем 618 в десятичную систему счисления:
  • 618 = 6*81+1*80 = 48 + 1 = 49
  • Получим сравнение:
  • 42 
    
  • Поскольку в задании дважды строгое сравнение (<), то количество целых чисел, удовлетворяющих условию:
  • 49 - 42 - 1 = 6
  • Проверим: 43, 44, 45, 46, 47, 48
  • Результат: 6

    📹 Видео


    1 задание. ГВЭ 11 класс по информатике 2018 (ФИПИ):

    Сколько значащих цифр в двоичной записи десятичного числа 129?
    1) 6
    2) 2
    3) 7
    4) 8


    Ответ: 4 ✍ Подробное решение
    • Выполним перевод из десятичной системы счисления в двоичную делением на 2, справа будем записывать остатки:
    
    129 / 1
    64  / 0
    32  / 0
    16  / 0
    8   / 0
    4   / 0
    2   / 0
    1
    
  • Перепишем остатки снизу вверх, начиная с последней единицы, которая уже не делится на два:
  • 
    10000001
    
  • Посчитаем количество разрядов в получившемся двоичном числе. Их 8, и все они значащие (незначащими могут быть только нули слева, например, 010 - это то же самое, что 10). Правильный ответ под номером 4
  • Результат: 4


    Решение 1 задания ЕГЭ по информатике (контрольный вариант экзаменационной работы 2018 года, С.С. Крылов, Д.М. Ушаков):

    Сколько существует натуральных чисел x, для которых выполняется неравенство

    10101128?

    В ответе укажите только количество чисел, сами числа писать не нужно.


    Ответ: 17

    📹 Видео


    Разбор 1 задания ЕГЭ вариант № 1, 2019 Информатика и ИКТ Типовые экзаменационные варианты (10 вариантов), С.С. Крылов, Т.Е. Чуркина::

    Вычислите значение выражения AE16 – 1916.
    В ответе запишите вычисленное значение в десятичной системе счисления.

    Подобные задания для тренировки


    Ответ: 149 ✍ Подробное решение
    • Переведем уменьшаемое и вычитаемое в десятичную систему счисления:
    
    1 0
    A E = 10*161 + 14*160 = 160 + 14 = 174
    
    

    * A16 соответствует числу 10 в десятичной системе счисления

    * E16 соответствует числу 14 в десятичной системе счисления

    
    1 0
    19 = 1*161 + 9*160 = 16 + 9 = 25
    
  • Найдем разность:
  • 
    174 - 25 = 149
    

    Результат: 149


    Пройти тест онлайн:

  • Переходите на следующий вопрос по кнопке NEXT
  • Проверяйте вариант ответа по кнопке CHECK ANSWER
  • После прохождения щелкните SUBMIT ALL ANSWERS...
  • labs-org.ru

    Теория и разбор 7 задания ЕГЭ по информатике

    Урок посвящен тому, как решать 7 задание ЕГЭ по информатике


    Объяснение заданий 7 ЕГЭ по информатике

    7-я тема — «Электронные таблицы Excel»- характеризуется, как задания базового уровня сложности, время выполнения – примерно 3 минуты, максимальный балл — 1

    * Некоторые изображения страницы взяты из материалов презентации К. Полякова

        

    Типы ссылок в ячейках

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

    • Имена ячеек в относительной формуле автоматически меняются при переносе или копировании ячейки с формулой в другое место таблицы:
    • Относительная адресация:
      имя столбца вправо на 1
      номер строки вниз на 1

    • Имена ячеек в абсолютной формуле не меняются при переносе или копировании ячейки с формулой в другое место таблицы.
    • Для указания того, что не меняется столбец, ставится знак $ перед буквой столбца. Для указания того, что не меняется строка, ставится знак $ перед номером строки:
    • Абсолютная адресация:
      имена столбцов и строк при копировании формулы остаются неизменными

    • В смешанных формулах меняется только относительная часть:
    • Смешанные формулы

    Стандартные функции Excel

    В ЕГЭ встречаются в формулах следующие стандартные функции:

    • СЧЕТ — количество непустых ячеек,
    • СУММ — сумма,
    • СРЗНАЧ — среднее значение,
    • МИН — минимальное значение,
    • МАКС — максимальное значение

    В качестве параметра функции везде указывается диапазон ячеек: МИН(А2:А240)

  • следует иметь в виду, что при использовании функции СРЗНАЧ не учитываются пустые ячейки и текстовые ячейки; например, после ввода формулы в C2 появится значение 2 (не учитывается пустая
    А2
    ):
  • Построение диаграмм

    • Диаграммы используются для наглядного представления табличных данных.
    • Разные типы диаграмм используются в зависимости от необходимого эффекта визуализации.
    • Так, круговая и кольцевая диаграммы отображают соотношение находящихся в выбранном диапазоне ячеек данных к их общей сумме. Иными словами, эти типы служат для представления доли отдельных составляющих в общей сумме.
    • Соответствие секторов круговой диаграммы (если она намеренно НЕ перевернута) начинается с «севера»: верхний сектор соответствует первой ячейке диапазона.
    • Типы диаграмм Линейчатая и Гистограмма (на левом рис.), а также График и Точечная (на рис. справа) отображают абсолютные значения в выбранном диапазоне ячеек.

    Егифка ©:

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

    Рассмотрим, как решается задание 7 ЕГЭ по информатике.

    Анализ диаграмм

    7_1:

    На диаграмме отображено количество участников тестирования по предметам в разных регионах России.

    Какая из диаграмм правильно отражает соотношение общего количества участников (из всех трех регионов) по каждому из предметов тестирования?


    ✍ Решение:
    • столбчатая диаграмма позволяет определить числовые значения. Так, например, в Татарстане по биологии количество участников 400 и т.п. Найдем с помощью нее общее количество участников со всех регионов по каждому предмету. Для этого посчитаем значения абсолютно всех столбцов в диаграмме:
    400 + 100 + 200 + 400 + 200 + 200 + 400 + 300 + 200 = 2400
  • по круговой диаграмме можно определить только доли отдельных составляющих в общей сумме: в нашем случае это доли участников по различным предметам тестирования;
  • для того чтобы разобраться, какая круговая диаграмма подходит, сначала посчитаем самостоятельно долю участников, тестирующихся по отдельным предметам; для этого из столбчатой диаграммы вычислим сумму участников по каждому предмету и разделим на уже полученное в первом пункте общее количество участников:
  • 
    Биология: 1200/2400 = 0,5 = 50%
    История: 600/2400 = 0,25 = 25%
    Химия: 600/2400 = 0,25 = 25%
    
  • Теперь сравним полученные данные с круговыми диаграммами. Данные соответствуют диаграмме под номером 1.
  • Результат: 1

    Предлагаем посмотреть подробный разбор данного 7 задания на видео:



    7_2:

    На диаграмме отображено количество участников тестирования по предметам в разных регионах России.

    Какая из диаграмм правильно отражает соотношение количества участников тестирования по истории в регионах?


    ✍ Решение:

    Результат: 2

    Подробный разбор задания смотрите на видео:


    Копирование формул

    7_3: ЕГЭ по информатике 2016, «Типовые тестовые задания по информатике», Крылова С.С., Чуркиной Т.Е. Вариант 2.:

    Дан фрагмент электронной таблицы.

    Из ячейки A3 в ячейку С2 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились.
    Каким стало числовое значение формулы в ячейке С2?

    Подобные задания для тренировки


    ✍ Решение:

    Разбор данного 7 задания смотрите на видео:



    7_4: ЕГЭ по информатике 2017, «Типовые тестовые задания по информатике», Крылова С.С., Чуркиной Т.Е. Вариант 5:

    Дан фрагмент электронной таблицы. Из ячейки A3 в ячейку E2 была скопирована формула. При копировании адреса ячеек автоматически изменились.
    Каким стало числовое значение формулы в ячейке E2?


    ✍ Решение:
    • Рассмотрим формулу в ячейке A3: = $E$1*A2. Знак доллара означает абсолютную адресацию: при копировании формулы буква или цифра, стоящая рядом с долларом, не изменится. То есть в нашем случае сомножитель $E$1 так и останется в формуле при копировании.
    • Поскольку копирование осуществляется в ячейку E2, необходимо посчитать на сколько столбцов вправо переместится формула: на 5 столбцов (от A до E). Соответственно, и в сомножителе A2 буква A заменится на E.
    • Теперь посчитаем на сколько строк вверх сместится при копировании формула: на одну (c A3 на E2). Соответственно и в сомножителе A2 цифра 2 заменится на 1.
    • Получим формулу и посчитаем результат: =$E$1*E1 = 1

    Результат: 1



    7_5: 7 задание. Демоверсия ЕГЭ 2018 информатика:

    Дан фрагмент электронной таблицы. Из ячейки B3 в ячейку A4 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились.
    Каким стало числовое значение формулы в ячейке A4?

    Примечание: знак $ обозначает абсолютную адресацию.


    ✍ Решение задания 7:
    • Знак доллара $ означает абсолютную адресацию:
    • $ перед буквой означает фиксацию столбца: т.е. при копировании формулы название столбца меняться не будет;
    • $ перед цифрой означает фиксацию строки: при копировании формулы название строки меняться не будет.
    • В нашем случае меняться не будут выделенные буквы и цифры: = $C2 + D$3
    • Копирование же формулы на один столбец влево, означает, что буква D (в D$3) должна поменяться на предшествующую ей C. При копировании формулы вниз на одну строку, значение 2 (в $C2) меняется на 3.
    • Получаем формулу:
    = $C3 + С$3
  • В итоге имеем результат: 300 + 300 = 600
  • Результат: 600

    Подробное решение данного 7 задания из демоверсии ЕГЭ 2018 года смотрите на видео:


    Какая формула была записана

    7_6: 7 задание ЕГЭ. Задание 6 ГВЭ 11 класс 2018 год (ФИПИ)

    Коле нужно с помощью электронных таблиц построить таблицу значений формулы 5х–3у для значений х и у от 2 до 5. Для этого сначала в диапазонах В1:Е1 и А2:А5 он записал числа от 2 до 5. Затем в ячейку В2 записал формулу (А2 – значение х; В1 – значение у), после чего скопировал её во все ячейки диапазона B2:E5. В итоге получил таблицу, представленную ниже.

    Какая формула была записана в ячейке В2?

    Примечание: знак $ используется для обозначения абсолютной адресации.

    Варианты:
    1)=5*$A$2–3*$B$1
    2)=5*$A2–3*B$1
    3)=5*A$2–3*$B1
    4)=5*A2–3*$B$1


    ✍ Решение:
    = 5 * $A 
  • Тогда как имя столбца B должно меняться (на C, D, E), чтобы цифры в вычитаемом менялись (3, 4, 5):
  • = 3 * B


    По вертикали:

  • Номер строки в уменьшаемом должен меняться, чтобы цифры в нем увеличивались (3, 4, 5). Тогда как строки в вычитаемом меняться не должны: $A2. Таким образом, необходимо поставить знак $ перед номером строки в уменьшаемом: B$1
  • В результате получаем формулу: = 5 * $A2 – 3 * B$1 , что соответствует номеру 2.
  • Результат: 2


    Значение формулы СУММ или СРЗНАЧ

    7_7: ЕГЭ по информатике задание 7 (пример задания P-00, Поляков К.)

    Задан фрагмент электронной таблицы:

    Как изменится значение ячейки C3, если после ввода формул переместить содержимое ячейки B2 в B3?
    («+1» означает увеличение на 1, «-1» означает уменьшение на 1):

    Варианты:
    1) -2
    2) -1
    3) 0
    4) +1


    ✍ Решение:
      Проанализируем данные электронной таблицы до перемещения:
    • В ячейке C2 будет находиться число 4, так как функция СЧЁТ подсчитывает количество непустых ячеек указанного диапазона.
    • В ячейке С3 будет находиться число 3:
    (1 + 2 + 2 + 6 + 4) / 5 = 3

    Теперь посмотрим, что произойдет после перемещения:

  • Перемещение содержимого ячейки означает, что ячейка B2 окажется пустой, а в ячейке B3 появится число 6.
  • Тогда расчёт формулы в ячейке C2 поменяется: количество непустых ячеек диапазона A1:B2 станет равным 3.
  • Соответственно изменится и значение после расчёта формулы ячейки C3: среднее значение содержимого диапазона ячеек A1:C2 станет равным:
  • (1 + 2 + 2 + 3) / 4 = 2

    (нужно не забывать, что функция СРЗНАЧ не учитывает пустые ячейки, поэтому ячейка B2 не учтена).

  • Таким образом, значение после перемещения формулы изменилось, уменьшившись на 1. Верный ответ 2
  • Результат: 2

    Подробное решение задания на видео:



    7_8:

    В электронной таблице значение формулы =СРЗНАЧ(С2:С5) равно 3.

    Чему равно значение формулы =СУММ(С2:С4), если значение ячейки С5 равно 5?


    ✍ Решение:
    • Функция СРЗНАЧ предназначена для вычисления среднего арифметического значения указанного диапазона ячеек. Т.е. в нашем случае среднее значение ячеек C2, C3, C4, C5.
    • Результат функции =СРЗНАЧ(С2:С5) задан по условию, подставим его в формулу:
    (C2 + C3 + C4 + C5)/4 = 3
  • Примем неизвестную сумму в за x и получим по формуле вычисления среднего значения:
  • x / 4 = 3
  • Найдем x:
  • x = 3 * 4 = 12  ->  C2 + C3 + C4 + C5 = 12
  • По заданию необходимо найти =СУММ(С2:С4). Зная значение в ячейке С5, вычтем его из полученной суммы и найдем ответ:
  • C2 + C3 + C4 = C2 + C3 + C4 + C5 - C5 = 
    = 12 - 5 = 7 

    Результат: 7

    Подробное решение смотрите на видео:


    Какое число должно быть записано в ячейке

    7_9: ЕГЭ по информатике 2017 задание ФИПИ вариант 7 (Крылов С.С., Чуркина Т.Е.):

    Дан фрагмент электронной таблицы:

    Какое целое число должно быть записано в ячейке А1, чтобы диаграмма, построенная по значениям ячеек А2:С2, соответствовала рисунку? Известно, что все значения ячеек из рассматриваемого диапазона неотрицательны.


    ✍ Решение:
    • Имеем круговую диаграмму, которая отображает доли отдельных составляющих в общей сумме. По изображению диаграммы можно судить о том, что, скорее всего, значения во всех ячейках формулы должны быть равны (секторы диаграммы визуально равны).
    • Получим выражения из формул ячеек, подставив вместо A1 -> x:
    
    А2: х + 4 - 3 = х + 1
    В2: (5 * х + 5) / 5
    С2: (х + 1)*(х - 4) = х2 - 3 * х - 4
    
  • Так как секторы диаграммы равны, то приравняем любые два из полученных выражений (например, С2 = А2):
  • 
    х²-3 * х - 4 = х + 1
    х²-4 * х - 5 = 0
    х1,2 = (4±√16 - 4 * 1 * (-5)) / 2 = (4±6) / 2
    x1 = 5, x2 = -1
    
  • По условию задания число не должно быть отрицательным, поэтому нам подходит 5
  • Результат: 5

    Для более детального разбора предлагаем посмотреть видео решения данного 7 задания ЕГЭ по информатике:


    Рассмотрим еще один пример решения 7 задания ЕГЭ по информатике:

    7_10: ЕГЭ по информатике 2017 задание 7 ФИПИ вариант 15 (Крылов С.С., Чуркина Т.Е.):

    Дан фрагмент электронной таблицы:

    Какое целое число должно быть записано в ячейке C1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек А2:С2 соответствовала рисунку?
    Известно, что все значения диапазона, по которым построена диаграмма, имеют один и тот же знак.


    ✍ Решение:
    • Круговая диаграмма отображает доли отдельных частей в общей сумме. В нашем случае в диаграмме отражаются результаты вычисления формул в ячейках А2:С2
    • По диаграмме можно судить о том, что, скорее всего, полученные значения в формулах во всех ячейках должны быть равны (секторы диаграммы визуально равны).
    • Получим выражения из формул ячеек, подставив вместо С1 -> x:
    
    А2: х + 2
    В2: 8/2 = 4
    С2: х * 2
    
  • Так как секторы диаграммы равны, то приравняем два из полученных выражений (например, С2 = В2):
  • 
    2 * х = 4 => x = 2
    

    Результат: 2

    Детальный разбор можно посмотреть в видеоуроке решения данного 7 задания ЕГЭ по информатике:



    7_11: Пример задания с ege.yandex.ru

    Задан фрагмент электронной таблицы:

    Какое число должно быть записано в ячейке B1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A2:C2 соответствовала рисунку:


    ✍ Решение:
    • По диаграмме можно судить только о следующем: если она не перевернута, то значения в ячейках A2 и B2 должны быть равны, а значение ячейки C2 — в два раза больше каждой из них.
    • Поскольку у нас неизвестны значения двух ячеек, то обозначим B1 за x, а C1 за y.
    • Подставим неизвестные в формулы и получим:
    • Исходя из первого пункта, получаем:
    A2 = B2 = C2/2
  • Составим систему уравнений:
  • 
    4y = x - y
    2 * 4y = x - y + 4
    
  • Первое уравнение нам дает x = 5y. Подставим это значение во второе уравнение:
  • 8y = 5y - y + 4  ->  y = 1
  • Таким образом, x=5. А значения ячеек A2 = B2 = 4, C2 = 8. Т.е. изображение диаграммы действительно сходится с полученными значениями.
  • Результат: 5

    Подробное решение смотрите на видео:



    7_12: Задание № 10, К. Поляков:

    Дан фрагмент электронной таблицы в режиме отображения формул:

    После копирования диапазона ячеек АЗ:ЕЗ в диапазон А4:Е6 была построена диаграмма (график) по значениям столбцов диапазона ячеек В2:Е6.

    Значениям D2:D6 соответствует график:
     
    Варианты:
    1) А   2) Б   3) В   4) Г


    ✍ Решение:
    • Копирование диапазона ячеек АЗ:ЕЗ в диапазон А4:Е6 буквально означает выделение диапазона АЗ:ЕЗ и протягивание маркера копирования до конца указанного блока ячеек.
    • Поскольку нас интересует только столбец D, то посмотрим, что там за формула, и что с ней произойдет при копировании:
    • в ячейке D3 значение зависит от ячейки A3 и оно равно 2;
    • при копировании формулы столбец остается тот же (D), поэтому и в формуле буквы остаются теми же (D и A), а вот строки копируются вниз, т.е. цифры в формуле увеличиваются на единицу при движении вниз на каждую строку; соответственно, нас интересуют еще ячейки A4, A5, A6;
    • формулы ячеек A4, A5, A6 зависят от ячеек столбца B, поэтому рассмотрим получившиеся при копировании формулы столбцов A и B:
    • Теперь вычислим значения в этих столбцах:
    • Получаем точки по столбцу D: 1, -1, -1, -7, -15, что соответствует графику Г (ответ 4)

    Результат: 4

    Разбор задания смотрите на видео:



    7_13: Задание № 83, Поляков К.:

    Дан фрагмент электронной таблицы:


    Какое целое число должно быть записано в ячейке C1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A2:D2 соответствовала рисунку? Известно, что все значения диапазона, по которым построена диаграмма, положительные.


    ✍ Решение задания 7:
    • На изображенной диаграмме (если она преднамеренно не перевернута) секторы соответствуют указанному диапазону ячеек при движении по часовой стрелке с «севера на юг»: т.е. А2 — синий сектор, B2 — красный и т.п. Таким образом, делаем следующий вывод:
    А2 = B2 = 2 * C2 = 2 * D2
  • Поскольку необходимо найти C1, и оно встречается в формулах, то примем его за x.
  • Перепишем формулы согласно введенному обозначению:
  • Приравняем формулы в ячейках B2 и D2 (см. п.1) и получим:
  • 
    B2 = 2 * D2
    2(x + 5) = x + 21
    2x - x = 21 - 10
    x = 11
    
  • Т.е. С1 = 11
  • Результат: 11

    Видеоразбор задания:


    labs-org.ru

    Информатика ЕГЭ 5 задание разбор и объяснение

    Урок посвящен тому, как решать 5 задание ЕГЭ по информатике


    Кодирование информации

    5-я тема характеризуется, как задания базового уровня сложности, время выполнения – примерно 2 минуты, максимальный балл — 1

    • Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
    • Кодирование бывает равномерным и неравномерным:
    • при равномерном кодировании всем символам соответствуют коды одинаковой длины;
    • при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.
    Пример: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:

    Таким образом, мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодов (2).

    Кодирование и расшифровка сообщений

    Декодирование (расшифровка) — это восстановление сообщения из последовательности кодов.

    Для решения задач с декодированием, необходимо знать условие Фано:

    Условие Фано: ни одно кодовое слово не должно являться началом другого кодового слова (что обеспечивает однозначное декодирование сообщений с начала)

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

    • если сообщение декодируется с конца, то его можно однозначно декодировать, если выполняется обратное условие Фано:
    • Обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова

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


    • условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

    Однозначное декодирование обеспечивается:

    Однозначное декодирование


    Декодирование

    Егифка ©:

    Решение 5 заданий ЕГЭ

    ЕГЭ 5.1: Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).

    Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.


    ✍ Решение:
    • Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
    
    О -> 0 -> 00
    В -> 1 -> 01
    Д -> 2 -> 10
    П -> 3 -> 11
    А -> 4 -> 100
    
  • Теперь закодируем последовательность букв из слова ВОДОПАД:
  • 
    010010001110010
    
  • Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:
  • 
    010 010 001 110 010
     ↓   ↓   ↓   ↓   ↓
     2   2   1   6   2
    

    Результат: 22162

    Решение ЕГЭ данного задания по информатике, видео:


    Рассмотрим еще разбор 5 задания ЕГЭ:

    ЕГЭ 5.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
    a b c d e
    000 110 01 001 10

    Какой набор букв закодирован двоичной строкой 1100000100110?


    ✍ Решение:
    
    110 000 01 001 10
     ↓   ↓   ↓  ↓  ↓
     b   a  c   d  e 
    

    Результат: b a c d e.

    ✎ 2 вариант решения:

      Этот вариант решения 5 задания ЕГЭ более сложен, но тоже верен.
    • Сделаем дерево, согласно кодам в таблице:
    • Сопоставим закодированное сообщение с кодами в дереве:
    
    110 000 01 001 10

    Результат: b a c d e.

    Кроме того, вы можете посмотреть видео решения этого задания ЕГЭ по информатике:


    Решим следующее 5 задание:

    ЕГЭ 5.3:
    Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110).

    Определите, какое число пе­ре­да­ва­лось по ка­на­лу в виде 01100010100100100110.


    ✍ Решение:
    • Рассмотрим пример из условия задачи:
    
    Было 2310
    Стало 00101001102
  • Где сами цифры исходного числа (выделим их красным цветом):
  •  0010100110  (0010 - 2, 0011 - 3)
  • Первая добавленная цифра 1 после двоичной двойки — это проверка четности (1 единица в 0010 — значит нечетное), 0 после двоичной тройки — это также проверка нечетности (2 единицы в 0011, значит — четное).
  • Исходя из разбора примера решаем нашу задачу так: поскольку «нужные» нам цифры образуются из групп по 4 числа в каждой плюс одно число на проверку четности, то разобьем закодированное сообщение на группы по 5, и отбросим из каждой группы последний символ:
  • разбиваем по 5:
  • 01100 01010 01001 00110
  • отбрасываем из каждой группы последний символ:
  • 0110 0101 0100 0011
  • Результат переводим в десятичную систему:
  • 
    0110 0101 0100 0011
     ↓    ↓     ↓    ↓
     6    5     4    3
    

    Ответ: 6 5 4 3

    Вы можете посмотреть видео решения этого задания ЕГЭ по информатике:



    ЕГЭ 5.4:

    Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10.

    Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

    Подобные задания для тренировки


    ✍ Решение:1 вариант решения основан на логических умозаключениях:
    • Найдём самые короткие возможные кодовые слова для всех букв.
    • Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).
    • Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
    • Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
    • Суммарная длина всех четырёх кодовых слов равна:
    (Н)1 + (К)2 + (Л)3 + (М)3 = 9

    2 вариант решения:

    • Будем использовать дерево. Влево откладываем 0, вправо — 1:
    • Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:
    
    (Н) -> 0   -> 1 символ
    (К) -> 10  -> 2 символа
    (Л) -> 110 -> 3 символа
    (М) -> 111 -> 3 символа
    
  • Суммарная длина всех четырёх кодовых слов равна:
  • (Н)1 + (К)2 + (Л)3 + (М)3 = 9

    Ответ: 9



    5.5: ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 2 (под редакцией Крылова С.С., Чуркиной Т.Е.):

    По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова:

    
    А: 101010, 
    Б: 011011, 
    В: 01000
    

    Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

    Подобные задания для тренировки


    ✍ Решение:
    • Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010, Б начинается с нуля — 011011).
    • Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.

    Результат: 00



    5.6: ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 16 (под редакцией Крылова С.С., Чуркиной Т.Е.):

    Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код:

    
    А - 01 
    Б - 00
    В - 11
    Г - 100
    

    Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.


    ✍ Решение:
    • Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:
    • Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:
    • Перепишем сверху вниз получившееся кодовое слово для Д: 101

    Результат: 101

    Подробней разбор урока можно посмотреть на видео ЕГЭ по информатике 2017:


    5.7: 5 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

    По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

    Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

    Похожие задания для тренировки


    ✍ Решение:
    • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
    • При рассмотрении дерева видим, что все ветви «закрыты» листьями, кроме одной ветви — 1100:

    Результат: 1100

    Подробное решение данного 5 задания из демоверсии ЕГЭ 2018 года смотрите на видео:



    5.8: Задание 5_9. Типовые экзаменационные варианты 2017. Вариант 4 (Крылов С.С., Чуркина Т.Е.):

    По каналу связи передаются шифрованные сообщения, содержащие только четыре букв: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются кодовые слова:

    
    А: 00011 
    Б: 111 
    В: 1010
    

    Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.


    ✍ Решение:
    • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
    • Поскольку в задании явно не указано о том, что код должен удовлетворять условию Фано, то дерево нужно построить как с начала (по условию Фано), так и с конца (обратное условие Фано).
    • Дерево по условию Фано (однозначно декодируется с начала):

    • Получившееся числовое значение кодового слова для буквы Г01.
    • Дерево по обратному условию Фано (однозначно декодируется с конца):

    • Получившееся числовое значение кодового слова для буквы Г00.
    • После сравнения двух кодовых слов (01 и 00), код с наименьшим числовым значением — это 00.

    Результат: 00



    5.9: Тренировочный вариант №3 от 01.10.2018 (ФИПИ):

    По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:

    
    Е – 000
    Д – 10
    К – 111
    

    Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
    В ответе напишите число – количество бит.


    ✍ Решение:
    • С помощью дерева отобразим известные коды для букв:
    • В результирующем слове — ДЕДМАКАР — вде буквы А. Значит, для получения наименьшей длины необходимо для буквы А выбрать наименьший код в дереве. Учтем это и достроим дерево для остальных трех букв А, М и Р:
    • Расположим буквы в порядке их следования в слове и подставим их кодовые слова:
    
    Д   Е   Д   М   А   К   А   Р
    10 000 10  001 01  111 01  110
    
  • Посчитаем количество цифр в итоговом коде и получим 20.
  • Результат: 20

    Смотрите виде решения задания:


    labs-org.ru

    Разбор 15 задания егэ информатика

    На уроке рассматривается решение 15 задания ЕГЭ по информатике


    Объяснение заданий 15 ЕГЭ по информатике

    15 тема — «Графы и поиск количества путей» — характеризуется, как задания повышенного уровня сложности, время выполнения – примерно 3 минуты, максимальный балл — 1

    Графы. Поиск количества путей

    • Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть:
    • NR = NX + NY + NZ

    • где NR — это количество путей из вершины A в вершину R
    • Число путей не бесконечно, исключением является только граф, в котором есть циклы – замкнутые пути.
    • Часто задачи с графами целесообразней решать с конца.

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

    ЕГЭ по информатике 2017 задание 15 ФИПИ вариант 15 (Крылов С.С., Чуркина Т.Е.):

    На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

    Сколько существует различных путей, ведущих из города А в город М и проходящих через город Г?


    ✍ Решение:
    • Удалим ребра, которые проходят «мимо» вершины Г или до которых от пункта А можно дойти, минуя вершину Г:
    • Вершина В удалена, т.к. возможны только следующие траектории движения через этот пункт (которые НЕ проходят через пункт Г):
    • 1. А — Б — В — И — М
    • 2. А — Б — В — Е — И — М
    • 3. А — Б — В — Е — М
    • 4. А — Б — В — Е — К — М
    • Теперь посчитаем результаты по оставшимся вершинам:
    
    М = И + Е + К 
    -----
     И = Е 
       Е = Г + Ж 
        Г = Б + А + Д = 1 + 1 + 1 = 3 
        Ж = Г = 3
     К = Е + Ж
    
    Теперь возвращаемся, подставляя найденные значения: ↑
       Е = Г + Ж = 3 + 3 = 6 
        Ж = Г = 3
     И = Е = 6 (получили из последующих шагов)
     К = Е + Ж = 6 + 3 = 9       
    М = И + Е + К = 6 + 6 + 9 = 21  
    

    Результат: 21

    Видео ЕГЭ по информатике 2017, подробное решение данного 15 задания:

    ЕГЭ по информатике 2017 задание 15 ФИПИ вариант 14 (Крылов С.С., Чуркина Т.Е.):

    На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

    Сколько существует различных путей, ведущих из города А в город М и не проходящих через город Г?


    ✍ Решение:
    • Удалим ребра, которые проходят через вершину Г:
    • Теперь посчитаем результаты по оставшимся вершинам:
    
    М = И + Е + К
    -----
    И = В + Е
      В = 1
      Е = В + Ж
         Ж = 1
    
    Теперь возвращаемся, подставляя найденные значения: ↑
      Е = В + Ж = 1 + 1 = 2
    И = В + Е = 1 + 2 = 3 
    К = Е = 2 
    М = И + Е + К = 3 + 2 + 2 = 7  
    

    Результат: 7

    Подробное решение данного 15 задания в видеоуроке:

    15 задание. Демоверсия ЕГЭ 2018 информатика:

    На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
    По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

    Сколько существует различных путей из города А в город М, проходящих через город Ж?


    ✍ Решение:

    Результат: 20

    Подробное решение 15 задания демоверсии ЕГЭ 2018 года смотрите на видео:

    labs-org.ru

    Как решать 5 задание ЕГЭ по информатике 2018

    5-е задание: «Кодирование и расшифровка сообщений»
    Уровень сложности — базовый,
    Максимальный балл — 1,
    Примерное время выполнения — 2 минуты.

    ЕГЭ 5.1: Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).

    Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

    Ответ: 22162

    ✍ Показать решение:
    • Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
    
    О -> 0 -> 00
    В -> 1 -> 01
    Д -> 2 -> 10
    П -> 3 -> 11
    А -> 4 -> 100
    
  • Теперь закодируем последовательность букв из слова ВОДОПАД:
  • 
    010010001110010
    
  • Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:
  • 
    010 010 001 110 010
     ↓   ↓   ↓   ↓   ↓
     2   2   1   6   2
    

    📹 Видео


    ЕГЭ 5.2: Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
    a b c d e
    000 110 01 001 10

    Какой набор букв закодирован двоичной строкой 1100000100110?

    Ответ: b a c d e

    ✍ Показать решение:
    
    110 000 01 001 10
     ↓   ↓   ↓  ↓  ↓
     b   a  c   d  e 
    

    Результат: b a c d e.

    ✎ 2 вариант решения:

      Этот вариант решения 5 задания ЕГЭ более сложен, но тоже верен.
    • Сделаем дерево, согласно кодам в таблице:
    • Сопоставим закодированное сообщение с кодами в дереве:
    
    110 000 01 001 10

    📹 Видео


    ЕГЭ 5.3:
    Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110).

    Определите, какое число пе­ре­да­ва­лось по ка­на­лу в виде 01100010100100100110.

    Ответ: 6 5 4 3

    ✍ Показать решение:
    • Рассмотрим пример из условия задачи:
    
    Было 2310
    Стало 00101001102
  • Где сами цифры исходного числа (выделим их красным цветом):
  •  0010100110  (0010 - 2, 0011 - 3)
  • Первая добавленная цифра 1 после двоичной двойки — это проверка четности (1 единица в 0010 — значит нечетное), 0 после двоичной тройки — это также проверка нечетности (2 единицы в 0011, значит — четное).
  • Исходя из разбора примера решаем нашу задачу так: поскольку «нужные» нам цифры образуются из групп по 4 числа в каждой плюс одно число на проверку четности, то разобьем закодированное сообщение на группы по 5, и отбросим из каждой группы последний символ:
  • разбиваем по 5:
  • 01100 01010 01001 00110
  • отбрасываем из каждой группы последний символ:
  • 0110 0101 0100 0011
  • Результат переводим в десятичную систему:
  • 
    0110 0101 0100 0011
     ↓    ↓     ↓    ↓
     6    5     4    3
    

    📹 Видео


    ЕГЭ 5.4:
    Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 10.

    Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

    Подобные задания для тренировки

    Ответ: 9

    ✍ Показать решение: ✎ 1 вариант решения основан на логических умозаключениях:
    • Найдём самые короткие возможные кодовые слова для всех букв.
    • Кодовые слова 01 и 00 использовать нельзя, так как тогда нарушается условие Фано (начинаются с 0, а 0 — это Н).
    • Начнем с двухразрядных кодовых слов. Возьмем для буквы Л кодовое слово 11. Тогда для четвёртой буквы нельзя подобрать кодовое слово, не нарушая условие Фано (если потом взять 110 или 111, то они начинаются с 11).
    • Значит, надо использовать трёхзначные кодовые слова. Закодируем буквы Л и М кодовыми словами 110 и 111. Условие Фано соблюдается.
    • Суммарная длина всех четырёх кодовых слов равна:
    (Н)1 + (К)2 + (Л)3 + (М)3 = 9

    2 вариант решения:

    • Будем использовать дерево. Влево откладываем 0, вправо — 1:
    • Теперь выпишем соответствие каждой буквы ее кодового слова согласно дереву:
    
    (Н) -> 0   -> 1 символ
    (К) -> 10  -> 2 символа
    (Л) -> 110 -> 3 символа
    (М) -> 111 -> 3 символа
    
  • Суммарная длина всех четырёх кодовых слов равна:
  • (Н)1 + (К)2 + (Л)3 + (М)3 = 9

    ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 2 (под редакцией Крылова С.С., Чуркиной Т.Е.):

    По каналу связи передаются сообщения, содержащие только 4 буквы: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова:

    
    А: 101010, 
    Б: 011011, 
    В: 01000
    

    Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

    Подобные задания для тренировки

    Ответ: 00

    ✍ Показать решение:
    • Наименьшие коды могли бы выглядеть, как 0 и 1 (одноразрядные). Но это не удовлетворяло бы условию Фано (А начинается с единицы — 101010, Б начинается с нуля — 011011).
    • Следующим наименьшим кодом было бы двухбуквенное слово 00. Так как оно не является префиксом ни одного из представленных кодовых слов, то Г = 00.

    ЕГЭ по информатике 5 задание 2017 ФИПИ вариант 16 (под редакцией Крылова С.С., Чуркиной Т.Е.):

    Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код:

    
    А - 01 
    Б - 00
    В - 11
    Г - 100
    

    Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.

    Ответ: 101

    ✍ Показать решение:
    • Так как необходимо найти кодовое слово наименьшей длины, воспользуемся деревом. Влево будем откладывать нули, а вправо — единицы:
    • Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:
    • Перепишем сверху вниз получившееся кодовое слово для Д: 101

    📹 Видео


    5 задание. Демоверсия ЕГЭ 2018 информатика (ФИПИ):

    По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

    Укажите кратчайшее кодовое слово для буквы Б, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.

    Похожие задания для тренировки

    Ответ: 1100

    ✍ Показать решение:
    • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
    • При рассмотрении дерева видим, что все ветви «закрыты» листьями, кроме одной ветви — 1100:

    📹 Видео


    Типовые экзаменационные варианты 2017. Вариант 4 (Крылов С.С., Чуркина Т.Е.):

    По каналу связи передаются шифрованные сообщения, содержащие только четыре букв: А, Б, В, Г; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются кодовые слова:

    
    А: 00011 
    Б: 111 
    В: 1010
    

    Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

    Ответ: 00

    Показать решение:
    • Для решения будем использовать дерево. Ветви, соответствующие нулю, будем откладывать влево, единице — вправо.
    • Поскольку в задании явно не указано о том, что код должен удовлетворять условию Фано, то дерево нужно построить как с начала (по условию Фано), так и с конца (обратное условие Фано).
    • Дерево по условию Фано (однозначно декодируется с начала):

    • Получившееся числовое значение кодового слова для буквы Г01.
    • Дерево по обратному условию Фано (однозначно декодируется с конца):

    • Получившееся числовое значение кодового слова для буквы Г00.
    • После сравнения двух кодовых слов (01 и 00), код с наименьшим числовым значением — это 00.

    Результат: 00


    Тренировочный вариант №3 от 01.10.2018 (ФИПИ):

    По каналу связи передаются сообщения, содержащие только буквы: А, Е, Д, К, М, Р; для передачи используется двоичный код, удовлетворяющий условию Фано. Известно, что используются следующие коды:

    
    Е – 000
    Д – 10
    К – 111
    

    Укажите наименьшую возможную длину закодированного сообщения ДЕДМАКАР.
    В ответе напишите число – количество бит.

    Ответ: 20

    Показать решение:
    • С помощью дерева отобразим известные коды для букв:
    • В результирующем слове — ДЕДМАКАР — вде буквы А. Значит, для получения наименьшей длины необходимо для буквы А выбрать наименьший код в дереве. Учтем это и достроим дерево для остальных трех букв А, М и Р:
    • Расположим буквы в порядке их следования в слове и подставим их кодовые слова:
    
    Д   Е   Д   М   А   К   А   Р
    10 000 10  001 01  111 01  110
    
  • Посчитаем количество цифр в итоговом коде и получим 20.
  • Результат: 20

    📹 Видео


    labs-org.ru

    Отправить ответ

    avatar
      Подписаться  
    Уведомление о