§24. Математические модели кодирования информации
ИнфоКонсалтинг
Образовательный сервис


Новости сайта

02.10.2017 С наступающим Днём Учителя, дорогие наши учителя!

24.08.2017 Успейте подобрать репетитора на новый учебный год! Это можно сделать на соответствующей странице нашего сайта, притом по любому предмету, в любом городе России и с учётом индивидуальных требований.

Сервис предоставлен Ассоциацией репетиторов.

Найти репетитора

Отправить заявку

24.08.2017 Страницы сайта переиндексированы для системы поиска ИнфоКонсалтинг.

Поиск по нашему сайту

04.10.2016 В разделе "К экзамену" появилось решение задачи 23 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 23 демо-версии 2017 г. по информатике

04.10.2016 В разделе "К экзамену" появилось решение задачи 26 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 26 демо-версии 2017 г. по информатике


§24. Математические модели кодирования информации


Найти репетитора

§24. Математические модели кодирования информации

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

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

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

Однако математический аспект действий с информацией связан не только с качественными преобразованиями информации, но и её количеством. Как живой объект, так и неживой может воспринять и сохранить лишь определённое количество информации. При этом становится актуальным вопрос об измерении этого количества, выраженного в единицах информации. Одной из задач информатики является уменьшение количества информации при сохранении её качества. Решение этой задачи связано с интерпретацией информации в виде знаний (см. §15 о том, что такое знания), ведь знания, будучи сами по себе информацией, способны породить новую информацию однозначно, следственно (хотя и в данное время и в данных условиях).

    • Для того, чтобы решить какую-либо задачу, не требуется вспоминать решение аналогичной, ранее рассматриваемой; достаточно знать, как это делается в принципе. Человек, умеющий решать задачи в определённой области только по шаблону, не обладает достаточным уровнем знаний для того, чтобы вообще заниматься проблемами в этой области. Напротив, понимание поставленной проблемы указывает на наличие знаний в области, в которой данная проблема имеет место.

Количество информации тесно связано с мощностью алфавита языка (числом составляемых символов) и количеством и сложностью правил его грамматики. Рассмотрим примеры, в которых показано, что чем больше знаков (символов) содержит алфавит, тем бо́льшим количеством бит будет кодироваться каждый из них (Примеры 1 и 2).

  • 1

    • Задача. Имеется алфавит некоторого языка, содержащий 4 символа: '', '', '', ''. Закодировать каждый символ этого алфавита, используя битовые последовательности.


      Решение. В данном случае каждый символ этого алфавита будет кодироваться двумя битами (ср. с Примером 2), ведь один бит уменьшает неопределённость знания в 2 раза.

      Пусть первый символ алфавита '' будет обозначен нулём (0), а второй ('') — единицей (1). Тогда на третий и четвёртый символы потребуется уже двухбитная кодировка, поскольку бит не может принять других значений, кроме упомянутых (см. §19). Третий символ ('') обозначим как 10, а четвёртый ('') — как 11. Поскольку максимальное количество бит, требуемое для кодирования символов данного алфавита, составляет два, то будем считать, что для кодирования каждого его символа потребуется 2 бита: '' — 00, '' — 01, '' — 10, '' — 11. Фактически мы составили таблицу транслитерации, в которой каждому символу алфавита соответствует уникальная битовая последовательность — идентификатор. Что и требовалось сделать по условию задания.

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

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

  • 2

    • Задача. Имеется алфавит некоторого языка, содержащий 6 символов: '←', '→', '↑', '↓', '↗', '↙'. Закодировать каждый символ этого алфавита, используя битовые последовательности.


      Решение. Закодируем каждый знак алфавита собственной последовательностью бит:

      Символ
      Идентификатор011011100101

      Мы видим, что последний знак кодируется максимальным количеством бит — тремя, — значит, нужно сделать так, чтобы каждый символ исходного алфавита кодировался тремя битами. Допишем к кодам необходимое количество лидирующих нулей:

      Символ
      Идентификатор000001010011100101

      Из полученной таблицы транслитерации видно, что имеются "неизрасходованные" трёхбитные комбинации (нет идентификаторов 110 и 111), так что показанный вариант не является единственно возможным в этой ситуации. Никто не запретит сделать, например, такие идентификаторы:

      Символ
      Идентификатор010011100101110111

Из рассмотренных примеров следует, что совокупность из десяти произвольных символов, взятых из алфавита Примера 1, несёт в себе меньше информации, чем совокупность из десяти произвольных символов, взятых из алфавита Примера 2 (20 и 30 бит соответственно).

Тогда понятно, что такое, напротив, неравномерное кодирование.

В Примерах 1 и 2 было применено как раз равномерное кодирование. А вот как можно выполнить неравномерное кодирование, видно из Примера 3.

