Представление информации. Урок № 3

Задача.
Из каждого из пунктов A, B, C и D имеется путь в остальные пункты, расстояния между которыми известны: AB=7, AC=5, AD=4, BC=6, BD=1, CD=8. Необходимо, начиная от одного из этих пунктов и побывав в каждом из пунктов только один раз, вернуться в исходный пункт. Какой маршрут надо выбрать, чтобы путь оказался кратчайшим?

Урок № 3
Представление
информации

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

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

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

Представьте информацию

Способы кодирования информации
Для кодирования одной и той же информации могут быть использованы разные способы; их выбор зависит от ряда обстоятельств: цели кодирования, условий, имеющихся средств.
Если надо записать текст в темпе речи — используем стенографию; если надо передать текст за границу — используем английский алфавит; если надо представить текст в виде, понятном для грамотного русского человека, — записываем его по правилам грамматики русского языка.
«Здравствуй, Саша!»
«Zdravstvuy, Sasha!»

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

Технические способы
кодирования информации

Оптический телеграф Шаппа
В 1792 году во Франции Клод Шапп создал систему передачи визуальной информации, которая получила название «Оптический телеграф».
В простейшем виде это была цепь типовых строений, с расположенными на кровле шестами с подвижными поперечинами, которая создавалась в пределах видимости одно от другого. Шесты с подвижными поперечинами — семафоры — управлялись при помощи тросов специальными операторами изнутри строений.
Шапп создал специальную таблицу кодов, где каждой букве алфавита соответствовала определенная фигура, образуемая Семафором, в зависимости от положений поперечных брусьев относительно опорного шеста.
Система Шаппа позволяла передавать сообщения на скорости два слова в минуту и быстро распространилась в Европе. В Швеции цепь станций оптического телеграфа действовала до 1880 года.

СЭМЮЭЛЬ МОРЗЕ
Телеграф - средство передачи информаии на расстояние, изобретенный в 1837 году американцем Сэмюэлем Морзе.
Телеграфное сообщение — это последовательность электрических сигналов, передаваемая от одного телеграфного аппарата по проводам к другому телеграфному аппарату.
Эти технические обстоятельства привели Морзе к
идее использования всего двух видов сигналов — короткого и длинного — для кодирования сообщения, передаваемого по линиям телеграфной связи.
Телеграф

Самым знаменитым телеграфным сообщением является сигнал бедствия «SOS»
(Save Our Souls - спасите наши души).
Вот как он выглядит в коде азбуки Морзе:
Три точки обозначают букву S, три тире — букву О
Азбука Морзе

Азбука Морзе

Неравномерность кода
− • − − • • • − − • • −
Характерной особенностью азбуки Морзе является переменная длина кода разных букв, поэтому код Морзе называют неравномерным кодом.
Буквы, которые встречаются в тексте чаще, имеют более короткий код, чем редкие буквы. Это сделано для того, чтобы сократить длину всего сообщения. Но из-за переменной длины кода букв возникает проблема отделения букв друг от друга в тексте. Поэтому для разделения приходится использовать паузу (пропуск). Следовательно, телеграфный алфавит Морзе является троичным, т.к. в нем используются три знака: точка, тире, пропуск.

Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно декодировалось, достаточно, чтобы никакой код не был началом другого (более длинного) кода.
Пример неравномерного кода, выполняющего условие Фано:
Условие Фано
Тогда слово «ОЛОВО» кодируется как «1100110» и имеет только один вариант дешифровки.

Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно декодировалось, достаточно, чтобы никакой код не был началом другого (более длинного) кода.
Пример неравномерного кода, выполняющего условие Фано:
Условие Фано
Тогда слово «ОЛОВО» кодируется как «1100110» и имеет только один вариант дешифровки.

Пример №1 (прямое условие Фано выполняется корректно). Известны коды следующих символов: A, B, C, D.
Проверим код буквы A=00. Как видно, ни один другой символ не начинается на связку битов 00. Аналогичные умозаключения можно сделать, если провести анализ остальных букв алфавита, т е букв B, C и D. В данном примере условие Фано выполняется.

