2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4, 5 ... 7  След.
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 15:10 
Аватара пользователя
приведите пример слова длины 8

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 15:14 
Аватара пользователя
alcoholist в сообщении #1379574 писал(а):
приведите пример слова длины 8
$w_1 = (a_{1}a_{2}a_{3}a_{4}a_{1}a_{2}a_{3}a_{4})$ - с отношением дружественности - каждый элемент дружит с каждым.

$w_2 = (a_{1}a_{1}a_{2}a_{2}a_{3}a_{3}a_{4}a_{4})$ - с отношением дружественности - никто не дружит.

Им будут соответствовать матрицы:

$\mathbf{M}(w_1) = \begin{pmatrix}
0 &  1 & 1 & 1\\
1 &  0 & 1 & 1\\
1 &  1 & 0 & 1\\
1 &  1 & 1 & 0
\end{pmatrix}$

$\mathbf{M}(w_2) = \begin{pmatrix}
0 &  0 & 0 & 0\\
0 &  0 & 0 & 0\\
0 &  0 & 0 & 0\\
0 &  0 & 0 & 0
\end{pmatrix}$

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 15:19 
Аватара пользователя
ну так перечислите матрицы, которые таким путем можно получить

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 15:27 
Аватара пользователя
alcoholist в сообщении #1379576 писал(а):
ну так перечислите матрицы, которые таким путем можно получить
Не понял Вас!
Я уже показал как по "слову" можно построить матрицу. Теперь, чтобы показать взаимно-однозначное соответствие между "словами" и матрицами, мне нужно показать обратное, что по любой квадратной матрице над полем $\mathbb{Z}_2 $ с нулевой главной диагональю можно построить "слово".

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 15:30 
Аватара пользователя
не всякой 0-1матрице соответствует слово... а каким?

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 15:30 
Аватара пользователя
situs в сообщении #1379575 писал(а):
Ему будет соответствовать матрица:
$M_{13}$ и $M_{24}$ тоже, видимо, нолики? $a_1$ с $a_3$ нигде не соседствуют и т.п.

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 15:32 
Аватара пользователя
alcoholist в сообщении #1379581 писал(а):
не всякой 0-1матрице соответствует слово... а каким?
Квадратная симметричная матрица над полем $\mathbb{Z}_2 $ с нулевой главной диагональю.

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 15:45 
Аватара пользователя
Что-то будет тяжело с биекцией: в алфавите длины $3$, все слова, где нет двух одинаковых букв подряд, отобразятся в одну и ту же матрицу

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 15:54 
Аватара пользователя
waxtep в сообщении #1379584 писал(а):
Что-то будет тяжело с биекцией: в алфавите длины $3$, все слова, где нет двух одинаковых букв подряд, отобразятся в одну и ту же матрицу
Не так. На алфавите длины 3 будет 8 разных "слов" и соответственно 8 разных матриц.

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 16:00 
Аватара пользователя
situs в сообщении #1379586 писал(а):
Не так. На алфавите длины 3 будет 8 разных "слов" и соответственно 8 разных матриц.
Возможно, чего-то не понимаю, скажите, какими будут матрицы для слов $xyzxyz$ и $xyxzyz$? Я из Вашего описания понял, что для обоих слов будет матрица с нулями на главной диагонали и единицами вне.

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 16:07 
Аватара пользователя
поточнее описание «слов»

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 16:13 
Аватара пользователя
waxtep в сообщении #1379588 писал(а):
матрицы для слов $xyzxyz$ и $xyxzyz$


$\mathbf{M}(xyzxyz) = \bordermatrix{
& x & y & z\cr
x & 0 & 1 & 1\cr
y & 1 & 0 & 1 \cr
z & 1 & 1 & 0  \cr}$

$\mathbf{M}(xyxzyz) = \bordermatrix{
& x & y & z\cr
x & 0 & 1 & 0\cr
y & 1 & 0 & 1 \cr
z & 0 & 1 & 0  \cr}$

