4 мин)
Разработала Фоминова Елена Владимировна,
учитель физики и информатики МБОУ
СОШ № 23 МО Усть-Лабинский район Краснодарского края
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Подготовка к ЕГЭ "Кодирование данных, комбинаторика, системы счисления"
Содержание
- 1. Подготовка к ЕГЭ "Кодирование данных, комбинаторика, системы счисления"
- 2. Задача 1Азбука Морзе позволяет кодировать символы для
- 3. Алексей составляет таблицу кодовых слов для передачи
- 4. Азбука Морзе позволяет кодировать символы для сообщений
- 5. Азбука Морзе позволяет кодировать символы для сообщений
- 6. Сколько существует различных последовательностей из символов «плюс»
- 7. Шахматная доска состоит 8 столбцов и 8
- 8. Какое минимальное количество бит потребуется для кодирования
- 9. Формула Шеннона: N = log2(1/p), где N
- 10. В коробке лежат 64 цветных карандаша. Сообщение
- 11. В корзине лежат черные и белые шары.
- 12. В закрытом ящике находится 32 карандаша, некоторые
- 13. Для передачи сигналов на флоте используются специальные
- 14. Световое табло состоит из лампочек. Каждая лампочка
- 15. На световой панели в ряд расположены 7
- 16. Для передачи аварийных сигналов договорились использовать специальные
- 17. Сколько существует различных символьных последовательностей длины от
- 18. Рассматриваются символьные последовательности длины 5 в шестибуквенном
- 19. Все 5-буквенные слова, составленные из букв А,
- 20. Сколько слов длины 5, начинающихся с гласной
- 21. Все 5-буквенные слова, составленные из букв А,
- 22. Все 5-буквенные слова, составленные из букв А,
- 23. Все 5-буквенные слова, составленные из букв А,
- 24. Все 5-буквенные слова, составленные из букв А,
- 25. Все 5-буквенные слова, составленные из букв А,
- 26. Все 5-буквенные слова, составленные из букв А,
- 27. Все 5-буквенные слова, составленные из букв А,
- 28. Все 4-буквенные слова, составленные из букв М,
- 29. Все 5-буквенные слова, составленные из букв А,
- 30. Все 5-буквенные слова, составленные из букв В,
- 31. Сколько есть различных символьных последовательностей длины от
- 32. Сколько существует различных символьных последовательностей длины 7
- 33. Сколько существует различных символьных последовательностей длины 6
- 34. Крылов С.С. ЕГЭ 2017. Информатика. Тематические тестовые
- 35. Интернет-ресурсыСлайд 1 ЕГЭ http://bashgymn.ucoz.ru/muzi/may/a12183fc240047e94e1f82d423bb0dd0.jpgКлетка http://www.kab35.ru/wpimages/wpc58224db_06.pngСлайд 2 -33 дети http://www.yiliti.com/d/file/20160320/658-151111092Q4M9.jpgСлайд 2, 3, 6, 9Человек с книгами https://rostovmama.ru/upload/000/u2/371/fb28decb.png
- 36. Скачать презентанцию
Задача 1Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе
Слайды и текст этой презентации
Слайд 1Кодирование данных, комбинаторика,
системы счисления
Задание 10 (базовый уровень, время –
4 мин)
СОШ № 23 МО Усть-Лабинский район Краснодарского края
Слайд 2Задача 1
Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи,
задавая комбинацию точек и тире. Сколько различных символов (цифр, букв,
знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)?Если слово состоит из k букв, причем каждая буква может быть выбрана n способами, то число возможных слов вычисляется как
N = nk
Алфавит состоит из двух символов «-» и «.».
Длина кода 4≤k≤5.
Количество символов:
N=24+25=16+32=48
Решение:
Ответ: 48
Слайд 3Алексей составляет таблицу кодовых слов для передачи сообщений, каждому сообщению
соответствует своё кодовое слово. В качестве кодовых слов Алексей использует
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
Слайд 4Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая
комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков
пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее двух и не более четырёх сигналов (точек и тире)?Задача 3
Решение:
Алфавит состоит из двух символов «-» и «.».
Длина кода 2≤k ≤ 4.
Количество символов:
N=22+23+24=4+8+16=28
Ответ: 28
Слайд 5Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая
комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков
пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не более пяти сигналов (точек и тире)?Задача 4
Решение:
Алфавит состоит из двух символов «-» и «.».
Длина кода k ≤ 5.
Количество символов:
N=21+22+23+24+25=2+4+8+16+32=62
Ответ: 62
Слайд 6Сколько существует различных последовательностей из символов «плюс» и «минус», длиной
ровно в пять символов?
Задача 5
Решение:
Если слово состоит из k букв,
причем каждая буква может быть выбрана n способами, то число возможных слов вычисляется какN = nk
Слово состоит из 5 символов, Мощность алфавита составляет 2,
тогда число возможных слов:
N = 25=32
Ответ: 32
Слайд 7Шахматная доска состоит 8 столбцов и 8 строк. Какое минимальное
количество бит потребуется для кодирования координат одного шахматного поля?
Задача 6
Решение:
Ответ:
6Всего координат шахматного поля
8х8=64.
Мощность алфавита составляет 2
(бит – это «0» или «1»),
тогда
N =64, N= 2k 64= 2k
26 = 2k k=6
Слайд 8Какое минимальное количество бит потребуется для кодирования положительных чисел, меньших
60?
Задача 7
Решение:
Ответ: 6
Меньше 60 59 чисел N =59.
N= 2k
59= 2k25 =32 недостаточно,
26=64 достаточно k=6
Слайд 9Формула Шеннона:
N = log2(1/p),
где N - это количество
информации,
р – это вероятность события.
В корзине лежат 8 черных шаров
и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?Задача 8
Решение:
Ответ: 2
Вероятность того, что достали черный шар:
р=
Воспользуемся формулой Шеннона
N = log2(1/p)= log2(4)= log2(22)=2.
Слайд 10В коробке лежат 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
Слайд 11В корзине лежат черные и белые шары. Среди них 18
черных шаров. Сообщение о том, что достали белый шар, несет
2 бита информации. Сколько всего шаров в корзине?Задача 10
Решение:
Ответ: 24
Пусть всего у шаров в корзине. Вероятность того, что достали белый шар:
р=
По условию задачи N=2.
Воспользуемся формулой Шеннона:
N=2= log2(у/(у-18)) 4=
у=24
Слайд 12В закрытом ящике находится 32 карандаша, некоторые из них синего
цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ
синий» несёт 4 бита информации. Сколько синих карандашей в ящике?Задача 11
Решение:
Пусть у – число синих карандашей, тогда вероятность того, что достали НЕ синий карандаш : р= 1-
По условию задачи N=4. Воспользуемся формулой Шеннона: N=4= log2(32/(32-у))
16= у=30
Ответ: 30
Слайд 13Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые
в одну линию (последовательность важна). Какое количество различных сигналов может
передать корабль при помощи четырех сигнальных флагов, если на корабле имеются флаги трех различных видов (флагов каждого вида неограниченное количество)?Задача 12
Решение:
N = mk,
где m– мощность алфавита, а k– длина кода.
По условию m=3, k=4
N = 34=81
Ответ: 81
Слайд 14Световое табло состоит из лампочек. Каждая лампочка может находиться в
одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее
количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов?Задача 13
Решение:
N = mk,
где m– мощность алфавита, а k– длина кода .
По условию N=18, k=4
18 = 3k 32 =9, 33 =27
k=3
Ответ: 3
Слайд 15На световой панели в ряд расположены 7 лампочек. Каждая из
первых двух лампочек может гореть красным, жёлтым или зелёным цветом.
Каждая из остальных пяти лампочек может гореть одним из двух цветов - красным или белым. Сколько различных сигналов можно передать с помощью панели (все лампочки должны гореть, порядок цветов имеет значение)?Задача 14
Решение:
Воспользуемся формулой N = mk.
Для первых двух лампочек: 32 =9,
для оставшихся пяти лампочек 25 =32
N=N1 N2=9 32= 288
Ответ: 288
Слайд 16Для передачи аварийных сигналов договорились использовать специальные цветные сигнальные ракеты,
запускаемые последовательно. Одна последовательность ракет — один сигнал; в каком порядке
идут цвета — существенно. Какое количество различных сигналов можно передать при помощи запуска ровно четырёх таких сигнальных ракет, если в запасе имеются ракеты пяти различных цветов (ракет каждого вида неограниченное количество, цвет ракет в последовательности может повторяться)?Задача 15
Решение:
Ответ: 625
Воспользуемся формулой N = mk.
По условию задачи m=5, k=4 54 =625.
Слайд 17Сколько существует различных символьных последовательностей длины от одного до трёх
в четырёхбуквенном алфавите {A, C, G, T}?
Задача 16
Решение:
Воспользуемся формулой N
= mk.По условию задачи m=4, 1≤k ≤ 3
N= 41+ 42+ 43 =4+16+64=84.
Ответ: 84
Слайд 18Рассматриваются символьные последовательности длины 5 в шестибуквенном алфавите {У, Ч,
Е Н, И, К}. Сколько существует таких последовательностей, которые начинаются
с буквы У и заканчиваются буквой К?Задача 17
Решение:
Воспользуемся формулой N = mk.
По условию задачи m=6, k=5,
все слова которые начинаются с буквы У и заканчиваются буквой К У***К k=3
N= 63 =216.
Ответ: 216
Слайд 19Все 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=УОУАУ.
Ответ: УОУАУ
Слайд 20Сколько слов длины 5, начинающихся с гласной буквы, можно составить
из букв Е, Г, Э? Каждая буква может входить в
слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.Задача 19
Решение:
Мощность алфавита m=3, длина слова k=5.
Слова, начинающиеся с гласной буквы:
Е**** 34=81
Э**** 34=81 281=162
Ответ: 162
Слайд 21Все 5-буквенные слова, составленные из букв А, О, У, записаны
в алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААО
3. ААААУ
4. АААОА
……
Укажите номер первого слова, которое начинается с буквы У.Задача 20
Решение:
Рассмотрим троичную систему, в которой А=0, О=1, У=2. Первое слово, начинающееся на У – УАААА=200003=281=162.
Первое слово, начинающиеся с буквы У, стоит на 163 месте.
Ответ: 163
Слайд 22Все 5-буквенные слова, составленные из букв А, К, Р, У,
записаны в алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААК
3. ААААР
4.
ААААУ5. АААКА …… Укажите номер первого слова, которое начинается с буквы К.
Задача 21
Решение:
Рассмотрим четверичную систему, в которой А=0, К=1, Р=2, У=3. Первое слово, начинающееся на К – КАААА=100004=44=256.
Первое слово, начинающиеся с буквы К,
стоит на 257 месте.
Ответ: 257
Слайд 23Все 5-буквенные слова, составленные из букв А, О, У, записаны
в алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААО
3. ААААУ
4. АААОА
……
Укажите номер слова УАУАУ.Задача 22
Решение:
Мощность алфавита m=3, длина слова k=5.
Закодируем каждую букву: А-0, О-1, У-2, тогда УАУАУ=20202 202023= 234+ 232+ 230=
=162+18+2=182 202023= 18210 номер - 183
Ответ: 183
Слайд 24Все 5-буквенные слова, составленные из букв А, К, Р, У,
записаны в алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААК
3. ААААР
4.
ААААУ5. АААКА
…… Укажите номер слова УКАРА.
Задача 23
Решение:
Закодируем каждую букву: А-0, К-1, Р-2, У-3, тогда УКАРА=31020
310204= 344+ 143+ 241=3256+64+8=
=768+64+8=840 202023= 84010 номер - 841
Ответ: 841
Слайд 25Все 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=АУУРК
Ответ: АУУРК
Слайд 26 Все 5-буквенные слова, составленные из букв А, К, Р, У,
записаны в алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААК
3. ААААР
4.
ААААУ5. АААКА
…… Укажите номер первого слова, которое начинается с буквы У.
Задача 25
Решение:
Мощность алфавита m=4, длина слова k=5.
Всего слов 45=1024. На каждую букву приходится 1024:4=256 слов
А****К****Р****У****
256 256 256 256
3256=768. Первое слово, начинающиеся с буквы У, стоит на 769 месте.
Ответ: 769
Слайд 27Все 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
Слайд 28Все 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=ХХХМ
Ответ: ХХХМ
Слайд 29Все 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=АААОА
Ответ: АААОА
Слайд 30Все 5-буквенные слова, составленные из букв В, Е, К, Н,
О, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1.
ВВВВВ2. ВВВВЕ
3. ВВВВК
4. ВВВВН
5. ВВВВО
6. ВВВЕВ
Под каким номером стоит первое из слов, которое начинается с буквы О?
Задача 28
Решение:
Мощность алфавита m=5, длина слова k=5.
Всего слов 55=3125. На каждую букву приходится 3125:5=625 слов
В****Е****К****Н****О****
625 625 625 625 625
4625=2500. Первое слово, начинающиеся с буквы О, стоит на 2501 месте.
Ответ: 2501
Слайд 31Сколько есть различных символьных последовательностей длины от одного до четырёх
в трёхбуквенном алфавите {А, 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
Слайд 32Сколько существует различных символьных последовательностей длины 7 в четырёхбуквенном алфавите
{А, B, C, D}, которые содержат ровно пять букв А?
Задача
30Решение:
Определим количество возможных вариантов комбинаций, согласно условию задачи, используя формулу числа перестановок:
n1 и n2 – количество разных символов в слове, например ААААА**
n1 =5, n2 =2 Р(5,2)=(5+2)!/5!2!=7!/5!2!=37=21
Таким образом 21 вариант последовательностей. В каждом варианте 32 слова. 219=189
Ответ: 189
Слайд 33Сколько существует различных символьных последовательностей длины 6 в четырёхбуквенном алфавите
{А, B, C, D}, которые содержат не менее двух букв
А?Задача 31
Решение:
Определим количество возможных вариантов комбинаций, используя формулу
числа перестановок:
АА****n1=4,n2=2 Р(4,2)=6!/4!2!=53=15; 1534=1215;
ААА***n1=3, n2=3 Р(3,3)=6!/3!3!=45=20; 2033=540;
АААА**n1=2, n2=4 Р(2,4)=6!/4!2!=53=15; 1532=135;
ААААА*n1=1, n2=5 Р(1,5)=6!/1!5!=6; 631=18;
АААААА 1;
N=1+18+135+540+1215=1909
Ответ: 1909
Слайд 34Крылов С.С. ЕГЭ 2017. Информатика. Тематические тестовые задания. -М.: Издательство
«Экзамен», 2017
Крылов С.С., Чуркина Т.Е. ЕГЭ 2017. Информатика и ИКТ:
типовые экзаменационные варианты: 20 вариантов. –М.: Издательство «Национальное образование», 2017Сайт Полякова К.И. http://kpolyakov.spb.ru
Список использованной литературы
Слайд 35Интернет-ресурсы
Слайд 1
ЕГЭ http://bashgymn.ucoz.ru/muzi/may/a12183fc240047e94e1f82d423bb0dd0.jpg
Клетка http://www.kab35.ru/wpimages/wpc58224db_06.png
Слайд 2 -33
дети http://www.yiliti.com/d/file/20160320/658-151111092Q4M9.jpg
Слайд 2,
3, 6, 9
Человек с книгами https://rostovmama.ru/upload/000/u2/371/fb28decb.png
