2014 dxdy logo

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

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





Начать новую тему Ответить на тему
 
 Минимизация булевых функций для сжатия данных
Сообщение29.04.2017, 09:02 


18/05/09
77
Булеву функцию проще всего представить в виде ряда нулей и единиц. Чтобы минимизировать, нужно еще предварительно добавить список значений аргументов по крайней мере для единичных значений. Результат минимизации случайной булевой функции скорее всего займет намного больше места, чем исходный бинарный ряд. Есть ли способ представления формулы минимизированной случайной булевой функции, чтобы для ее хранения требовалось меньше места по сравнению с простейшим представлением?

 Профиль  
                  
 
 Re: Минимизация булевых функций для сжатия данных
Сообщение29.04.2017, 09:30 
Заслуженный участник


14/01/11
1043
0101 в сообщении #1213103 писал(а):
Есть ли способ представления формулы минимизированной случайной булевой функции, чтобы для ее хранения требовалось меньше места по сравнению с простейшим представлением?

Если речь именно о случайной булевой функции, то, очевидно, нет. Сжать можно только функцию, о которой известно, что её колмогоровская сложность в достаточной мере меньше размера её таблицы истинности.

 Профиль  
                  
 
 Re: Минимизация булевых функций для сжатия данных
Сообщение29.04.2017, 12:18 


18/05/09
77
Как оценить колмогоровскую сложность в этом случае?

 Профиль  
                  
 
 Re: Минимизация булевых функций для сжатия данных
Сообщение29.04.2017, 14:18 
Заслуженный участник


14/01/11
1043
Ну, учитывая её невычислимость, сделать это будет довольно затруднительно. :-) Способ "в лоб" - перебирать все машины Тьюринга по аналогии с https://en.wikipedia.org/wiki/Busy_beaver в порядке возрастания сложности и взять первую, которая, во-первых, остановится (вот тут основная сложность), а во-вторых, выдаст искомую двоичную последовательность.
Можно ограничиться вычислительными моделями вроде булевых схем или формул, чтобы не иметь дело с проблемой останова, что, вообще говоря, несколько ухудшит компрессию.

 Профиль  
                  
 
 Re: Минимизация булевых функций для сжатия данных
Сообщение29.04.2017, 16:40 
Заслуженный участник
Аватара пользователя


16/07/14
975
Москва
0101 в сообщении #1213125 писал(а):
Как оценить колмогоровскую сложность в этом случае?
Никак. Вы ни про какую функцию не сможете доказать, что ее сложность больше некоторой константы :-)
Зато у случайной функции от $n$ аргументов с вероятностью $0.99$ сложность будет хотя бы $0.99 \cdot 2^{2^n - 1}$.

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

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



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

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


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

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