Пример №2 (прямое условие Фано нарушено). Даны неравномерные коды символов A, B, C, D.
Очевидно, что в данном случае имеется нарушение прямого условия Фано! Давайте рассмотрим пару элементов множества: B, D. Начало кода буквы D на 100% совпадает с полным кодом буквы B.
Такие кодовые слова практически невозможно однозначно декодировать.

Обратное условие Фано также является достаточным условием однозначного декодирования неравномерного кода. В нём требуется, чтобы никакой код не был окончанием другого (более длинного) кода.
Для возможности однозначного декодирования достаточно выполнения одного из условий — или прямого, или обратного.
Заметим, что существуют варианты неравномерного кодирования, для которых оба условия нарушены, и тем не менее они однозначно декодируются.
Обратное условие Фано

Телеграф Бодо
Равномерный телеграфный код был изобретен французом Жаном Морисом Бодо в 1872 г. В нем использовалось всего два разных вида сигналов. Не важно, как их назвать: точка и тире, плюс и минус, ноль и единица. Это два отличающихся друг от друга электрических сигнала. Длина кода всех символов одинаковая и равна пяти. В таком случае не возникает проблемы отделения букв друг от друга: каждая пятерка сигналов — это знак текста. Поэтому пропуск не нужен.
Код называется равномерным, если длина кода всех символов равна.
Код Бодо — это первый в истории техники способ двоичного кодирования, информации. Благодаря этой идее удалось создать буквопечатающий телеграфный аппарат, имеющий вид пишущей машинки. Нажатие на клавишу с определенной буквой вырабатывает соответствующий пятиимпульсный сигнал, который передается по линии связи.
В честь Бодо была названа единица скорости передачи информации — бод.
В современных компьютерах для кодирования текста также применяется равномерный двоичный код.
ЖАН БОДО

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

Почему двоичное кодирование
С точки зрения технической реализации использование двоичной системы счисления для кодирования информации оказалось намного более простым, чем применение других способов. Действительно, удобно кодировать информацию в виде последовательности нулей и единиц, если представить эти значения как два возможных устойчивых состояния электронного элемента:
0 – отсутствие электрического сигнала;
1 – наличие электрического сигнала.
Эти состояния легко различать. Недостаток двоичного кодирования – длинные коды. Но в технике легче иметь дело с большим количеством простых элементов, чем с небольшим числом сложных.

Домашнее задание
1. Выучить конспект
2. п. 2 читать, отвечать на вопросы

Для кодирования одного символа требуется один байт информации.
Учитывая, что каждый бит принимает значение 1 или 0, получаем, что с помощью 1 байта можно закодировать 256 различных символов.
N=2i N – мощность алфавита
28=256 I – информационный вес
1 символ – 1 байт (8 бит)

Таблица, в которой всем символам компьютерного алфавита поставлены в соответствие порядковые номера (коды)
Таблица кодировки

Таблица кодировки ASCII
является стандартной, и ее понимают абсолютно все программы, работающие с текстами.

Кодовая таблица ASCII
American Standard Code for Information Interchange
коды от 0 до 31
функциональные
клавиши
коды от 128 до 255
национальный алфавит
коды от 32 до 127
буквы английского алфавита,
знаки математических операций и т.д

Таблица кодировки Unicode
Стандарт кодирования Unicode отводит на каждый символ 2 байта, что позволяет закодировать многие алфавиты в одной таблице.
N=2I=216=65 536

В настоящее время существует 5 кодовых таблиц для русских букв (Windows, MS-DOS, КОИ-8, Mac, ISO), поэтому тексты, созданные в одной кодировке, не будут правильно отображаться в другой.

Таблицы кодировки русскоязычных символов-
код обмена информации 8-битный
КОИ8-Р
CP1251
CP866
Mac
ISO

Декодировать текст с помощью кодовой таблицы ASCII:
99 111 109 112 117 116 101 114
Пример
computer

Цель: научиться определять числовые коды символов и вводить символы с помощью числовых кодов.
ПРАКТИЧЕСКАЯ РАБОТА

Работа в текстовом редакторе
MS Word
Запустите текстовый редактор MS Word. Удерживая клавишу «ALT», наберите коды на дополнительной цифровой клавиатуре:
152 170 174 171 160
Какое слово получили?
Ответ: Школа