-- 03.03.2019, 16:17 --

alcoholist в сообщении #1379590 писал(а):
поточнее описание «слов»
Куда еще точнее я пока не понимаю. Лучше скажите, что Вам непонятно?

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 16:23 
Аватара пользователя
situs в сообщении #1379593 писал(а):
waxtep в сообщении #1379588

писал(а):
матрицы для слов $xyzxyz$ и $xyxzyz$

$\mathbf{M}(xyzxyz) = \bordermatrix{
& x & y & z\cr
x & 0 & 1 & 1\cr
y & 1 & 0 & 1 \cr
z & 1 & 1 & 0  \cr}$

$\mathbf{M}(xyxzyz) = \bordermatrix{
& x & y & z\cr
x & 0 & 1 & 0\cr
y & 1 & 0 & 1 \cr
z & 0 & 1 & 0  \cr}$
Но ведь в $xyxzyz$ буква $z$ "дружит" (соседствует) и с буквой $x$, и с буквой $y$, почему в матрице отражена "дружба" $z$ только с $y$, но не с $x$?

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 16:31 
Аватара пользователя
situs
для того, чтобы буквы $x,y$ дружили, они должны расположиться обязательно как $\ldots xy\ldots xy\ldots$, или можно $\ldots xy\ldots yx\ldots$, или достаточно $\ldots xy\ldots$, как вы показали в примере для
situs в сообщении #1379593 писал(а):
$$\mathbf{M}(xyxzyz) = \bordermatrix{
& x & y & z\cr
x & 0 & 1 & 0\cr
y & 1 & 0 & 1 \cr
z & 0 & 1 & 0  \cr}$$

 
 
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 16:34 
Аватара пользователя
Ну, это обычные определения. Алфавит — произвольное множество; его элементы называются символами или буквами. Конечная последовательность символов — слово. Алфавит может быть и бесконечным (любой мощности), но Вас интересует только конечный алфавит.

Правила образования слов у Вас прописаны недостаточно подробно. Однозначно понятно, что если алфавит содержит $n$ символов, то слово должно содержать $2n$ символов, каждый по два раза.
Непонятно, могут ли соседние буквы быть одинаковыми. Например, в алфавите $A_1=\{a\}$ из одной буквы возможно только слово $aa$. Оно допустимо по вашим правилам или нет?
В алфавите $A=\{a,b\}$ из двух букв можно составить $6$ слов: $aabb$, $abab$, $abba$, $baab$, $baba$, $bbaa$. Какие из них допустимы?
В алфавите из $n$ букв по указанному правилу можно составить $\frac{(2n)!}{2^n}$ слов. Например, для $n=3$ получаем $\frac{6!}{2^3}=\frac{720}8=90$ слов.
С отношением дружественности неясностей больше.
Если буквы дружественные, они могут стоять в слове рядом или обязаны стоять в слове рядом? Во втором случае обе пары или достаточно одной пары? Если обе пары, то в одном и том же порядке или могут в разных? То есть, обязательно $xy\ldots xy$ или можно и $xy\ldots yx$?

В наиболее естественной для меня интерпретации отношение дружественности указывает, какие буквы могут, но не обязаны стоять рядом, при этом буква сама для себя является дружественной, то есть, две одинаковые буквы могут стоять рядом. Количество таких отношений дружественности для алфавита из $n$ букв равно $2^{\frac{n(n-1)}2}$, что при $n\geqslant 2$ не равно количеству слов. Легко проверить, что $$\frac{(2n)!}{2^n}>2^{\frac{n(n-1)}2}\text{ при }2\leqslant n\leqslant 12,$$ $$\frac{(2n)!}{2^n}<2^{\frac{n(n-1)}2}\text{ при }n>12.$$

Уточняйте, пожалуйста.

 
 
 [ Сообщений: 95 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 7  След.


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