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

1. Проверим домашнее задание:

1.
Значение арифметического выражения
77⋅812031 + 23⋅7291037 − 7⋅93023
записали в системе счисления с основанием 81. Определите количество цифр в
этой записи, числовое значение которых кратно 4.
Ответ:
2029
2
Операнды арифметического выражения записаны в системе счисления с
основанием 25.
2xx2612925 + 54xxx71125
В записи чисел переменной x обозначена неизвестная цифра из алфавита 25ричной системы счисления. Определите наименьшее значение x, при котором
значение данного арифметического выражения кратно 24. Для найденного x
вычислите частное от деления значения арифметического выражения на 24 и
укажите его в ответе в десятичной системе счисления.
1996970915
Ответ:

2. Проверим домашнее задание:

1.
Ответ: 466456
2
Ответ: 2527

3. Комбинаторика

Кодирование информации
3
Комбинаторика
Задача 1. Сколько существует четырёхзначных
чисел, составленных из чётных цифр?
4 5 5 5 = 500
4
5
2, 4, 6, 8 0, 2, 4, 6, 8
N m1 m2 m3 m4
К. Поляков, 2006-2016
! Правило умножения!
http://kpolyakov.spb.ru

4. Комбинаторика

Кодирование информации
4
Комбинаторика
Задача 2. Сколько существует четырёхзначных
чисел, составленных из чётных цифр, в которых
цифры не повторяются?
4 4 3 2 = 96
4
5
2, 4, 6, 8
0, 2, 4, 6, 8
одна цифра уже
использована!
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

5. Комбинаторика

Кодирование информации
5
Комбинаторика
Задача 3. Сколько существует двоичных кодов
длиной 4 бита?
2 2 2 2 =24=16
N M
2
! Правило умножения!
0, 1
N M M M M
L
длина
сообщения
мощность
алфавита
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

6. Комбинаторика

Кодирование информации
6
Комбинаторика
Задача 4. Сколько существует двоичных кодов
длиной от 2 до 5 битов?
L = 2:
L = 4:
N2 = 22 = 4
N4 = 24 = 16
L = 3:
L = 5:
N2 = 23 = 8
N5 = 25 = 32
N = 4 + 8 + 16 + 32 = 60
N = N2 + N3 + N4 + N5
К. Поляков, 2006-2016
! Правило сложения!
http://kpolyakov.spb.ru

7. Комбинаторика

Кодирование информации
7
Комбинаторика
Задача 5. В некоторой стране живут 1000
человек. Правительство решило присвоить
каждому собственный код, причем все коды
должны быть одинаковой длины и состоять
только из цифр 1, 2, 3 и 4. Определите
наименьшую длину таких кодов.
N = 4L ≥ 1000
L = 1:
L = 2:
L = 3:
41 = 4 < 1000
42 = 16 < 1000
43 = 64 < 1000
К. Поляков, 2006-2016
L = 4:
L = 5:
44 = 256 < 1000
45 = 1024 > 1000
http://kpolyakov.spb.ru

8.

from itertools import product
k=0
for i in product("0123456", repeat=7):
p=",".join(i)
if p[0]!="3" and p[0]!="5"and p[0]!="0" and (p.count("22")==0 ) and (p.count("44")== 0) :
k=k+1
print(k)

9.

from itertools import product
k=0
for i in product("0123456", repeat=7):
p=",".join(i)
if p[0]!="3" and p[0]!="5"and p[0]!="0" and (p.count("22")==0 ) and (p.count("44")== 0) :
k=k+1
print(k)

10.

В семеричной системе счисления числа состоят из 7 различных цифр (0, 1, 2,
3, 4, 5, 6).
Семизначное число не может начинаться с цифр 3 и 5. Это значит, что первые
две цифры числа могут быть любыми из 5 доступных: 1, 2, 4, 6.
10

11.

from itertools import product
count = 0
number = 0
for p in product(sorted(“ПАРУС"), repeat=5):
number += 1
if p[0]!=“У“:
flag=0
for i in range(0,len(p)-1):
if p[i]!=p[i+1] and p[i]=“А”:
flag=1
if flag==0:
count+=1
print(count)

12.

12

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

Кодирование
информации
Тема 1. Язык и кодирование
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

14. Что такое кодирование?

Кодирование информации
14
Что такое кодирование?
Кодирование – это запись информации с помощью
некоторой знаковой системы (языка).
? Зачем кодируют информацию?
кодирование
данные (код)
Информация передается,
обрабатывается и хранится
в виде кодов.
10101001010
передача
данные (код)
11111100010
борьба с помехами
(специальные способы
кодирования)
К. Поляков, 2006-2016
передача
обработка
хранение
http://kpolyakov.spb.ru

15. Языки

Кодирование информации
15
Языки
Язык – знаковая система, используемая для хранения и
передачи информации.
– естественные (русский, английский, …)
есть правила и исключения
– формальные (строгие правила)
E mc
2
program qq;
begin
writeln("Привет!");
end.
16 1016 208 10000 2
Грамматика – правила по которым из символов алфавита строятся
слова.
Синтаксис – правила, по которым из слов строятся предложения.
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

16. Код Морзе

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

17. Азбука Морзе

Кодирование информации
17
Азбука Морзе
Задача 1. Закодируйте свое имя с помощью азбуки Морзе.
ВАСЯ
! Код неравномерный, нужен разделитель!
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

18. Кодовые таблицы

Кодирование информации
18
Кодовые таблицы
Задача 2. Закодируйте свое имя с помощью кодовой
таблицы (Windows-1251):
0 1 2 3 4 5 6 7 8 9 A B C D E F
C А Б В Г Д Е Ж З И Й К Л М Н О П
D Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
ВАСЯ
В А С Я
С2 С0 D1 DF
! Код равномерный, разделитель НЕ нужен!
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

19. Цели и способы кодирования

Кодирование информации
19
Цели и способы кодирования
Текст:
в России: Привет, Вася!
Windows-1251: CFF0E8E2E52C20C2E0F1FF21
передача за рубеж (транслит): Privet, Vasya!
стенография:
шифрование: Рсйгжу-!Гбта”
?
Числа:
Как зашифровано?
для вычислений: 25
прописью: двадцать пять
римская система: XXV
! Информация (смысл сообщения) может
быть закодирована разными способами!
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

20. Задача 3

Кодирование информации
Кодирование
информации
Тема 2. Двоичное кодирование
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

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

22
Двоичное кодирование
Двоичное кодирование – это кодирование всех видов
информации с помощью двух знаков (обычно 0 и 1).
Передача электрических сигналов:
сигнал с помехами
U
U
сигнал с помехами
5В
«1»
1
полезный
сигнал
К. Поляков, 2006-2016
время
полезный
сигнал
0
1
«0»
время
http://kpolyakov.spb.ru

22. Двоичное кодирование

Кодирование информации
23
Двоичное кодирование
символы
рисунки
кодировщик
101011011101110110101
• в такой форме можно закодировать (почти) все
виды информации
• нужны только устройства с двумя состояниями
• почти нет ошибок при передаче данных
• компьютеру легче обрабатывать данные
человеку сложно воспринимать двоичные коды
? Можно ли использовать не «0» и «1», а другие
символы, например, «А» и «Б»?
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

23. Двоичное кодирование

Кодирование информации
24
Декодирование
Декодирование – это восстановление сообщения из
последовательности кодов.
М
А
Ы
Л
У
пробел
00
1
01
0
10
11
МАМА МЫЛА ЛАМУ → 00 1 00 1 11 00 01 0 1 11 0 1
00 10
Приняли сообщение:
0010011100010111010010 ???
ЛЛАЛЛАААЛЛЛАЛАА
АЛАЛЛАЛ
Не все коды допускают однозначное
декодирование!
!
? Почему?
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

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

Кодирование информации
25
Равномерные коды
Равномерные коды – все кодовые слова (коды
отдельных букв) имеют одинаковую длину.
М
А
Ы
Л
У
пробел
000
001
010
011
100
101
МАМА МЫЛА ЛАМУ:
000 001 000 001 101 000 010 011 001 101 011 001 000 100
! Равномерные коды позволяют однозначно
декодировать сообщения!
сообщения получаются длинными
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

25. Равномерные коды

Кодирование информации
26
Неравномерные коды
кодовые слова имеют разную длину
М
А
Ы
Л
У
пробел
01
00
1011
100
1010
11
0
1
0
1
А
М
0100010011011011100001110000011010
0
1
0
Л
1
0
У
1
Ы
М А М А
М
Ы
Л
А
Л
А М
У
Префиксный код – ни одно кодовое
слово не совпадает с началом
другого кодового слова
(условие Фано).
! Любой префиксный код позволяет
однозначно декодировать сообщения!
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

26. Неравномерные коды

Кодирование информации
27
Задачи на построение кода
1
Для передачи по каналу связи сообщения, состоящего только
из букв А, Б, В, Г, решили использовать неравномерный по
длине код:
А
Б
В
Г
1
000
001
?
Как нужно закодировать букву Г, чтобы длина кода была
минимальной и допускалось однозначное разбиение
кодированного сообщения на буквы?
1) 00
2) 01
3) 11
4) 010
Решение:
1) для букв А-Б-В выполнятся условие Фано
2) при Г=00 условие Фано нарушится (пары Г-Б, Г-В)
3) при Г=01 условие Фано выполняется
4) при Г=11 условие Фано нарушится (пара А-Г)
5) при Г=010 условие Фано выполняется (но длиннее 01)
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

27. Задачи на построение кода

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

28. Задачи

Кодирование информации
29
Постфиксные коды
Постфикс = окончание слова.
Постфиксный код – ни одно кодовое слово не
совпадает с концом другого кодового слова
(«обратное» условие Фано).
М
А
Ы
Л
У
пробел
10
00
1101
001
0101
11
! Любой постфиксный код позволяет
однозначно декодировать сообщения
(с конца)!
для декодирования нужно получить всё
сообщение целиком
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

29. Постфиксные коды

Кодирование информации, 10 класс
30
Задача 64
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д,
используется неравномерный двоичный код, позволяющий однозначно
декодировать полученную двоичную последовательность. Вот этот код: А–00, Б–
010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового
слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды
остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Б – 01
2) это невозможно
3) для буквы В – 01
4) для буквы Г – 01
здесь
однозначность
декодирования
получается за
счёт того, что
при движении
построим двоичное дерево, в котором от каждого узла отходит две
ветки, от
корня к любой
соответствующие выбору следующей цифры кода – 0 или 1; разместим
букве в
на этом дереве буквы А, Б, В, Г и Д так, чтобы их код получалсясередине
как
пути
не встречается
последовательность чисел на рёбрах, составляющих путь от корня
до
других букв
данной буквы
(выполняется
условие Фано);
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

30. Задача 6

Кодирование информации, 10 класс
Задача
31
5
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д,
используется неравномерный двоичный код, позволяющий однозначно
декодировать полученную двоичную последовательность. Вот этот код: А–00, Б–
010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового
слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды
остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Б – 01
2) это невозможно
3) для буквы В – 01
4) для буквы Г – 01
теперь проверим
варианты ответа:
предлагается
перенести одну
из букв, Б, В или
Г, в узел с кодом
01, выделенный
синим цветом
видим, что при переносе любой из этих букв нарушится условие Фано; например, при переносе буквы Б
в синий узел она оказывается на пути от корня до В, и т.д.; это значит, что предлагаемые варианты не
позволяют выполнить прямое условие Фано
хочется уже выбрать вариант 2 («это невозможно»), но у нас есть еще обратное условие Фано,
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

31. Задача

Кодирование информации, 10 класс
34
Задача 76
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г,
решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно
закодировать букву Г, чтобы длина кода была минимальной и допускалось
однозначное разбиение кодированного сообщения на буквы?
1) 1
2) 1110 3) 111
4) 11
Строим дерево,
расставляем буквы
правильный ответ – 3.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

32. Задача

Кодирование информации, 10 класс
35
Задача 87
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д,
используется неравномерный двоичный код, позволяющий однозначно
декодировать полученную двоичную последовательность. Вот этот код: А – 0; Б –
100; В – 1010; Г – 111; Д – 110. Требуется сократить для одной из букв длину
кодового слова так, чтобы код по-прежнему можно было декодировать однозначно.
Коды остальных букв меняться не должны.
Каким из указанных способов это можно сделать?
1) для буквы В – 101
2) это невозможно
3) для буквы В – 010
4) для буквы Б – 10
Строим дерево,
расставляем буквы
правильный ответ – 1.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

33. Задача

Кодирование информации, 10 класс
36
Задача 98
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г,
решили использовать неравномерный двоичный код, удовлетворяющий условию
Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110.
Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
1) 7
2) 8
3) 9
4) 10
условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового
слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева,
то есть в узлах, которые не имеют потомков;
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

34. Задача 7

Кодирование информации, 10 класс
37
Задача
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г,
решили использовать неравномерный двоичный код, удовлетворяющий условию
Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110.
Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
1) 7
2) 8
3) 9
4) 10
правильный ответ – 3.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

35. Задача 8

Кодирование информации, 10 класс
38
9
Задача 10
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д,
Е, решили использовать неравномерный двоичный код, удовлетворяющий условию
Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10.
Какова наименьшая возможная сумма длин всех шести кодовых слов? Примечание.
Условие Фано означает, что никакое кодовое слово не является началом другого
кодового слова. Это обеспечивает возможность однозначной расшифровки
закодированных сообщений.
Неверный
вариант
правильный ответ – 19.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

36. Задача 9

Кодирование информации, 10 класс
39
10
Задача 11
правильный ответ – 2.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

37. Задача

Кодирование информации, 10 класс
40
Реши самостоятельно:
1
2
3
4
5
6
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

38. Задача 10

Кодирование информации, 10 класс
42
Реши самостоятельно:
7
8
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

39. Задача 11

Кодирование информации, 10 класс
44
Реши самостоятельно:
9
10
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

40. Реши самостоятельно:

Кодирование информации, 10 класс
50
Реши самостоятельно:
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

41.

Кодирование информации, 10 класс
52
Домашнее задание
*Докажите, что все сообщения, закодированные
этим кодом, декодируются однозначно.
А
0
Б
11
В
010
01000011001011110000100
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

42. Реши самостоятельно:

53

43. Реши самостоятельно:

Кодирование информации
К. Поляков, 2006-2016
54
http://kpolyakov.spb.ru

44. Реши самостоятельно:

Кодирование информации
Кодирование
информации
Тема 2. Кодирование чисел и
символов
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

45.

Кодирование информации
56
Кодирование чисел (двоичная система)
Алфавит: 0, 1
Основание (количество цифр): 2
10 2
19
18
1
2
9
8
1
2
4
4
0
2
2
2
0
2 10
43210
19 = 100112
2
1
0
система
счисления
2
0
1
разряды
100112 = 1·24 + 0·23 + 0·22 + 1·21 + 1·20
= 16 + 2 + 1 = 19
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

46. Реши самостоятельно:

Кодирование информации
57
Кодирование символов
Текстовый файл
• на экране (символы)
• в памяти – двоичные
коды
10000012 10000102 10000112 10001002
65
66
67
68
! В файле хранятся не изображения символов, а
их числовые коды в двоичной системе!
А где же хранятся изображения?
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

47.

Кодирование информации
58
Кодирование символов
1. Сколько символов надо использовать
одновременно? 256 или 65536 (UNICODE)
2. Сколько места надо выделить на символ:
8 бит на символ
256 = 28
3. Выбрать 256 любых символов (или 65536) алфавит.
4. Каждому символу – уникальный код 0..255
(или 0..65535). Таблица символов:
коды
…
65
66
67
68
A
B
C
D
…
5. Коды – в двоичную систему.
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

48. Реши самостоятельно:

Кодирование информации
8-битные кодировки (1 байт на символ)
0
127
1
таблица ASCII
(международная)
128
254
59
255
расширение
(национальный алфавит)
ASCII = American Standard Code for Information Interchange
управляющие символы:
7 – звонок, 10 – новая строка, 13 – возврат каретки, 27 – Esc.
32 пробел
знаки препинания: . , : ; ! ?
специальные знаки:
+ - * / () {} []
48-57 цифры 0..9
65-90 заглавные латинские буквы A-Z
97-122 строчные латинские буквы a-z
0-31
Кодовая страница (расширенная таблица ASCII)
для русского языка:
CP-866
для системы MS DOS
CP-1251 для системы Windows (Интернет)
КОИ8-Р
для системы UNIX (Интернет)
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

49.

Кодирование информации
8-битные кодировки (1 байт на символ)
60
• 1 байт на символ – файлы небольшого
размера!
• просто обрабатывать в программах
• нельзя использовать символы разных
кодовых страниц одновременно (русские
и французские буквы, и т.п.)
• неясно, в какой кодировке текст
(перебор вариантов!)
• для каждой кодировки нужен свой
шрифт (изображения символов)
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

50. Реши самостоятельно:

Кодирование информации
61
Стандарт UNICODE
! Идея: объединить все символы в
одну таблицу!
• 110 182 символа (2012)
• каждому символу присвоен код
кириллица:
А – 041016,
Б – 041116, …
а – 043016,
б – 043116, …
• коды 0..10FFFF16, всего 1 114 112
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

51. Реши самостоятельно:

Кодирование информации
UNICODE в Windows (UTF-16)
• общеупотребительные символы
0..65535 = 216-1 (0..FFFF16)
• эти символы можно закодировать с
помощью 16 бит
• кодировка UTF-16 (почти все символы по 16 бит)
62
можно одновременно использовать
символы разных языков (Интернет)
размер файла увеличивается
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

52. Домашнее задание

Кодирование информации
UNICODE в Linux (кодировка UТF-8)
63
• символы ASCII – 1 байт на символ
• остальные символы от 2 до 4 байт
• более 50% сайтов используют UTF-8
• тексты, состоящие только из кодов ASCII
(коды 0 – 127) не увеличиваются в размере
• переменное число байтов на символ
• замедление работы программ
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

53.

Практическая работа
64