Как найти объем информации в битах - Сайт, где вы сможете решить свои вопросы

Мы ежедневно работаем с информацией из разных источников. При этом каждый из нас имеет некоторые интуитивные представления о том, что означает, что один источник является для нас более информативным, чем другой. Однако далеко не всегда понятно, как это правильно определить формально. Не всегда большое количество текста означает большое количество информации. Например, среди СМИ распространена практика, когда короткое сообщение из ленты информационного агентства переписывают в большую новость, но при этом не добавляют никакой «новой информации». Или другой пример: рассмотрим текстовый файл с романом Л.Н. Толстого «Война и мир» в кодировке UTF-8. Его размер — 3.2 Мб. Сколько информации содержится в этом файле? Изменится ли это количество, если файл перекодировать в другую кодировку? А если заархивировать? Сколько информации вы получите, если прочитаете этот файл? А если прочитаете его второй раз?

По мотивам открытой лекции для Computer Science центра рассказываю о том, как можно математически подойти к определению понятия “количество информации”.

В классической статье А.Н. Колмогорова “Три подхода к определению понятия количества информации” (1965) рассматривают три способа это сделать:

комбинаторный (информация по Хартли),
вероятностный (энтропия Шеннона),
алгоритмический (колмогоровская сложность).

Мы будем следовать этому плану.

Комбинаторный подход: информация по Хартли

Мы начнём самого простого и естественного подхода, предложенного Хартли в 1928 году.

Пусть задано некоторое конечное множество . Количеством информации в будем называть .

Можно интерпретировать это определение следующим образом: нам нужно chi(A) битов для описания элемента из .

Почему мы используем биты? Можно использовать и другие единицы измерения, например, триты или байты, но тогда нужно изменить основание логарифма на 3 или 256, соответственно. В дальшейшем все логарифмы будут по основанию 2.

Этого определения уже достаточно для того, чтобы измерить количество информации в некотором сообщении. Пусть про xin A стало известно, что xin B . Теперь нам достаточно битов для описания , таким образом нам сообщили битов информации.

Пример

Загадано целое число от до . Нам сообщили, что делится на . Сколько информации нам сообщили?

Воспользуемся рассуждением выше.

$log_2 1000 - log_2 166 = log_2 frac{1000}{166} approx 2.59 text{битов.}$

(Тот факт, что некоторое сообщение может содержать нецелое количество битов, может показаться немного неожиданным.)

Можно ещё сказать, что сообщение, уменшающее пространство поиска в alpha раз приносит битов информации. В данном примере пространство поиска уменьшилось в 1000/166 раз.

Интересно, что одного этого определения уже достаточно для того, чтобы решать довольно нетривиальные задачи.

Применение: цена информации

Загадано целое число от до . Разрешается задавать любые вопросы на ДА/НЕТ. Если ответ на вопрос “ДА”, то мы должны заплатить рубль, если ответ “НЕТ” — два рубля. Сколько нужно заплатить для отгадывания числа ?

Любой вопрос можно сформулировать как вопрос о принадлежности некоторому множеству, поэтому мы будем считать, что все вопросы имеют вид “ xin T ?” для некоторого множества .

Каким образом нужно задавать вопросы? Нам бы хотелось, чтобы вне зависимости от ответа цена за бит информации была постоянной. Другими словами, в случае ответа “НЕТ” и заплатив два рубля мы должны узнать в два больше информации, чем при ответе “ДА”. Давайте запишем это формально.

Потребуем, чтобы

Пусть , тогда . Подставляем и получаем, что

Это эквивалентно квадратному уравнению Положительный корень этого уравнения . Таким образом, при любом ответе мы заплатим рублей за бит информации, а в сумме мы заплатим примерно clog n рублей (с точностью до округления).

Осталось понять, как выбирать такие множества . Будем выбирать в качестве непрерывные отрезки прямой. Пусть нам известно, что принадлежит отрезку [a,b] (изначально это отрезок [1,n] ). В следующего множества возмём отрезок , где. Тогда за каждый заплаченный рубль текущий отрезок будет уменьшаться в раз. Когда длина отрезка станет меньше единицы, мы однозначно определим . Поэтому цена отгадывания не будет превосходить

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

Вероятностный подход: энтропия Шеннона

Вероятностный подход, предложенный Клодом Шенноном в 1948 году, обобщает определение Хартли на случай, когда не все элементы множества являются равнозначными. Вместо множества в этом подходе мы будем рассматривать вероятностное распределение на множестве и оценивать среднее по распределению количество информации, которое содержит случайная величина.

Пусть задана случайная величина , принимающая различных значений с вероятностями . Энтропия Шеннона случайной величины определяется как

$H(X) = sum_{i=1}^k p_icdotlogfrac1p_i.$

(По непрерывности тут нужно доопределить $0cdot logfrac10 = 0$ .)

Энтропия Шеннона оценивает среднее количество информации (математическое ожидание), которое содержится в значениях случайной величины.

При первом взгляде на это определение, может показаться совершенно непонятно откуда оно берётся. Шеннон подошёл к этой задаче чисто математически: сформулировал требования к функции и доказал, что это единственная функция, удовлетворяющая сформулированным требованиям.

Я попробую объяснить происхождение этой формулы как обобщение информации по Хартли. Нам бы хотелось, чтобы это определение согласовывалось с определением Хартли, т.е. должны выполняться следующие “граничные условия”:

Будем искать в виде математического ожидания количества информации, которую мы получаем от каждого возможного значения .

$H(X) = sum_i p_icdot text{(информация в событии $X=a_i$)}.$

Как оценить, сколько информации содержится в событии X = a_i ? Пусть — всё пространство элементарных исходов. Тогда событие X = a_i соответствует множеству элементарных исходов меры p_i . Если произошло событие X = a_i , то размер множества согласованных с этим событием элементарных исходов уменьшается с |U| до , т.е. событие X = a_i сообщает нам битов информации. Тут мы пользуемся тем, что количество информации в сообщении, которое уменьшает размер пространство поиска в 1/p_i раз приносит битов информации.

Примеры

Свойства энтропии Шеннона

Для случайной величины , принимающей значений с вероятностями , выполняются следующие соотношения.

.
распределение вырождено.
.
распределение равномерно.

Чем распределение ближе к равномерному, тем больше энтропия Шеннона.

Энтропия пары

Понятие энтропии Шеннона можно обобщить для пары случайных величин. Аналогично это обощается для тройки, четвёрки и т.д.

Пусть совместно распределённые случайные величины и принимают значения и , соответственно. Энтропия пары случайных величин и определяется следующим соотношением:

$H(X,Y) = sum_{i=1}^ksum_{j=1}^mPr[X = a_i, Y=b_j]cdot logfrac{1}{Pr[X = a_i, Y = b_j]}.$

Примеры

Рассмотрим эксперимент с выбрасыванием двух игральных кубиков — синего и красного.

Свойства энтропии Шеннона пары случайных величин

Для энтропии пары выполняются следующие свойства.

Условная энтропия Шеннона

Теперь давайте научимся вычислять условную энтропию одной случайной величины относительно другой.

Условная энтропия относительно определяется следующим соотношением:

Примеры

Рассмотрим снова примеры про два игральных кубика.

Свойства условной энтропии

Условная энтропия обладает следующими свойствами

Взаимная информация

Ещё одна информационная величина, которую мы введём в этом разделе — это взаимная информация двух случайных величин.

Информация в о величине (взаимная информация случайных величин и ) определяется следующим соотношением

Примеры

И снова обратимся к примерам с двумя игральными кубиками.

Свойства взаимной информации

Выполняются следующие соотношения.

. Т.е. определение взаимной информации симметрично и его можно переписать так:

Или так: .
и .
.
.

Все информационные величины, которые мы определили к этому моменту можно проиллюстрировать при помощи кругов Эйлера.

Мы пойдём дальше и рассмотрим информационную величину, зависящую от трёх случайных величин.

Пусть , и совместно распределены. Информация в о при условии определяется следующим соотношением:

Свойства такие же как и обычной взаимной информации, нужно только добавить соответствующее условие ко всем членам.

Всё, что мы успели определить можно удобно проиллюстрировать при помощи трёх кругов Эйлера.

Из этой иллюстрации можно вывести все определения и соотношения на информационные величины.

Мы не будем продолжать дальше и рассматривать четыре случайные величины по трём причинам. Во-первых, рисовать четыре круга Эйлера со всеми возможными областями — это непросто. Во-вторых, для двух и трёх случайных величин почти все возможные соотношения можно вывести из кругов Эйлера, а для четырёх случайных величин это уже не так. И в третьих, уже для трёх случайных величин возникают неприятные эффекты, демонстрирующие, что дальше будет хуже.

Рассмотрим треугольник в пересечении всех трёх кругов H(X) , H(Y) и H(Z) . Этот треугольник соответствуют взаимной информации трёх случайных величин . Проблема с этой информационной величиной заключается в том, что ей не удаётся придать какой-то “физический” смысл. Более того, в отличие от всех остальных величин на картинке может быть отрицательной!

Рассмотрим пример трёх случайных величин равномерно распределённых на {0,1} . Пусть и будут независимы, а . Легко проверить, что . При этом . В то же время . Получается следующая картинка.

Мы знаем, что . При этом . Получается, что a=b=c=1 , а d=-1 , т.е. для таких случайных величин.

Применение энтропии Шеннона: кодирование

В этом разделе мы обсудим, как энтропия Шеннона возникает в теории кодирования. Будем рассматривать коды, которые кодируют каждый символ по отдельности.

Пусть задан алфавит Sigma . Код — это отображение из Sigma в ${0,1}^*$ . Код называется однозначно декодируемым, если любое сообщение, полученное применением к символам некоторого текста, декодируется однозначно.

Код называется префиксным (prefix-free), если нет двух символов alpha и beta таких, что является префиксом C(beta) .

Префиксные коды являются однозначно декодируемыми. Действительно, при декодировании префиксного кода легко понять, где находятся границы кодов отдельных символов.

Теорема [Шеннон]. Для любого однозначно декодируемого кода существует префиксный код с теми же длинами кодов символов.

Таким образом для изучения однозначно декодируемых кодов достаточно рассматривать только префиксные коды.

Задача об оптимальном кодировании.
Дан текст . Нужно найти такой код , что

$sum_{i=1}^n |C(a_i)| to min.$

Пусть $Sigma = {alpha_1,alpha_2,dotsc,alpha_k}$ . Обозначим через f_i частоту, с которой символ alpha_i встречается в . Тогда выражение выше можно переписать как

$nsum_{i=1}^k f_icdot |C(alpha_i)| to min.$

Следующая теорема могла встречаться вам в курсе алгоритмов.

Теорема [Хаффман]. Код Хаффмана, построенный по , является оптимальным префиксным кодом.

Алгоритм Хаффмана по набору частот эффективно строит оптимальный код для задачи оптимального кодирования.

Связь с энтропией

Имеют место две следующие оценки.

Теорема [Шеннон]. Для любого однозначно декодируемого кода выполняется

$sum_{i=1}^k f_icdot|C(alpha_i)|ge sum_{i=1}^n f_icdot logfrac1{f_i}.$

Теорема [Шеннон]. Для любых значений ${f_1,f_2,dotsc,f_k}$ существует префиксный код , такой что

$sum_{i=1}^n f_icdot|C(alpha_i)|le sum_{i=1}^n f_icdot logfrac1{f_i} + 1.$

Рассмотрим случайную величину , равномерно распределённую на символах текста . Получим, что $H(X) = f_icdot logfrac1{f_i}$ . Таким образом, эти две теоремы задают оценку на среднюю длину кода символа при оптимальном кодировании, т.е. и для кодирования Хаффмана.

$H(X) le sum_{i=1}^n f_icdot|C(alpha_i)|le H(X) + 1.$

Следовательно, длину кода Хаффмана текста можно оценить, как

Применение энтропии Шеннона: шифрования с закрытым ключом

Рассмотрим простейшую схему шифрования с закрытым ключом. Шифрование сообщения с ключом шифрования выполняется при помощи алгоритма шифрования . В результате получается шифрограмма . Зная получатель шифрограммы восстанавливает исходное сообщение : .

Мы будем анализировать эту схему с помощью аппарата энтропии Шеннона. Пусть и являются случайными величинами. Противник не знает и , но знает , которая так же является случайной величиной.

Для совершенной схемы шифрования (perfect secrecy) выполняются следующие соотношения:

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

Теорема [Шеннон]. , даже если условие нарушается (т.е. алгоритм использует случайные биты).

Эта теорема утверждает, что для совершенной схемы шифрования длина ключа должна быть не менее длины сообщения. Другими словами, если вы хотите зашифровать и передать своему знакомому файл размера 1Гб, то для этого вы заранее должны встретиться и обменяться закрытым ключом размера не менее 1Гб. И конечно, этот ключ можно использовать только однажды. Таким образом, самая оптимальная совершенная схема шифрования — это “одноразовый блокнот”, в котором длина ключа совпадает с длиной сообщения.

Если же вы используете ключ, который короче пересылаемого сообщения, то шифрограмма раскрывает некоторую информацию о зашифрованном сообщении. Причём количество этой информации можно оценить, как разницу между энтропией сообщения и энтропией ключа. Если вы используете пароль из 10 символов при пересылке файла размера 1Гб, то вы разглашаете примерно 1Гб – 10 байт.

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

Современная криптография строится на предположении об ограниченности вычислительных возможностей противника. Тут есть свои проблемы, а именно отсутствие математического доказательства криптографической стойкости (все доказательства строятся на различных предположениях), так что может оказаться, что вся эта криптография бесполезна (подробнее можно почитать в статье о мирах Рассела Импальяццо, которая переведена на хабре), но это уже совсем другая история.

Доказательство. Нарисуем картинку для трёх случайных величин и отметим то, что нам известно.

.
, следовательно , а значит .
(по свойству взаимной информации), следовательно , а значит .
. Таким образом,

В доказательстве мы действительно не воспользовались тем, что .

Алгоритмический подход: колмогоровская сложность

Подход Шеннона хорош для случайных величин, но если мы попробуем применить его к текстам, то выходит, что количество информации в тексте зависит только от частот символов, но не зависит от их порядка. При таком подходе получается, что в “Войне и мире” и в тексте, который получается сортировкой всех знаков в “Войне и мире”, содержится одинаковое количество информации. Колмогоров предложил подход, позволяющий измерять количество информации в конкретных объектах (строках), а не в случайных величинах.

Внимание. До этого момента я старался следить за математической строгостью формулировок. Для того, чтобы двигаться дальше в том же ключе, мне потребовалось бы предположить, что читатель неплохо знаком с математической логикой и теорией вычислимости. Я пойду более простым путём и просто буду махать руками, заметая под ковёр некоторые подробности. Однако, все утверждения и рассуждения дальше можно математически строго сформулировать и доказать.

Нам потребуется зафиксировать способ описания битовой строки. Чтобы не углубляться в рассуждения про машины Тьюринга, мы будем описывать строки на языках программирования. Нужно только сделать оговорку, что программы на этих языках будут запускаться на компьютере с неограниченным объёмом оперативной памяти (иначе мы получили бы более слабую вычислительную модель, чем машина Тьюринга).

Сложностью K_F(x) строки относительно языка программирования называется длина кратчайшей программы, которая выводит .

Таким образом сложность “Войны и мира” относительноя языка Python — это длина кратчайшей программы на Python, которая печатает текст “Войны и мира”. Естественным образом сложность отсортированной версии “Войны и мира” относительно языка Python получится значительно меньше, т.к. её можно предварительно закодировать при помощи RLE.

Сравнение языков программирования

Дальше нам потребуется научиться любимой забаве всех программистов — сравнению языков программирования.

Будем говорить, что язык не хуже языка программирования и обозначать Fprec G , если существует константа c_G такая, что для для всех $xin{0,1}^*$ выполняется

Исходя из этого определения получается, что язык Python не хуже (!) этого вашего Haskell! И я это докажу. В качестве константы $c_text{Haskell}$ мы возьмём длину реализации интепретатора Haskell на Python. Таким образом, любая программа на Haskell переделывается в программу на Python просто дописыванием к ней интерпретатора Haskell на Python.

Соломонов и Колмогоров пошли дальше и доказали существования оптимального языка программирования.

Теорема [Соломонова-Колмогорова]. Существует способ описания (язык программирования) такой, что для любого другого способа описания выполняется Uprec F .

И да, некоторые уже наверное догадались, что — это JavaScript. Или любой другой Тьюринг полный язык программирования.

Это приводит нас к следующему определению, предложенному Колмогоровым в 1965 году.

Колмогоровской сложностью строки будем называть её сложность относительно оптимального способа описания и будем обозначать .

Важно понимать, что при разных выборах оптимального языка программирования колмогоровская сложность будет отличаться, но только на константу. Для любых двух оптимальных языков программирования F_1 и F_2 выполняется и , т.е. существует такая константа , что $|K_{F_1} - K_{F_2}| le c.$ Это объясняет, почему в этой науке аддитивные константы принято игнорировать.

При этом для конкретной строки и конкретного выбора колмогоровская сложность определена однозначно.

Свойства колмогоровской сложности

Начнём с простых свойств. Колмогоровская сложность обладает следующими свойствами.

Первое свойство выполняется потому, что мы всегда можем зашить строку в саму программу. Второе свойство верно, т.к. из программы, выводящей строку , легко сделать программу, которая выводит эту строку дважды.

Примеры

Несжимаемые строки

Важнейшее свойство колмогоровской сложности заключается в существовании сложных (несжимаемых строк). Проверьте себя и попробуйте объяснить, почему не бывает идеальных архиваторов, которые умели бы сжимать любые файлы хотя бы на 1 байт, и при этом позволяли бы однозначно разархивировать результат.

В терминах колмогоровской сложности это можно сформулировать так.

Вопрос. Существует ли такая длина строки , что для любой строки $xin{0,1}^n$ колмогоровская сложность меньше ?

Следующая теорема даёт отрицательный ответ на этот вопрос.

Теорема. Для любого существует $xin{0,1}^n$ такой, что .

Доказательство. Битовых строк длины всего 2^n . Число строк сложности меньше не превосходит число программ длины меньше , т.е. таких программ не больше чем

$1+2+dotsb +2^{n-1} = 2^n - 1 < 2^n.$

Таким образом, для какой-то строки гарантированно не хватит программы.

Верна и более сильная теорема.

Теорема. Существует c > 0 такое, что для 99% слов длины верно

Другими словами, почти все строки длины имеют почти максимальную сложность.

Колмогоровская сложность: вычислимость

В этом разделе мы поговорим про вычислимость колмогоровской сложности. Я не буду давать формально определение вычислимости, а буду опираться на интуитивные предствления читателей.

Теорема. Не существует программы, которая по двоичной записи числа выводит строку , такую что .

Эта теорема говорит о том, что не существует программы-генератора, которая умела бы генерировать сложные строки по запросу.

Доказательство. Проведём доказетельство от противного. Пусть такая программа существует и . Тогда с одной стороны сложность не меньше , а с другой стороны мы можем описать при помощи log n битов и кода программы.

Это приводит нас к противоречию, т.к. при достаточно больших значениях неизбежно станет больше, чем .

Как следствие мы получаем невычислимость колмогоровской сложности.

Следствие. Отображение не является вычислимым.

Опять же, предположим, что это нет так и существует программа , которая по строку вычисляет её колмогоровскую сложность. Тогда на основе программы можно реализовать программу из теоремы выше: она будет перебирать все строки длины не более и находить лексикографически первую, для которой сложность будет не меньше . А мы уже доказали, что такой программы не существует.

Связь с энтропией Шеннона

Теорема. Пусть длины содержит pcdot n единиц и нулей, тогда

$K(x)le left(pcdotlogfrac1p + (1-p)cdotlogfrac{1}{1-p}right)cdot n + O(log n).$

Я надеюсь, что вы уже узнали энтропию Шеннона для случайной величины с двумя значениями с вероятностями и 1-p .

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

Применение колмогоровской сложности: бесконечность множества простых чисел

Начнём с довольно игрушечного применения. С помощью колмогоровской сложности мы докажем следующую теорему, знакомую нам со школы.

Теорема. Простых чисел бесконечно много.

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

Доказательство. Проведём доказательство от обратного. Пусть существует всего простых чисел: . Тогда любое натуральное раскладывается на степени простых:

$x = p_1^{k_1}cdot p_2^{k_2}cdotdotsmcdot p_m^{k_m},$

т.е. определяется набором степеней . Каждое , т.е. задаётся битами. Поэтому любое можно задать при помощи битов (помним, что — это константа).

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

Противоречие.

Применение колмогоровской сложности: алгоритмическая случайность

Колмогоровская сложность позволяет решить следующую проблему из классической теории вероятностей.

