Сколько битовых строк длины 10
Перейти к содержимому

Сколько битовых строк длины 10

  • автор:

6.1 Основные комбинаторные принципы

Решение многих комбинаторных задач основывается на двух фундаментальных правилах, называемых правилами суммы и произведения. Правило суммы . Если X 1 и X 2 – непересекающиеся конечные множества, содержащие n 1 и n 2 элементов соответственно, то объединение X 1 U X 2 содержит n 1 + n 2 элементов. Сформулированное правило можно распространить на случай произвольного числа слагаемых: если множества X 1 ,X 2 ,…,X k образуют разбиение множества X , то n = n 1 + n 2 +…+ n k , где n=|X| – число элементов множества X , а n i =|X i | – число элементов (мощность) множества X i , i = 1, 2,…, k . Напомним, что разбиением множества X называется набор его непересекающихся подмножеств, объединение которых дает все исходное множество X . Правило суммы можно приспособить и для подсчета числа элементов объединения двух множеств с непустым пересечением: (1) В самом деле, множества X 1 \X 2 и X 1 ∩X 2 образуют разбиение множества X 1 , поэтому

Аналогично Кроме того, множества X 1 \X 2 , X 2 \X 1 и X 1 ∩X 2 образуют разбиение множества X 1 U X 2 , так что

Подставляя сюда выражения X 1 \ X 2 = X 1 X 1 I X 1 , и
X 2 \ X 1 = X 2 X 1 I X 1 , приходим к утверждению (1).

□ Пример . Найдем количество положительных целых чисел, меньше или раных 1000, которые делятся на 3 или на 5. Количество элементов множества S положительных целых чисел, меньших 1000, которые делятся на 3, равно 1000 3 или 333. Количество элементов множества Т положительных целых чисел, меньших 1000, которые делятся на 5, равно 1000 5 или 200. Элементами множества S∩T являются целые числа, меньшие 1000, которые делятся на 5 и на 3, и поэтому делятся

на 15. Следовательно, S I T 1000 = 66 . Значит
= 15
S U T = S + T S I T = 333 + 200 − 66 = 467

Пример . Предположим, что на курсе из 100 студентов 60 человек изучают математику, 75 — историю, а 45 человек — и то, и другое. а) Сколько студентов изучают математику или историю? Пусть универсум U — группа из 100 студентов, М — множество студентов, изучающих математику, Н — множество студентов, изучающих историю. Тогда количество студентов, изучающих математику или историю,

равно M U H = M + H M I H = 60 + 75 − 45 = 90 .
б) Сколько студентов не изучают ни математику, ни историю?
Количество студентов, не изучающих ни математику, ни историю,
равно M I H . Но M I H = M U H , поэтому
I = = 100 − 90 = 10 .
M H M U H

Существует альтернативный метод решения приведенных выше задачи, который является более информативным. Рассмотрим его на следующем примере. Пример . Предположим, что из 100 студентов курса 50 изучают химию, 53 — математику, 42 — физику, 15 — химию и физику, 20 занимаются физикой 2

