К.Ю. Поляков, Е.А. Ерёмин, 2013 1 Кодирование информации § 5. Язык и алфавитЯзык и алфавит § 6. КодированиеКодирование. - презентация

1 К.Ю. Поляков, Е.А. Ерёмин, Кодирование информации § 5. Язык и алфавит Язык и алфавит § 6. Кодирование Кодирование

2 К.Ю. Поляков, Е.А. Ерёмин, Кодирование информации § 5. Язык и алфавит 2

3 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Язык 3 Язык это система знаков, используемая для хранения, передачи и обработки информации. Египетское письмо Иероглифы (Китай) рука солнце дом луна кобра дождь лев гора вода лошадь Иероглифы:

4 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Алфавитное письмо 4 Алфавит это набор знаков, который используется в языке. Мощность алфавита это количество знаков в алфавите. АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ ,;?!-:…«»() мощность 56 Слово это последовательность символов алфавита, которая используется как самостоятельная единица и имеет определённое значение.

5 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Сообщения 5 Сообщение это любая последовательность символов некоторого алфавита. Пример: # $ %. Сообщения длины # $ %. Сколько сообщений длины L ? ? Сообщения @% ## #$ #% $# $$ $% %# %$ % всего 16 всего 4

6 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Количество возможных сообщений 6 Если алфавит языка состоит из N символов (имеет мощность N), количество различных сообщений длиной L знаков равно Q = N L Сколько возможных 5-буквеных слов в русском языке? возможных 3-буквеных слов в английском языке?

7 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Какие бывают языки? 7 Естественные Формальные русский английский китайский шведский суахили … 1. e2-e4 e7-e5… Формальный язык – это язык, в котором однозначно определяется значение каждого слова, а также правила построения предложений и придания им смысла.

8 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Естественные и формальные языки 8 результат развития общества для общения в быту значения слов зависят от контекста есть синонимы есть омонимы нет строгих правил образования предложений есть исключения созданы людьми в специальных областях знаний значения слов не зависит от контекста синонимов нет омонимов нет правила образования предложений строго определены нет исключений Естественные Формальные

9 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 9 1. Сколько различных пятизначных чисел можно записать с помощью цифр 4 и 2? 2. В языке разрешены только четырёхбуквенные слова, которые можно образовывать из букв алфавита в любых комбинациях. Словарный запас языка составляет 81 слово. Какова мощность алфавита? 3. Какое наименьшее число символов должно быть в алфавите, чтобы с помощью всевозможных трёхбуквенных слов можно было передать не менее 9 различных сообщений?

10 К.Ю. Поляков, Е.А. Ерёмин, Кодирование информации § 6. Кодирование 10

11 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Что такое кодирование? 11 Кодирование это представление информации в форме, удобной для её хранения, передачи и обработки. Правило такого преобразования называется кодом. Текст: в России: Привет, Вася! передача за рубеж (транслит): Privet, Vasya! Windows-1251: CFF0E8E2E52C20C2E0F1FF21 стенография: шифрование: Рсйгжу-!Гбта Числа: для вычислений: 25 прописью: двадцать пять римская система: XXV Как зашифровано? ? Зачем? ?

12 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Код Морзе 12 А О Э Б П Ю В Р Я Г С Д Т 1 Е У 2 Ж Ф 3 З Х 4 И Ц 5 Й Ч 6 К Ш 7 Л Щ 8 М Ь 9 Н Ы 0 Код неравномерный, нужен разделитель! ! ВАСЯ ВА, АК, ПТ, ЕМЕТ?

13 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Двоичное кодирование 13 Двоичное кодирование это кодирование с помощью двух знаков. АБВГ АБАВГБ Количество сообщений длиной I битов: N = 2 I Пример. Нужно закодировать номер спортсмена от 1 до 200. Сколько битов потребуется? 8 битов 2 7 < = 256 Равномерный код:

14 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи Сколько существует в коде Морзе различных последовательностей из точек и тире, длина которых от 4 до 6 символов? 2. Вася и Петя передают друг другу сообщения, используя синий, красный и зелёный фонарики. Это они делают, включая по одному фонарику на одинаковое короткое время в некоторой последовательности. Количество вспышек в одном сообщении 3 или 4, между сообщениями паузы. Сколько различных сообщений могут передавать мальчики?

15 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи Шахматная доска состоит из 8 столбцов и 8 строк. Какое минимальное количество битов потребуется для кодирования координат одной шахматной фигуры? 4. Для кодирования значений температуры воздуха (целое число в интервале от –50 до 40) используется двоичный код. Какова минимальная длина двоичного кода? 5. Дорожный светофор подаёт шесть видов сигналов (непрерывные красный, жёлтый и зелёный, мигающие жёлтый и зелёный, мигающие красный и жёлтый одновременно). Подряд записано 100 сигналов светофора. Определите информационный объём этого сообщения в битах.

16 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи Автомобильный номер длиной 6 символов составляется из заглавных букв (всего используется 12 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством битов, а каждый номер одинаковым и минимально возможным количеством байтов. Определите объём памяти, необходимый для хранения 32 автомобильных номеров.

17 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Декодирование 17 Декодирование это восстановление сообщения из последовательности кодов. ВАСЯ Когда разделитель не нужен? ? АБВГД A A 0 корень В В Б Б 0 1 Д Д 0 1 Г Г Все кодовые слова заканчиваются на листьях дерева!

18 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Декодирование 18 A A 0 корень В В Б Б 0 1 Д Д 0 1 Г Г Г АВДБ Префиксный код это код, в котором ни одно кодовое слово не совпадает с началом другого кодового слова (условие Фано). Сообщения декодируются однозначно.

19 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи Для передачи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: A = 0, Б = 10, В = 110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное декодирование? 2. Для передачи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный код: A = 0, Б = 100, В = 101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное декодирование?

20 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Постфиксные коды 20 Постфиксный код это код, в котором ни одно кодовое слово не совпадает с окончанием другого кодового слова. Сообщения декодируются однозначно (с конца!). АБВГД БДГБВ

21 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Неоднозначное декодирование 21 АБВГД АБАГД АБВГА Выполняются ли условия Фано? ? Декодирование может быть неоднозначным… Может быть, что условия Фано не выполнены, а декодирование однозначно (см. учебник)! !

22 Кодирование информации, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задача 22 АБВ *Докажите, что все сообщения, закодированные этим кодом, декодируются однозначно