Существует ли в математике мера структурированности?

[Eugene567]

Как ввести меру структурированности? К примеру есть щепотка песка. Из этой щепотки можно сделать часть кремниевого процессора. Здесь отвлечемся от химии и технологических процессов. Так вот, на мой взгляд, геометрия микросхемы содержит больше информации, чем та которую содержит ячейка кристаллической структуры частицы песка. Для описания кристаллической структуры достаточно информации о геометрии ячейки и о том как ее повторить. Если нагреем кремний до газообразного состояния, то для описания положения всех частиц системы в любой момент времени без учета скоростей, потребуется громадное количество информации и более того в этой информации не будет никакой упорядоченности. Такую информацию нельзя назвать структурированной. С другой стороны расположение транзисторов в микросхеме не является хаотичным. Таким образом, кремневая часть микропроцессора является чем-то промежуточным между сверхупорядоченностью, как в чистом кристалле и хаосом, как газообразном кремнии.

Или еще пример. Допустим у меня есть последовательность нулей и единиц. Если у меня все единицы: 1111111..., то такая информация очень упорядоченная и ее можно легко сжать. Если же у меня последовательность $a_{n}$ такая, что вероятность выпадения следующего нуля или единицы 50/50, то такая информация очень хаотична. Но если же последовательность вроде 1001100110011001..., то в ней обнаруживается паттерн 1001. Паттерн не обязательно должен быть постоянным, он может меняться. Такая информация не тривиальная, но и не хаотична. То есть обнаруживается структура. Вот как это измерить? Какую функцию f надо ввести? При этом функцию можно было бы применить для систем любой природы.

Если взять значение 1 - для систем абсолютно упорядоченных, а 0 - для абсолютно хаотичных, то должно поучиться, что-то типа:

$f(1111111...) = 1$

$f(a_{n}) = 0$, где $a_{n}$ - последовательность, такая что вероятность выпадения следующего нуля или единицы 50/50.

$f(p_{n}) = x$, где $p_{n}$ - последовательность с паттернами, $x\in[0;1]$

[Pphantom]

Eugene567 в сообщении #1410356 писал(а):

Как ввести меру структурированности?

Выяснить, что такое информационная энтропия (например, энтропия Шеннона или Реньи).

[Eugene567]

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

[Aritaborian]

Eugene567 в сообщении #1410370 писал(а):

Энтропия графа введена в математике?

Такой термин существует.

[fractalon]

Конечно, существует, и не одна. Те же тригсуммы или вопросы представимости чисел в виде сумм из множества - чем не метрики?

Более того, существует целая наука, изучающая их природу и взаимосвязь - [url=https://ru.wikipedia.org/wiki/Аддитивная_комбинаторика]аддитивная комбинаторика[/url]. Например, структурированность вашей $1001100110011001$ в её терминах означает, что множество единиц представимо в виде $A+B$, где $|B|$ не великой. Но если структура была бы не столь идеальной, можно было бы рассматривать, насколько маленькой надмножество (большое подмножество) представимо в таком виде, и делать это метрикой, и т. п.

Ещё на youtube есть курс лекций Владимира Арнольда "Измерение объективной степени случайности конечного набора точек". Не знаю, что там (всё руки не доходят посмотреть), но, судя по названию, вам может быть интересно.

(Оффтоп)

Админы, помогите, почему ссылка на википедию не вставляется нормально, хотя другая на её месте работает?

[Sender]

Можно ещё посмотреть в сторону колмогоровской сложности.

[Sender]

(fractalon)

Проблемы с урлом, возможно, возникают из-за кириллических символов в нём. Спасает урл-кодирование:
Аддитивная комбинаторика

[url=https://ru.wikipedia.org/wiki/%D0%90%D0%B4%D0%B4%D0%B8%D1%82%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D0%BA%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%B8%D0%BA%D0%B0]Аддитивная комбинаторика[/url]