Рассмотрим кратко необходимые для решения 10 задания ЕГЭ понятия и формулы.

Измерение количества информации

1 байт (bytе) = 8 бит
1 Кб (килобайт) = 1024 байта
1 Мб (мегабайт) = 1024 Кб
1 Гб (гигабайт) = 1024 Мб
1 Тб (терабайт) = 1024 Гб
1 Пб (петабайт) = 1024 Тб

1024=2¹⁰

Рассмотрим еще несколько определений:

• Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
• 1 бит – это количество информации, которое можно передать с помощью одного знака в двоичном коде (0 или 1).
• 

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

• Алфавит — это набор знаков, используемый в том или ином языке.
• Мощность алфавита — это количество используемых в алфавите знаков.
• Сообщение — это любая последовательность символов какого-либо алфавита

• Для вычисления количества информации применяются несколько различных формул в зависимости от ситуации:

  Двоичное кодирование сообщений (равновероятностные события)

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

  N = 2^I
  • N — количество сообщений
  • I — длиной битов

   
  * следует иметь в виду, что также приняты следующие обозначения: Q = 2^k

  Пример 2: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:
  

  
  Решение:

  Таким образом мы получили равномерный код, т.к. длина каждого кодового слова одинакова для всех кодов (2).

  А количество сообщений длиной I битов:

  N = 2^I

  Т.е. количество сообщений длиной 2 бита, как в примере с нашими буквами, будет равно Q = 2² = 4

  Количество различных сообщений в алфавите разной мощности

  Рассмотрим вариант с 5 буквами (мощность алфавита = 5), которые надо разместить в сообщении длиной 2 символа:

  

  Найдем формулу для нахождения количества различных сообщений в алфавите различной мощности:

  Если мощность некоторого алфавита составляет N, то количество различных сообщений длиной L знаков:
  

  • N – мощность алфавита
  • L – длина сообщения
  • Q – количество различных сообщений

  Пример: Сколько существует всевозможных трехбуквенных слов в английском языке?

  
  Решение:

  В английском алфавите 26 букв. Значит мощность алфавита = 26. Длина сообщения = 3. Найдем по формуле количество трехбуквенных слов:
  Q = 26³

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

  N = n1 * n2 * … * nL

  Количество сообщений при различном вхождении (встречаемости) букв

  Иногда в заданиях 10 приходится использовать формулу комбинаторики для проверки полученных результатов перебора. Число сочетаний из n элементов по k элементов:

  

  Число сочетаний из n элементов
  по k элементов

  • I – количество информации в битах
  • N – количество вариантов

   

  Пример: Сколько существует всевозможных пятибуквенных слов в алфавите из 4 букв: А, Б, В, Г, если известно, что буква А встречается ровно два раза?

  
  Решение:

  два раза буква А, на остальных местах - одна из трех оставшихся букв:
  А А 3 3 = 3 * 3 = 32 = 9
  А 3 А 3 
  А 3 3 А 
  3 А А 3 
  3 А 3 А 
  3 3 А А 
   
  

  Число сочетаний из n элементов по k элементов:
  C^k_n=n!/(n!*(n-k)!)

  C24 = 4!/(2!*(4-2)!) = 24/(2*2) = 6 вариантов 
  
  Факториал числа n! = 0*1*2*3..*n
  

  6 * 9 = 54

  • Длина сообщения = 4. Мощность алфавита = 4. Но мешает условие: буква А встречается ровно два раза.
  • В таких заданиях используется способ перебора всевозможных вариантов:
  • Получили 6 вариантов, каждый из которых равен 9.
  • Проверим формулой числа сочетаний:
  • Т.е. проверка прошла успешно, мы получили 6 вариантов.
  • Осталось посчитать количество всех сообщений:

  Дополнительные формулы

  Количество информации и равновероятные события

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

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

  x = log₂(1/p)

  • x — количество информации в сообщении о событии
  • p — ве­ро­ят­ность со­бы­тия

   

  • Формула вероятности случайного события:

  p(A) = m/n

  • m — кол-во благоприятных исходов (число случаев, способствующих событию А)
  • n — кол-во общих исходов (общее число равновозможных случаев)

   

  Количество информации и неравновероятные события

  При использовании неравновероятного события, вероятность которого равна p, для вычислениия количества информации используется формула:

  i = -[log₂p]

  *квадратные скобки означают ближайшее целое, меньшее или равное значению выражения в скобках

  Формула Хартли:

  

  Формула Хартли

  • I – количество информации в битах
  • N – количество вариантов

   

  Алфавитный подход:

  Информационный объем сообщения длиной L:

  

  Алфавитный подход

  • N — мощность алфавита
  • L — длина сообщения

  Примеры заданий:

  ЕГЭ по информатике 2017 задание 10 ФИПИ вариант 1 (Крылов С.С., Чуркина Т.Е.): Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 6. Сколько различных вариантов шифра можно задать, если известно, что цифра 1 должна встречаться в коде ровно 1 раз, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?

  Решение:

  Q=N^L

  Итак, что у нас дано из этой формулы:

  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
  

  625 * 5 = 3125
  

  • Формула количества различных сообщений:
  • Длина сообщения (L) = 5 символов
  • Начальная мощность алфавита (N) = 6 (цифры от 1 до 6). Но так как цифра 1 встречается ровно один раз, а остальные 5 цифр — любое количество раз, то будем считать, что N = 5 (цифры от 2 до 6)
  • Количество различных сообщений (вариантов шифра) = Q = ?
  • Согласно условию получим следующие варианты размещения (5 цифр размещаем на 4 позиции):
  • В итоге получим:

  Результат: 3125

  ЕГЭ по информатике 2017 задание 10 ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

  Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является одной из букв X, Y или Z. Сколько различных вариантов шифра можно задать, если известно, что буква X должна встречаться в коде ровно 2 раза, а каждая из других допустимых букв может встречаться в шифре любое количество раз или не встречаться совсем?

  
  Решение:  

  Q = N^L

  Итак, что у нас дано из этой формулы:

  Перебор всех вариантов:

  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
  

  Число сочетаний из n элементов по k элементов:
  C^k_n=n!/(n!*(n-k)!)

  C25 = 5!/(2!*(5-2)!) = 120/(12) = 10 вариантов 
  
  * Факториал числа: n! = 0*1*2*3..*n
  

  8 * 10 = 80
  

  • Формула количества различных сообщений:
  • Начальная мощность алфавита (N) = 3 (буквы X, Y, Z). Но так как буква X встречается ровно два раза, то мы ее рассмотрим отдельно, а остальные 2 буквы — любое количество раз, значит будем считать, что N = 3-1 = 2 (Y и Z)
  • Исходя из предыдущего пункта, длина сообщения тоже сократится: (L) = 5-2 = 3 символа (остальные два символа отведем на размещение X)
  • Количество различных сообщений (вариантов шифра) = Q = ?
  • Согласно условию получим следующие варианты размещения:
  • Проверим получившееся количество вариантов при помощи формулы поиска числа сочетаний.
  • Количество вариантов проверено (=10). В итоге получаем:

  Результат: 80

  ЕГЭ по информатике 2017 задание 10 ФИПИ вариант 10 (Крылов С.С., Чуркина Т.Е.):

  Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является либо буквой (A или B) или цифрой (1, 2 или 3). Сколько различных вариантов шифра можно задать, если известно, что в коде присутствует ровно одна буква, а все другие символы являются цифрами?

  
  Решение:

  Формула количества различных сообщений:

  Q = N^L

  Q = 2 * 34 = 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
  

  • Так как цифры (1, 2, 3) могут занимать 4 позиции из пяти, а две буквы (А и В) одну из позиций, значит:
  • Согласно условию получим следующие варианты размещения:
  • Получили по 5 вариантов с размещением букв А и B
  • Осталось умножить: 5*162 = 810

  Результат: 810