2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Булев куб
Сообщение04.10.2011, 21:56 
Аватара пользователя
Пожалуйста, объясните, что такое $N$-мерные булев куб, $\pm1$-куб и соответствующие симплексы?
В каких областях математики наиболее полно развита их теория? Где об этом можно подробно прочесть?

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 07:08 
Аватара пользователя
Совершенно непонятно о чем Вы спрашиваете. Даже мне. Даже с утра.

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 07:16 
serval в сообщении #489588 писал(а):
$N$-мерные булев куб

Это $\{ 0;1\}^N$ - граф на множестве векторов длины $N$ и нулями и единицами. Используется в аналитической геометрии, для решения задач булева линейного программирования (NP-задачи на графах) и еще много где.
serval в сообщении #489588 писал(а):
$\pm1$-куб

:shock:
serval в сообщении #489588 писал(а):
соответствующие симплексы

$N$ - мерный симплекс - полный граф на $N+1$ линейно независимых точках в $N$-мерном пространстве (при $N=0$ - точка, при $N=1$ - отрезок, при $N=2$ - треугольник, при $N=4$ - треугольная пирамида и т.п.). Извините за кривое определение. Вообще, их начинают изучать в аналитической геометрии, а потом где только не используют.
$\pm 1$-симплекс - :shock:

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 09:05 
Аватара пользователя
Sonic86 в сообщении #489638 писал(а):
serval в сообщении #489588 писал(а):
$\pm1$-куб

:shock:
Предполагаю, что это то же самое, что и булев куб, но только с плюсиками там, где были единички, и с минусиками там, где были нолики.

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 10:03 
Аватара пользователя
Цитата:
Совершенно непонятно о чем Вы спрашиваете.

Вот, вчера наткнулся, среди прочего

Информационные процессы, Том 8, № 4, 2008, стр. 201-204.
МАТЕМАТИЧЕСКИЕ МОДЕЛИ, ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ
"О квадратичных формах, равных единице на большом множестве вершин n-мерного куба"
Селиверстов, Любецкий


цитирую:
Цитата:
Кубом, или точнее n-мерным ±1-кубом, называется многогранник, вершинами которого являются точки с координатами ±1.

Я хотел узнать подробнее о свойствах этого куба. Похоже, это изобретение авторов статьи.

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 10:21 
Аватара пользователя
serval в сообщении #489678 писал(а):
Цитата:
Кубом, или точнее n-мерным ±1-кубом, называется многогранник, вершинами которого являются точки с координатами ±1.

Я хотел узнать подробнее о свойствах этого куба. Похоже, это изобретение авторов статьи.

Понятно, значит по-сути это же самое, что и булев куб. И какие именно свойства Вас интересуют? Может просто стоит почитать процитированную книжку дальше?

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 10:26 
epros в сообщении #489663 писал(а):
Предполагаю, что это то же самое, что и булев куб, но только с плюсиками там, где были единички, и с минусиками там, где были нолики.

Ааа, тогда понятно.
Я с перепугу подумал, что это размерность такая.

-- Ср окт 05, 2011 07:27:13 --

serval в сообщении #489678 писал(а):
Я хотел узнать подробнее о свойствах этого куба. Похоже, это изобретение авторов статьи.

Да обычный куб, образ при гомотетии булева $N$-мерного куба смотря, что авторы в нем откопали.

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 11:31 
Аватара пользователя
Цитата:
И какие именно свойства Вас интересуют?

Сейчас я попробую сформулировать.

В $3$-мерном случае вершины куба имеют координаты: $(0,0,0),\ (1,0,0),\ (0,1,0),\ (1,1,0),\ (0,0,1),\ (1,0,1),\ (0,1,1),\ (1,1,1)$
а вершины его грани построенной на первых дух ортах: $(0,0,0),\ (1,0,0),\ (0,1,0),\ (1,1,0)$

Пусть размерность $N=4$.
Вершины грани гиперкуба построенной на первых трех ортах будут иметь координаты (к координатам вершин куба добавится $0$ в четвертой позиции): $(0,0,0,0),\ (1,0,0,0),\ (0,1,0,0),\ (1,1,0,),\ (0,0,1,0),\ (1,0,1,0),\ (0,1,1,0),\ (1,1,1,0)$
Тогда через любые $3$ из этих вершин можно провести прямую (или правильно будет сказать - гиперплоскость размерности $N-1$ ?), это верно? Например, через точки имеющие ровно $2$ ненулевые координаты - $(1,1,0),\ (1,0,1),\ (0,1,1)$

Пусть размерность $N$ произвольна.
Как пронумеровать подмножества вершин грани содержащие по $N-1$ вершине, каждая из которых имеет ровно $3$ ненулевые координаты?

Можно ли выписать эти подмножества (или, хотя бы, вершины) не выковыривая их по одной из всего множества сочетаний из $N-1$ по $3$?

Нельзя ли использовать, например, то свойство, что все такие вершины принадлежат одной грани, а их радиус-векторы имеют одинаковую длину и значит их кратчайший обход можно совершить по дуге окружности?

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 11:43 
serval в сообщении #489702 писал(а):
Как пронумеровать подмножества вершин грани содержащие по $N-1$ вершине, каждая из которых имеет ровно $3$ ненулевые координаты?