и математикой, 25 — математикой и химией и 5 студентов изучают все три предмета. а) Сколько студентов изучают хотя бы один из трех перечисленных предметов? б) Сколько студентов не изучают ни один из трех перечисленных предметов? в) Сколько студентов изучают только математику? г) Сколько студентов изучают физику или химию, но не изучают математику? д) Сколько студентов не изучают ни математику, ни химию? Поскольку 5 человек изучают все три предмета, а 15 человек — химию и физику, остаются 10 человек, изучающих химию и физику, но не изучающих математику. Аналогично, 25 — 5 = 20 человек занимаются математикой и химией, но не физикой, и 20 — 5 = 15 человек изучают математику и физику, но не изучают химию. Данную ситуацию изображает диаграмма Эйлера, приведенная на следующем рисунке слева Поскольку 50 студентов изучают химию и 35 из них уже учтены, то оставшиеся 15 изучают только химию. Аналогично, 53 студента занимаются математикой и 40 из них уже учтены. Поэтому 13 человек изучают только математику. Наконец, 42 студента изучают физику, и 30 из них уже учтены, поэтому 12 человек изучают только физику. а) Суммируя количество людей, принадлежащих семи непересекающимся подмножествам, получаем 90 тех, кто изучает хотя бы один из трех предметов. б) Поскольку 90 из 100 студентов изучают хотя бы один предмет, то 10090 = 10 человек не изучают ни один из этих трех предметов. в) Из диаграммы Эйлера следует, что 13 человек изучают только математику. г) Тридцать семь студентов занимаются химией или физикой, но не изучают математику. д) Из диаграммы Эйлера, изображенной на предыдущем рисунке справа, следует, что 75 человек изучают математику или физику. Поэтому 100 — 75 = 25 студентов не изучают ни математику, ни физику. □ Пример . Сколько имеется путей из вершины a в вершину b в сети, показанной на следующем рисунке (движение возможно только вправо или вверх)?

Обозначим множество всех путей из a в b через L ab и разобьем его на два непересекающихся подмножества: L acb – пути, проходящие через вершину c; L adb – пути, проходящие через вершину d. Имеем L ab = L acb + L adb . Очевидно, что интересующее нас количество путей зависит только от размеров решетки, поэтому обозначим через l m,n количество путей в сети, имеющей m горизонтальных и n вертикальных