Пусть в лаборатории живёт обезьянка, которую научили печатать на печатной машинке так, что каждую кнопку она нажимает с одинаковой вероятность. Вам предлагается посмотреть на лист печатного текста и сказать, верите ли вы, что его напечатала эта обезьянка. Вы смотрите на лист и видите, что это первая страница “Гамлета” Шекспира. Поверите ли вы? Очевидно, что нет. Хорошо, а если это не Шекспир, а, скажем, текст детектива Дарьи Донцовой? Скорей всего тоже не поверите. А если просто какой-то набор русских слов? Опять же, очень сомневаюсь, что вы поверите.

Внимание, вопрос. А как объяснить, почему вы не верите? Давайте для простоты считать, что на странице помещается 2000 знаков и всего на машинке есть 80 знаков. Вы можете резонно заметить, что вероятность того, что обезьянка случайным образом породила текст “Гамлета” порядка $1/80^{2000}$ , что астрономически мало. Это верно.

Теперь предположим, что вам показали текст, который вас устроил (он с вашей точки зрения будет похож на “случайный”). Но ведь вероятность его появления тоже будет порядка $1/80^{2000}$ . Как же вы определяете, что один текст выглядит “случайным”, а другой — не выглядит?

Колмогоровская сложность позволяет дать формальный ответ на этот вопрос. Если у текста отстутствует короткое описание (т.е. в нём нет каких-то закономерностей, которые можно было бы использовать для сжатия), то такую строку можно назвать случайной. И как мы увидели выше почти все строки имеют большую колмогоровскую сложность. Поэтому, когда вы видите строку с закономерностями, т.е. маленькой колмогоровской сложности, то это соответствует очень редкому событию. В противоположность наблюдению строки без закономерностей. Вероятность увидеть строку без закономерностей близка к 1.

Это обобщается на случай бесконечных последовательностей. Пусть . Как определить понятие случайной последовательности?

(неформальное определение)
Последовательность случайна по Мартину–Лёфу, если каждый её префикс является несжимаемым.

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

Свойства случайных последовательностей

Почти все последовательности являются случайными по Мартину–Лёфу, а мера неслучайных равна .
Всякая случайная по Мартину-Лёфу последовательность невычислима.
Если случайная по Мартин-Лёфу, то

$lim_{ntoinfty} frac{text{число единиц в префиксе длины n}}{n} = frac12.$

Заключение

Если вам интересно изучить эту тему подробнее, то я рекомендую обратиться к следующим источникам.

Верещагин Н.К., Щепин Е.В. Информация, кодирование и предсказание. МЦНМО. (нет в свободном доступе, но pdf продаётся за копейки)
В.А. Успенский, А.Х. Шень, Н.К. Верещагин. Колмогоровская сложность и алгоритмическая случайность.
Курс “Введение в теорию информации” А.Е. Ромащенко в Computer Science клубе.

Если вам интересны подобные материалы, подписывайтесь в соцсетях на CS клуб и CS центр, а так же на наши каналы на youtube: CS клуб, CS центр.

Источник

Все мы привыкли к тому, что все вокруг можно измерить. Мы можем определить массу посылки, длину стола, скорость движения автомобиля. Но как определить количество информации, содержащееся в сообщении? Ответ на вопрос в статье.

Итак, давайте для начала выберем сообщение. Пусть это будет «Принтер — устройство вывода информации.«. Наша задача — определить, сколько информации содержится в данном сообщении. Иными словами — сколько памяти потребуется для его хранения.

Определение количества информации в сообщении

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

В слове Принтер 6 различных символов (р встречается дважды и считается один раз), далее 7-й символ пробел и девятый — тире. Так как пробел уже был, то после тире мы его не считаем. В слове устройство 10 символов, но различных — 7, так как буквы с, т и о повторяются. Кроме того буквы т и р уже была в слове Принтер. Так что получается, что в слове устройство 5 различных символов. Считая таким образом дальше мы получим, что в сообщении 20 различных символов.

Далее вспомним формулу, которую называют главной формулой информатики:

2ⁱ=N

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

2ⁱ=20

Вспомним степени двойки и поймем, что i находится в диапазоне от 4 до 5 (так как 2⁴=16, а 2⁵=32). А так как бит — минимальная единица измерения информации и дробным быть не может, то мы округляем i в большую сторону до 5. Иначе, если принять, что i=4, мы смогли бы закодировать только 2⁴=16 символов, а у нас их 20. Поэтому получаем, что i=5, то есть каждый символ в нашем сообщении несет 5 бит информации.

Осталось посчитать сколько символов в нашем сообщении. Но теперь мы будем считать все символы, не важно повторяются они или нет. Получим, что сообщение состоит из 39 символов. А так как каждый символ — это 5 бит информации, то, умножив 5 на 39 мы получим:

5 бит x 39 символов = 195 бит

Это и есть ответ на вопрос задачи — в сообщении 195 бит информации. И, подводя итог, можно написать алгоритм нахождения объема информации в сообщении:

посчитать количество различных символов.
подставив это значение в формулу 2i=N найти вес одного символа (округлив в большую сторону)
посчитать общее количество символов и умножить это число на вес одного символа.

Автор:

Источник

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 17 мая 2019 года; проверки требуют 47 правок.

Формула Хартли или хартлиевское количество информации или мера Хартли — логарифмическая мера информации, которая определяет количество информации, содержащееся в сообщении.

${displaystyle I=Klog _{2}N}$

Где N — количество символов в используемом алфавите (мощность алфавита), K — длина сообщения (количество символов в сообщении), I — количество информации в сообщении в битах.

Формула была предложена Ральфом Хартли в 1928 году как один из научных подходов к оценке сообщений.

Для случая определения количества информации i в одном символе алфавита мощности N, формула Хартли принимает вид:

${displaystyle i=log _{2}N}$

Соответственно, мощность алфавита равна:

${displaystyle N=2^{i}}$

Из формулы Хартли следует, что алфавит, содержащий только 1 символ не может быть использован для передачи информации:

${displaystyle log _{2}1=0}$

Пусть, имеется алфавит А, из N букв которого составляется сообщение:

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

${displaystyle M=N^{K},}$

где M — возможное количество различных сообщений, N — количество букв в алфавите, K — количество букв в сообщении.

Рассмотрим следующий пример. Цепь ДНК состоит из 4 видов азотистых оснований: Аденин (A), Гуанин (G), Тимин (T), Цитозин (C). Следовательно, мощность «алфавита» ДНК N равна 4. Значит, каждое азотистое основание несет ${displaystyle i=log _{2}4=2}$ бита информации.

Пример: Пусть алфавит состоит из 16 символов «1», «2», «3», «4», «5», «6», «7», «8», «9», «0», «+», «-», «*», «/», «^», «#», а длина сообщения составляет 10 символов (например, команда «*123*1*3^#») — таким образом, мощность алфавита N = 16, а длина сообщения K = 10. При выбранных нами алфавите и длине сообщения можно составить ${displaystyle M=N^{K}=16^{10}=1099511627776}$ сообщений. По формуле Хартли можно определить, что количество информации в каждом символе одного из этих сообщений равно ${displaystyle i=log _{2}N=log _{2}16=4}$ бита, а количество информации во всем сообщении, соответственно, равно ${displaystyle I=Klog _{2}N=10log _{2}16=10cdot 4=40}$ бит.

При равновероятности символов ${displaystyle p={frac {1}{m}},m={frac {1}{p}}}$ формула Хартли переходит в собственную информацию.

Иллюстрация[править | править код]

Допустим, нам требуется что-либо найти или определить в той или иной системе. Есть такой способ поиска, как «деление пополам». Например, кто-то загадывает число от 1 до 100, а другой должен отгадать его, получая лишь ответы «да» или «нет». Задаётся вопрос: «число меньше N?». Любой из ответов «да» и «нет» сократит область поиска вдвое. Далее по той же схеме диапазон снова делится пополам. В конечном счёте загаданное число будет найдено.

Сколько вопросов надо задать, чтобы найти задуманное число от 1 до 100. Допустим, загаданное число 27. Вариант диалога:

Больше 50? Нет.
Больше 25? Да.
Больше 38? Нет.
Меньше 32? Да.
Меньше 29? Да.
Меньше 27? Нет.
Это число 28? Нет.

Если число не 28 и не меньше 27, то это явно 27. Чтобы угадать методом «деления пополам» число от 1 до 100, нам потребовалось 7 вопросов.

Можно просто спрашивать: это число 1? Это число 2? И т. д. Но тогда вам потребуется намного больше вопросов. «Деление пополам» — оптимальный в данном случае способ нахождения числа. Объём информации, заложенный в ответ «да»/«нет», если эти ответы равновероятны, равен одному биту (действительно, ведь бит имеет два состояния: 1 или 0). Итак, для угадывания числа от 1 до 100 нам потребовалось 35 битов (семь ответов «да»/«нет»).

${displaystyle N=2^{i}}$

Такой формулой можно представить, сколько вопросов (битов информации) потребуется, чтобы определить одно из возможных значений. N — это количество значений, а i — количество битов. Например, в нашем примере 27 меньше, чем 28, однако больше, чем 26. Да, нам могло бы потребоваться и всего 6 вопросов, если бы загаданное число было 28.

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

${displaystyle i=log _{2}N.}$

Количество информации (i), необходимой для определения конкретного элемента, есть логарифм по основанию 2 общего количества элементов (N).

Формула Шеннона^[1][править | править код]

Когда события не равновероятны, может использоваться формула Шеннона:

${displaystyle I=-sum _{i}p_{i}log _{2}p_{i},}$

где p_i вероятность i-го события.

См. также[править | править код]

Собственная информация

Примечания[править | править код]

↑ Шеннон, Клод // Википедия. — 2019-08-05.

Источник

Информатика

7 класс

Урок № 6

Единицы измерения информации

Перечень вопросов, рассматриваемых в теме:

Алфавитный подход к измерению информации.
Наименьшая единица измерения информации.
Информационный вес одного символа алфавита и информационный объём всего сообщения.
Единицы измерения информации.
Задачи по теме урока.

Тезаурус:

Каждый символ информационного сообщения несёт фиксированное количество информации.

Единицей измерения количества информации является бит – это наименьшаяединица.

1 байт = 8 бит

1 Кб (килобайт) = 1024 байта= 2¹⁰байтов

1 Мб (мегабайт) = 1024 Кб = 2¹⁰Кб

1 Гб (гигабайт) = 1024 Мб = 2¹⁰ Мб

1 Тб (терабайт) =1024 Гб = 2¹⁰ Гб

Формулы, которые используются при решении типовых задач:

Информационный вес символа алфавита и мощность алфавита связаны между собой соотношением: N = 2ⁱ.

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

I = К · i,

I – объём информации в сообщении;

К – количество символов в сообщении;

i – информационный вес одного символа.

Основная литература:

Босова Л. Л. Информатика: 7 класс. // Босова Л. Л., Босова А. Ю. – М.: БИНОМ, 2017. – 226 с.

Дополнительная литература:

Босова Л. Л. Информатика: 7–9 классы. Методическое пособие. // Босова Л. Л., Босова А. Ю., Анатольев А. В., Аквилянов Н.А. – М.: БИНОМ, 2019. – 512 с.
Босова Л. Л. Информатика. Рабочая тетрадь для 7 класса. Ч 1. // Босова Л. Л., Босова А. Ю. – М.: БИНОМ, 2019. – 160 с.
Босова Л. Л. Информатика. Рабочая тетрадь для 7 класса. Ч 2. // Босова Л. Л., Босова А. Ю. – М.: БИНОМ, 2019. – 160 с.
Гейн А. Г. Информатика: 7 класс. // Гейн А. Г., Юнерман Н. А., Гейн А.А. – М.: Просвещение, 2012. – 198 с.

Теоретический материал для самостоятельного изучения.

Любое сообщение несёт некоторое количество информации. Как же его измерить?

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

Сегодня на уроке мы узнаем, чему равен информационный вес одного символа и научимся определять информационный объём сообщения.

Что же такое символ в компьютере? Символом в компьютере является любая буква, цифра, знак препинания, специальный символ и прочее, что можно ввести с помощью клавиатуры. Но компьютер не понимает человеческий язык, он каждый символ кодирует. Вся информация в компьютере представляется в виде нулей и единичек. И вот эти нули и единички называются битом.

Информационный вес символа двоичного алфавита принят за минимальную единицу измерения информации и называется один бит.

Алфавит любого понятного нам языка можно заменить двоичным алфавитом. При этом мощность исходного алфавита связана с разрядностью двоичного кода соотношением: N = 2ⁱ.

Эту формулу можно применять для вычисления информационного веса одного символа любого произвольного алфавита.

Рассмотрим пример:

Алфавит древнего племени содержит 16 символов. Определите информационный вес одного символа этого алфавита.

Составим краткую запись условия задачи и решим её:

Дано:

N=16, i = ?

Решение:

N = 2ⁱ

16 = 2ⁱ, 2⁴ = 2ⁱ, т. е. i = 4

Ответ: i = 4 бита.

Информационный вес одного символа этого алфавита составляет 4 бита.

Сообщение состоит из множества символов, каждый из которых имеет свой информационный вес. Поэтому, чтобы вычислить объём информации всего сообщения, нужно количество символов, имеющихся в сообщении, умножить на информационный вес одного символа.

Математически это произведение записывается так: I = К · i.

Например: сообщение, записанное буквами 32-символьного алфавита, содержит 180 символов. Какое количество информации оно несёт?

Дано:

N = 32,

K = 180,

I= ?

Решение:

I = К · i,

N = 2ⁱ

32 = 2ⁱ, 2⁵ = 2ⁱ, т.о. i = 5,

I = 180 · 5 = 900 бит.

Ответ: I = 900 бит.

Итак, информационный вес всего сообщения равен 900 бит.

В алфавитном подходе не учитывается содержание самого сообщения. Чтобы вычислить объём содержания в сообщении, нужно знать количество символов в сообщении, информационный вес одного символа и мощность алфавита. То есть, чтобы определить информационный вес сообщения: «сегодня хорошая погода», нужно сосчитать количество символов в этом сообщении и умножить это число на восемь.

I = 23 · 8 = 184 бита.

Значит, сообщение весит 184 бита.

Как и в математике, в информатике тоже есть кратные единицы измерения информации. Так, величина равная восьми битам, называется байтом.

Бит и байт – это мелкие единицы измерения. На практике для измерения информационных объёмов используют более крупные единицы: килобайт, мегабайт, гигабайт и другие.

1 байт = 8 бит

1 Кб (килобайт) = 1024 байта= 2¹⁰байтов

1 Мб (мегабайт) = 1024 Кб = 2¹⁰Кб

1 Гб (гигабайт) = 1024 Мб = 2¹⁰ Мб

1 Тб (терабайт) =1024 Гб = 2¹⁰ Гб

Итак, сегодня мы узнали, что собой представляет алфавитный подход к измерению информации, выяснили, в каких единицах измеряется информация и научились определять информационный вес одного символа и информационный объём сообщения.

Материал для углубленного изучения темы.

Как текстовая информация выглядит в памяти компьютера.

Набирая текст на клавиатуре, мы видим привычные для нас знаки (цифры, буквы и т.д.). В оперативную память компьютера они попадают только в виде двоичного кода. Двоичный код каждого символа, выглядит восьмизначным числом, например 00111111. Теперь возникает вопрос, какой именно восьмизначный двоичный код поставить в соответствие каждому символу?

Все символы компьютерного алфавита пронумерованы от 0 до 255. Каждому номеру соответствует восьмиразрядный двоичный код от 00000000 до 11111111. Этот код ‑ просто порядковый номер символа в двоичной системе счисления.

Таблица, в которой всем символам компьютерного алфавита поставлены в соответствие порядковые номера, называется таблицей кодировки.Таблица для кодировки – это «шпаргалка», в которой указаны символы алфавита в соответствии порядковому номеру. Для разных типов компьютеров используются различные таблицы кодировки.

Таблица ASCII (или Аски), стала международным стандартом для персональных компьютеров. Она имеет две части.

В этой таблице латинские буквы (прописные и строчные) располагаются в алфавитном порядке. Расположение цифр также упорядочено по возрастанию значений. Это правило соблюдается и в других таблицах кодировки и называется принципом последовательного кодирования алфавитов. Благодаря этому понятие «алфавитный порядок» сохраняется и в машинном представлении символьной информации. Для русского алфавита принцип последовательного кодирования соблюдается не всегда.

Запишем, например, внутреннее представление слова «file». В памяти компьютера оно займет 4 байта со следующим содержанием:

01100110 01101001 01101100 01100101.

А теперь попробуем решить обратную задачу. Какое слово записано следующим двоичным кодом:

01100100 01101001 01110011 01101011?

В таблице 2 приведен один из вариантов второй половины кодовой таблицы АSСII, который называется альтернативной кодировкой. Видно, что в ней для букв русского алфавита соблюдается принцип последовательного кодирования.

Вывод: все тексты вводятся в память компьютера с помощью клавиатуры. На клавишах написаны привычные для нас буквы, цифры, знаки препинания и другие символы. В оперативную память они попадают в форме двоичного кода.

Из памяти же компьютера текст может быть выведен на экран или на печать в символьной форме.

Сейчас используют целых пять систем кодировок русского алфавита (КОИ8-Р, Windows, MS-DOS, Macintosh и ISO). Из-за количества систем кодировок и отсутствия одного стандарта, очень часто возникают недоразумения с переносом русского текста в компьютерный его вид. Поэтому, всегда нужно уточнять, какая система кодирования установлена на компьютере.

Разбор решения заданий тренировочного модуля

№1. Определите информационный вес символа в сообщении, если мощность алфавита равна 32?

Варианты ответов:

Решение:

Информационный вес символа алфавита и мощность алфавита связаны между собой соотношением: N = 2ⁱ.

32 = 2ⁱ, 32 – это 2⁵, следовательно, i =5 битов.

Ответ: 5 битов.

№2. Выразите в килобайтах 2¹⁶ байтов.

Решение:

2¹⁶ можно представить как 2⁶· 2¹⁰.

2⁶ = 64, а 2¹⁰ байт – это 1 Кб. Значит, 64 · 1 = 64 Кб.

Ответ: 64 Кб.

№3. Тип задания: выделение цветом

8^х = 32 Кб, найдите х.

Варианты ответов:

Решение:

8 можно представить как 2³. А 32 Кб переведём в биты.

Получаем 2^3х=32 · 1024 ·8.

Или 2^3х = 2⁵ · 2¹⁰· 2³.

2^3х = 2¹⁸.

3х = 18, значит, х=6.

Ответ: 6.

Источник

На уроке рассматривается разбор 8 задания ЕГЭ по информатике про измерение количества информации

8-е задание: «Измерение количества информации»

Уровень сложности

— базовый,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 4 минуты.

Проверяемые элементы содержания: Знание о методах измерения количества информации

До ЕГЭ 2021 года — это было задание № 10 ЕГЭ

Типичные ошибки и рекомендации по их предотвращению:

“При использовании способа решения со системой счисления с основанием N следует помнить, что слова в списке нумеруются с единицы, поэтому числу 0 будет соответствовать первое слово”

ФГБНУ “Федеральный институт педагогических измерений”

Содержание:

Объяснение темы
- Измерение количества информации
- Двоичное кодирование сообщений (равновероятностные события)
- Количество различных сообщений в алфавите разной мощности
- Количество сообщений при различном вхождении (встречаемости) букв
- Дополнительные формулы
Тренировочные задания 8 ЕГЭ по информатике и их решение
- Сколько вариантов шифра или кодовых слов
- Перестановка букв в слове (каждая буква 1 раз)
- Сколько существует n-значных чисел, записанных в m-ной системе счисления
- Список в алфавитном порядке
- Вероятность событий

Объяснение темы

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

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

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

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

8 = 2³
1024 = 2¹⁰

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

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

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

Сообщение — это любая последовательность символов какого-либо алфавита.

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

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

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

N = 2^L

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

L — длиной битов

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

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

Решение:

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

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

N = 2^L

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

Ответ: 4

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

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

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

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

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

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

Решение:

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

= 17576

Ответ: 17576

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

N = n1 * n2 * … * nL

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

В таком случае можно использовать формулу для вычисления числа перестановок с повторениями; для двух разных символов она выглядит так:

[ P = frac{na+n*!}{na!n*!} ]

na – количество букв a

n* — количество звёздочек или кол-во вариантов

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

[ C{binom{k}{n}}= frac{n!}{k!(n-k)!} ]

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

N – количество вариантов

n! = 1 * 2 * 3 * … * n

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

Решение:

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

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

Получили 6 вариантов, каждый из которых равен 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 ]

* Факториал числа n! = 1 * 2 * 3 *..* n

Т.е. проверка прошла успешно, мы получили 6 вариантов.
Осталось посчитать количество всех сообщений:

6 * 9 = 54

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

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

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

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

x = log₂(1/p)

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

p — вероятность события

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

p(A) = m / n

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

n — количество общих исходов (общее число равновозможных случаев)

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

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

i = -[log₂p]

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

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

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

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

N – количество вариантов

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

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

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

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

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

Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ

Сколько вариантов шифра или кодовых слов

Такие задания можно решить программированием.

На языке PascalAbc.net можно использовать язык интегрированных запросов LINQ (Language Integrated Query).

Cartesian(n) — метод расширения последовательности, возвращающий декартову степень множества символов Когда применяется:
Если требуется полный перебор вариантов букв для каждой позиции (каждая буква может встречаться в кодовом слове любое количество раз)

Пример:
Сравним полный перебор букв слова «школа», размещенных на две позиции:

Pascal PascalABC.NET

##
var str:='школа';
foreach var s1 in str do
  foreach var s2 in str do
         print(|s1,s2|)

## // 1 вариант
var str:='школа';
str.cartesian(2).print
 
## // 2 вариант
'школа'.cartesian(2).print
 
### // 3 вариант (спортивное прогр-е)
'школа'.cart(2).print

Результат:

[ш,ш] [ш,к] [ш,о] [ш,л] [ш,а] [к,ш] [к,к] [к,о]
[к,л] [к,а] [о,ш] [о,к] [о,о] [о,л] [о,а] [л,ш]
[л,к] [л,о] [л,л] [л,а] [а,ш] [а,к] [а,о] [а,л] [а,а]

Итого 25 штук (5*5)

[ш,ш] [ш,к] [ш,о] [ш,л] [ш,а] [к,ш] [к,к] [к,о]
[к,л] [к,а] [о,ш] [о,к] [о,о] [о,л] [о,а] [л,ш]
[л,к] [л,о] [л,л] [л,а] [а,ш] [а,к] [а,о] [а,л] [а,а]

Permutations — метод возвращает все перестановки множества элементов, заданного массивом или последовательностью Когда применяется:
Если требуется перестановка букв в слове. То есть количество каждой буквы в словах сохраняется, и каждая буква встречается только 1 раз

Пример:
Сравним перестановку букв слова «мимикрия»:

Pascal PascalABC.NET

## // 1 вариант
 'мимикрия'.Permutations
  // собираем в строку:
  // к строкам можно distinct применять, а к массивам - нет
 .Select(w->w.JoinToString('')) 
 .Distinct  // выбираем уникальные, т.к. от перестановки двух букв "м" 
            // и букв "и" слово не меняется
 .Count.Print

1	## // 2 вариант

### // 3 вариант (спортивное прогр-е)
'мимикрия'.Prm
 .Sel(w->w.ToS('')) 
 .Dst  
 .Cnt.Pr

Результат:

[М,И,М,И,К,Р,И,Я] [М,И,М,И,К,Р,Я,И] [М,И,М,И,К,И,Р,Я] [М,И,М,И,К,И,Я,Р] [М,И,М,И,К,Я,Р,И] [М,И,М,И,К,Я,И,Р] [М,И,М,И,Р,К,И,Я] [М,И,М,И,Р,К,Я,И]
…

Используются также следующие запросы и методы LINQ:

Фильтрация последовательностей (Where)
Метод Count([Type -> boolean]) Вычисление скаляра
Метод CountOf(s: Type) — Возвращает количество элементов, равных указанному значению
Метод First() — Возвращает первый элемент последовательности.
Метод Last() — Возвращает последний элемент последовательности.
Метод Pairwise(Self: sequence of T; func: (T,T)->Res) — Превращает последовательность в последовательность пар соседних элементов, применяет func к каждой паре полученных элементов и получает новую последовательность

8_1:

Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 6.

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

Типовые задания для тренировки

✍ Решение:

✎ Решение теоретическое:

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

Q = N^L

Итак, что у нас дано из этой формулы:
Длина сообщения (L) = 5 символов
Мощность алфавита (N) = 6 (цифры от 1 до 6).
Но так как цифра 1 встречается по условию ровно один раз, а остальные 5 цифр — любое количество раз, то будем считать, что N = 5 (цифры от 2 до 6, исключая 1). Т.е. возьмем вариант, когда 1 стоит на первом месте, а остальные 5 цифр размещаем на 4 позиции:

1 5 5 5 5 - 1 * Q = 5⁴ = 625

✎ 1 способ. Найдем количество вариантов методом перебора:

Методом перебора найдем количество вариантов размещения:

1 5 5 5 5 - 1 * Q=5⁴ = 625
5 1 5 5 5 - 1 * Q=5⁴ = 625
5 5 1 5 5 - 1 * Q=5⁴ = 625
5 5 5 1 5 - 1 * Q=5⁴ = 625
5 5 5 5 1 - 1 * Q=5⁴ = 625

получили 5 вариантов;

✎ 2 способ. Найдем количество вариантов при помощи формулы комбинаторики:

[ C{binom{4}{5}}= frac{5!}{4!(5-4)!} = 5 ]

получили 5 вариантов;
В итоге получим:

625 * 5 = 3125

Результат: 3125

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := '123456';
  foreach var s1 in str do
    foreach var s2 in str do
      foreach var s3 in str do
        foreach var s4 in str do
          foreach var s5 in str do
          begin
            if (s1 + s2 + s3 + s4 + s5).CountOf('1') = 1 then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='123456'.Cartesian(5) 
.where(w->w.countOf('1')=1)// кол-во '1' в слове
.count.print

Cartesian(5) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 5-знаковых слов из заданных символов

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

n=0
str='123456'
for s1 in str:
  for s2 in str:
    for s3 in str:
      for s4 in str:
        for s5 in str:
          if (s1+s2+s3+s4+s5).count('1')==1:
            n+=1
print(n)

С++:

Детальный теоретический разбор задания 8 ЕГЭ по информатике предлагаем посмотреть в видеоуроке:

📹 YouTube здесьздесь (теоретическое решение)

8_2:

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

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

✍ Решение:

✎ Решение теоретическое:

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

Q = N^L

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

Q = 2 * 3⁴ = 162

Имеем 162 вариантов шифра для слова, в котором буквы могут стоять на первой позиции:

AB  123 123 123 123 = 162

Получим все варианты размещения:

"2" означает одна из двух букв: А или B, "3" - одна из трех цифр:

2 3 3 3 3 -> Q = 2 * 3⁴ = 162
3 2 3 3 3 -> Q = 2 * 3⁴ = 162
3 3 2 3 3 -> Q = 2 * 3⁴ = 162
3 3 3 2 3 -> Q = 2 * 3⁴ = 162
3 3 3 3 2 -> Q = 2 * 3⁴ = 162

Получили 5 вариантов с размещением букв А и B.
Осталось умножить:

5 * 162 = 810

Результат: 810

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'AB123';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5];
            if (res.CountOf('A') = 1) and (res.CountOf('B') = 0) 
            or (res.CountOf('B') = 1) and (res.CountOf('A') = 0) then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='АВ123'.Cartesian(5) 
.where(w->w.count(letter -> letter in 'АВ')=1)// кол-во букв в слове
.count.print

Cartesian(5) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 5-знаковых слов из заданных символов

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

n=0
str='AB123'
for s1 in str:
  for s2 in str:
    for s3 in str:
      for s4 in str:
        for s5 in str:
          if ((s1+s2+s3+s4+s5).count('A')==1 and (s1+s2+s3+s4+s5).count('B')==0) 
          or ((s1+s2+s3+s4+s5).count('B')==1 and (s1+s2+s3+s4+s5).count('A')==0):
            n+=1
print(n)

С++:

Подробное теоретическое решение данного задания предлагаем посмотреть на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_3:

Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег использует 4-буквенные слова, в которых есть только буквы A, Б, В, Г, Д и Е, причём буква Г появляется ровно 1 раз и только на первом или последнем месте. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем.

Сколько различных кодовых слов может использовать Олег?

✍ Решение:

✎ Решение теоретическое:

Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
Рассмотрим варианты, когда буква Г встречается на первом или последнем месте:

Г ? ? ? = 1 * 5 * 5 * 5 = 5³ = 125 
? ? ? Г = 5 * 5 * 5 * 1 = 5³ = 125

Вместо знаков ? может стоять одна из пяти букв (А, Б, В, Д, Е), т.к. буква Г там стоять не может
Теперь суммируем количество найденных вариантов:

125 + 125 = 250

Результат: 250

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'АБВГДЕ';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4];
            if (res[1]='Г') and (res[2]<>'Г') and (res[3]<>'Г') and (res[4]<>'Г')
            or (res[1]<>'Г') and (res[2]<>'Г') and (res[3]<>'Г') and (res[4]='Г') then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='АБВГДЕ'.Cartesian(4)
.where(w->(w.countOf('Г')=1)and((w.First='Г')or(w.Last='Г'))) // или: 
// .where(w->(w.countOf('Г')=1)and(w[1]<>'Г')and(w[2]<>'Г'))
.count.print

Cartesian(4) — метод расширения последовательности, возвращающий декартову степень множества символов, т.е. в нашем случае перебор 4-знаковых слов из заданных символов

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

n=0
str='АБВГДЕ'
for s1 in str:
  for s2 in str:
    for s3 in str:
      for s4 in str:
        if (s1 =='Г') and (s2!='Г') and (s3!='Г') and (s4!='Г') 
        or (s1 !='Г') and (s2!='Г') and (s3!='Г') and (s4=='Г'):
            n+=1
print(n)

С++:

Видеоразбор данного задания (теоретический способ):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_4:

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

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

Типовые задания для тренировки

✍ Решение:

✎ Решение теоретическое:

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

Q = N^L

Итак, что у нас дано из этой формулы:
Начальная мощность алфавита (N) = 3 (буквы X, Y, Z). Но так как буква X встречается ровно два раза, то мы ее рассмотрим отдельно, а остальные 2 буквы — встречаются любое количество раз, значит, будем считать, что:

N = 3 - 1 = 2 (Y и Z)

Исходя из предыдущего пункта, длина сообщения тоже сократится:

(L) = 5 - 2 = 3 символа (остальные два символа отведем на размещение X)

Количество различных сообщений (вариантов шифра) = Q = ?
Т.е. для одного варианта размещения (для одного варианта шифра) имеем:

X X ? ? ? -> 1² * Q = 2³ = 8

Согласно условию получим следующие варианты размещения:

✎1 способ. Перебор всех вариантов:

X X ? ? ? - 1² * Q = 2³ = 8
X ? X ? ? - 1² * Q = 2³ = 8
X ? ? X ? - 1² * Q = 2³ = 8
X ? ? ? X - 1² * Q = 2³ = 8
? X X ? ? - 1² * Q = 2³ = 8
? X ? X ? - 1² * Q = 2³ = 8
? X ? ? X - 1² * Q = 2³ = 8
? ? X X ? - 1² * Q = 2³ = 8
? ? X ? X - 1² * Q = 2³ = 8
? ? ? X X - 1² * Q = 2³ = 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

Количество вариантов найдено верно, т.к. результат обоих способов = 10. В итоге получаем:

8 * 10 = 80

* задание достаточно решить одним из способов!

Результат: 80

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'xyz';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5];
            if res.countOf('x') = 2 then // или if res.Count(y -> y = 'x') = 2 then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='XYZ'.Cartesian(5)
.where(w->w.countOf('X')=2)
.count.print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

n=0
str='xyz'
for s1 in str:
  for s2 in str:
    for s3 in str:
      for s4 in str:
        for s5 in str:
          if (s1+s2+s3+s4+s5).count('x') == 2:
            n+=1
print(n)

С++:

Детальный теоретический разбор задания 8 ЕГЭ по информатике теоретическим способом предлагаем посмотреть в видеоуроке:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_5:

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

Типовые задания для тренировки

✍ Решение:

✎ Решение теоретическое:

Из букв слова ОСЕНЬ имеем 2 гласных буквы (О, Е) и 2 согласных буквы (С, Н). Буква мягкий знак «нейтральна».
Подсчитаем количество букв на каждой из 5 позиций:

2   5   5   5   2
^{СН   все  все  все   ОЕ}

Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
Т.е. количество вариантов равно произведению полученных чисел:

N = 2 * 5 * 5 * 5 * 2 = 500

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'ОСЕНЬ';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5];
            if ((res[1] = 'С') or (res[1] = 'Н')) and ((res[5] = 'О') or (res[5] = 'Е')) then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

1	'ОСЕНЬ'.Cartesian(5).Where(w->w[0] in 'СН').Where(w->w[4] in 'ОЕ').Count.Print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

str = 'ОСЕНЬ'
n = 0
for s1 in str:
    for s2 in str: 
        for s3 in str:
            for s4 in str:
                for s5 in str:
                    res = s1 + s2 + s3 + s4
                    if (s1 == 'С' or s1 == 'Н') and (s5 == 'О' or s5 == 'Е'):
                        n += 1
print(n)

С++:

Результат: 500

Разбор можно также посмотреть на видео (теоретическое решение):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_6:

Вася составляет 4-буквенные слова, в которых есть только буквы Л, Е, Т, О, причём буква Е используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.

✍ Решение:

✎ Решение теоретическое:

✎ 1 способ:

Количество вариантов различных слов вычислим по формуле:

N = n1 * n2 * n3 * …
где

n1 — количество вариантов выбора первой буквы и т.п.
Рассмотрим все варианты расположения буквы Е:

1. Е ? ? ? или 
2. ? Е ? ? или 
3. ? ? Е ? или
4. ? ? ? Е 

Где вопросительный знак означает любую букву из Л, Е, Т, О.

Подсчитаем по формуле количество слов для варианта 1:

Е ? ? ? = 1 * 4 * 4 * 4 = 64

т.е. на первой позиции - только 1 буква - Е, на каждой последующей - одна из четырех букв Л, Е, Т, О.

Подсчитаем по формуле количество слов для варианта 2; учтем, что на первой позиции букву Е мы уже посчитали для первого варианта!:

? Е ? ? = 3 * 1 * 4 * 4 = 48

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

? ? Е ? = 3 * 3 * 1 * 4 = 36

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

? ? ? Е = 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

Вычтем из первого варианта невозможный вариант № 2:

256 - 81 = 175

Результат: 175

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'ЛЕТО';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4];
            if res.countOf('Е') >= 1 then // или if res.Count(y -> y = 'Е') >= 1 then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

1 2	## var d:='лето'.Cartesian(4).where(w->w.countOf('е')>=1).count.print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

n=0
str='ЛЕТО'
for s1 in str:
  for s2 in str:
    for s3 in str:
      for s4 in str:
          if (s1+s2+s3+s4).count('Е') >= 1:
            n+=1
print(n)

С++:

Теоретическое решение задания 8 смотрите в видеоуроке:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_7:

Вася составляет 4-буквенные слова, в которых есть только буквы К, А, Т, Е, Р, причём буква Р используется в каждом слове хотя бы 2 раза. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем.

✍ Решение:

✎ Решение теоретическое:

Количество возможных вариантов слов вычислим по формуле:

N = n1 * n2 * n3 * … * nL = n^L

где n1 — количество вариантов выбора первой буквы, n2 — количество вариантов выбора второй буквы и т.п.
Сначала по формуле получим все варианты для всех пяти букв, включая букву Р:

5 * 5 * 5 * 5 = 5⁴ = 625

Из общего количества вариантов нам необходимо исключить те варианты, где Р не встречается вообще и Р встречается только 1 раз. Найдем их последовательно:
1. Буква Р не встречается совсем:

4 * 4 * 4 * 4 = 4⁴ = 256

2. Буква Р встречается только один раз:

р ? ? ? = 1 * 4 * 4 * 4 = 4³
? р ? ? = 4 * 1 * 4 * 4 = 4³
? ? р ? = 4 * 4 * 1 * 4 = 4³
? ? ? р = 4 * 4 * 4 * 1 = 4³

Получим  4³ * 4 = 256

Теперь вычтем из общего количества найденные варианты (№ 1 и № 2):

625 - 256 - 256 = 113

✎ Решение с использованием программирования:

PascalABC.net (традиционный):

begin
  var n := 0;
  var str := 'КАТЕР';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4];
            if res.CountOf('Р') >= 2 then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (LINQ):

1 2	## var d:='катер'.Cartesian(4).where(w->w.countOf('р')>=2).count.print

Python:

n=0
str='КАТЕР'
for s1 in str:
  for s2 in str:
    for s3 in str:
      for s4 in str:
          if (s1+s2+s3+s4).count('Р') >= 2:
            n+=1
print(n)

С++:

Результат: 113

Теоретическое решение 8 задания предлагаем посмотреть в видеоуроке:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_8:

Олег составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Олег использует 5-буквенные слова, в которых есть только буквы A, Б, В, и Г, причём буква Г появляется не более одного раза и только на последнем месте. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем.

Сколько различных кодовых слов может использовать Олег?

✍ Решение:

✎ Решение теоретическое:

Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

где n1 — количество вариантов выбора первой буквы,
n2 — количество вариантов выбора второй буквы и т.п.
Так как буква Г появляется не более одного раза и только на последнем месте, значит, она может либо появиться 1 раз на последнем месте, либо не появиться совсем.
Рассмотрим варианты, когда буква Г встречается 1 раз на последнем месте и встречается 0 раз:

1 раз: ? ? ? ? Г = 3 * 3 * 3 * 3 * 1 = 3⁴ = 81 
0 раз: ? ? ? ? ? = 3 * 3 * 3 * 3 * 3 = 3⁵ = 243

Вместо знаков ? может стоять одна из трех букв (А, Б, В), т.к. буква Г там стоять не может
Теперь суммируем количество найденных вариантов:

81 + 243 = 324

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'АБВГ';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s4];
            if (res[1]<>'Г') and (res[2]<>'Г')and (res[3]<>'Г') and (res[4]<>'Г') then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='абвг'.Cartesian(5)
.where(w->(w.countOf('г')<=1)and(w[0]<>'г')and(w[1]<>'г')and(w[2]<>'г')
     and(w[3]<>'г')).count.print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Результат: 324

8_9:

Вася составляет 4-буквенные слова, в которых есть только буквы К, О, М, А, Р, причём буква А используется в них не более 3-х раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная.

✍ Решение:

✎ Решение теоретическое:

Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

где n1 — количество вариантов выбора первой буквы,
n2 — количество вариантов выбора второй буквы и т.п.
Так как буква А по условию используется не более 3-х раз, это значит, что она используется либо 3 раза, либо 2 раза, либо 1 раз, либо не используется совсем. Рассмотрим все эти варианты отдельно.
1. Буква А используется 3 раза:

А А А _  -> 1 * 1 * 1 * 4 = 4
А А _ А  -> 1 * 1 * 4 * А = 4
А _ А А  -> 1 * 4 * 1 * 1 = 4
_ А А А  -> 4 * 1 * 1 * 1 = 4

Итого получаем 4 варианта, в которых вместо символа _ может быть любая из 4 букв: К О М Р. Значит, имеем:

 4 * 4 = 16 вариантов

2. Буква А используется 2 раза:

А А _ _  -> 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

Итого получаем 6 вариантов, в которых вместо символа _ может быть любая из 4 букв: К О М Р. Значит имеем:

 16 * 6 = 96 вариантов

3. Буква А используется 1 раз:

А _ _ _  -> 1 * 4 * 4 * 4 = 64
_ А _ _  -> = 64
_ _ А _  -> = 64
_ _ _ А  -> = 64

Итого имеем:

64 * 4 = 256 вариантов

Буква А используется 0 раз:

_ _ _ _ -> 4⁴ = 256

Суммируем результаты всех трех случаев:

16 + 96 + 256 + 256 = 624

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'КОМАР';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          begin
            var res := str[s1] + str[s2] + str[s3] + str[s4];
            if res.CountOf('А') <=3 then
              n += 1;
          end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

1
2
3

##
var d:='комар'.Cartesian(4)
.where(w->w.countOf('а')<=3).count.print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

str = 'КОМАР'
n = 0
for s1 in str:
    for s2 in str: 
        for s3 in str:
            for s4 in str:
                res = s1 + s2 + s3 + s4
                if res.count('А')<=3:
                    n += 1
print(n)

С++:

Результат: 624

Теоретическое решение смотрите также на видео:

📹 YouTube здесьздесь (теоретическое решение)

8_10:

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

✍ Решение:

✎ Решение теоретическое:

Вспомним формулу получения количества возможных вариантов слов:

N = n1 * n2 * n3 * … * nL = n^L

где n1 — количество вариантов выбора первой буквы,
n2 — количество вариантов выбора второй буквы и т.п.
Будем рассматривать варианты, расставляя каждую букву последовательно по алфавиту, начиная с первой буквы. При этом будем учитывать указанные ограничения для букв А, B и С:

Начинаем с A: A D 4_ABCD = 1 * 1 * 4 = 4 
Начинаем с B: B A D, B B 2_BD, B D 4_ABCD = 7
Начинаем с C: C A D, C C 2_CD, C D 4_ABCD = 7
Начинаем с D: D A 3_BCD, D B 2_BD, D C 2_CD, D D 4_ABCD = 11