В лоб. Вектору $\bar x = (x_1,..,x_n), x_j \in E$ можно поставить в соответствие число $a(\bar x) = \sum\limits_{k=0}^n x_k2^{k-1}$, номер вектора - это номер элемента в упорядоченном списке $a (\bar x)$. Причем условие $\sum\limits_k x_k = 3$ не требуется - это работает для любого числа единиц в векторе.
serval в сообщении #489702 писал(а):
Можно ли выписать эти подмножества (или, хотя бы, вершины) не выковыривая их по одной из всего множества сочетаний из $N-1$ по $3$?

Можно :-) и не обязательно для 3-х единиц. Соответствующий код на С++ занимает ровно 7 строк. Чтобы их выписать, нужно Вам выписать все эти векторы, упорядочить их покомпонентно и внимательно на них посмотреть - порядок виден, он не сложный.
serval в сообщении #489702 писал(а):
Нельзя ли использовать, например, то свойство, что все такие вершины принадлежат одной грани, а их радиус-векторы имеют одинаковую длину и значит их кратчайший обход можно совершить по дуге окружности?

Может и можно :roll: Хотя говорить "дуга окружности" там не совсем правильно.

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 12:53 
Аватара пользователя
Цитата:
не обязательно для 3-х единиц

В моей задаче это обязательное условие.
Цитата:
нужно Вам выписать все эти векторы

Все-таки, выписать все. Я надеялся, что существует способ аналитически ограничить это множество.
Цитата:
говорить "дуга окружности" там не совсем правильно

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

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 12:59 
serval в сообщении #489726 писал(а):
е-таки, выписать все. Я надеялся, что существует способ аналитически ограничить это множество.

Нет!!! Не поняли Вы меня.
Чтобы Вам увидеть закономерность в расположении упорядоченных векторов длины $n$ с $k$ единичками, Вам нужно самому взять например $n=6,k=3$ и ручками выписать все эти вектора, посмотреть на них и увидеть закономерность. После того, как Вы ее увидите, Вы сможете выписывать их сами или программно или даже через формулу для любых $n,k$ без полного перебора всех векторов.
serval в сообщении #489726 писал(а):
Я хотел сказать, что вдоль такой дуги вершины вписанного многоугольника имеющего эти вершины упорядочены естественным образом. Как бы вычислить порядок их следования?

Я имел ввиду, что если этот объект и есть, то это не дуга и не многоугольник (это плоские объекты) - нужно их называть соответствующими словами, указывающими на их $N$-мерность.

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 14:14 
Аватара пользователя
Цитата:
ручками выписать все эти вектора, посмотреть на них и увидеть закономерность.

Я пробовал. Как раз для случая $N=6$ пытался придумать алгоритм пересчета (вроде пересчета всех сочетаний) - и затруднился. Поэтому и обратился с вопросом.
Цитата:
это не дуга

Пусть будет гипердуга :-)
Можно я не буду лепить к каждому термину эту приставку? А то получается коряво. Просто будем понимать, по аналогии с гиперкубом, что все объекты имеют соответствующую размерность.
Но тут я запутался. С одной стороны, через $N-1$ такую точку можно провести прямую, а с другой - все они лежат на дуге окружности. где я ошибся? Или это шутки многомерия?

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 14:24 
Я в многомерье не рублю - это не ко мне.
serval в сообщении #489737 писал(а):
Я пробовал. Как раз для случая $N=6$ пытался придумать алгоритм пересчета (вроде пересчета всех сочетаний) - и затруднился. Поэтому и обратился с вопросом.

Так там всего 20 векторов, на листочек влазит. Просто выпишите их хоть перебором и отсортируйте. Если так трудно - используйте Excel или возьмите $n=4,k=2$.
Попробуйте выписать из рекуррентных соображений: т.е. вектор длины 6, у него 1-й элемент, либо 1, либо 0 - по этому признаку множество векторов разбивается на 2 класса, причем 1-й класс - это множество всех векторов длины 5 с 2-я единичками (размерность уменьшилась!), а 2-й класс - это множество всех векторов длины 5 с 3-я единичками (размерность уменьшилась снова!). Это соответствует рекуррентной формуле $C_n^k = C_{n-1}^{k-1}+C_{n-1}^k$ - слагаемые - это мощности классов.
Пишите результат здесь. Это просто.

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 15:33 
Аватара пользователя
Вот эти векторы для $N=6$ в порядке их появления при переборе сочетаний:

$(1,1,1,0,0,0)$
$(1,1,0,1,0,0)$
$(1,0,1,1,0,0)$
$(0,1,1,1,0,0)$
$(1,1,0,0,1,0)$
$(1,0,1,0,1,0)$
$(0,1,1,0,1,0)$
$(1,0,0,1,1,0)$
$(0,1,0,1,1,0)$
$(0,0,1,1,1,0)$
$(1,1,0,0,0,1)$
$(1,0,1,0,0,1)$
$(0,1,1,0,0,1)$
$(1,0,0,1,0,1)$
$(0,1,0,1,0,1)$
$(0,0,1,1,0,1)$
$(1,0,0,0,1,1)$
$(0,1,0,0,1,1)$
$(0,0,1,0,1,1)$
$(0,0,0,1,1,1)$

 
 
 
 Re: Булев куб
Сообщение05.10.2011, 15:46 
Аватара пользователя
Ну? А вопрос в чём? Да, они не лежат на дуге окружности. И на одной прямой не лежат. Приставку "гипер-" можно опустить, но только в том случае, если сами себя понимаете без неё.

 
 
 [ Сообщений: 27 ]  На страницу 1, 2  След.


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