вершин. Тогда последнее равенство можно записать в виде l 4,5 = l 3,5 + l 4,4 . И
вообще, l m , n = l m − 1, n + l m , n − 1 . Пользуясь этим соотношением, подсчитаем
количество путей на рисунке: + l 4,3 ) = l 2,5 + 3 l 3,4
l 4,5 = l 3,5 + l 4,4 = ( l 2,5 + l 3,4 ) + ( l 3,4 =
= ( l 1,5 + l 2,4 ) + 3 ( l 2,4 + l 3,3 ) = l 1,5 + 4 l 2,4 + 3 l 3,3 =
= l 1,5 + 4 ( l 1,4 + l 2,3 ) + 3 ( l 2,3 + l 3,2 ) = l 1,5 + 4 l 1,4 + 10 l 2,3 =
l 1,5 = 1, l 1,4 = 1, l 2,3 = 1 + 4 + 10 3 = 35
поскольку = 3 .

□ Другое фундаментальное правило дает, доказанная ранее Теорема . Мощность декартового произведения двух конечных множеств равна произведению их мощностей A × B = A B . Обобщение ее на декартово произведение n множеств называется правилом произведения . Рассмотрим упорядоченные наборы ( a 1 , a 2 ,…, a k ) заданной длины k . Предположим, что элемент a 1 из множества X 1 может быть выбран n 1 способами, т.е. X 1 = n 1 . При уже выбранном элементе a 1 , элемент a 2 из множества X 2 может быть выбран n 2 способами, т.е. X 2 = n 2 . При фиксированных a 1 и a 2 элемент a 3 из множества X 3 может быть выбран

n 3 способами, т.е. X 3 = n 3 и т.д. При фиксированных a 1 , a 2 ,…, a k–1 элемент
a k из множества X k может быть выбран n k способами. Тогда число

различных упорядоченных наборов равно произведению n 1 × n 2 × . × n k . Это означает, что Это правило часто называют комбинаторным принципом умножения. Доказательство. Будем доказывать теорему методом математической индукции. Базис индукции . Пусть n=2 . В этом случае все элементы 4

множества Х 1 х Х 2 , т. е. упорядоченные пары ( х 1 , х 2 ), можно расположить в виде прямоугольной таблицы со строками — элементами Х 1 и столбцами — элементами Х 2 . В этой таблице, очевидно, будет |X 1 | x |X 2 | элементов. Индуктивный переход . Предположим справедливость утверждения теоремы для n . Покажем, что для n+1 оно будет тоже справедливо. В самом деле, добавляя еще одно множество в декартово произведение, видим, что В случае, когда X 1 =X 2 =…=X k эта формула принимает вид X k = X k . В этом случае множество X называется алфавитом, его элементы – буквами, а элементы декартова произведения X k , т.е. упорядоченные пары из k букв ( x 1 , x 2 ,…, x k ) называют словами в алфавите X . Число k называется длиной слова. Пусть |X|=m , тогда формулу X k = X k можно сформулировать следующим образом: число слов длины k в алфавите из m букв равно m k . Пример . Битовая строка – это строка, состоящая из элементов множества <0, 1>, т.е. каждый из элементов имеет значение 0 или 1. Сколько существует битовых строк длины 5? Сколько существует битовых строк длины k ? Поскольку каждый символ строки может иметь значение 1 или 0, то существует два варианта выбора для каждой позиции. Следовательно, существует 2 x 2 x 2 x 2 x 2 = 2 5 битовых строк длины 5. По аналогичным соображениям, имеется 2 k битовых строк длины k . □ Пример . Используя правило произведения и правило суммы, найдем число различных трехзначных чисел, не содержащих одинаковых цифр, и число различных трехзначных чисел, содержащих хотя бы две одинаковые цифры Пусть a 1 , a 2 , a 3 – цифры трехзначного числа. Первую цифру a 1 можно выбрать девятью способами (в качестве нее можно взять любую цифру, кроме нуля); при фиксированной первой цифре вторую цифру a 2 можно выбрать также девятью способами (в качестве нее можно взять любую цифру, кроме a 1 ); наконец, при фиксированных первой и второй цифрах третью цифру можно выбрать восемью способами. По правилу произведения число трехзначных чисел, не содержащих одинаковых цифр, равно 9 · 9 · 8=648. Всего имеется 900 различных трехзначных чисел (от 100 до 999). Каждое из них либо содержит две одинаковые цифры, либо нет. Следовательно, имеется 900 – 648 = 252 различных трехзначных числа, содержащих хотя бы две одинаковые цифры. □

Третьим важным принципом является правило взаимно однозначного соответствия (правило биекции или правило равенства): множества A и B имеют одинаковое количество элементов | A | = | B | тогда и только тогда, когда между ними можно установить взаимно однозначное соответствие. В качестве примера применения этого принципа подсчитаем количество всевозможных подмножеств множества M, состоящего из n элементов. Так это количество не зависит от природы элементов множества М, возьмем M=<1,2,…,n>. Произвольному подмножеству A M поставим в соответствие двоичное слово α 1 α 2 . α n по следующему правилу: 1, еслиi A α i = 0 , еслиi A Это соответствие взаимно однозначное. Отсюда число всех подмножеств n – элементного множества равно числу двоичных слов длины n , т.е. равно 2 n . Пример . Сколькими способами можно разложить 10 монет разной стоимости по двум карманам? Формализуя задачу, отметим, что два кармана дадут два подмножества 10 – элементного множества; объединение множеств монет, лежащих в этих двух карманах, дает все множество; пересечение этих множеств пусто. Это значит, что те монеты, которые лежат в одном кармане, полностью определяют содержимое второго кармана. Используя правило биекции, можем сказать, что требуемых способов столько, сколько подмножеств в 10 – элементном множестве. Т.о. можем написать ответ: 2 10 =1024. □ Напомним также принцип Дирихле, который мы формулировали следующим образом. Пусть f : А —> В — функция, причем как A , так и В — конечные множества. Предположим, что А состоит из n элементов: a 1 , а 2 ,… a n . Принцип Дирихле гласит, что если |А|>|В| , то по крайней мере одно значение f встретится более одного раза. Проще говоря, найдется пара элементов a i ≠ a j , для которых f ( a i ) = f ( a j ) . Пример . Показать, что если в прямоугольнике со сторонами 6 и 8 сантиметров помещены пять точек, то существуют две точки, расстояние между которыми не более 5 сантиметров. Разделим исходный прямоугольник на четыре прямоугольника, размером 3 на 4 сантиметра каждый. Поскольку пять точек должны находиться либо внутри, либо на границах четырех прямоугольников, то хотя бы две точки должны быть либо внутри, либо на границе одного и того же прямоугольника размера 3 х 4. Но любые такие точки находятся на расстоянии не более 5 сантиметров. □

Как найти количество строк длины N,что не содержат S как подстроку?

Дано строку что может содержать только буквы A,B,C, тогда количество всех строк длины N из етих букв будет 3^N,тогда ответ на задачу : 3^N — (количество строк что имеют подстрочку S). Как эффективно посчитать количество строк что не содержат подстроки S? А да забыл сказать S содержит только буквы A,B. Ограничения:

N = 16 1  
2 AB 

Нам не подходит одна строка AB, тогда количество 3^2 - 1 = 8.Так же написал brute force алгоритм на котором можно проверить тестики:

from itertools import product n = int(input()) s = str(input()) a = [''.join(i) for i in product('ABC',repeat = n) if s not in "".join(i)] print(len(a)) 

Функции и операторы для битовых строк

В этом разделе описываются функции и операторы для проверки и обработки битовых строк, то есть значений типов bit и bit varying. (Хотя в этих таблицах упоминается только тип bit, вместо них можно использовать значения типа bit varying) Битовые строки поддерживают обычные операторы сравнения, показанные в таблице Операторы сравнения, а также операторы, перечисленные в Таблице 14.

Таблица 14. Операторы для битовых строк

bit || bit → bit

B'10001' || B'011' → 10001011

bit & bit → bit

Побитовое И (операнды должны быть одинаковой длины)

B'10001' & B'01101' → 00001

bit | bit → bit

Побитовое ИЛИ (операнды должны быть одинаковой длины)

B'10001' | B'01101' → 11101

bit # bit → bit

Побитовое исключающее ИЛИ (операнды должны быть одинаковой длины)

B'10001' # B'01101' → 11100

bit >> integer → bit

Битовый сдвиг вправо (с сохранением длины строки)

B'10001' >> 2 → 00100

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

Таблица 15. Функции для битовых строк

bit_count ( bit ) → bigint

Возвращает количество установленных битов (единиц) в битовой строке (эта операция также известна как «popcount»).

bit_length ( bit ) → integer

Возвращает количество битов в битовой строке.

length ( bit ) → integer

Возвращает количество битов в битовой строке.

octet_length ( bit ) → integer

Возвращает количество байтов в битовой строке.

overlay ( битовая_строка bit PLACING новая_подстрока bit FROM начало integer [ FOR число integer ] ) → bit

Заменяет в битовой_строке подстроку, начинающуюся с бита на позиции начало и длиной в заданное число бит, на новую_подстроку. Если число опущено, по умолчанию количество заменяемых битов определяется длиной новой_подстроки.

overlay(B'01010101010101010' placing B'11111' from 2 for 3) → 0111110101010101010

position ( подстрока bit IN битовая_строка bit ) → integer

Возвращает начальную позицию первого вхождения подстроки в битовой_строке или ноль, если такого вхождения нет.

position(B'010' in B'000001101011') → 8

substring ( битовая_строка bit [ FROM начало integer ] [ FOR число integer ] ) → bit

Извлекает из битовой_строки подстроку, начиная с бита на позиции начало (если таковая указана), и останавливаясь после заданного числа бит, если оно указано. Должен присутствовать хотя бы один из параметров: начало или число.

substring(B'110010111111' from 3 for 2) → 00

get_bit ( битовая_строка bit, n integer ) → integer

Извлекает из битовой строки n-й бит; первый (самый левый) бит имеет номер 0.

get_bit(B'101010101010101010', 6) → 1

set_bit ( битовая_строка bit, n integer, новое_значение integer ) → bit

Устанавливает для n-го бита в битовой строке новое_значение; первый (самый левый) бит имеет номер 0.

set_bit(B'101010101010101010', 6, 0) → 101010001010101010

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

44::bit(10) 0000101100 44::bit(3) 100 cast(-44 as bit(12)) 111111010100 '1110'::bit(4)::integer 14 

Обратите внимание, что приведение к типу «bit» без длины означает приведение к bit(1) и выдаст только один младший значащий бит целого.

Copyright © KVANTOM LLC, 2019-2023

Научный форум dxdy

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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

Вероятность встретить подстроку в строке

На страницу 1 , 2 След.

Вероятность встретить подстроку в строке
24.06.2007, 20:20

Последний раз редактировалось Willow 28.06.2007, 09:46, всего редактировалось 1 раз.

Меня уже длительное время мучает следующая задача:

Есть битовая строка $S$, длиной $n$бит. Какова вероятность, того что в ней отсутствует битовая подстрока $C$длиной $l$бит, при условии, что $l<n$.

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

$\left(\frac<2^l-1></p>
<p>Одна из моих оценок, \right)^$, не учитывает факта зависимости не встретить строку в соседних позициях, но я к сожалению не могу оценить ее неточность.

P.S. Дабы устранить неточность проявившуюся во время обсуждения, добавляю, что и строка и подстрока выбираются случайным образом из всего множества строк/подстрок равновероятно.

24.06.2007, 21:28

Заслуженный участник

Для того, чтобы ответить на этот вопрос нужно понять, сколько раз $l$может встретится в $n$. Допустим существует такое равенство $n - l = m$, тогда вероятность будет равна $ \frac 1 <m+1>$, что присутствует. Далее образуете сумму по индексу $k$, который указывает количество возможный подстрок ($n = k\cdot l + r$) и вычитаете из 1.

24.06.2007, 21:41

$n = k\cdot l + r$

1)Я не совсем понял формулу