Любой битовый код читается (декодируется) следующим образом. Рассматривается первый бит в битовой последовательности: в таблице транслитерации ищется идентификатор, представленный этим битом. Если такой идентификатор в таблице присутствует, что считается, что первый символ кода распознан, и первый бит из последовательности можно отбросить. После этих действий аналогичным образом поступаем со вторым и последующими битами. Если же в таблице транслитерации такого идентификатора нет, то к первому биту присоединяется второй, и в таблице транслитерации отыскивается уже двухбитный идентификатор. Опять же, если в таблице он находится, то отбрасываются уже два бита и всё начинается заново, а если нет — то присоединяется третий бит, чтобы далее искать уже трёхбитный идентификатор, и т. д. Действия повторяются до тех пор, пока вся битовая последовательность не будет прочитана (если это вообще возможно, см. Примеры 4 — 6).

  • 4

    • Задача. Имеется таблица транслитерации в битовый код:

      Символ
      Идентификатор00011011

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


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

      Третий бит равен нулю, такого идентификатора в таблице нет, поэтому присоединим к нему четвёртый. Искать теперь следует комбинацию битов 01, и такой идентификатор есть — он соответствует символу ''.

      Осталось прочитать символьную последовательность, представленную последними двумя битами исходной битовой последовательности. Пятый бит равен 1, и мы уже сталкивались при чтении первого символа с тем, что в таблице транслитерации отсутствует идентификатор 1. Поэтому присоединим к нему шестой бит и получим, что требуется искать идентификатор 10. Такой также обнаруживается, потому последний символ искомой строки — ''.

      Итак, искомая строка — '♦♣♥'.


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

      Первые два бита соответствуют идентификатору 11 из таблицы, что указывает на символ ''.

      Вторая "порция" из двух бит соответствует идентификатору 01, который кодирует символ ''.

      Третья двухбитная часть битовой последовательности (10) представляет символ ''.

      Искомая строка: '♦♣♥'.

Покажем, что бывает, если при создании битовой последовательности использована нераспознаваемая грамматика (Пример 5).

  • 5

    • Задача. Имеется таблица транслитерации в битовый код (символ 000 — это пробел):

      Символ айклопсты
      Идентификатор000000110001011011010001011100111

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


      Решение. Минимальная длина идентификатора в данной таблице — 2 бита, но среди идентификаторов, имеющих такую длину, нет идентификатора 01. Среди "трёхзначных" нет идентификатора 010, значит, первый идентификатор, который мы находим — это 0100, что соответствует символу 'п'. Первый символ распознан, осталось декодировать часть последовательности 01111011010100011100111100000010011110 (без первых четырёх битов).

      Поступая аналогично, далее последовательно распознаём символы 'о', 'л', 'о', 'с', ' ' (пробел), 'л', 'й'… Поскольку мы делаем это вручную, то можем почувствовать что-то не то: не похоже это на русское слово… Однако надо продолжать, потому что всякое можно закодировать! Так поступила бы и машина…

      На данный момент мы распознали символьную последовательность 'полос лй', а остаток битовой последовательности — 0111100000010011110.

      Осуществляя декодирование далее, получаем символы 'о', 'л', ' ' (пробел), 'о', ' ' (пробел), 'й', 'о' и остаток битовой последовательности 110. То есть, нам, вроде бы, осталось распознать последний символ в заданной битовой последовательности! Тем более, что мы видим символ с идентификатором 110, — это 'т'!

      Не тут-то было! Дело в том, что её фрагменту 11 соответствует символ 'л', а символов, для которых длина идентификатора равнялась бы единице, просто не существует. Таким образом, остающемуся "в одиночестве" биту 0 не соответствует ни один символ алфавита.

      Итак, данный код по установленному стандартному алгоритму распознать нельзя, ему не может быть поставлена в соответствие ни одна строка символов исходного алфавита. Это — ответ на вопрос задания.

  • 6

    • Задача. Имеется таблица транслитерации в битовый код:

      Символ
      Идентификатор011011

      Показать возможные символьные последовательности (строки), соответствующие битовому коду 0010.


      Решение. Если первые два символа последовательности очевидны — это '♠♠', то с другими возникает проблема. Оставшуюся часть последовательности можно прочитать как '', поскольку биты 1 и 0 вместе кодируют именно этот символ. Однако эти два бита могут представлять и два символа: '' и '' соответственно. Поэтому вариантами битовой последовательности в виде символов алфавита являются '♠♠♥' и '♠♠♣♠'.

Однако не надо думать, что неравномерное кодирование является основой только лишь для нераспознаваемой грамматики. Подробнее оно описано в §26 и §27. Пока же поясним, как вообще грамматики можно классифицировать по признаку распознаваемости.

    • Обратите внимание: неполное, или недостаточное знание образует нераспознаваемую грамматику! То же можно сказать о любой неполной информации.



Поддержите нас!


Обращаем Ваше внимание:

Ваш браузер недостаточно эффективен. Установите достойный браузер здесь.

Все анонсы? / ?



Индекс цитирования
CY, Page Rank
Яндекс.Метрика