Теперь суммируем количество найденных вариантов:

4 + 7 + 7 + 11 = 29

Результат: 29

Видеоурок демонстрирует подробное теоретическое решение задания:

📹 YouTube здесьздесь (теоретическое решение)

8_22:

Лена составляет 5-буквенные слова из букв Я, С, Н, О, В, И, Д, Е, Ц, причём слово должно начинаться с согласной и заканчиваться гласной. Первая и последняя буквы слова встречаются в нем только один раз; остальные буквы могут повторяться.

Сколько слов может составить Лена?

✍ Решение:

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='ясновидец'.Cartesian(5) 
.where(l->(l[0] in 'снвдц') and (l[4] in 'яоие'))// учитываем гласные и согласные
.where(l->(l.countOf(l[0])=1)and(l.countOf(l[4])=1))//учитываем, что они не повторяются
.count.print

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var str := 'ЯСНОВИДЕЦ';
  var n := 0;
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
          begin
            var slovo := str[s1] + str[s2] + str[s3] + str[s4] + str[s5];
            if (slovo[1] in 'СНВДЦ') and (slovo[5] in 'ЯОИЕ') then
              if (slovo[1] <> slovo[2]) and (slovo[1] <> slovo[3]) and (slovo[1] <> slovo[4])            
              and (slovo[1] <> slovo[5]) and (slovo[5] <> slovo[1]) and (slovo[5] <> slovo[2]) 
              and (slovo[5] <> slovo[3]) and (slovo[5] <> slovo[4]) then
              begin
                n += 1
              end;
          end;
  print(n)
end.

Python:

С++:

Результат: 6860

Использование метода Pairwise()

8_11:

Из букв С, Р, Е, Д, А составляются трехбуквенные комбинации по следующему правилу – в комбинации не может быть подряд идущих гласных и одинаковых букв.

Например, комбинации ААР или ЕСС не являются допустимыми.

Сколько всего комбинаций можно составить, используя это правило?

✍ Решение:

✎ Решение теоретическое:

Рассмотрим два варианта: когда слово начинается с гласной буквы, и когда оно начинается с согласной.

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

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

### 
'среда'.cart(3)// 
 .Select(w -> w.JoinToString('')) // собираем в строку;
 .where(w->w.Pairwise.All((a,b) -> a+b not in 'еае'))
 .where(w->w.Pairwise.All((a,b) -> a<>b))
 .count.print

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'СРЕДА';
  var glas := 'ЕА';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
      begin
        var res := str[s1] + str[s2] + str[s3];
        // условие для подряд идущих гласных
        if not ((res[1] in glas) and (res[2] in glas) or
           (res[2] in glas) and (res[3] in glas)) then
        // условие для подряд идущих одинаковых букв
          if not ((res[1] = res[2]) or (res[2] = res[3])) then
            n += 1;
      end;
  print(n)
end.

Python:

str = 'СРЕДА'
glas = 'ЕА'
n = 0
for s1 in str:
    for s2 in str: 
        for s3 in str:
            res = s1 + s2 + s3 
            if not (s1 in glas and s2 in glas or
           s2 in glas and s3 in glas) :
                if not (s1 == s2 or s2 == s3) :
                    n += 1
print(n)

С++:

Результат: 66

Перестановка букв в слове (каждая буква 1 раз)

8_12:

Дано слово КОРАБЛИКИ. Таня решила составлять новые 5-буквенные слова из букв этого слова по следующим правилам:
1) слово начинается с гласной буквы;
2) гласные и согласные буквы в слове должны чередоваться;
3) буквы в слове не должны повторяться.

✍ Решение:

✎ Решение теоретическое:

Учтем, что в слове КОРАБЛИКИ две буквы К и две И.
Всего в слове 4 гласных, но поскольку две буквы И, то необходимо считать только 3 гласных.
Всего в слове 5 согласных, однако две из них — буквы К, поэтому считать следует 4 согласных.
Посчитаем количество согласных и гласных для каждой из 5 позиций слова, учитывая, что с каждой последующей буквой количество используемых гласных/согласных уменьшается. Под позициями приведем пример букв:

гл   с   гл   с   гл  
3    4    2   3    1
^{оаи   крбл   оа   крб    и}

Количество слов вычисляется как произведение полученных чисел:

3 * 4 * 2 * 3 * 1 = 72

Результат: 72

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

###
'кораблики'
.Cart(5)
.select(w->w.JoinToString(''))
.Distinct //Обязательно!
.where(w-> w.First in 'оаи')
.where(w->w.Pairwise.All((a,b)->not ((a in 'оаи') and (b in 'оаи')) 
       and not( ( a in'крбл') and (b in 'крбл' ))))
.where(w->'корабли'.All(c->w.countOf(c)<=1))
.count.print

Python:

С++:

Результат: 72

8_21:

Ксюша составляет слова, меняя местами буквы в слове МИМИКРИЯ.
Сколько различных слов, включая исходное, может составить Ксюша?

✍ Решение:

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var str := 'МИМИКРИЯ';
  var set1: set of string;
  set1 := [];
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do 
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do 
          for var s5 := 1 to length(str) do  
            for var s6 := 1 to length(str) do
              for var s7 := 1 to length(str) do  
                for var s8 := 1 to length(str) do 
                begin
                  var slovo := str[s1] + str[s2] + str[s3] + str[s4] + str[s5] + str[s6] + str[s7] + str[s8];
                  if (slovo.CountOf('М') = 2) and (slovo.CountOf('И') = 3)
                  and (slovo.CountOf('К') = 1)
                  and (slovo.CountOf('Р') = 1)
                  and (slovo.CountOf('Я') = 1) then
                    include(set1, slovo);
                end;
  print(set1.count);
end.

Смысл решения в использовании типа множества (set). При добавлении новых элементов к множеству исключаются повторения.

PascalABC.net (использование LINQ, быстрое решение):

### 
 'МИМИКРИЯ'.Permutations // перестановки букв
 .Select(w->w.JoinToString('')) // собираем в строку
 .Distinct  // выбираем уникальные
 .Count.Print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Ответ: 3360

Подробное решение программным способом смотрите на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (программное решение)

8_19:

Петя составляет шестибуквенные слова

перестановкой букв

слова АДЖИКА. При этом он избегает слов с двумя подряд одинаковыми буквами. Сколько всего различных слов может составить Петя?

Типовые задания для тренировки

✍ Решение:

✎ Решение теоретическое:

Посчитаем количество слов без двух подряд одинаковых букв. Будем считать относительно буквы А, которых две в заданном слове АДЖИКА. Буквы не могут повторяться, поэтому их кол-во в каждом варианте будет уменьшается:

А*А*** = 4*3*2*1 = 24 слова с данным расположением буквы А. 
А**А** = 4*3*2*1 = 24
А***А* = 4*3*2*1
А****А = ...
*А*А**
*А**А*
*А***А
**А*А*
**А**А
***А*А

Получили 10 вариантов, и в каждом из них можно составить по 24 слова.
Таким образом, получим общее количество слов:

10 * 24 = 240

✎ Решение с использованием программирования:

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var s: set of string;
  s := [];
  var str := 'АДЖИКА';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
            for var s6 := 1 to length(str) do
            begin
              var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5] + str[s6];
              if (res.CountOf('А') = 2) and (res.CountOf('Д') = 1) 
                  and (res.CountOf('Ж') = 1) and (res.CountOf('И') = 1) 
                  and (res.CountOf('К') = 1) then
                     if (res[1] <> res[2]) and (res[2] <> res[3]) and (res[3] <> res[4]) 
                        and (res[4] <> res[5]) and (res[5] <> res[6]) then
                           include(s, res);
            end;
  print(s.count)
end.

Смысл решения в использовании типа — множества (set). При добавлении новых элементов к множеству исключаются повторения.

PascalABC.net (использование LINQ, быстрое решение):

### 
'аджика'.Permutations
 .Select(w -> w.JoinToString('')) // собираем в строку;
 .distinct // исключаем дубли
 .where(s -> not ('аа' in s)) // исключаем две подряд буквы 'а'
  // или так: .where(w->w.Pairwise.All((a,b) -> a<>b))
 .count.pr

Python:

С++:

Ответ: 240

8_20:

Маша составляет 7-буквенные коды из букв В, Е, Н, Т, И, Л, Ь. Каждую букву нужно использовать

ровно 1 раз

, при этом код буква Ь не может стоять на последнем месте и между гласными. Сколько различных кодов может составить Маша?

Типовые задания для тренировки

✍ Решение:

✎ Решение теоретическое:

Выполним задание следующим образом: 1. посчитаем общее количество слов, не учитывая никакие ограничения. 2. Затем посчитаем случаи, которые необходимо исключить. 3. Вычтем из результата пункта 1 результат пункта 2.
Общее количество независимо от ограничений (учтем, что буквы не должны повторяться):

7 6 5 4 3 2 1 - количество возможных вариантов букв на семи позициях

ИТОГО:
7! = 5040 слов

Посчитаем варианты, которые необходимо исключить. Их будет несколько:
а) буква ь — на последнем месте:

6 5 4 3 2 1 Ь = 6! = 720

б) буква ь — между гласными:

И Ь Е 4 3 2 1  = 24 варианта
Так как буквы смещаются по всем позициям, то получим (4 И Ь Е 3 2 1, ...):
24 * 5 = 120
Е Ь И 4 3 2 1  = 24 варианта
24 * 5 = 120

Посчитаем количество слов, согласно условию задачи:

5040 - 720 - 120 - 120 = 4080

✎ Решение с использованием программирования:
Стоит заметить, что теоретическое решение занимает меньше времени, чем программный способ!

PascalABC.net (приближенный к традиционному, долгое решение):

begin
  var n := 0;
  var str := 'ВЕНТИЛЬ';
  var glas := 'ЕИ';
  for var s1 := 1 to length(str) do
    for var s2 := 1 to length(str) do
      for var s3 := 1 to length(str) do
        for var s4 := 1 to length(str) do
          for var s5 := 1 to length(str) do
            for var s6 := 1 to length(str) do
              for var s7 := 1 to length(str) do
              begin
                var res := str[s1] + str[s2] + str[s3] + str[s4] + str[s5] + str[s6] + str[s7];
                if (res.CountOf('В') = 1) and (res.CountOf('Е') = 1) 
                    and (res.CountOf('Н') = 1) and (res.CountOf('Т') = 1) 
                    and (res.CountOf('И') = 1) and (res.CountOf('Л') = 1)
                    and (res.CountOf('Ь') = 1) then
                  if not (res[7] = 'Ь') then
                    if not ((res[1] in glas) and (res[3] in glas) and (res[2] = 'Ь') or
                        (res[2] in glas) and (res[4] in glas) and (res[3] = 'Ь') or
                        (res[3] in glas) and (res[5] in glas) and (res[4] = 'Ь') or
                        (res[4] in glas) and (res[6] in glas) and (res[5] = 'Ь') or
                        (res[5] in glas) and (res[7] in glas) and (res[6] = 'Ь')) then
                      n += 1
              end;
  print(n)
end.

PascalABC.net (использование LINQ, быстрое решение):

### 
'вентиль'.Permutations// здесь можно без distinct, т.к. буквы не повторяются
 .Select(w -> w.JoinToString('')) // собираем в строку
 .where(s -> not ('еьи' in s) and not ('иье' in s) and (s.last <> 'ь'))
.Count.Print

Python:

С++:

Ответ: 4080

8_23:

Артур составляет 6-буквенные коды перестановкой букв слова ВОРОТА. При этом нельзя ставить рядом две гласные.
Сколько различных кодов может составить Артур?

✍ Решение:

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, спортивное прогр-е):

###
'ВОРОТА'.prm
.Sel(w->w.ToS('')).dst
.Wh(w-> not w.Pairwise.Any((a,b)->a+b in 'АООАА'))
.Cnt.pr

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Ответ: 72

Сколько существует n-значных чисел, записанных в m-ной системе счисления

8_18: Объяснение 8 задания экзамена ЕГЭ 2020 г. (со слов учащегося):

Сколько существует восьмизначных чисел, записанных в восьмеричной системе счисления, в которых все цифры различны и рядом не могут стоять 2 чётные или 2 нечётные цифры?

Типовые задания для тренировки

✍ Решение:

✎ Решение теоретическое:

Выпишем все четные и нечетные цифры, которые могут использоваться в 8-й с.с.:

четные: 0, 2, 4, 6 - итого 4 цифры
нечетные: 1, 3, 5, 7 - итого 4 цифры

Рассмотрим два случая построения числа по заданию: 1) начиная с четной цифры и 2) начиная с нечетной цифры. Изобразим схематично числа, указывая сверху возможное количество цифр на разряд:

1) с четной цифры:
3  4  3  3  2  2  1  1 = 3*4*3*3*2*2*1*1 = 432
ч  н  ч  н  ч  н  ч  н

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

2) с нечетной цифры:
4  4  3  3  2  2  1  1 = 4*4*3*3*2*2*1*1 = 576
н  ч  н  ч  н  ч  н  ч

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

Сложим количество вариантов в обеих случаях:

432 + 576 = 1008

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

###
'01234567'.Permutations // т.к. цифр итак 8 штук
.where(w->w.First<>'0') // первая цифра не может быть 0
.where(w->w.Pairwise.All((a,b)-> (a.ToDigit + b.ToDigit).IsOdd)) // проверка пар четных и нечетных
.count.print

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Ответ: 1008

Список в алфавитном порядке

8_13:

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

1. ААААА
2. ААААО
3. ААААУ
4. АААОА
…

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

✍ Решение:

✎ Решение теоретическое:

Данное задание лучше решать следующим образом. Подставим вместо букв цифры (А -> 0, О -> 1, У -> 2):

Видим, что каждая последующее число получается путем прибавления в столбик единицы к предыдущему числу. В троичной системе счисления! Т.к. цифр всего три.
Порядковый номер, написанный рядом с пунктом, всегда на единицу больше располагающейся рядом цифры в троичной системе счисления.
Значит, пункту под номером 242 будет соответствовать число 241 в троичной системе счисления.
Переведем 241 в 3-ю систему делением на 3:

        ^{остатки}
241 | 3 | 1
 80 | 3 | 2
 26 | 3 | 2
  8 | 3 | 2
  2 |   |

Перепишем остатки снизу вверх: 22221, им соответствуют буквы УУУУО

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

##
var d:='АОУ'.Order // сортируем по алфавиту
.Cartesian(5)
.Numerate.print

Смотрим слова и находим по номеру нужное слово:

… (241,[У,У,У,У,А]) (242,[У,У,У,У,О]) (243,[У,У,У,У,У])

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Результат: УУУУО

Подробное решение теоретическим способом смотрите на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_14: 8 задание. Демоверсия ЕГЭ 2018 информатика:

Все 4-буквенные слова, составленные из букв Д, Е, К, О, Р, записаны в алфавитном порядке и пронумерованы, начиная с 1.
Ниже приведено начало списка.

1. ДДДД
2. ДДДЕ
3. ДДДК
4. ДДДО
5. ДДДР
6. ДДЕД
…

Под каким номером в списке идёт первое слово, которое начинается с буквы K?

✍ Решение:

✎ Решение теоретическое:

Подставим вместо букв цифры (Д -> 0, Е -> 1, К -> 2, О -> 3, Р -> 4):

Видим, что каждое последующее число получается путем прибавления единицы в столбик к предыдущему (в пятеричной системе счисления! т.к. цифр всего пять).
Порядковый номер, написанный рядом с пунктом, всегда на единицу больше располагающейся рядом цифры в пятеричной системе счисления.
Определим число, которое получится, если мы в начале слова поставим букву К (остальные должны остаться нулями, т.к. числа идут по порядку, а нам необходимо первое, начинающееся с К):

K -> 2 -> 2000

Полученное число — 2000 — необходимо перевести из пятеричной системы счисления в десятичную, чтобы узнать порядковый номер:

По формуле разложения числа по степеням основания:

2000₅ = 2 * 5³ + 0 * 2² + 0 + 0 = 2 * 125 = 250₁₀

Поскольку порядковый номер числа всегда на единицу больше самого числа, то имеем 251.

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

###
var d:='декор'.Order // сортируем по алфавиту
.Cartesian(4) // d - массива из массивов символов 
.Numerate // нумерация
.where((i,w)->w[0] = 'к') // рассматриваем и номер и слово
.first[0].print // выводим именно номер

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Результат: 251

Подробное решение 8 (10) задания демоверсии ЕГЭ 2018 года смотрите на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_15:

Все 4-буквенные слова, составленные из букв П, Р, С, Т, записаны в алфавитном порядке.
Вот начало списка:

1. ПППП
2. ПППР
3. ПППС
4. ПППТ
5. ППРП
... ...

✍ Решение:

Результат: 65

Видеоразбор задания смотрите ниже:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

8_16:

Все четырёхбуквенные слова, составленные из букв В, Е, Г, А, Н записаны в алфавитном порядке и пронумерованы, начиная с 1. Начало списка выглядит так:

1. АААА
2. АААВ
3. АААГ
4. АААЕ
5. АААН
6. ААВА
…

Под каким номером в списке идёт первое слово, в котором нет буквы А?

✍ Решение:

✎ Решение теоретическое:

Пронумерованный список начинается со всех букв А. Представим, что А — 0, В — 1, Г — 2, Е — 3, Н — 4. Получим следующий список:

Такой список представляет из себя увеличивающиеся числа 5-й системы счисления.
Так как букве А соответствует 0, то первое (самое младшее) четырехзначное число без нуля — это 1111.
Чтобы вычислить под каким номером стоит данное число, переведем его в 10-ю систему и прибавим к результату единицу (так как порядковые номера в списке на единицу больше самих чисел):

1111₅ = 1 * 5³ + 1 * 5² + 1 * 5¹ + 1 * 5⁰ = 156
156 + 1 = 157

✎ Решение с использованием программирования:

PascalABC.net (использование LINQ, быстрое решение):

###
var d:='веган'.Order // сортируем по алфавиту
.Cartesian(4) // d - массива из массивов символов
.Select(x->x.JoinToString(''))// d - массив из строк 
.Numerate // нумерация
.where((i,w)->'а' not in w) // рассматриваем и номер и слово
.first[0].print // выводим именно номер

* LINQ (Language Integrated Query) — язык интегрированных запросов

Python:

С++:

Результат: 157

Видеорешение задания (теоретическое):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

Вероятность событий

8_17:

За четверть Василий Пупкин получил 20 оценок. Сообщение о том, что он вчера получил четверку, несет 2 бита информации.

Сколько четверок получил Василий за четверть?

✍ Решение:

Для решения данного задания необходимо вспомнить две формулы:

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

x = log₂(1/p)

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

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

p(A) = m/n

m - число случаев, способствующих событию А
n - общее число равновозможных случаев

Подставим в первую формулу известное значение — вероятность того, что Василий получил четверку:

2 = log₂(1/p);
    => 
1/p = 4; 
    =>
p = 1/4

Затем подставим известное по условию значение в формулу вероятности случайного события:

p = ?/20

Поскольку p мы уже нашли, подставим найденное значение и найдем искомое число — количество четверок за четверть:

1/4 = ?/20

? = 1/4 * 20 = 5

Результат: 5

Видеоразбор задания:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь (теоретическое решение)

Источник

Комбинаторный подход: информация по Хартли

Пример

Применение: цена информации

Вероятностный подход: энтропия Шеннона

Примеры

Свойства энтропии Шеннона

Энтропия пары

Примеры

Свойства энтропии Шеннона пары случайных величин

Условная энтропия Шеннона

Примеры

Свойства условной энтропии

Взаимная информация

Примеры

Свойства взаимной информации

Применение энтропии Шеннона: кодирование

Связь с энтропией

Применение энтропии Шеннона: шифрования с закрытым ключом

Алгоритмический подход: колмогоровская сложность

Сравнение языков программирования

Свойства колмогоровской сложности

Примеры

Несжимаемые строки

Колмогоровская сложность: вычислимость

Связь с энтропией Шеннона

Применение колмогоровской сложности: бесконечность множества простых чисел

Применение колмогоровской сложности: алгоритмическая случайность

Свойства случайных последовательностей

Заключение

Иллюстрация[править | править код]

Формула Шеннона[1][править | править код]

См. также[править | править код]

Примечания[править | править код]

Объяснение темы

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

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

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

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

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

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

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

Сколько вариантов шифра или кодовых слов

Перестановка букв в слове (каждая буква 1 раз)

Сколько существует n-значных чисел, записанных в m-ной системе счисления

Список в алфавитном порядке

Вероятность событий

Вам также может понравиться

Как найти мультики дикие скричеры

Как найти номер владельца по номеру автомобиля

Как найти в телефоне загрузки музыки

Добавить комментарий Отменить ответ

Формула Шеннона^[1][править | править код]