2) по формуле $ \frac 1 <m+1>$, получается, что в любой строке с вероятностью <img decoding=.5$" />.5$" />.5$" /> встретится любая подстрока ровно один раз?

24.06.2007, 21:52

Заслуженный участник

Willow писал(а):

$n = k\cdot l + r$

1)Я не совсем понял формулу

Эта формула описывает остаточный член не использованных под подстроку байтов и максимальное количество подстрок, если подстрока встречается более чем один раз.
Пример.
Допустим сама строка $n = 12$, а длина подстроки равна $l = 5$. Какое наибольшее число подстрок (не пересекающихся) можно разместить на одной строке? Правильно: 2. Но при этом следует учитывать, что 2 байта всё равно остануться незанятыми ($12 - 2 \cdot 5 = 2$). В любом случае для нахождения максимального индекса должно выполняться неравенство $r < l$

Цитата:

2) по формуле $ \frac 1 <m+1>$, получается, что в любой строке с вероятностью <img decoding=.5$" />.5$" />.5$" /> встретится любая подстрока ровно один раз?

Хм, а это как? Вообще-то предполагается, что ответ будет зависеть от количесва ячеек, а само это количество будет зависеть от длин строки и подстроки.

Добавлено спустя 2 минуты 29 секунд:

Кстати, Вам надо ещё учитывать в самой сумме, что подстрока идёт сплошным потоком, т.е. не имеет разрывов

