Кодирование в ЕГЭ 8-2

1.

КЕГЭ-8

2.

0–А
1–К
2–Р
3–У
450.
449
10
Ответ. КУААК
= 130014
1.
2.
3.
4.
5.
00000
00001
00002
00003
00010
= КУААК

3.

4.

0–А
1–О
2–У
163. 16210
УАААА = 200003
= 16210
Ответ. 163
0–А
1–О
2–У
92. 9110
Ответ. 92
ОАОАО = 101013
= 9110

5.

6.

0–О
1–П
2–Р
3–Т
[20103 .. 30102]
ТОПОР
РОПОТ
30102
20103
30102 – 20103 + 1 =
30103
– 201034
100004 = 25610
Ответ. 256

7.

8.

9.

10.

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

11.

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

12.

Кодирование информации
13
Комбинаторика
Задача 0. Сколько существует слов длиной в 3
символа, составленных из трех букв А, В, С?
ААА
ААВ
ААС
АВА
АВВ
АВС
АСА
АСВ
АСС
ВАА
ВАВ
ВАС
ВВА
ВВВ
ВВС
ВСА
ВСВ
ВСС
САА
САВ
САС
СВА
СВВ
СВС
ССА
ССВ
ССС
3
3
3
= 27
3
3
А, В,С А, В, С А, В, С
N m1 m2 m3
К. Поляков, 2006-2016
3
! Правило умножения!
http://kpolyakov.spb.ru

13.

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

14.

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

15.

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

16.

Кодирование информации
17
Комбинаторика
Задача 4. Сколько существует двоичных кодов
длиной 4 бита?
0000
0001
0010
0011
2 2 2 2 =24=16
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
N M
К. Поляков, 2006-2016
2
! Правило умножения!
0, 1
N M M M M
L
длина
сообщения
мощность
алфавита
http://kpolyakov.spb.ru

17.

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

18.

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

19.

Кодирование информации
20
Задачи
1. Сколько существует слов длиной в 3 символа, составленных из
трех букв А, В, С, и буквы могут повторяться?
3 * 3 * 3 = 27
2. Сколько существует слов длиной в 3 символа, составленных из
четырех букв А, В, С, D и буквы могут повторяться?
4 * 4 * 4 = 64
3. Сколько существует слов длиной в 4 символа, составленных из
четырех букв А, Б, В, Г и буквы могут повторяться?
4 * 4 * 4 * 4 = 256
4. Сколько существует слов длиной в 5 символов, составленных
из трех букв X, Y ,Z, и буквы могут повторяться?
3 * 3 * 3 * 3 * 3 = 243
5. Сколько существует слов длиной в 3 символа, составленных из
трех букв А, В, С, и буквы не повторяются?
3*2*1=6
6. Сколько существует слов длиной в 4 символа, составленных из
четырех букв А, В, С, D и буквы не повторяются?
4 * 3 * 2 * 1 = 24
7. Сколько существует слов длиной в 5 символов, составленных
из пяти букв А, В, С, D, E и буквы не повторяются?
5 * 4 * 3 * 2 * 1 = 120
8. Сколько существует слов длиной в 6 символа, составленных из
7 букв А, В, С, D, E, F, G и буквы не повторяются?
7 * 6 * 5 * 4 * 3 * 2 = 5040
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

20.

Кодирование информации
21
9. Сколько слов длины 4, начинающихся с согласной буквы,
можно составить из букв К, О, Д? Каждая буква может
входить в слово несколько раз. Слова не обязательно
должны быть осмысленными словами русского языка.
2 * 3 * 3 * 3 = 54
10. Сколько слов длины 5, начинающихся с согласной буквы,
можно составить из букв К, О, Д,Ы? Каждая буква может
входить в слово несколько раз. Слова не обязательно
должны быть осмысленными словами русского языка.
2 * 4 * 4 * 4 * 4 = 512
11. Сколько слов длины 4, начинающихся и
заканчивающиеся согласной буквой, можно составить из
букв К, О, Д? Каждая буква может входить в слово
несколько раз. Слова не обязательно должны быть
осмысленными словами русского языка.
12. Сколько слов длины 5, начинающихся с согласной буквы
и заканчивающихся гласной, можно составить из букв
П, Е, С, Н, Я? Каждая буква может входить в слово
несколько раз. Слова не обязательно должны быть
осмысленными словами русского языка.
К. Поляков, 2006-2016
2 * 3 * 3 * 2 = 36
3 * 5 * 5 * 5 * 2 = 750
http://kpolyakov.spb.ru

21.

