2014 dxdy logo

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

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




 
 Найти обратное преобразование
Сообщение09.07.2020, 01:11 
Пусть у нас есть матрица
$\begin{equation*}
X =
\begin{pmatrix}
1 & 0 & 1 & 1\\
0 & 1 & 1 & 0\\
0 & 0 & 1 & 0\\
1 & 0 & 0 & 0
\end{pmatrix}
\end{equation*}$

и на нее действует преобразование

$F(X) = Y$
$\begin{equation*}

Y =
\begin{pmatrix}
1 & 0 & 1 & 0\\
1 & 0 & 0 & 0\\
0 & 0 & 1 & 1\\
1 & 0 & 1 & 0
\end{pmatrix}
\end{equation*}$

Преобразование работает следующим образом:
сначала для каждого элемента матрицы вычисляется сумма его и его 8 соседей(для крайних элементов,
представляем что матрица склеена как тор) и затем из этой матрицы вычитается исходная матрица X

$\begin{equation*}
\hat{X} =
\begin{pmatrix}

3 & 5 & 3 & 4\\
3 & 4 & 4 & 5\\
2 & 4 & 2 & 3\\
2 & 4 & 3 & 5
\end{pmatrix}
\end{equation*}$


Затем, для каждого элемента делаем следующее
Если $(\hat{x}_{ij}=3) | (x_{ij}= 1\quad   \&  \quad \hat{x}_{ij}=2)$ истинно то 1 иначе 0.

Так вот, вопрос.
Пусть нам известна матрица Y и преобразование $F()$
Можно ли найти $ X $

$X = F^{-1}(Y)$.

Ну то есть вопрос следующий.
Как, зная преобразование $F()$ найти $F^{-1}()$, и существует ли оно?

P.S. Я понимаю, что условие задачи сформулировал очень коряво, и отвечу на любой вопрос, если не поняли условие.

 
 
 
 Re: Найти обратное преобразование
Сообщение09.07.2020, 01:46 
Аватара пользователя
Это самое запутанное описание игры "Жизнь", которое я видел.

 
 
 
 Re: Найти обратное преобразование
Сообщение09.07.2020, 02:10 
Это необратимое преобразование, поэтому обратного не существует. Необратимость можно показать контрпримером: матрица из всех единиц преобразуется во все нули, а матрица из всех нулей тоже преобразуется во все нули. Поэтому когда у нас есть матрица Y из всех нулей, мы не сможем узнать, исходная матрица была из нулей или из единиц. Аналогично тому как при возведении числа в квадрат мы теряем информацию о том было оно положительным или отрицательным. Конечно можно пробовать найти все возможные предыдущие состояния, но в некоторых случаях будут десятки подходящих вариантов. Чтобы сделать многозначное обратное преобразование, видимо можно пробовать представить преобразование в виде системы уравнений, но это громоздко.

 
 
 
 Re: Найти обратное преобразование
Сообщение09.07.2020, 02:46 
ИСН в сообщении #1472995 писал(а):
Это самое запутанное описание игры "Жизнь", которое я видел.
Кстати, если я правильно помню, конфигурации типа "Сад Эдема" (у которых нет предков) были найдены еще где-то в 80-х годах.

 
 
 
 Re: Найти обратное преобразование
Сообщение11.07.2020, 10:54 
ИСН в сообщении #1472995 писал(а):
Это самое запутанное описание игры "Жизнь", которое я видел.

Да, загуглил, обычная игра жизнь. Спасибо, не знал как называется.


ИСН в сообщении #1472995 писал(а):
Это самое запутанное описание игры "Жизнь", которое я видел.
abicorios в сообщении #1472997 писал(а):
Это необратимое преобразование, поэтому обратного не существует. Необратимость можно показать контрпримером: матрица из всех единиц преобразуется во все нули, а матрица из всех нулей тоже преобразуется во все нули. Поэтому когда у нас есть матрица Y из всех нулей, мы не сможем узнать, исходная матрица была из нулей или из единиц. Аналогично тому как при возведении числа в квадрат мы теряем информацию о том было оно положительным или отрицательным. Конечно можно пробовать найти все возможные предыдущие состояния, но в некоторых случаях будут десятки подходящих вариантов. Чтобы сделать многозначное обратное преобразование, видимо можно пробовать представить преобразование в виде системы уравнений, но это громоздко.


А можно ли предсказать не обратное преобразование, а условную вероятность обратного преобразования?
ну то есть в каждой ячейки будет не 0 или 1, а вероятность того, что он 1

 
 
 
 Re: Найти обратное преобразование
Сообщение11.07.2020, 15:05 
Аватара пользователя
tetricka12 в сообщении #1473292 писал(а):
А можно ли предсказать не обратное преобразование, а условную вероятность обратного преобразования?
ну то есть в каждой ячейки будет не 0 или 1, а вероятность того, что он 1


Да, если у Вас есть вероятностное распределение на множестве всех конфигураций (допустим, из конечного числа $N$ клеток, тогда их $2^N$) на предыдущем шаге, то каждому прообразу конфигурации, имеющейся на текущем шаге, можно сопоставить условную вероятность, равную отношению вероятности этого прообраза к сумме вероятностей прообразов. Далее для условной вероятности того, что в данной клетке 1, можно просуммировать условные вероятности всех тех прообразов, у кого там стоит 1. Проблема в другом: какое распределение предполагать на множестве конфигураций? Если в исходный момент времени оно равномерное (все $2^N$ конфигураций равновероятны), то на следующем шагу уже так не будет. Получается, результат зависит от того, как давно у Вас идет процесс.

 
 
 
 Re: Найти обратное преобразование
Сообщение12.07.2020, 12:51 
Аватара пользователя
Кстати, игра "Жизнь" - наиболее известный, но лишь один представитель из класса подобных игр. Их можно изучать на разные свойства, например, насколько они благоприятны или нет для роста клеток. Мне как-то попалась статья об этом, может кому-то будет интересно - http://www.mathnet.ru/php/archive.phtml ... n_lang=rus

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

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


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