24.06.2007, 21:57

Вот строка из 12-ти символов
101010101010
сколько в ней раз может встретится строка из 5-ти символов 10101
ответ четыре раза а не два.

P.S. Возможно или я, что-то не договорил в условии, или абсолютно не понял вашей задумки.

24.06.2007, 23:27

Заслуженный участник

Willow писал(а):

Вот строка из 12-ти символов
101010101010
сколько в ней раз может встретится строка из 5-ти символов 10101
ответ четыре раза а не два.

P.S. Возможно или я, что-то не договорил в условии, или абсолютно не понял вашей задумки.

4 потому что у Вас пересечение есть. Я думала так: если есть первые 5 символов, то они уже не относятся к другой подстроке, т.е. вот так:

10101 0 10101 0 - две подстроки

Добавлено спустя 1 минуту 25 секунд:

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

Добавлено спустя 4 минуты 46 секунд:

Во вторых подсчёт вероятности под именно это условие проходит как-раз через $m+1$ячеек. Всего у Вас образовано 8 ячеек, в половине которых возможно появление Вашего кода.
Вам для этого надо вычислить саму вероятность появления подстроки в ячейки. Поскольку это будет зависеть от количества символов алфавита (ну у Вас их всего 2 - и их появление равновозможно), а во вторых появления нужной последовательности.
Я предлагаю тогда следующее: рассмотреть для начала саму подстроку и определить именно эту вероятность, исходя из вышеприведённых соображений. Домножать каждый раз количество ячеек на эту самую вероятность.
Прошу прощения, я просто изначально исходила из того, что появление подстроки имеет устойчивую вероятность в $\frac 1 2$. На практике безусловно это не совсем так.

