Погода
Календарь
Май 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 12345
6789101112
13141516171819
20212223242526
2728293031  
Страницы сайта

Перебор слов и системы счисления.

ИЗМЕРЕНИЕ КОЛИЧЕСТВА ИНФОРМАЦИИ

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

Единицы измерения:
1 байт (bytе) = 8 бит
1 Кб (килобайт) = 1024 байта
1 Мб (мегабайт) = 1024 Кб
1 Гб (гигабайт) = 1024 Мб
1 Тб (терабайт) = 1024 Гб
1 Пб (петабайт) = 1024 Тб

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

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

ДВОИЧНОЕ КОДИРОВАНИЕ СООБЩЕНИЙ (РАВНОВЕРОЯТНОСТНЫЕ СОБЫТИЯ)

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

N — количество сообщений L — длиной битов

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

двоичное кодирование

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

Количество сообщений длиной L битов: N = 2L

Количество сообщений длиной 2 бита, как в примере с нашими буквами, будет равно  N = 22 = 4

Ответ: 4

КОЛИЧЕСТВО РАЗЛИЧНЫХ СООБЩЕНИЙ В АЛФАВИТЕ РАЗНОЙ МОЩНОСТИ

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

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

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

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

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

При определении количества информации для равновероятностных событий могут понадобиться две формулы: Формула Шеннона: x = log2(1/p) x — количество информации в сообщении о событии p — ве­ро­ят­ность со­бы­тия Формула вероятности случайного события: p(A) = m / n — количество благоприятных исходов (число случаев, способствующих событию А) n — количество общих исходов (общее число равновозможных случаев)

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

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

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

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

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

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

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

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

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

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

N — мощность алфавита

L — длина сообщения

Задание 1.  Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке.

Вот начало списка:

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

Запишите слово, которое стоит на 240-м месте от начала списка.

 Решение (1 способ, перебор с конца):

  1. подсчитаем, сколько всего 5-буквенных слов можно составить из трех букв;
  2. очевидно, что есть всего 3 однобуквенных слова (А, О, У); двух буквенных слов уже 3´3=9 (АА, АО, АУ, ОА, ОО, ОУ, УА, УО и УУ)
  3. аналогично можно показать, что есть всего 35 = 243 слова из 5 букв
  4. очевидно, что последнее, 243-е слово – это УУУУУ
  5. далее идём назад: предпоследнее слово УУУУО (242-е), затем идет УУУУА (241-е) и, наконец, УУУОУ (240-е).  Ответ:  УУУОУ.

Решение  2:

  1. по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию)
  2. выпишем начало списка, заменив буквы на цифры:

1. 00000

2. 00001

3. 00002

4. 00010

……

  • это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д.
  • тогда легко понять, что на 240-м месте стоит число 239, записанное в троичной системе счисления
  • переведем 239 в троичную систему: 239 = 222123
  • заменяем обратно цифры на буквы: 22212 ® УУУОУ

         Ответ:  УУУОУ.

Задание 2.  Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке.

Вот начало списка:     

1. ААААА

2. ААААК

3. ААААЛ

4. ААААО

5. ААААШ

6. АААКА

……

На каком месте от начала списка стоит слово ШКОЛА?

 Решение:

  1. по аналогии с предыдущим решением будем использовать пятеричную систему счисления с заменой А на 0, К на 1, Л на 2, О на 3 и Ш на 4
  2. слово ШКОЛА запишется в новом коде так: 413205
  3. переводим это число в десятичную систему:

413205 = 4×54 + 1×53 + 3×52 + 2×51 = 2710

  • поскольку нумерация элементов списка начинается с 1, а числа в пятеричной системе – с нуля, к полученному результату нужно прибавить 1, тогда… Ответ:  2711.

Задание 3.  Вася составляет 3-буквенные слова, в которых есть только буквы В, Е, С, Н , А, причём буква А используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Решение (способ 1):

  1. буква А может стоять на одном из трёх мест: А**, *А*, **А, где * обозначает любой из пяти символов
  2. в каждом случае в остальных двух позициях может быть любая из пяти букв
  3. для шаблона А** получаем  (перемножая количество вариантов для каждой позиции)

1 · 5 · 5 = 25 слов

  • для шаблона *А* тоже получим 25 слов, но нужно учесть, что все слова, в который первая буква А мы уже подсчитали, поэтому считаем только слова, где на первом место стоит какая-то другая буква (В, Е, С или Н)
  • отсюда находим, что шаблон *А* добавляет 4 · 1 · 5 = 20 новых слов
  • рассматривая шаблон **А, не учитываем уже подсчитанные слова, в которых буква А  есть на первом или втором местах, количество новых слов – 4 · 4 · 1 = 16
  • всего получается 25 + 20 + 16 = 61 слово. Ответ: 61.

Решение (способ 2):

  1. количество слов с буквой А можно вычислить как разность между количеством всех возможных слов и количеством слов, в которых нет буквы А
  2. количество всех слов 5 · 5 · 5 = 53 = 125 (на любой из 3-х позиций может стоять любая из 5 букв)
  3. количество слов, в которых нет буквы А равно 4 · 4 · 4 = 43 = 64 (на любой из 3-х позиций может стоять любая из 4 букв, кроме А)
  4. получается 125 – 64 = 61 слово, в котором есть буква А (она или несколько). Ответ: 61.

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

Решение 1:

  1. первая буква слова может быть выбрана двумя способами (Е или Э), остальные – тремя
  2. общее число различных слов равно 2*3*3*3*3 = 162.

Ответ: 162.

Решение 2:

  1. Дано слово длиной 5 символов типа *****,  где красная звездочка – гласная буква (Е или Э), а черная буква любая из трёх заданных.
  2. Общая формула количества вариантов:

N = M L, где М – мощность алфавита, а L – длина кода.

  • Так как положение одной из букв строго регламентировано (знак умножения в зависимых событиях), то формула всех вариантов примет вид:  N = M1L1 ∙ M2L2,
  • Тогда M1 = 2 (алфавит гласных букв), а  L1 = 1 (только 1 позиция в слове). 

            M2 = 3 (алфавит всех букв), а  L2 = 4 (оставшиеся 4 позиции в слове).

  • В итоге получаем: N = 21 ∙ 34 = 2 ∙ 81 = 162.

Ответ: 162.

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

Решение:

Мы имеем ал­фа­вит из двух букв: точка и тире. Из двух букв можно со­ста­вить 24 четырёхбук­вен­ных слова и 25 пя­ти­бук­вен­ных слов.

Со­от­вет­ствен­но, ко­ли­че­ство за­ко­ди­ро­ван­ных сим­во­лов будет равно ко­ли­че­ству раз­лич­ных слов, а их 16 + 32 = 48.

Ответ: 48

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

Решение:

На пер­вой по­зи­ции в слове могут быть все че­ты­ре буквы А, В, С и Х, а со вто­рой по пятую — 3. Зна­чит всего можно со­ста­вить 4 · 3 · 3 · 3 · 3 = 324 слова.

 Ответ: 324.

Задание 7. (Демонстрационный вариант ЕГЭ по информатике 2018 года). Все 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

  • Получили список из чисел, записанных в пятиричной системе счисления (всего 5 цифр используется во всем списке)
  • Первое слово, которое начинается с буквы «К» — это КДДД, ему соответствует число 20005
  • Переведем полученное число из 5-ной системы счисления в десятичную и мы получим на единицу меньше искомого номера (т.к. нумерация в списке начинается с 1, а счет в любой позиционной системе счисления — с 0!)

 20005 + 1 = 2*53 + 1 = 125 + 1 = 251

Ответ: 251

Top