Кодирование информации
22
17. Иван составляет 4-буквенные слова из букв А, Б, В, Г, Д, Я. В
каждом слове содержится ровно одна буква Я, причём только на
первой или последней позициях. Сколько различных кодовых
слов может составить Иван?
Ответ. 250
18. Иван составляет 5-буквенные слова из букв А, Б, В, Г, Д, Я. В
каждом слове содержится ровно одна буква Я, причём только на
первой или последней позициях. Сколько различных кодовых
слов может составить Иван?
Ответ. 1250
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

22.

Кодирование информации
23
А. Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению
соответствует своё кодовое слово. В качестве кодовых слов Олег использует 4буквенные слова, в которых есть только буквы A, Б, В, Г и Д, причём буква Г
появляется ровно 1 раз и только на первом или последнем месте. Каждая из
других допустимых букв может встречаться в кодовом слове любое количество раз или
не встречаться совсем. Сколько различных кодовых слов может использовать Олег?
Б. Олег составляет таблицу кодовых слов для передачи сообщений, каждому
сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег
использует 4-буквенные слова, в которых есть только буквы A, Б, В, Г, Д, причём буква
Г появляется не более одного раза и только на последнем месте. Каждая из
других допустимых букв может встречаться в кодовом слове любое количество раз или
не встречаться совсем. Сколько различных кодовых слов может использовать Олег?
4*4 *4* 5
А
Б
В
Д
А
Б
В
Д
А
Б
В
Д
К. Поляков, 2006-2016
А
Б
В
Г
Д
http://kpolyakov.spb.ru

23.

Кодирование информации
24
ДЕМО 2019
Комбинаций:
И * * * *
{ЗИМ}
И * 2 * 2 * 2 * 2 = 16
* И * * *
* * И * *
16 * 5 = 80
* * * И *
* * * * И
Комбинаций:
{ЗАМ} 16 * 5 = 80
Всего: 80 + 80 = 160
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

24.

Кодирование информации
25
ЕГЭ-8
>=2
*2
*3
*4
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

25.

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

26.

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

27.

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

28.

Кодирование информации
29
90. Вася составляет 4-буквенные коды из букв К, Р, О, Й.
Каждую букву нужно использовать ровно 1 раз, при этом код
не может начинаться с буквы Й и
не может содержать сочетания ОЙ.
Сколько различных кодов может составить Вася?
Всего комбинаций:
К, Р, О, Й
4* 3 *2 *1 = 24
ИТОГО:
Все – плохие =
Начинаются с Й:
Й * * *
Й*3* 2*1=6
24 - 6 - 6 = 12
Содержат сочетания ОЙ
1 способ
2 способ
ОЙ * *
ОЙ 2 1
ОЙ * *
* ОЙ *
2 ОЙ 1
*
* ОЙ
К. Поляков, 2006-2016
2 1 ОЙ
2*3 = 6
ХКР
3*2*1=6
http://kpolyakov.spb.ru

29.

Кодирование информации
30
99. Вася составляет 5-буквенные коды из букв Н, И, Ч, Ь, Я.
Каждую букву нужно использовать ровно 1 раз, при этом код
не может начинаться с буквы Ь и
не может содержать сочетания ЬИЯ.
Сколько различных кодов может составить Вася?
Всего комбинаций: Н И Ч Ь Я
ИТОГО: Все – плохие =
5* 4* 3 *2 *1 = 120
120 - 28 = 92
Начинаются с Ь:
Ь * * * *
Ь * 4 * 3 * 2 * 1 = 24
Содержат сочетания ЬИЯ
Ь
ЬИЯ * *
ЬИЯ
Х НЧ
3*2*1=6
К. Поляков, 2006-2016
Плохие:
24 + 6 - 2 = 28
ЬИЯ**
http://kpolyakov.spb.ru

30.

Кодирование информации
31
100. Вася составляет 6-буквенные коды из букв П, А, Н, Е, Л, Ь.
Каждую букву нужно использовать ровно 1 раз, при этом код не
может начинаться с буквы Ь и не может содержать сочетания
ЕАП. Сколько различных кодов может составить Вася?
101. Вася составляет 6-буквенные коды из букв Ш, А, Н, Е, Л, Ь.
Каждую букву нужно использовать ровно 1 раз, при этом код не
может начинаться с буквы Ь и не может содержать сочетания
ЕАЬ. Сколько различных кодов может составить Вася?
102. Вася составляет 6-буквенные коды из букв Н, И, Г, Р, О, Л.
Каждую букву нужно использовать ровно 1 раз, при этом код не
может начинаться с буквы О и не может содержать сочетания
ОИГ. Сколько различных кодов может составить Вася?
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

31.

Кодирование информации
32
92. Вася составляет 5-буквенные коды из букв M, А, Н, О, К. Каждую
букву нужно использовать ровно 1 раз, при этом код не может
начинаться с буквы О и не может содержать сочетания АО. Сколько
различных кодов может составить Вася?
Б. Вася составляет 5-буквенные коды из букв M, А, Н, О, К. Каждую
букву нужно использовать ровно 1 раз, при этом код не может
начинаться с буквы О и не может содержать сочетания ОК. Сколько
различных кодов может составить Вася?
В. Вася составляет 5-буквенные коды из букв M, А, Н, О, К. Каждую
букву нужно использовать ровно 1 раз, при этом код не может
начинаться с буквы О и не может содержать сочетания ОКА. Сколько
различных кодов может составить Вася?
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

32.

Кодирование информации
33
114
Петя составляет четырёхбуквенные слова перестановкой букв слова АБАК.
При этом он избегает слов с двумя подряд одинаковыми буквами. Сколько
всего различных слов может составить Петя?
Всего комбинаций: 4 * 3 * 2 *1 = 24
АБАК
БААК
КААБ
АБАК
АБКА
БАКА
КАБА
АБКА
АКАБ
АКАБ
БКАА
КБАА
АКБА
АКБА
БКАА
КБАА
ААБК
ААБК
БААК
КААБ
ААКБ
ААКБ
БАКА
КАБА
Различимых комбинаций перестановкой букв слова АБАК = 12
4 * 3 * 2 *1
24
--------------- = ---- = 12
2*1
2
С двумя подряд одинаковыми буквами: АА** = ХБК = 3*2*1=6
Итого: 12 – 6 = 6
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

33.

Кодирование информации
34
Петя составляет шестибуквенные слова перестановкой букв слова КАБАЛА.
Сколько всего различных слов может составить Петя?
КАБАЛА
АААКБЛ
ААА
6*5*4*3*2*1
----------------- = 120
3*2*1
XYZ
3*2*1 = 6
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

34.

Кодирование информации
35
117
Петя составляет шестибуквенные слова перестановкой букв слова КАБАЛА.
При этом он избегает слов с двумя подряд одинаковыми буквами. Сколько
всего различных слов может составить Петя?
КАБАЛА
АКАБАЛ
АКБАЛА
АКАБЛА
3А2А1А
А3А2А1
А32А1А
А3А21А
6 + 6 + 6 + 6 = 24
Петя составляет шестибуквенные слова перестановкой букв слова КБЛАОУ.
При этом он избегает слов с двумя подряд гласными буквами. Сколько
всего различных слов может составить Петя?
КАБОЛУ
АКОБУЛ
АКБОЛУ
АКОБЛУ
332211
332211
332211
332211
36*4 = 144
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

35.

Кодирование информации
36
Петя составляет шестибуквенные слова перестановкой букв слова АВРОРА.
При этом он избегает слов с двумя подряд одинаковыми буквами.
Сколько всего различных слов может составить Петя?
АВРОРА
ААРРВО
ААВРОР
ХВРОР
РРАВОА
УАВОА
6*5*4*3*2*1
----------------- = 180
2*1*2*1
ИТОГО: Все – плохие =
180 - 96 = 84
5*4*3*2*1 120
------------- = ----- = 60
2*1
2
5*4*3*2*1 120
------------- = ----- = 60
2*1
2
АА
РР
ААРРВО
МNВО =4*3*2*1 = 24
ААРР
Плохие:
60 +60 – 24 = 96
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

36.

Кодирование информации
37
121. Петя составляет шестибуквенные слова перестановкой букв
слова ТАРТАР. Сколько всего различных слов может составить
Петя?
122. Петя составляет шестибуквенные слова перестановкой букв
слова МОЛОКО. Сколько всего различных слов может составить
Петя?
123. Петя составляет семибуквенные слова перестановкой букв
слова АССАСИН. Сколько всего различных слов может составить
Петя?
124. Петя составляет шестибуквенные слова перестановкой букв
слова ЧИУАУА. Сколько всего различных слов может составить
Петя?
125. Петя составляет семибуквенные слова перестановкой букв
слова ТРАТАТА. Сколько всего различных слов может составить
Петя?
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

37.

Кодирование информации
38
121. Петя составляет шестибуквенные слова перестановкой букв слова ТАРТАР.
Сколько всего различных слов может составить Петя?
К. Поляков, 2006-2016
http://kpolyakov.spb.ru

38.

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