Добавлено спустя 10 минут 7 секунд:

$\frac 1 <2^5></p><div class='code-block code-block-13' style='margin: 8px 0; clear: both;'>
<!-- 13theinternet -->
<script src=

Вероятности появления нужной подстроки в 5 символов из алфавита в 2 буквы ("1" и "0") равна $" />

Добавлено спустя 21 минуту 50 секунд:

Ну и наконец последнее - перечетав Ваше сообщение, я, честно говоря, не совсем хорошо поняла, что Вы делаете.
Проблема там вот в чём, обычно под вероятностью понимают отношение счастливых исходов ко всем исходам. Почему Вы вдруг решили рассмотреть именно эту строку? Это не всё $n$.
Количество всех строк будет описано так: $n = 2^<12>$ и будет содержать все перстановки "1" и "0" начиная с 000000000000 и заканчивая 111111111111. Или это у Вас просто какой-то конкретный пример?

Добавлено спустя 40 минут 42 секунды:

Вот, у меня возникла одна мысля, как эту задачу вообще очень просто сделать.
Для случая, когда строка не содержит подстрок. Нужно подсчитать вероятность не выпадания подстроки в ячейки. Она в этом случае будет ' - \frac 1 = \frac $. Т.е вероятность всех других вариантов. A теперь надо просто перемножить (пересечение эту вероятность по всем ячейкам, т.е. $\frac  ^< (m + 1)>$ или более общая формула $\frac <\frac <a^l - 1> ^< (m+1)>> $, где $a$- количество знаков, $l$длина подстроки и $m = n - l$, где $n$длина самой строки. Вот, вышла Ваша формула.

24.06.2007, 23:39

Я решаю следующую задачу:

Есть случайная строка, есть случайная подстрока. Надо оценить вероятность не появления (или появления какого-то конкретного числа раз) подстроки в строке. Причем единственная фиксированная информация это длины.

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

Capella писал(а):
Вот, вышла Ваша формула.

$a^n$

Не совсем моя, - у меня не было деления на

$l=1$

Если рассмотреть случай, когда , то окажется, что ни Ваша ни моя формулы не верны.

25.06.2007, 00:07

Заслуженный участник

$a^n$

Да, на не надо делить. Это я неправильно оценила новую омегу, она не будет больше зависеть от длины строки, а от длины подстроки

Добавлено спустя 3 минуты 56 секунд:

А какой Вы случай рассмотрели для $l=1$?
Для $n = 2$и $n = 3$вроде всё в порядке. Да и в целом формула $^ = ^$ верна, поскольку подразумевает одно распределение двух элементов по $n$ячейкам (в данном случае везде "0" например).

