2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Раскрасить булев куб в (n+1) цвет
Сообщение30.07.2013, 17:47 


22/04/11
6
Здравствуйте!

Помогите, пожалуйста, решить следующую задачу. Нужно раскрасить булев куб так, чтобы цвета всех соседей каждой вершины, считая ее саму, были различны. Т.е. минимальное число нужных цветов - $(n+1)$.

Вот здесь http://ru-math.livejournal.com/708956.html в комментариях пишут, что можно раскрасить в $(n+1)$ цвет, если $n=2^{k}-1$.

Мне нужно раскрасить хотя бы в линейное по n число цветов. На крайний случай можно даже в полиномиальное)

Спасибо.

 Профиль  
                  
 
 Re: Раскрасить булев куб в (n+1) цвет
Сообщение30.07.2013, 19:23 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
Так а в чём проблема? Если Вы знаете раскраску для $2^k-1$, то по заданному $n$ подбираете натуральное число $m$ так, чтобы $2^{m-1}\leqslant n \leqslant 2^m-1$ и используете раскраску куба размерности $2^m-1$. Для неё понадобится $2^m$ цветов, что не больше, чем $2n$, т.е. линейно по $n$.
Другое дело - если раскраску для $2^k-1$ не знаете. Тогда, так и быть, подскажу 8-).
Нижняя оценка $n+1$, вообще говоря, не всегда достижима. Например, при $n=2$ нужно не менее $4$ цветов.

 Профиль  
                  
 
 Posted automatically
Сообщение30.07.2013, 20:11 
Супермодератор
Аватара пользователя


20/11/12
5727
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

antake, наберите, пожалуйста, формулы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

 Профиль  
                  
 
 Re: Раскрасить булев куб в (n+1) цвет
Сообщение11.08.2013, 12:16 
Админ форума
Аватара пользователя


19/03/10
8952
Вернул.

 Профиль  
                  
 
 Re: Раскрасить булев куб в (n+1) цвет
Сообщение11.08.2013, 14:22 


22/04/11
6
Уезжал в отпуск, поэтому молчал.
Dave, спасибо, я как раз случай $2^{k}-1$ и не могу решить. Если подскажете, буду очень благодарен!

 Профиль  
                  
 
 Re: Раскрасить булев куб в (n+1) цвет
Сообщение11.08.2013, 18:47 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
Насколько я понимаю, задача взята не "с потолка", а представляет собой задачу вычисления хэш-функции, позволяющей отслеживать и исправлять ошибку величиной не более один бит в передаваемой битовой последовательности длины $n$, при этом считается, что сам хэш передаётся по надёжному каналу.
Итак, пусть у нас есть булев куб размерности $n=2^k-1$ и нам нужно найти требуемую раскраску, используя $n+1=2^k$ цветов. Это означает, что нужно построить функцию от $2^k-1$ бит, возвращающую $k$-битное значение, причём значения функции при отличии аргумента не менее, чем на один, но не более, чем на два бита, должны быть различными (т.к. входные строки, отличающиеся на один бит, можно рассматривать как любую вершину и точку, соседнюю с ней, а отличающиеся на два бита - как две точки, соседние с какой-то вершиной; в обоих случаях выходные строки должны быть различными).
Попробуйте найти искомую функцию $F(x_1,x_2,\dots,x_{2^k-1})=(f_1,f_2,\dots,f_k)$ в виде: $$f_1=\bigoplus_{i \in A_1} {x_i},$$$$f_2=\bigoplus_{i \in A_2} {x_i},$$$$\quad \dots$$$$f_k=\bigoplus_{i \in A_k} {x_i},$$ где $\oplus$ - операция $XOR$, а $A_1,A_2,\dots,A_k$ - неизвестные подмножества множества $\{1,2,\dots,2^k-1\}$, т.е можно считать, что это подмножества исходных битов (не значений этих битов!, а самих битов как неких физических объектов, ячеек памяти, например). При этом нужно, чтобы выполнялись два свойства:
1) Каждый из $2^k-1$ битов принадлежит хотя бы одному из множеств $A_i$ (иначе при изменении этого бита ничего не изменится).
2) Для любых двух различных битов наборы множеств, которым они принадлежат, отличаются (иначе при смене значений двух этих битов в каждой сумме $\oplus$ произойдёт взаимоисключение или вообще ничего не произойдёт).

 Профиль  
                  
 
 Re: Раскрасить булев куб в (n+1) цвет
Сообщение12.08.2013, 20:10 


22/04/11
6
Dave, огромное спасибо! Буду разбираться)
Задача у меня из области расшифровки булевых функций, я не криптограф. Кстати, а Вы не знаете, а это опубликовано где-либо?

 Профиль  
                  
 
 Re: Раскрасить булев куб в (n+1) цвет
Сообщение12.08.2013, 20:40 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
Пожалуйста. Алгоритм придумал сам, по поводу публикации не подскажу. Но наверняка этим простейшим случаем уже кто-то занимался, раз уже более 50 лет назад придумали гораздо более сложные Коды Рида — Соломона.

 Профиль  
                  
 
 Re: Раскрасить булев куб в (n+1) цвет
Сообщение15.08.2013, 15:38 


22/04/11
6
Спасибо!
На спецсеме дважды рассказывали коды Рида-Соломона, что ж я их прослушал((

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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