2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Энтропия клеточных автоматов
Сообщение22.04.2011, 19:51 
Аватара пользователя


22/09/08
174
Вот попалась такая "демонстрация" на Wolfram Demonstrations:
http://demonstrations.wolfram.com/Cellu ... taEntropy/
У кого нет Wolfram на компе, может, вроде, скачать бесплатный плеер
и посмотреть онлайн. Собственно, смотреть там особо нечего.
Клеточный автомат - это обобщение игры "Жизнь". Начальная двоичная конфигурация на прямой или плоскости преобразуется по определенным правилам в новую. Ну, я надеюсь, тему все знают. А вот энтропия этих конфигураций, это любопытно. Автор демонстрации предлагает вычислять энтропию данного состояния по простейшей формуле:
$H=-N(black)*P(black)*log_2 P(black)-N(white)*P(white)*log_2 P(white)$.
Но если сравнить узоры, порождаемые по правилу, скажем, 23 и по правилу 165, то первый явно упорядочен, а второй гораздо более хаотичен. Между тем энтропия получается одинаковой.
Ну, по такой формуле она и будет одинаковой.
Но, может, есть более корректные способы вычисления энтропии как меры хаотичности?
В свое время интересовался эти вопросом и даже какбе понял, чем энтропия Колмогорова-Синая отличается от топологической. Но всё это относилось к динамике траекторий во времени; на статические конфигурации чето мозгов не хватает :-(

 Профиль  
                  
 
 Re: Энтропия клеточных автоматов
Сообщение23.04.2011, 11:10 
Аватара пользователя


31/10/08
1244
Цитата:
Но всё это относилось к динамике траекторий во времени; на статические конфигурации чето мозгов не хватает
Все просто в качестве параметра t возьми координату чёрной точки.

Вот для двухмерного случая надо подумать.

 Профиль  
                  
 
 Re: Энтропия клеточных автоматов
Сообщение23.04.2011, 13:58 
Админ форума
Аватара пользователя


19/03/10
8952
 i 
Pavia в сообщении #437941 писал(а):
Все просто в качестве параметра t возьми координату чёрной точки.
Pavia, напоминаю: у нас на форуме принято обращение на "Вы".

 Профиль  
                  
 
 Re: Энтропия клеточных автоматов
Сообщение23.04.2011, 20:23 
Аватара пользователя


22/09/08
174
Toucan, Вы, пожалуйста, не придирайтесь (^_^),
ведь никаких грубостей не наблюдается!
Хоть кто-то ответил...
Конечно, меня беспокоит двумерный случай.
Если свести его к одномерному путем сканирования по строкам
и столбцам, то в смысле оценки порядка/хаоса явно многое
потеряется или исказится. Собственно, вопрос не мелкий и связан со многими приложениями - как корректно оценить меру хаотичности
двумерного бинарного массива? Догадываюсь, что полностью корректной
и замкнутой процедуры не существует; но любые соображения приветствуются!

 Профиль  
                  
 
 Re: Энтропия клеточных автоматов
Сообщение28.04.2011, 23:55 
Заслуженный участник


26/07/09
1559
Алматы
2Lesobrod
Цитата:
как корректно оценить меру хаотичности
двумерного бинарного массива?

В принципе, можно попробовать, ну например вычесть (поэлементно) из исходного массива (матрицы) его "сглаженную" версию, т.е. результат свертки с "гауссианом", а потом просуммировать ячейки. Это я к тому, что можно воспользоваться связью энтропии и количеством информации (в конечном счете, я предлагаю оценивать степень архивируемости узора-картинки; а для оценки этой величины ведь можно даже архиваторы типа winzip'а приспособить :) )...

 Профиль  
                  
 
 Re: Энтропия клеточных автоматов
Сообщение01.05.2011, 19:29 
Аватара пользователя


22/09/08
174
Circiter в сообщении #439803 писал(а):
2Lesobrod
ведь можно даже архиваторы типа winzip'а приспособить :) )...
Спасибо, вот это конструктивно!
Вообще, тема глубокая оказалась.
Нарисовал иконку 8х8 черно-белую с закономерностями;
в bmp заняла 246 байт, и ессессно 100% по узору. Сохранил в jpg.
100 едениц качества, черно-белый вариант тоже 100% сохранили узор,
но заняло 646 байт. Ниже качество занимает меньше места, но выдает
серые артефакты.
Упаковал в zip, уровень 9. Получилось 173 байта. Распаковалась отлично.
Игрался потом долго. Рекорд - 188 байт (против 246 в оригинале).
Я уверен, что это был совершенно случайный набор, и тем не менее,
удалочь передать его заметно меньшим количеством информации.

 Профиль  
                  
 
 Re: Энтропия клеточных автоматов
Сообщение02.05.2011, 13:48 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Ну заголовки BMP и DIB около 100 байт занимают ЕМНИП, так что на таких объемах будет сильно влиять.
Экспериментируйте с чистыми данными, без служебной информации.

 Профиль  
                  
 
 Re: Энтропия клеточных автоматов
Сообщение14.05.2011, 13:58 
Заслуженный участник


26/07/09
1559
Алматы
2Lesobrod
Может быть вас это заинтересует, H.Zenil, Compression-based investigation of the dynamical properties of cellular automata and other systems (arXiv:0910.4042v4 [cs.CC]).

 Профиль  
                  
 
 Re: Энтропия клеточных автоматов
Сообщение14.05.2011, 15:50 
Аватара пользователя


22/09/08
174
Спасибо!
Мужик серьёзно подошёл к вопросу.
Меня вот что еще интересует. Допустим, есть некий алгоритм
типа клеточного автомата или "хаотических" преобразований
Фейгенбаума, пекаря и т.п. Возможны как минимум два подхода
к оценке степени хаотичности (любым методом).
1. Анализ только конечного состояния.
2. Анализ всей последовательности состояний.
Например, если начать игру "Жизнь" со случайно заполненного поля,
уже на втором шаге получится структура, т.е. энтропия будет падать
(кстати, предел как-то можно оценить?..)
Я наблюдал и обратную картину, когда заполненное в шахматном порядке поле одним из автоматов превращалось в хаос (по виду, а количественно еще надо оценить).
Вот ищу материалы на эту тему..

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group