25.06.2007, 06:36

Дам. это я напутал.
Но формула все равно не правильная. Она не учитывает, то что события не независимы. И для случая $l=2$завышает примерно в два раза (ну как минимум для некоторых $n$).

25.06.2007, 15:59

Заслуженный участник

Да нет, думается мне формула правильная для счастливых случаев. Просто теперь осталось рассмотреть все возможные ячейки. По длине строки надо будет брать их пересечение, но учитывая то, что строк тоже много (вот где всё-таки приходит в игру $a^n$), надо будет рассмотреть их объединение. Пересечение будет иметь $m+1$членов, т.е. сколько ячеек возможно в одной строке (все они должны выполняться). А вот объединение будет задаваться через https://dxdy-04.korotkov.co.uk/f/f/8/f/f8f25e4580c418a51dc556db0d8d2b9382.png^n$- т.е. для $n = 4$Вы имеете 16 различных строк.
Например $n = 4, l = 2$. Вам подходит такой случай: $(\frac 3 4)^3$, т.е. Вы рассматриваете 3 варианта из четырёх для трёх ячеек - то что код не появляется в одной из подстрок какой-то отдельной строки. Это счастливые случаи. Их надо обощить для общего числа строк. Каждая строка имеет по 3 таких случая (здесь зависимость), но всего таких строк 16 - нужно взять их объединение.
Возможно лучше разбить строки по группам (например по количеству "1" в строке) и рассмотреть отдельно вероятность каждой группы, потому что там вероятности там не будут равны (вероятность для отдельных подстрок).

Добавлено спустя 32 минуты 17 секунд:

$a^n$

А всё таки я правильно делила в начале на . Это даёт Вам все возможные строки - и те, которые имеют в себе подстроку, и те, которые не имеют. Именно из этого числа надо выбирать теперь те строки, которую подстроку содержат.
А вообще для разных подстрок Вы имеете и разные вероятности: например для кода "10" в вышеприведённом примере найдётся 11 строк из 16, а для "11" только 8. поэтому лучше разбивать по группам и считать в них.

25.06.2007, 17:59

$\frac<2\frac<11></p>
<p>+2\frac>=\frac$ - вероятность вычисленная практически.

Если считать по формуле без деления то получается $\frac<27>$,
а если еще поделить на $a^n$то получится $\frac<27>$. Даже если домножить последнее на кол-во строк которые не встречались, то все равно ничего не получится.

25.06.2007, 18:14

Заслуженный участник

А что значит Ваша формула?

Смотрите, сделаем полный расклад.
Условие: какова вероятность, что подстрока "11" (например) не будет проходить в 4-значной строке. (это насколько я понимаю та идея, которую Вы хотите посчитать).

Решение: Очевидно, если строка не содержит знака "1" или содержит его на каком-то месте вероятность встречи искомой подстроки равна 0. Эта вероятность равна 1, если строка содержит три или четыре знака "1". Таким образом Вы получаете 5 заведомо удачных и 5 заведомо неудачных решений.
Рассмотрите теперь случай, когда количество "0" и "1" в строке по 2 знака. Перечислим все случаи:
1100, 1010, 1001, 0110, 0101, 0011
Имеем 3 удачных случая (2,3,5 случаи). Таким образом работая по группам имеем для групп с:
ни одной "1": 1 из 1
одна "1": 4 из 4
две "1": 3 из 6
три "1": 0 из 4
четыре "1": 0 из 1
Cкладывая ненулевые вероятности первых трёх групп получится: $\frac 1 + \frac 4 + \frac 3 = \frac 8 = \frac 1 2$.
В знаменателе стоит общее количество строк ($a^n$), а в числителе только тех строк, где точно не встречается "11".

25.06.2007, 20:36

$\left(\frac</p>
<p>Предложенный Вами вариант это частное решение. <br />Я хочу (пытаюсь) решить общий вариант. Я беру на угад последовательность короткую и длинную, и хочу знать вероятность того, что короткой последовательности не будет в длинной, или она там будет, ну скажем, ровно три раза. <br />Вот пример практических расчетов для последовательностей с длиной 4 и 2: <br />Таблица в которой приводится количество встреч строк 01 и 11 (для 10 и 00 варианты зеркальные) <br />_____01 11 <br />0000 <br />0001 1 <br />0010 1 <br />0011 1 1 <br />0100 1 <br />0101 2 <br />0110 1 <br />0111 1 2 <br />1000 <br />1001 1 <br />1010 1 <br />1011 1 1 <br />1100 1 <br />1101 1 1 <br />1110 2 <br />1111 3 <br />То есть, строка 01 - 10 раз встречается единожды, 1 раз дважды, и 5 раз не встречается. Строка 11 - 4 раза единожды, 2 раза дважды, один раз трижды и 9 раз не встречается. Вероятность встретить строки 01, 11 - 1/4. Таким образом: </p>
<ul>
вероятность не встретить строку длиной 2 символа в строке длиной 4 символа: <br />\frac+\frac\frac\right)2=\frac$

$\left(\frac</p>
<p>вероятность встретить строку длиной 2 символа 1 раз в строке длиной 4 символа: <br />\frac+\frac\frac\right)2=\frac$

$\left(\frac</p>
<p>вероятность встретить строку длиной 2 символа 2 раза в строке длиной 4 символа: <br />\frac+\frac\frac\right)2=\frac$

$\left(\frac</p>
<p>вероятность встретить строку длиной 2 символа 3 раза в строке длиной 4 символа: <br />\frac+\frac\frac\right)2=\frac$

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

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

25.06.2007, 21:59

Заслуженный участник

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

25.06.2007, 22:12

Заслуженный участник

Несколько соображений. Несложно оценить вероятность того, что короткая строка не будет совсем входить в длинную, в случае, когда $l$фиксировано, а $n$растёт.

Скажем, при $l=2$: Строки 01 и 10 не будут входить в $n+1$строк каждая, строки 00 и 11 --- в $F_<n+2>$ строк каждая, где $F_n=\frac1<\sqrt5>\left(\left(\frac2\right)^n+\left(\frac2\right)^n\right)$ --- последовательность Фибоначчи. Соответственно, вероятность равна $\frac<F_<n+2>+n+1>>\sim\frac\cdot\left(\frac4\right)^n$.
Видно, что "основной вклад" в вероятность дают строки 00 и 11. Так будет и в общем случае. А именно, пусть $l$фиксировано. Тогда при $n\to\infty$количество строк длины $n$, в которые не входит $\underset<l><\underbrace<00\ldots0>>$, асимптотически равно
$\sim\frac<\alpha-1>-l>\cdot\alpha^,$
где $\alpha=\alpha_l$--- корень уравнения $\alpha^<l+1>-2\alpha^l+1=0$, $\alpha>1$. При больших $l$он приближённо равен
$\alpha_l=2-2^<-l>-l2^-(3l^2+l)2^-\left(\frac83l^3+2l^2+\frac13l\right)2^+O(l^42^).$
(Если я не наврал в вычислениях. )

Для каждой из строк длины $l$, отличной от сплошных нулей или единиц, количество строк длины $n$, не содержащих её, есть $O(\beta^n)$, где $\beta=\beta_l<\alpha_l$. Соответственно, при фиксированном $l$и растущих $n$, вероятность получается
$\sim\frac<4(\alpha-1)>-l>\cdot\left(\frac\alpha2\right)^.$

Скорее всего, эти асимптотики можно написать и в случае, когда $l$может расти вместе с $n$, но достаточно медленно, но меня что-то ломает это проверять.
Вроде бы так.

Страница 1 из 2 [ Сообщений: 22 ] На страницу 1 , 2 След.
Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *