2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 среднее количество двоичных векторов, удовл. равенству
Сообщение24.04.2009, 12:30 
помогите найти среднее количество векторов, удовлетворяющих равенству
${X_1}{X_2} \oplus {X_2}{X_3} \oplus ..... \oplus {X_{n - 1}}{X_n} = \varphi ({X_1}, \ldots ,{X_n})$

нужно рассмотривать все булевые функции зависящие от$({X_1}, \ldots ,{X_n})$

[/math]

 
 
 
 
Сообщение24.04.2009, 12:41 
Аватара пользователя
Не понял формулировку.
Требуется найти среднее по всем булевым функциям $\varphi$ от $n$ переменных количество наборов, удовлетворяющих равенству?

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

Если так, то все просто
$\frac{1}{|P_2(n)|} \sum\limits_{\varphi\in P_2(n)}\#\{x|f(x) = \varphi(x)\}$ не зависит от $f$.

Так что, скорее всего, имелось в виду что-то другое

 
 
 
 
Сообщение24.04.2009, 16:45 
Xaositect писал(а):
Не понял формулировку.
Требуется найти среднее по всем булевым функциям $\varphi$ от $n$ переменных , удовлетворяющих равенству?

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

Если так, то все просто
$\frac{1}{|P_2(n)|} \sum\limits_{\varphi\in P_2(n)}\#\{x|f(x) = \varphi(x)\}$ не зависит от $f$.

Так что, скорее всего, имелось в виду что-то другое


количество наборов \[({X_1}, \ldots ,{X_n})\] которые удовлетворяют равенству
\[{X_1}{X_2} \oplus {X_2}{X_3} \oplus ... \oplus {X_{n - 1}}{X_n} = 1\], я подсчитал что ровняеться \[{2^{n - 1}} - {2^{\left\lfloor {\frac{n}
{2}} \right\rfloor  - 1 + n(\bmod 2)}}\]

существует \[{2^{{2^n}}}\] булевых функций зависящих от \[({X_1}, \ldots ,{X_n})\]. Нужно для каждой функции подсчитать количество наборов, которые удовлетворяют ${X_1}{X_2} \oplus {X_2}{X_3} \oplus ..... \oplus {X_{n - 1}}{X_n} = \varphi ({y_1}, \ldots ,{y_k})$, сложить их и делить на \[{2^{{2^n}}}\]

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

a1020 писал(а):
Xaositect писал(а):
Не понял формулировку.
Требуется найти среднее по всем булевым функциям $\varphi$ от $n$ переменных , удовлетворяющих равенству?

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

Если так, то все просто
$\frac{1}{|P_2(n)|} \sum\limits_{\varphi\in P_2(n)}\#\{x|f(x) = \varphi(x)\}$ не зависит от $f$.

Так что, скорее всего, имелось в виду что-то другое


количество наборов \[({X_1}, \ldots ,{X_n})\] которые удовлетворяют равенству
\[{X_1}{X_2} \oplus {X_2}{X_3} \oplus ... \oplus {X_{n - 1}}{X_n} = 1\], я подсчитал что ровняеться \[{2^{n - 1}} - {2^{\left\lfloor {\frac{n}
{2}} \right\rfloor  - 1 + n(\bmod 2)}}\]

существует \[{2^{{2^n}}}\] булевых функций зависящих от \[({X_1}, \ldots ,{X_n})\]. Нужно для каждой функции подсчитать количество наборов, которые удовлетворяют ${X_1}{X_2} \oplus {X_2}{X_3} \oplus ..... \oplus {X_{n - 1}}{X_n} = \varphi ({y_1}, \ldots ,{y_k})$, сложить их и делить на \[{2^{{2^n}}}\]


простите, вышла апечатка, нужно для каждой функции подсчитать количество наборов, которые удовлетворяют ${X_1}{X_2} \oplus {X_2}{X_3} \oplus ..... \oplus {X_{n - 1}}{X_n} = \varphi ({X_1}, \ldots ,{X_n})$, сложить их и делить на \[{2^{{2^n}}}\][/quote]

 
 
 
 
Сообщение24.04.2009, 17:04 
Аватара пользователя
Проведите замену $\varphi(x_1,\dots, x_n) = x_1x_2\oplus x_2x_3\oplus\dots\oplus x_{n-1}x_n \oplus \psi(x_1,\dots,x_n)$
Если $\varphi$ пробегает все функции, то и $\psi$ пробегает все функции.

 
 
 
 
Сообщение24.04.2009, 17:36 
Xaositect писал(а):
Проведите замену $\varphi(x_1,\dots, x_n) = x_1x_2\oplus x_2x_3\oplus\dots\oplus x_{n-1}x_n \oplus \psi(x_1,\dots,x_n)$
Если $\varphi$ пробегает все функции, то и $\psi$ пробегает все функции.


не понял мысли, чем это поможет в подсчете?

 
 
 
 
Сообщение24.04.2009, 18:09 
Аватара пользователя
Количество наборов, где $\varphi(x_1,\dots, x_n) = x_1x_2\oplus x_2x_3\oplus\dots\oplus x_{n-1}x_n$, равно количеству наборов, где $\psi(x_1,\dots,x_n) = 0$

 
 
 
 
Сообщение24.04.2009, 18:23 
Xaositect писал(а):
Количество наборов, где $\varphi(x_1,\dots, x_n) = x_1x_2\oplus x_2x_3\oplus\dots\oplus x_{n-1}x_n$, равно количеству наборов, где $\psi(x_1,\dots,x_n) = 0$


Спасибо, понял, только как доказать что \[\psi ({X_1}, \ldots ,{X_n})\] пробегает все функции?

 
 
 
 
Сообщение24.04.2009, 19:37 
Аватара пользователя
a1020 в сообщении #207810 писал(а):
Спасибо, понял, только как доказать что \[\psi ({X_1}, \ldots ,{X_n})\] пробегает все функции?

Ну это совсем просто.
Для любого $\psi$ существует $\varphi$, из которого оно получается. Формулу напишите сами :)

 
 
 
 
Сообщение24.04.2009, 19:44 
Xaositect писал(а):
a1020 в сообщении #207810 писал(а):
Спасибо, понял, только как доказать что \[\psi ({X_1}, \ldots ,{X_n})\] пробегает все функции?

Ну это совсем просто.
Для любого $\psi$ существует $\varphi$, из которого оно получается. Формулу напишите сами :)


спасибо большое

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group