Объяснение заданий 10 ЕГЭ по информатике
Рассмотрим кратко необходимые для решения 10 задания ЕГЭ понятия и формулы.
Измерение количества информации
- Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
- 1 бит – это количество информации, которое можно передать с помощью одного знака в двоичном коде (0 или 1).
- Алфавит — это набор знаков, используемый в том или ином языке.
- Мощность алфавита — это количество используемых в алфавите знаков.
- Сообщение — это любая последовательность символов какого-либо алфавита.
1 Кб (килобайт) = 1024 байта
1 Мб (мегабайт) = 1024 Кб
1 Гб (гигабайт) = 1024 Мб
1 Тб (терабайт) = 1024 Гб
1 Пб (петабайт) = 1024 Тб
8 = 23
1024 = 210
Рассмотрим еще несколько определений:
Мощность алфавита
Для вычисления количества информации применяются несколько различных формул в зависимости от ситуации:
Двоичное кодирование сообщений (равновероятностные события)
При вычислении количества информации в сообщении для равновероятностных событий, общее количество которых равно N, используется формула:
Решение:
Количество сообщений длиной L битов:
Т.е. количество сообщений длиной 2 бита, как в примере с нашими буквами, будет равно N = 22 = 4
Ответ: 4
Количество различных сообщений в алфавите разной мощности
Рассмотрим вариант с 5 буквами (мощность алфавита = 5), которые надо разместить в сообщении длиной 2 символа:
Найдем формулу для нахождения количества различных сообщений в алфавите различной мощности:
- N – мощность алфавита
- L – длина сообщения
- Q – количество различных сообщений
Решение:
Q = 263
или
26 * 26 * 26 = 17576
Ответ: 17576
Количество сообщений при различном вхождении (встречаемости) букв
Иногда в заданиях 10 приходится использовать формулу комбинаторики для проверки полученных результатов перебора. Число сочетаний из n элементов по k элементов:
\[ C{\binom{k}{n}}= \frac{n!}{k!(n-k)!} \]
Решение:
- Длина сообщения = 4. Мощность алфавита = 4. Но мешает условие: буква А встречается ровно два раза.
- В таких заданиях можно использовать способ перебора всевозможных вариантов:
два раза буква А, на остальных местах - одна из трех оставшихся букв: А А 3 3 = 3 * 3 = 32 = 9 А 3 А 3 = 9 А 3 3 А = 9 3 А А 3 = 9 3 А 3 А = 9 3 3 А А = 9
Число сочетаний из n элементов по k элементов:
\[ C{\binom{k}{n}}= \frac{n!}{k!(n-k)!} \]
\[ C{\binom{2}{4}}= \frac{4!}{2!(4-2)!} = \frac{24}{2*2} = 6 \]
6 * 9 = 54
Дополнительные формулы
Количество информации и равновероятные события
При определении количества информации для равновероятностных событий могут понадобиться две формулы:
Количество информации и неравновероятные события
При использовании неравновероятного события, вероятность которого равна p, для вычисления количества информации используется формула:
*квадратные скобки означают ближайшее целое, меньшее или равное значению выражения в скобках
Формула Хартли
Информационный объем сообщения длиной L:
Алфавитный подход
Решение заданий 10 ЕГЭ по информатике
Сколько вариантов шифра или кодовых слов
Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 6.
Сколько различных вариантов шифра можно задать, если известно, что цифра 1 должна встречаться в коде ровно 1 раз, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?
✍ Решение:
- Формула нахождения количества различных сообщений:
- Итак, что у нас дано из этой формулы:
- Длина сообщения (L) = 5 символов
- Мощность алфавита (N) = 6 (цифры от 1 до 6).
- Но так как цифра 1 встречается по условию ровно один раз, а остальные 5 цифр — любое количество раз, то будем считать, что N = 5 (цифры от 2 до 6, исключая 1). Т.е. возьмем вариант, когда 1 стоит на первом месте, а остальные 5 цифр размещаем на 4 позиции:
1 5 5 5 5 - 1 * Q = 54 = 625
✎ 1 способ. Найдем количество вариантов методом перебора:
1 5 5 5 5 -1 * Q=54= 625 5 1 5 5 5 -1 * Q=54= 625 5 5 1 5 5 -1 * Q=54= 625 5 5 5 1 5 -1 * Q=54= 625 5 5 5 5 1 -1 * Q=54= 625
✎ 2 способ. Найдем количество вариантов при помощи формулы комбинаторики:
\[ C{\binom{4}{5}}= \frac{5!}{4!(5-4)!} = 5 \]
625 * 5 = 3125
Результат: 3125
Детальный разбор задания 10 ЕГЭ по информатике предлагаем посмотреть в видеоуроке:
Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является либо буквой (A или B) или цифрой (1, 2 или 3).
Сколько различных вариантов шифра можно задать, если известно, что в коде присутствует ровно одна буква, а все другие символы являются цифрами?
✍ Решение:
- Формула нахождения количества различных сообщений:
- Посчитаем количество возможных шифров для одного из вариантов (например, когда буквы находятся на первой позиции). Так как цифры (1, 2, 3) могут занимать 4 позиции из пяти, а две буквы (А и В) одну из позиций, значит:
Q = 2 * 34 = 162
AB 123 123 123 123 = 162
"2" означает одна из двух букв: А или B, "3" - одна из трех цифр: 2 3 3 3 3 -> Q = 2 * 34 = 162 3 2 3 3 3 -> Q = 2 * 34 = 162 3 3 2 3 3 -> Q = 2 * 34 = 162 3 3 3 2 3 -> Q = 2 * 34 = 162 3 3 3 3 2 -> Q = 2 * 34 = 162
5 * 162 = 810
Результат: 810
Подробное решение данного задания предлагаем посмотреть на видео:
Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег использует 4-буквенные слова, в которых есть только буквы A, Б, В, Г, Д и Е, причём буква Г появляется ровно 1 раз и только на первом или последнем месте. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем.
Сколько различных кодовых слов может использовать Олег?
✍ Решение:
- Вспомним формулу получения количества возможных вариантов слов:
- где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
- Рассмотрим варианты, когда буква Г встречается на первом или последнем месте:
N = n1 * n2 * n3 * … * nL = nL
Г ? ? ? = 1 * 5 * 5 * 5 = 53 = 125 ? ? ? Г = 5 * 5 * 5 * 1 = 53 = 125
125 + 125 = 250
Результат: 250
Видеоразбор данного задания:
Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является одной из букв X, Y или Z.
Сколько различных вариантов шифра можно задать, если известно, что буква X должна встречаться в коде ровно 2 раза, а каждая из других допустимых букв может встречаться в шифре любое количество раз или не встречаться совсем?
Типовые задания для тренировки
✍ Решение:
- Формула нахождения количества различных сообщений:
- Итак, что у нас дано из этой формулы:
- Начальная мощность алфавита (N) = 3 (буквы X, Y, Z). Но так как буква X встречается ровно два раза, то мы ее рассмотрим отдельно, а остальные 2 буквы — встречаются любое количество раз, значит, будем считать, что:
N = 3 - 1 = 2 (Y и Z)
(L) = 5 - 2 = 3 символа (остальные два символа отведем на размещение X)
X X ? ? ? -> 12 * Q = 23 = 8
✎1 способ. Перебор всех вариантов:
X X ? ? ? - 12 * Q = 23 = 8 X ? X ? ? - 12 * Q = 23 = 8 X ? ? X ? - 12 * Q = 23 = 8 X ? ? ? X - 12 * Q = 23 = 8 ? X X ? ? - 12 * Q = 23 = 8 ? X ? X ? - 12 * Q = 23 = 8 ? X ? ? X - 12 * Q = 23 = 8 ? ? X X ? - 12 * Q = 23 = 8 ? ? X ? X - 12 * Q = 23 = 8 ? ? ? X X - 12 * Q = 23 = 8
✎ 2 способ. При помощи формулы поиска числа сочетаний:
\[ C{\binom{k}{n}}= \frac{n!}{k!(n-k)!} \]
Число сочетаний из n элементов по k элементов:
\[ C{\binom{2}{5}}= \frac{5!}{2!(5-2)!} = \frac{120}{12} = 10 \]
* Факториал числа: n! = 1 * 2 * 3 * .. * n
8 * 10 = 80
Результат: 80
Детальный разбор задания 10 ЕГЭ по информатике предлагаем посмотреть в видеоуроке:
Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв ОСЕНЬ? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
Типовые задания для тренировки
✍ Решение:
- Из букв слова ОСЕНЬ имеем 2 гласных буквы (О, Е) и 2 согласных буквы (С, Н). Буква мягкий знак «нейтральна».
- Подсчитаем количество букв на каждой из 5 позиций:
2 5 5 5 2 СН все все все ОЕ
N = n1 * n2 * n3 * … * nL = nL
N = 2 * 5 * 5 * 5 * 2 = 500
Результат: 500
Разбор можно также посмотреть на видео:
Вася составляет 4-буквенные слова, в которых есть только буквы Л, Е, Т, О, причём буква Е используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.
Сколько существует таких слов, которые может написать Вася?
Типовые задания для тренировки
✍ Решение:
-
✎ 1 способ:
- Количество вариантов различных слов вычислим по формуле:
- n1 — количество вариантов выбора первой буквы и т.п.
- Рассмотрим все варианты расположения буквы Е:
N = n1 * n2 * n3 * …
где
1. Е ? ? ? или 2. ? Е ? ? или 3. ? ? Е ? или 4. ? ? ? Е Где вопросительный знак означает любую букву из Л, Е, Т, О.
Е ? ? ? = 1 * 4 * 4 * 4 = 64 т.е. на первой позиции - только 1 буква - Е, на каждой последующей - одна из четырех букв Л, Е, Т, О.
? Е ? ? = 3 * 1 * 4 * 4 = 48
? ? Е ? = 3 * 3 * 1 * 4 = 36
? ? ? Е = 3 * 3 * 3 * 1 = 27
64 + 48 + 36 + 27 = 175
Результат: 175
✎ 2 способ:
- Так как по условию буква Е встретится хотя бы 1 раз, значит, можно утверждать, что не может быть такого, чтобы буква Е не встретилась бы ни одного раза.
- Таким образом, рассчитаем случай, когда буква Е встречается все 4 раза (т.е. все случаи) и отнимем от результата невозможный случай: когда буква Е не встретится ни одного раза:
1. Буква Е используется 4 раза (т.е. на всех позициях): 4 * 4 * 4 * 4 = 256 2. Буква Е не используется совсем (т.е. только 3 буквы): 3 * 3 * 3 * 3 = 81
256 - 81 = 175
Результат: 175
Решение задания 10 смотрите в видеоуроке:
Вася составляет 4-буквенные слова, в которых есть только буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.
Сколько существует таких слов, которые может написать Вася?
Типовые задания для тренировки
✍ Решение:
- Количество возможных вариантов слов вычислим по формуле:
- где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
- Сначала по формуле получим все варианты для всех пяти букв, включая букву Р:
N = n1 * n2 * n3 * … * nL = nL
5 * 5 * 5 * 5 = 54 = 625
4 * 4 * 4 * 4 = 44 = 256
р ? ? ? = 1 * 4 * 4 * 4 = 43 ? р ? ? = 4 * 1 * 4 * 4 = 43 ? ? р ? = 4 * 4 * 1 * 4 = 43 ? ? ? р = 4 * 4 * 4 * 1 = 43 Получим 43 * 4 = 256
625 - 256 - 256 = 113
Результат: 113
Решение 10 задания предлагаем посмотреть в видеоуроке:
Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег использует 5-буквенные слова, в которых есть только буквы A, Б, В, и Г, причём буква Г появляется не более одного раза и только на последнем месте. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем.
Сколько различных кодовых слов может использовать Олег?
✍ Решение:
- Вспомним формулу получения количества возможных вариантов слов:
- где n1 — количество вариантов выбора первой буквы,
- n2 — количество вариантов выбора второй буквы и т.п.
- Так как буква Г появляется не более одного раза и только на последнем месте, значит, она может либо появиться 1 раз на последнем месте, либо не появиться совсем.
- Рассмотрим варианты, когда буква Г встречается 1 раз на последнем месте и встречается 0 раз:
N = n1 * n2 * n3 * … * nL = nL
1 раз: ? ? ? ? Г = 3 * 3 * 3 * 3 * 1 = 34 = 81 0 раз: ? ? ? ? ? = 3 * 3 * 3 * 3 * 3 = 35 = 243
81 + 243 = 324
Результат: 324
Вася составляет 4-буквенные слова, в которых есть только буквы К, О, М, А, Р, причём буква А используется в них не более 3-х раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.
Сколько существует таких слов, которые может написать Вася?
Типовые задачи для тренировки
✍ Решение:
- Вспомним формулу получения количества возможных вариантов слов:
- где n1 — количество вариантов выбора первой буквы,
- n2 — количество вариантов выбора второй буквы и т.п.
- Так как буква А по условию используется не более 3-х раз, это значит, что она используется либо 3 раза, либо 2 раза, либо 1 раз, либо не используется совсем. Рассмотрим все эти варианты отдельно.
- 1. Буква А используется 3 раза:
N = n1 * n2 * n3 * … * nL = nL
А А А _ -> 1 * 1 * 1 * 4 = 4 А А _ А -> 1 * 1 * 4 * А = 4 А _ А А -> 1 * 4 * 1 * 1 = 4 _ А А А -> 4 * 1 * 1 * 1 = 4
_ может быть любая из 4 букв: К О М Р. Значит, имеем:4 * 4 = 16 вариантов
А А _ _ -> 1 * 1 * 4 * 4 = 16 А _ А _ -> 1 * 4 * 1 * 4 = 16 А _ _ А -> 1 * 4 * 4 * 1 = 16 _ А А _ -> 4 * 1 * 1 * 4 = 16 _ А _ А -> 4 * 1 * 4 * 1 = 16 _ _ А А -> 4 * 4 * 1 * 1 = 16
_ может быть любая из 4 букв: К О М Р. Значит имеем:16 * 6 = 96 вариантов
А _ _ _ -> 1 * 4 * 4 * 4 = 64 _ А _ _ -> = 64 _ _ А _ -> = 64 _ _ _ А -> = 64
64 * 4 = 256 вариантов
_ _ _ _ -> 44 = 256
16 + 96 + 256 + 256 = 624
Результат: 624
Решение смотрите также на видео:
Сколько существует различных символьных последовательностей длины 3 в четырёхбуквенном алфавите {A,B,C,D}, если известно, что одним из соседей A обязательно является D, а буквы B и C никогда не соседствуют друг с другом?
✍ Решение:
- Вспомним формулу получения количества возможных вариантов слов:
- где n1 — количество вариантов выбора первой буквы,
- n2 — количество вариантов выбора второй буквы и т.п.
- Будем рассматривать варианты, расставляя каждую букву последовательно по алфавиту, начиная с первой буквы. При этом будем учитывать указанные ограничения для букв А, B и С:
N = n1 * n2 * n3 * … * nL = nL
Начинаем с A: A D 4ABCD = 1 * 1 * 4 = 4 Начинаем с B: B A D, B B 2BD, B D 4ABCD = 7 Начинаем с C: C A D, C C 2CD, C D 4ABCD = 7 Начинаем с D: D A 3BCD, D B 2BD, D C 2CD, D D 4ABCD = 11
4 + 7 + 7 + 11 = 29
Результат: 29
Видеоурок демонстрирует подробное решение задания:
Из букв С, Р, Е, Д, А составляются трехбуквенные комбинации по следующему правилу – в комбинации не может быть подряд идущих гласных и одинаковых букв.
Сколько всего комбинаций можно составить, используя это правило?
✍ Решение:
- Рассмотрим два варианта: когда слово начинается с гласной буквы, и когда оно начинается с согласной.
1. С гласной:
1.1 2 3 2 = 2 * 3 * 2 = 12 гл с с 1.2 2 3 2 = 2 * 3 * 2 = 12 гл с гл
2. С согласной:
2.1 3 2 2 = 3 * 2 * 2 = 12 с с с 2.2 3 2 3 = 3 * 2 * 3 = 18 с гл с 2.3 3 2 2 = 3 * 2 * 2 = 12 с с гл
12 + 12 + 12 + 18 + 12 = 66
Результат: 66
Дано слово КОРАБЛИКИ. Таня решила составлять новые 5-буквенные слова из букв этого слова по следующим правилам:
1) слово начинается с гласной буквы;
2) гласные и согласные буквы в слове должны чередоваться;
3) буквы в слове не должны повторяться.
Сколько существует таких слов?
Типовые задачи для тренировки
✍ Решение:
- Учтем, что в слове КОРАБЛИКИ две буквы К и две И.
- Всего в слове 4 гласных, но поскольку две буквы И, то необходимо считать только 3 гласных.
- Всего в слове 5 согласных, однако две из них — буквы К, поэтому считать следует 4 согласных.
- Посчитаем количество согласных и гласных для каждой из 5 позиций слова, учитывая, что с каждой последующей буквой количество используемых гласных/согласных уменьшается. Под позициями приведем пример букв:
гл с гл с гл 3 4 2 3 1 оаи крбл оа крб и
3 * 4 * 2 * 3 * 1 = 72
Результат: 72
Список в алфавитном порядке
Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Ниже приведено начало списка:
1. ААААА
2. ААААО
3. ААААУ
4. АААОА
…
Запишите слово, которое стоит под номером 242 от начала списка.
✍ Решение:
- Данное задание лучше решать следующим образом. Подставим вместо букв цифры (А -> 0, О -> 1, У -> 2):
1. 00000 2. 00001 3. 00002 4. 00010 ...
остатки
241 | 3 | 1
80 | 3 | 2
26 | 3 | 2
8 | 3 | 2
2 | |
Результат: УУУУО
Подробное решение смотрите на видео:
Все 4-буквенные слова, составленные из букв Д, Е, К, О, Р, записаны в алфавитном порядке и пронумерованы, начиная с 1.
Ниже приведено начало списка.
1. ДДДД 2. ДДДЕ 3. ДДДК 4. ДДДО 5. ДДДР 6. ДДЕД …
Под каким номером в списке идёт первое слово, которое начинается с буквы K?
✍ Решение:
- Подставим вместо букв цифры (Д -> 0, Е -> 1, К -> 2, О -> 3, Р -> 4):
1. 0000 2. 0001 3. 0002 4. 0003 5. 0004 6. 0010 ...
K -> 2 -> 2000
По формуле разложения числа по степеням основания: 20005 = 2 * 53 + 0 * 22 + 0 + 0 = 2 * 125 = 25010
Результат: 251
Подробное решение 10 задания демоверсии ЕГЭ 2018 года смотрите на видео:
Все 4-буквенные слова, составленные из букв П, Р, С, Т, записаны в алфавитном порядке.
Вот начало списка:
1. ПППП 2. ПППР 3. ПППС 4. ПППТ 5. ППРП ... ...
На каком месте в списке стоит первое слово, начинающееся с буквы Р?
Типовые задачи для тренировки
✍ Решение:
Видеоразбор задания смотрите ниже:
Все четырёхбуквенные слова, составленные из букв В, Е, Г, А, Н записаны в алфавитном порядке и пронумерованы, начиная с 1. Начало списка выглядит так:
1. АААА 2. АААВ 3. АААГ 4. АААЕ 5. АААН 6. ААВА …
Под каким номером в списке идёт первое слово, в котором нет буквы А?
✍ Решение:
- Пронумерованный список начинается со всех букв А. Представим, что А — 0, В — 1, Г — 2, Е — 3, Н — 4. Получим следующий список:
1. 0000 2. 0001 3. 0002 4. 0003 5. 0004 6. 0010
11115 = 1 * 53 + 1 * 52 + 1 * 51 + 1 * 50 = 156
156 + 1 = 157
Результат: 157
Видеорешение задания:
Вероятность событий
За четверть Василий Пупкин получил 20 оценок. Сообщение о том, что он вчера получил четверку, несет 2 бита информации.
Сколько четверок получил Василий за четверть?
✍ Решение:
- Для решения данного задания необходимо вспомнить две формулы:
1. Формула Шеннона:
x - количество информации в сообщении о событии p - вероятность события
2. Формула вероятности случайного события:
m - число случаев, способствующих событию А n - общее число равновозможных случаев
2 = log2(1/p);
=>
1/p = 4;
=>
p = 1/4
p = ?/20
1/4 = ?/20
? = 1/4 * 20 = 5
Результат: 5
Видеоразбор задания:
