Подготовка к ЕГЭ "Кодирование данных, комбинаторика, системы счисления"

Подписи к слайдам:

Кодирование данных, комбинаторика, системы счисления Задание 10 (базовый уровень, время – 4 мин)

Разработала Фоминова Елена Владимировна,

учитель физики и информатики МБОУ СОШ № 23

МО Усть-Лабинский район Краснодарского края

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

Если слово состоит из k букв, причем каждая буква может быть выбрана n способами, то число возможных слов вычисляется как

N = nk

Подсказка

Алфавит состоит из двух символов «-» и «.».

Длина кода 4≤k≤5.

Количество символов:

N=24+25=16+32=48

Решение:

Ответ: 48

Алексей составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Алексей использует 5-буквенные слова, в которых есть только буквы A, B, C, X, причём буква X может появиться на первом месте или не появиться вовсе. Сколько различных кодовых слов может использовать Алексей? Алексей составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Алексей использует 5-буквенные слова, в которых есть только буквы A, B, C, X, причём буква X может появиться на первом месте или не появиться вовсе. Сколько различных кодовых слов может использовать Алексей?

Задача 2

Подсказка

Решение:

Если слово состоит из k букв, причем есть n1 вариантов выбора первой буквы, n2 вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение

N = n1 · n2 · … · nk

Слово состоит из 5 букв, причем 4 варианта выбора первой буквы, по 3 варианта выбора со второй по пятую буквы. Число возможных слов:

N = 4 · 3 · 3 · 3 · 3=324

Ответ: 324

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

Задача 3

Решение:

Алфавит состоит из двух символов «-» и «.».

Длина кода 2≤k ≤ 4.

Количество символов:

N=22+23+24=4+8+16=28

Ответ: 28

Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не более пяти сигналов (точек и тире)? Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не более пяти сигналов (точек и тире)?

Задача 4

Решение:

Алфавит состоит из двух символов «-» и «.».

Длина кода k ≤ 5.

Количество символов:

N=21+22+23+24+25=2+4+8+16+32=62

Ответ: 62

Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов? Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов?

Задача 5

Подсказка

Решение:

N = nk

Слово состоит из 5 символов, Мощность алфавита составляет 2,

тогда число возможных слов:

N = 25=32

Ответ: 32

Шахматная доска состоит 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля? Шахматная доска состоит 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля?

Задача 6

Решение:

Ответ: 6

Всего координат шахматного поля

8х8=64.

Мощность алфавита составляет 2

(бит – это «0» или «1»),

тогда

N =64, N= 2k  64= 2k

26 = 2k k=6

Какое минимальное количество бит потребуется для кодирования положительных чисел, меньших 60? Какое минимальное количество бит потребуется для кодирования положительных чисел, меньших 60?

Задача 7

Решение:

Ответ: 6

Меньше 60 59 чисел  N =59.

N= 2k  59= 2k

25 =32 недостаточно,

26=64 достаточно k=6

В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?

Формула Шеннона:

N = log2(1/p),

где N - это количество информации,

р – это вероятность события.

В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?

Задача 8

Решение:

Ответ: 2

Вероятность того, что достали черный шар:

р=

Воспользуемся формулой Шеннона

N = log2(1/p)= log2(4)= log2(22)=2.

Подсказка

В коробке лежат 64 цветных карандаша. Сообщение о том, что достали белый карандаш, несет 4 бита информации. Сколько белых карандашей было в коробке? В коробке лежат 64 цветных карандаша. Сообщение о том, что достали белый карандаш, несет 4 бита информации. Сколько белых карандашей было в коробке?

Задача 9

Решение:

Вероятность того, что достали белый шар:

р=

По условию задачи N=4.

Воспользуемся формулой Шеннона

N = log2(1/p) 

N= log2(64/n)= log2(26/n)=6- log2(n)=4,

log2(n)=2  n=4

Ответ: 4

В корзине лежат черные и белые шары. Среди них 18 черных шаров. Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько всего шаров в корзине? В корзине лежат черные и белые шары. Среди них 18 черных шаров. Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько всего шаров в корзине?

Задача 10

Решение:

Ответ: 24

Пусть всего у шаров в корзине. Вероятность того, что достали белый шар:

р=

По условию задачи N=2.

Воспользуемся формулой Шеннона:

N=2= log2(у/(у-18))  4=

 у=24

В закрытом ящике находится 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике? В закрытом ящике находится 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике?

Задача 11

Решение:

Пусть у – число синих карандашей, тогда вероятность того, что достали НЕ синий карандаш : р= 1-

По условию задачи N=4. Воспользуемся формулой Шеннона: N=4= log2(32/(32-у))

 16=  у=30

Ответ: 30

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

Задача 12

Решение:

N = mk,

где m– мощность алфавита, а k– длина кода.

По условию m=3, k=4

N = 34=81

Ответ: 81

Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов? Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов?

Задача 13

Решение:

N = mk,

где m– мощность алфавита, а k– длина кода .

По условию N=18, k=4

18 = 3k  32 =9, 33 =27

 k=3

Ответ: 3

На световой панели в ряд расположены 7 лампочек. Каждая из первых двух лампочек может гореть красным, жёлтым или зелёным цветом. Каждая из остальных пяти лампочек может гореть одним из двух цветов - красным или белым. Сколько различных сигналов можно передать с помощью панели (все лампочки должны гореть, порядок цветов имеет значение)? На световой панели в ряд расположены 7 лампочек. Каждая из первых двух лампочек может гореть красным, жёлтым или зелёным цветом. Каждая из остальных пяти лампочек может гореть одним из двух цветов - красным или белым. Сколько различных сигналов можно передать с помощью панели (все лампочки должны гореть, порядок цветов имеет значение)?

Задача 14

Решение:

Воспользуемся формулой N = mk.

Для первых двух лампочек: 32 =9,

для оставшихся пяти лампочек 25 =32

 N=N1 N2=9 32= 288

Ответ: 288

Для передачи аварийных сигналов договорились использовать специальные цветные сигнальные ракеты, запускаемые последовательно. Одна последовательность ракет — один сигнал; в каком порядке идут цвета — существенно. Какое количество различных сигналов можно передать при помощи запуска ровно четырёх таких сигнальных ракет, если в запасе имеются ракеты пяти различных цветов (ракет каждого вида неограниченное количество, цвет ракет в последовательности может повторяться)? Для передачи аварийных сигналов договорились использовать специальные цветные сигнальные ракеты, запускаемые последовательно. Одна последовательность ракет — один сигнал; в каком порядке идут цвета — существенно. Какое количество различных сигналов можно передать при помощи запуска ровно четырёх таких сигнальных ракет, если в запасе имеются ракеты пяти различных цветов (ракет каждого вида неограниченное количество, цвет ракет в последовательности может повторяться)?

Задача 15

Решение:

Ответ: 625

Воспользуемся формулой N = mk.

По условию задачи m=5, k=4  54 =625.

Сколько существует различных символьных последовательностей длины от одного до трёх в четырёхбуквенном алфавите {A, C, G, T}? Сколько существует различных символьных последовательностей длины от одного до трёх в четырёхбуквенном алфавите {A, C, G, T}?

Задача 16

Решение:

Воспользуемся формулой N = mk.

По условию задачи m=4, 1≤k ≤ 3

 N= 41+ 42+ 43 =4+16+64=84.

Ответ: 84

Рассматриваются символьные последовательности длины 5 в шестибуквенном алфавите {У, Ч, Е Н, И, К}. Сколько существует таких последовательностей, которые начинаются с буквы У и заканчиваются буквой К? Рассматриваются символьные последовательности длины 5 в шестибуквенном алфавите {У, Ч, Е Н, И, К}. Сколько существует таких последовательностей, которые начинаются с буквы У и заканчиваются буквой К?

Задача 17

Решение:

Воспользуемся формулой N = mk.

По условию задачи m=6, k=5,

все слова которые начинаются с буквы У и заканчиваются буквой К У***К  k=3

 N= 63 =216.

Ответ: 216

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Запишите слово, которое стоит на 210-м месте от начала списка.

Задача 18

Решение:

Мощность алфавита m=3, длина слова k=5. На 210-м месте стоит число 209 в троичной системе счисления, т.е. 20910=х3

209:3=69 (2), 69:3=23 (0), 23:3=7 (2), 7:3=2 (1)

20910=212023. Пусть А-0, О-1, У-2, тогда 21202=УОУАУ.

Ответ: УОУАУ

Сколько слов длины 5, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка. Сколько слов длины 5, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Задача 19

Решение:

Мощность алфавита m=3, длина слова k=5.

Слова, начинающиеся с гласной буквы:

Е****  34=81

Э****  34=81  281=162

Ответ: 162

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Укажите номер первого слова, которое начинается с буквы У.

Задача 20

Решение:

Рассмотрим троичную систему, в которой А=0, О=1, У=2. Первое слово, начинающееся на У – УАААА=200003=281=162.

Первое слово, начинающиеся с буквы У, стоит на 163 месте.

Ответ: 163

Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА …… Укажите номер первого слова, которое начинается с буквы К.

Задача 21

Решение:

Рассмотрим четверичную систему, в которой А=0, К=1, Р=2, У=3. Первое слово, начинающееся на К – КАААА=100004=44=256.

Первое слово, начинающиеся с буквы К,

стоит на 257 месте.

Ответ: 257

Задача 22

Решение:

Мощность алфавита m=3, длина слова k=5.

Закодируем каждую букву: А-0, О-1, У-2, тогда УАУАУ=20202 202023= 234+ 232+ 230=

=162+18+2=182 202023= 18210  номер - 183

Ответ: 183

Задача 23

Решение:

Закодируем каждую букву: А-0, К-1, Р-2, У-3, тогда УКАРА=31020

310204= 344+ 143+ 241=3256+64+8=

=768+64+8=840 202023= 84010  номер - 841

Ответ: 841

Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА …… Запишите слово, которое стоит на 250-м месте от начала списка.

Задача 24

Решение:

Мощность алфавита m=4, длина слова k=5. На 250-м месте стоит число 249 в четверичной системе счисления, т.е. 24910=х4

249:4=62 (1), 62:4=15 (2), 15:4=3 (3)

24910=33214. Длина слова 5  слово-03321  Если А-0, К-1, Р-2, У-3, то 03321=АУУРК

Ответ: АУУРК

Задача 25

Решение:

Мощность алфавита m=4, длина слова k=5.

Всего слов 45=1024. На каждую букву приходится 1024:4=256 слов 

А****К****Р****У****

256 256 256 256

 3256=768. Первое слово, начинающиеся с буквы У, стоит на 769 месте.

Ответ: 769

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Сколько букв А встречается в слове, стоящем на 101-м месте от начала списка.

Задача 25

Решение:

Мощность алфавита m=3, длина слова k=5. На 101-м месте стоит число 100 в троичной системе счисления, т.е. 10010=х3

100:3=33 (1), 33:3=11 (0), 11:3=3 (2), 3:3=1(0)

10010=102013  Если А-0, О-1, У-2, то 10201=ОАУАО

Ответ: 2

Все 4-буквенные слова, составленные из букв М, У, Х, А записаны в алфавитном порядке и пронумерованы. Все 4-буквенные слова, составленные из букв М, У, Х, А записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. АААА 2. АААМ 3. АААУ 4. АААХ 5. ААМА …… Запишите слово, которое стоит под номером 254.

Задача 26

Решение:

Мощность алфавита m=4, длина слова k=4. На 254-м месте стоит число 253 в четверичной системе счисления, т.е. 25310=х4

253:4=63 (1), 63:4=15 (3), 15:4=3 (3)

25310=33314  Если А-0, М-1, У-2, Х=3, то 3331=ХХХМ

Ответ: ХХХМ

Все 5-буквенные слова, составленные из букв А, О, У, записаны в обратном алфавитном порядке. Вот начало списка: Все 5-буквенные слова, составленные из букв А, О, У, записаны в обратном алфавитном порядке. Вот начало списка: 1. УУУУУ 2. УУУУО 3. УУУУА 4. УУУОУ …… Запишите слово, которое стоит на 240-м месте от начала списка.

Задача 27

Решение:

Мощность алфавита m=3, длина слова k=5. На 240-м месте стоит число 239 в троичной системе счисления, т.е. 10010=х3

239:3=79 (2), 79:3=26 (1), 26:3=8 (2), 8:3=2(2)

23910=222123  Если У-0, О-1, А-2, то 22212=АААОА

Ответ: АААОА

Все 5-буквенные слова, составленные из букв В, Е, К, Н, О, записаны в алфавитном порядке и пронумерованы. Вот начало списка: Все 5-буквенные слова, составленные из букв В, Е, К, Н, О, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. ВВВВВ 2. ВВВВЕ 3. ВВВВК 4. ВВВВН 5. ВВВВО 6. ВВВЕВ Под каким номером стоит первое из слов, которое начинается с буквы О?

Задача 28

Решение:

Мощность алфавита m=5, длина слова k=5.

Всего слов 55=3125. На каждую букву приходится 3125:5=625 слов 

В****Е****К****Н****О****

625 625 625 625 625

 4625=2500. Первое слово, начинающиеся с буквы О, стоит на 2501 месте.

Ответ: 2501

Сколько есть различных символьных последовательностей длины от одного до четырёх в трёхбуквенном алфавите {А, B, C}? Сколько есть различных символьных последовательностей длины от одного до четырёх в трёхбуквенном алфавите {А, B, C}?

Задача 29

Решение:

Мощность алфавита m=3, длина слова 1≤k ≤ 4.

Всего слов:

при N1=1 31=3

при N2=2 32=9

при N3=3 33=27

при N4=4 34=81

 N= N1+ N2 + N3 + N4 = 3+9+27+81=120.

Ответ: 120

Сколько существует различных символьных последовательностей длины 7 в четырёхбуквенном алфавите {А, B, C, D}, которые содержат ровно пять букв А? Сколько существует различных символьных последовательностей длины 7 в четырёхбуквенном алфавите {А, B, C, D}, которые содержат ровно пять букв А?

Задача 30

Решение:

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

n1 и n2 – количество разных символов в слове, например ААААА**

n1 =5, n2 =2  Р(5,2)=(5+2)!/5!2!=7!/5!2!=37=21

Таким образом 21 вариант последовательностей. В каждом варианте 32 слова.  219=189

Ответ: 189

Сколько существует различных символьных последовательностей длины 6 в четырёхбуквенном алфавите {А, B, C, D}, которые содержат не менее двух букв А? Сколько существует различных символьных последовательностей длины 6 в четырёхбуквенном алфавите {А, B, C, D}, которые содержат не менее двух букв А?

Задача 31

Решение:

Определим количество возможных вариантов комбинаций, используя формулу

числа перестановок:

АА****n1=4,n2=2  Р(4,2)=6!/4!2!=53=15; 1534=1215;

ААА***n1=3, n2=3  Р(3,3)=6!/3!3!=45=20; 2033=540;

АААА**n1=2, n2=4  Р(2,4)=6!/4!2!=53=15; 1532=135;

ААААА*n1=1, n2=5  Р(1,5)=6!/1!5!=6; 631=18;

АААААА  1;

N=1+18+135+540+1215=1909

Ответ: 1909

Крылов С.С. ЕГЭ 2017. Информатика. Тематические тестовые задания. -М.: Издательство «Экзамен», 2017

Крылов С.С. ЕГЭ 2017. Информатика. Тематические тестовые задания. -М.: Издательство «Экзамен», 2017
Крылов С.С., Чуркина Т.Е. ЕГЭ 2017. Информатика и ИКТ: типовые экзаменационные варианты: 20 вариантов. –М.: Издательство «Национальное образование», 2017
Сайт Полякова К.И. http://kpolyakov.spb.ru

Список использованной литературы

Интернет-ресурсы Слайд 1

ЕГЭ http://bashgymn.ucoz.ru/muzi/may/a12183fc240047e94e1f82d423bb0dd0.jpg
Клетка http://www.kab35.ru/wpimages/wpc58224db_06.png
дети http://www.yiliti.com/d/file/20160320/658-151111092Q4M9.jpg
Человек с книгами https://rostovmama.ru/upload/000/u2/371/fb28decb.png

Подготовка к ЕГЭ "Кодирование данных, комбинаторика, системы счисления"

Подписи к слайдам:

Информатика - еще материалы к урокам:

Предметы

Похожие материалы