cart-icon Товаров: 0 Сумма: 0 руб.
г. Нижний Тагил
ул. Карла Маркса, 44
8 (902) 500-55-04

Правило фано – А9 — ЕГЭ по информатике

    Условие Фано

    Здравствуйте! Меня зовут Александр Георгиевич и я являюсь московским профессиональным репетитором по информатике и программированию. Вам попалась задача, связанная с кодированием и декодированием информации, и вы запутались в алгоритме ее решения? Вам срочно нужно познакомиться с условием Фано, а также записаться ко мне на индивидуальные уроки. На своих уроках я акцентирую внимание на решении тематических простых и сложных упражнений.

    В чем смысл прямого условия Фано?

    Условие Фано названо в честь его создателя, итальянско-американского ученого Роберта Фано. Условие является необходимым в теории кодирования при построении самотерминирующегося кода. Учитывая другую терминологию, такой код называется префиксным.

    Сформулировать данное условие можно следующим образом: «ни одно кодовое слово не может выступать в качестве начала любого другого кодового слова».

    С математической точки зрения условие можно сформулировать следующим образом: «если код содержит слово B, то для любой непустой строки C слова BC не существует в коде».

    В чем смысл обратного условия Фано?

    Существует также и обратное правило Фано, формулировка которого звучит следующим образом: «ни одно кодовое слово не может выступать в качестве окончания любого другого кодового слова».

    С математической точки зрения обратное условие можно сформулировать следующим образом: «если код содержит слово B, то для любой непустой строки C слова CB не существует в коде».

    Практическое применение условия Фано

    Рассмотрим телефонные номера в традиционной телефонии. Если уже существует номер «102», то номер «1029876» попросту не будет выдан. В случае набора первых трех цифр АТС перестает распознавать и принимать все остальные цифры, соединяя с абонентом по номеру 102. Однако это правило не является действительным для операторов мобильной связи. Связано это с тем, что для набора номера необходимо нажатие соответствующей клавиши, которой, в основном, является клавиша с изображением зеленой телефонной трубки. По этой причине, номера «102», «1020» и «1029876» могут существовать и быть закрепленными за разными адресатами.

    Условие задачи: дана последовательность, которая состоит из букв «A», «B», «C», «D» и «E». Для кодирования приведенной последовательности применяется неравномерный двоичный код, при помощи которого можно осуществить однозначное декодирование.

    Буква

    A

    B

    C

    D

    E

    Двоичный эквивалент

    00

    010

    011

    101

    111


    Вопрос: есть ли возможность для одного из символов сократить длину кодового слова таким образом, чтобы сохранить возможность однозначного декодирования? При этом коды остальных символов должны остаться неизменными.

     

    Номер варианта

    1

    2

    3

    4

    Ответ

    B – 01

    Не представляется возможным

    C – 01

    D – 01

    Решение: для того, чтобы сохранилась возможность декодирования, достаточным является соблюдение прямого или обратного условия Фано. Проведем последовательную проверку вариантов 1, 3 и 4. В случае если ни один из вариантов не подойдет, правильным ответом будет вариант 2 (не представляется возможным).

    Вариант 1. Код: A — 00, B — 01, C — 011, D — 101, и E — 111. Прямое условие Фано не выполняется: код символа «B» совпадает с началом кода символа «C». Обратное правило Фано не выполняется: код символа «B» совпадает с окончанием кода символа «D». Вариант не является подходящим.

    Вариант 3. Код: A — 00, B — 010, C — 01, D — 101, и E — 111. Прямое условие Фано не выполняется: код символа «C» совпадает с началом кода символа «B». Обратное условие также не выполняется: код символа «C» совпадает с окончанием кода символа «D». Вариант не является подходящим.

    Вариант 4. Код: A — 00, B — 010, C — 011, D — 01, и E — 111. Прямое условие Фано не выполняется: код символа «D» совпадает с началом кода символов «B» и «C». Однако наблюдается выполнение обратного правила Фано: код символа «D» не совпадает с окончанием кода всех остальных символов. По этой причине, вариант является подходящим.

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

    Ответ: 4

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

    Остались вопросы?

    Если после прочтения данной публикации у вас все равно остались какие-то вопросы, непонимания или вы хотите закрепить пройденный материал практическими решениями, то звоните и записывайтесь ко мне на частные уроки по информатике и ИКТ.

    www.videoege.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 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
    abcde
    0001100100110

    Какой набор букв закодирован двоичной строкой 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 задание 2017 ФИПИ вариант 2 (под редакцией Крылова С.С., Чуркиной Т.Е.):

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

    101010, Б: 011011, В: 01000.

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


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

    Результат: 00

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

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

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


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

    • Поскольку у нас все ветви завершены листьями, т.е. буквами, кроме одной ветви, то остается единственный вариант, куда можно поставить букву Д:

    • Перепишем сверху вниз получившееся кодовое слово для Д: 101

    Результат: 101

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

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

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

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


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

    • Теперь, начиная с однобитных кодов, и, двигаясь сверху вниз, подбираем такой код, который бы удовлетворял условию Фано. С 0 можно не начинать, так как уже есть код 0 для буквы А:
    
1   - не подходит (все буквы кроме А начинаются с 1)
10  - не подходит (соответствует коду Д)
11  - не подходит (начало кодов Б, В и Г)
100 - не подходит (код Д - 10 - является началом данного кода)
101 - не подходит (код Д - 10 - является началом данного кода)
110 - не подходит (начало кода В и Г)
111 - не подходит (соответствует коду Б)
1000 - не подходит (код Д - 10 - является началом данного кода)
1001 - не подходит (код Д - 10 - является началом данного кода)
1010 - не подходит (код Д - 10 - является началом данного кода)
1011 - не подходит (код Д - 10 - является началом данного кода)
1100 - не подходит (начало кода В и Г)
1101 - подходит

    Результат: 1101

    Более подробное решение данного задания представлено в видеоуроке:

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

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

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

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


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

    • При рассмотрении дерева видим, что все ветви «закрыты» листьями, кроме одной ветви — 1100:

    Результат: 1100

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

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

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

    
А: 00011 
Б: 111 
В: 1010

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


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

      • Дерево по условию Фано (однозначно декодируется с начала):

    • Получившееся числовое значение кодового слова для буквы Г — 01.

      • Дерево по обратному условию Фано (однозначно декодируется с конца):

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

    Результат: 00

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

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

    
Е – 000
Д – 10
К – 111

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


    ✍ Решение:
    • С помощью дерева отобразим известные коды для букв:

    • В результирующем слове — ДЕДМАКАР — вде буквы А. Значит, для получения наименьшей длины необходимо для буквы А выбрать наименьший код в дереве. Учтем это и достроим дерево для остальных трех букв А, М и Р:

    • Расположим буквы в порядке их следования в слове и подставим их кодовые слова:
    
Д   Е   Д   М   А   К   А   Р
10 000 10  001 01  111 01  110
  • Посчитаем количество цифр в итоговом коде и получим 20.

    • Результат: 20

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

    labs-org.ru

    Материал для подготовки к ЕГЭ (ГИА) по информатике и икт (9, 11 класс) по теме: Однозначное декодирование. Условие Фано

    Слайд 1

    Однозначное декодирование Прямое и обратное условие Фано Учитель информатики и ИКТ МБОУ СОШ № 7 г. Оха Сахалинской области Сергиенко Татьяна Геннадьевна

    Слайд 2

    Задача 1 Пусть для кодирования фразы «Доброе утро» выбран такой код: Д О Б Р Е У Т Пробел 111 000 00 1 01 0 10 11

    Слайд 3

    Коды букв «сцепляются» в единую битовую строку и передаются, например, по сети: Доброе утро→ 11100000100001110101000 В пункте назначения возникает проблема – как восстановить исходное сообщение, и возможно ли это.

    Слайд 4

    11100000100001110101000 Раскодировать данное сообщение можно разными способами. В том числе предположим, что оно состоит только из букв Р – 1 и У – 0. Тогда получим РРРУУУУУРУУУУРРРУРУРУУУ, т.е. бессмысленный набор букв .

    Слайд 5

    Код называется однозначно декодируемым , если любое кодовое сообщение можно расшифровать единственным способом (однозначно ).

    Слайд 6

    Значит, код не является однозначно декодируемым.

    Слайд 7

    Задача 2 Равномерные коды. Для той же фразы используем равномерный код: Д О Б Р Е У Т Пробел 111 000 001 101 011 010 100 110

    Слайд 8

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

    Слайд 9

    Задача 3 Чтобы сократить длину сообщения, можно попробовать применить неравномерный код, т.е. код, в котором кодовые слова, соответствующие разным символам исходного алфавита, могут иметь разную длину, от одного до нескольких символов.

    Слайд 10

    Используем следующий код: 0100101110000101011111101111010000 Эта битовая цепочка декодируется однозначно. Д О Б Р Е У Т Пробел 01 00 1011 100 1010 1101 1110 1111

    Слайд 11

    Первая буква — Д (код 01), т.к. ни одно другое кодовое слово не начинается с 01. Вторая буква – О (код 00). Никакое другое слово не начинается с 00. Это же свойство, которое называется условием Фано , выполняется и для кодовых слов других букв.

    Слайд 12

    УСЛОВИЕ ФАНО Никакое кодовое слово не совпадает с началом другого кодового слова. Такие коды называются префиксными (раскодируются с начала сообщения) и декодируются однозначно.

    Слайд 13

    Задача 4 Рассмотрим ещё один код: Он не является префиксным, т.к. код буквы Д (10 ) совпадает с началом кода буквы Б (1011), У(1000) и код буквы О(00) совпадает с началом кода буквы Р (001 ). Д О Б Р Е У Т Пробел 10 00 1011 001 0101 1000 0111 1111

    Слайд 14

    Закодируем наше сообщение: ДОБРОЕ УТРО→ 10 00 1011 001 00 0101 1111 1000 0111 001 00 Начнём раскодировать с начала. Первая – Д, или У, а дальше идут вообще разные варианты : Р или Б… Т.е. надо «заглядывать» вперёд, что очень неудобно.

    Слайд 15

    Попробуем раскодировать сообщение с конца – оно однозначно декодируется! Выполняется обратное условие Фано : никакое кодовое слово не совпадает с окончанием другого кодового слова.

    Слайд 16

    Коды , для которых выполняется обратное условие Фано , называются постфиксными.

    Слайд 17

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

    Слайд 18

    Условие Фано — это достаточное, но не необходимое условие однозначной декодируемости Это значит, что: — для однозначной декодируемости достаточно выполнения хотя бы одного из двух условий — прямого или обратного. — могут существовать коды, для которых не выполняется ни прямое, ни обратное условие Фано , но тем не менее обеспечивается однозначное декодирование, т.к. иначе теряется смысл выражения.

    Слайд 19

    Задача 5 Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110.

    Слайд 20

    Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа: 1) для буквы Д -11 2) это невозможно 3) для буквы Г — 10 4) для буквы Д -10

    Слайд 21

    РЕШЕНИЕ: Исходный код – префиксный. Для него выполняется условие Фано – ни один из трёхбитных кодов не начинается ни с 00 (А), ни с 01 (Б). (При этом обратное условие Фано не выполняется – код А (00) совпадает с окончанием В (100), а код Б (01) совпадает с окончанием Г (101 ).)

    Слайд 22

    Теперь проверим ответы. Сократим Д до 11. Если полученный код нарушит прямое условие Фано , то свойство однозначного декодирования будет нарушено. Но этого не произошло, нет других кодов, начинающихся с 11. Это и есть верное решение. Проверим остальные варианты.

    Слайд 23

    Вариант 2 сразу не рассматриваем – ответ у нас найден. Вариант 3 нарушает прямое условие Фано – с 10 начинается код буквы В (101). Вариант 4 – так же нарушает прямое условие Фано . Т.е. ответ однозначный, других вариантов нет.

    Слайд 24

    Спасибо за внимание!

    nsportal.ru

    3. Коды без разделителя. Условие Фано

    Рассмотрев один из вариантов двоичного неравномерного кодирования, попробуем найти ответ на следующий вопрос: возможно ли такое кодирование без использования разделительных знаков?

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

    Наиболее простыми и употребимыми кодами без разделителя являются так называемые префиксные коды, которые удовлетворяют следующему условию –условию Фано:Сообщение, закодированное с использованием неравномерного кода может быть однозначно декодировано, если никакой из кодов в данном сообщении не совпадает с префиксом* (началом) какого-либо иного более длинного кода.

    Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр.

    Если условие Фано выполняется, то при прочтении (декодировании, расшифровке) закодированного сообщения путем сопоставления с таблицей кодов всегда можно точно указать, где заканчивается один код и начинается другой.

    Пример 1. Являются ли коды, представленные втабл. 4,префиксными? Коды, представленные в табл. 4, не являются префиксными. См., например, коды букв «О» и «Е», «А» и «Н», «С» и «М», «Д» и «Ч».

    Пример 2. Имеется таблица префиксных кодов (табл. 6). Требуется декодировать следующее сообщение, закодированное с использованием этой приведенной кодовой таблицы:

    00100010000111010101110000110

    Табл. 6. Таблица префиксных кодов

    А

    Л

    М

    Р

    У

    Ы

    10

    010

    00

    11

    0110

    0111

    Декодирование производится циклическим повторением следующих действий:

    1. «Отрезать» от текущего сообщения крайний слева символ, присоединить его справа к рабочему (текущему) кодовому слову;

    2. сравнить текущее кодовое слово с кодовой таблицей; если совпадения нет, вернуться к пункту 1.

    3. С помощью кодовой таблицы текущему кодовому слову поставить в соответствие символ первичного алфавита;

    4. Проверить, имеются ли еще знаки в закодированном сообщении; если да, то перейти к пункту 1.

    Применение данного алгоритма к предложенному выше закодированному сообщению дает:

    00100010000111010101110000110

    00

    10

    00

    10

    00

    0111

    010

    10

    11

    10

    00

    0110

    м

    а

    м

    а

    м

    ы

    л

    а

    р

    а

    м

    у

    Таким образом, доведя процедуру декодирования до конца, можно получить сообщение: «мама мыла раму».

    Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков.

    Однако условие Фано не устанавливает конкретного способа формирования префиксного кода, оставляя поле для деятельности по разработке наилучшего из возможных префиксных кодов.

    4. Префиксный код Шеннона–Фано

    Рассмотрим вариант кодирования, который был предложен в 1948 – 1949 гг. независимо К. Шенноном и Р. Фано.

    Рассмотрим схему кодирования (как она строится) Шеннона–Фано на следующем примере.

    Пусть имеется первичный алфавит , состоящий из шести знаков:, где. Пусть вероятности появления этих знаков в сообщениях таковы:,,,,и. Расположим эти знаки в таблице в порядке убывания вероятностей.

    Разделим знаки на две группы так, чтобы суммы вероятностей в каждой из этих двух групп были бы приблизительно равными. При этом в 1-ю группу попадут и, а остальные – во 2-ю группу. Знакампервой группы присвоим первый слева разряд их кодов «0», а первым слева разрядом кодов символов второй группы пусть будет «1».

    Продолжим деление каждой из получающихся групп на подгруппы по той же схеме, то есть так, чтобы суммы вероятностей на каждом шаге в обеих подгруппах делимой группы были бы возможно более близкими. Таким образом будем получать по одному следующие разряды кодов символов . Эти следующие разряды будем приписывать справа к уже имеющимся.

    Вся эта процедура может быть схематически изображена в табл 7.

    Табл. 7. Построение кода Шеннона-Фано

    Знак

    Разряды кода

    Код

    1-й

    2-й

    3-й

    4-й

    0.30

    0

    0

    00

    0.20

    0

    1

    01

    0.20

    1

    0

    10

    0.15

    1

    1

    0

    110

    0.10

    1

    1

    1

    0

    1110

    0.05

    1

    1

    1

    1

    1111

    Видно, что построенные коды знаков удовлетворяют условию Фано, следовательно, такое кодирование является префиксным.

    Найдем среднюю длину полученного кода по формуле

    ,

    где – число разрядов (символов) в коде, соответсвующем символу.

    Из таблицы видно, что ,,.

    Таким образом, получаем:

    .

    Таким образом, для кодирования одного символа первичного алфавитапотребовалось в среднем 2.45 символов вторичного (двоичного) алфавита.

    Определим среднее количество информации, приходящееся на знак первичного алфавита в первом приближении (с учетом различной вероятности появления этих знаков в сообщениях). Применим формулу Шеннона:

    .

    Найдем избыточность полученного двоичного кода:

    ,

    то есть избыточность – около 2.5.

    Выясним, является ли полученный код оптимальным. Нулей в полученных кодах – 6 штук, а единиц – 11 штук. Таким образом, вероятности появления 0 и 1 далеко не одинаковы. Следовательно, полученный код нельзя считать оптимальным.

    studfiles.net

    Сайт учителя информатики Ахметжановой М.

    Решение задач   А9 на тему  «Кодирование и декодирование информации»

    Уровень сложности-базовый,  время выполнения 2 мин

    Видеоуроки on-line

    http://videouroki.net/view_post.php?id=149 (сайт Д. Тарасова)

    Справочный материал:

    Существует равномерное и неравномерное кодирование. При равномерном кодировании сообщение декодируется однозначно.

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

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

     Однозначно декодировать – получить один единственный точный вариант. 

     

    Примеры решения задач на выполнение условия Фано

    Пример 1 A9  Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице: 

    a          b          c          d          e

    000      110      01        001      10

    Определите, какой набор букв закодирован двоичной строкой 1100000100110

    1) baade      2) badde        3) bacde     4) bacdb

    Решение: Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.

    Разобьём код слева направо по данным таблицы и переведём его в буквы:

    110 000 01 001 10 — b a c d e.

    Правильный ответ указан под номером 3.

    Пример 2 A9 . Для 6 букв латинского алфавита заданы их двоичные коды (для некоторых букв из двух бит, для некоторых – из трех). Эти коды представлены в таблице: 

    A         B         C         D         E         F

    00        100      10        011      11        101

    Определите, какая последовательность из 6 букв закодирована двоичной строкой 011111000101100.

    1) DEFBAC        2) ABDEFC     3) DECAFB     4) EFCABD

    Решение:.

    Мы видим, что условия Фано и обратное условие Фано не выполняются, значит код можно раскодировать неоднозначно.

    Будем пробовать разные варианты, отбрасывая те, в которых получаются повторяющиеся буквы:

    1) 011 11 100 0101100

    Первая буква определяется однозначно, её код 011: D.

    Вторая буква также определится однозначно  — E.

    Пусть третья буква B, тогда следующая начинается с кода 010, но таких букв в таблице нет, значит предположение не верно.

    2) 011 11 10 00 101 100

    Третья буква — С, потом — A. Мы хотим получить ещё две буквы, чтобы в сумме их было 6, тогда следующая буква — F, и последняя  — B.

    Окончательно получили ответ: DECAFB.

    Правильный ответ указан под номером 3.

    Пример 3 A9 Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111. 

    Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

     1) это невозможно          2) для буквы В – 000

    3) для буквы Б – 0            4) для буквы Г – 11

    Решение.

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

    Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.

    Вариант 3 не подходит, потому что 0 является началом кода 0001.

    Вариант 4 не подходит, потому что код 1 является началом кода 111.

    Вариант 2 подходит, так как не нарушает условия Фано.

    Правильный ответ указан под номером 2.

    Задачи А9     Кодирование+Системы счисления

    Для решения этих задач нужно знать алгоритм перевода из двоичной системы счисления в восьмеричную и шестнадцатеричную.

    Пример 1 A9  Для кодирования букв А, Б, В, Г используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов БГАВ и записать результат в восьмеричном коде, то получится:

    1) 175423    2) 115612  3) 62577     4) 12376

    Решение .

    Закодируем последовательность букв: БГАВ — 1001101110001010. Теперь разобьём это представление на тройки справа налево и переведём полученный набор чисел сначала в десятичный код,(в таком представлении восьмеричный код совпадает с десятеричным):

    1 001 101 110 001 010 — 1 1 5 6 1 2.

    Правильный ответ указан под номером 2.

    Пример 2 A9 Для кодирования букв А, В, С, D используются трехразрядные последовательные двоичные числа, начинающиеся с 1 (от 100 до 111 соответственно). Если таким способом закодировать последовательность символов CDAB и записать результат в шестнадцатеричном коде, то получится: 

    1) А52    2) 4С8          3) 15D    4) DE5

    Решение.

    Закодируем последовательность букв: CDAB — 110111100101. Теперь разобьём это представление на четвёрки справа налево и переведём полученный набор чисел сначала в десятичный код, затем в шестнадцатеричный:

    1101 1110 0101 — 13 14 5 — DE5.

    Правильный ответ указан под номером 4.

    Задачи А9   Найти правильное кодирование

    Пример 1  Для кодирования сообщения, состоящего только из букв A, B, C, D и E, используется неравномерный по длине двоичный код: 

    A         B         C         D         E

    000      11        01        001      10

    Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

    1) 110000010011110                 2) 110000011011110

    3) 110001001001110                   4) 110000001011110

    Решение.

    Разобьём каждый ответ на посимвольный код и найдём нужное:

    Вариант 1: 11 000 001 001 11 10 (этот вариант уже подходит, но проверим и остальные).

    Вариант 2: 11 000 001 10 11 11 0 — последняя часть кода не может быть раскодирована.

    Вариант 3: 11 000 10 01 001 11 0 — аналогично.

    Вариант 4: 11 000 000 10 11 11 0 0 — аналогично.

    Правильный ответ указан под номером 1.

    Пример 2 A9 . Для кодирования сообщения, состоящего только из букв О, К, Л, М и Б, используется неравномерный по длине двоичный код: 

    О         К         Л         М        Б

    00        01        11        010      0110

    Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

    1) 110001001001110       2) 10000011000111010

    3) 110001001101001      4) 1000110001100010

    Решение:

    Разобьём каждый ответ на посимвольный код и найдём нужный  вариант:

    Вариант 1: 11 00 010 01 00 11 10 — при таком разбиении последняя часть кода может быть раскодирована, а если разбить по-другому 11 00 01 00 10011, то сообщение также недекодируемо.

    В вариантах 2 и 4 невозможно раскодировать начало кода.

    Вариант 3: 11 00 01 00 11 01 00 1  — при таком разбиении последняя часть кода может быть раскодирована. Разобьём по-другому: 11 00 01 00 11 010 01 — такой вариант разбиения может быть раскодирован.

     .Правильный ответ указан под номером 3.

     

    Задачи на кодирование буквы

    Пример 1 A9 . Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? 

    1) 0001      2) 000       3) 11      4) 101    

    Решение. .

    Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.

    Рассмотрим варианты для буквы Г, начиная с самого короткого.

    3) Г=11: код буквы A является началом этого кода, поэтому этот вариант не подходит.

    4) Код Г=101 не подходит по аналогичной причине.

    2) Код Г=000 не сопадает с началом ни одного кода,следовательно это и есть правильный ответ.

    Правильный ответ указан под номером 2.

    Другие задачи на кодирование

    Пример 1 A9 . По каналу связи передаются сообщения, содержащие только 4 буквы: E, H, O, T. Для кодирования букв E, H, O используются 5-битовые кодовые слова: E — 00000, H — 00111, O — 11011. 

    Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трех позициях.

    Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы T, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

    1) 11111        2) 11100        3) 00011           4) не подходт ни одно из указанных выше слов

    Решение   Пользуясь правилом «любые два слова из набора отличаются не менее чем в трех позициях» проверим все возможные варианты.

    Число 11111 отличается от кодового слова 00111 только в двух позициях.

    Число 11100 отличается от кодового слова 00000 — в трех позициях, от 00111 — в четырех позициях, 11011 — в трех позициях.

    Правильный вариант ответа второй.

     

    akhmetganovams.ucoz.net

    Утверждены правила взаимодействия РАН и ФАНО

    На сайте Правительства РФ опубликовано постановление, посвященное координации деятельности РАН и ФАНО, а также положение о закупке Академией наук товаров, работ и услуг.

    На сайте Правительства России 3 июня были опубликованы два утвержденных правительством и подписанных премьер-министром Дмитрием Медведевым документа: «Правила координации деятельности Федерального агентства научных организаций и федерального государственного бюджетного учреждения «Российская академия наук» при реализации возложенных на них полномочий» и Положение о закупке товаров, работ и услуг РАН.

    В первом документе Академии наук предписывается согласовывать с ФАНО планы научных исследований своих институтов, в рамках выполнения утвержденной кабинетом министров в 2012 г. «Программы фундаментальных научных исследований государственных академий наук на 2013-2020 годы». Также РАН должна проводить оценку научной работы институтов, проверять полученные ими результаты и согласовывать с ФАНО кандидатуры на должности их научных руководителей.

    Правительство, согласно этому документу, координирует взаимодействие Академии и федерального агентства в соответствии с законодательством РФ и соглашением о сотрудничестве между РАН и ФАНО, заключенным 10 сентября 2014 года. Координация осуществляется через издание Правительством нормативных актов, проведение совещаний (которые может инициировать как президент Академии, так и глава федерального агентства) и образование координационных и совещательных органов.

    При возникновении конфликта между РАН и ФАНО, стороны должны сначала постараться урегулировать его сами, созвав в течение 10 дней согласительное совещание. Если это не дает результата, руководители обеих организаций подписывают соответствующий протокол и направляют его в Правительство. Последующие действия кабмина в связи с этим в документе не прописаны, однако указано, что «обеспечением разрешения и устранения разногласий» между учеными и чиновниками будет заниматься соответствующий зампред Правительства РФ.

    В комментарии к «Правилам координации…» на правительственном сайте выражается уверенность, что они будут «способствовать эффективному взаимодействию ФАНО России и Российской академии наук при реализации возложенных на них полномочий».

    Что же касается второго документа, то в нем содержатся требования к закупкам, производимым РАН, в том числе за счет грантов. Устанавливается порядок подготовки к закупкам, выбор участников и проведение процедур, а также порядок заключения и исполнения договоров. Академии предписывается размещать информацию по проведению каждой закупки в Единой информационной системе (ЕИС) в сфере госзакупок.

    В целом, опубликованные документы лежат полностью в рамках общей тенденции продолжающегося реформирования российской науки. Пока что оно идет не слишком гладко — так, обнародованные недавно Минобрнауки планы по оптимизации субсидирования научных институтов заставили ученых говорить о надвигающемся «бюрократическом апокалипсисе». Далеки от радужных и отношения РАН и ФАНО, что выразилось уже в нескольких громких скандалах. Например, когда федеральное агентство отказалось спасать научное судно «Академик Николай Страхов» на Шри-Ланке, или когда попыталось уволить директора Института геохимии, академика Эрика Галимова, резко критиковавшего его деятельность.

    Острые вопросы взаимодействия с ФАНО обсуждались на III Конференции научных работников, проходившей 29 мая в Президиуме РАН в Москве. Мы вели текстовую трансляция этого события, да и вообще регулярно сообщаем новости о реформе РАН.

    scientificrussia.ru

    Правительство утвердило правила координации деятельности ФАНО и РАН — Наука

    МОСКВА, 3 июня. /ТАСС/. Правительство РФ утвердило правила координации деятельности Федерального агентства научных организаций (ФАНО) и Российской академии наук (РАН), а также положение о закупке товаров, работ и услуг РАН. Соответствующие документы, подписанные премьер-министром Дмитрием Медведевым, опубликованы 3 июня на официальном сайте кабмина.

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

    Дмитрий Медведев

    председатель правительства РФ

    Координация взаимодействия

    В правительстве напомнили, что ФАНО и РАН взаимодействуют в рамках Научно-координационного совета, образованного агентством, а также в соответствии с соглашением о сотрудничестве между ФАНО и Академией, заключенным 10 сентября 2014 года.

    Подписанным постановлением утверждены правила координации деятельности ФАНО и РАН при реализации возложенных на них полномочий. Также внесены изменения в Положение о ФАНО России в части согласования с Академией программ развития научных организаций, подведомственных агентству.

    «В целях координации деятельности ФАНО и РАН правительство будет издавать нормативные правовые акты, проводить совещания по предложениям руководителей этих организаций, а также создавать соответствующие координационные и совещательные органы, — проинформировали в кабмине. — Кроме этого, установлено, что при взаимодействии с ФАНО в отношении подведомственных ему научных организаций РАН должна согласовывать планы проведения научных исследований, проводить оценку научной деятельности, экспертизу научных и (или) научно-технических результатов, согласовывать кандидатуры на должности научных руководителей научных организаций, уставами которых предусмотрена такая должность».

    Реализация положений этого документа будет способствовать эффективному взаимодействию ФАНО и РАН, уверены в правительстве.

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

    Документ регулирует отношения, связанные с закупками, которые РАН проводит, в частности, за счет грантов и в качестве исполнителя по контракту в случае привлечения на основании договора других лиц.

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

    24 марта 2013 года министр образования Дмитрий Ливанов заявил о неэффективности РАН, предложив создать альтернативную организацию из «ученых дееспособного возраста». В ответ академики Жорес Алферов и Владимир Фортов вышли из общественного совета при Минобрнауки. 27 июня 2013 года правительство рассмотрело и одобрило законопроект о реорганизации РАН. Глава правительства Дмитрий Медведев поддержал законопроект, заявив, что «РАН давно нуждается в обновлении. Ученые должны прежде всего заниматься наукой и исследованиями». Президент России Владимир Путин подписал закон о реформировании Российской академии наук и указ о создании агентства научных организаций.

    В рамках реформы была осуществлена передача управления научно-исследовательскими институтами от президиума РАН к вновь созданному государственному ведомству — Федеральному агентству научных организаций (ФАНО) и объединение РАН с академиями медицинских и сельскохозяйственных наук. Значительная часть научных сотрудников, опасаясь за свое будущее, выражала недовольство, выходила на уличные протесты. Среди протестующих были и известные академики.

    История реформирования Российской академии наук

    Продолжение

    Создание и задачи ФАНО

    Федеральное агентство научных организаций было создано президентским указом, подписанным одновременно с законом о реформе РАН 27 сентября 2013 года. Михаил Котюков, до этого занимавший пост замминистра финансов РФ, был назначен главой ФАНО 24 октября.

    Правительственное агентство будет отвечать за все научные организации (НИИ, и другие), управление которыми в рамках реформы академической науки было решено вывести из подчинения РАН. В соответствии с новым законодательством, ФАНО является учредителем этих организаций, утверждает госзадания на проведение фундаментальных и научных исследований с учетом предложений Академии. Однако формирование научных заданий входит в функции РАН.

    После назначения Котюкова президент РАН заявил, что готов к сотрудничеству с ним. «У меня нет никаких предубеждений, и я очень надеюсь на такое сотрудничество», — сказал Фортов. В то же время Фортов отметил, что важный вопрос, как Котюков видит будущее взаимодействие между ФАНО и РАН. «Если бы я был назначен, у меня была бы своя логика, а какой логика будет здесь, я, естественно, еще не знаю», — пояснил он.

    Что такое ФАНО: досье

    tass.ru

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *