Обобщение западных пожирающих алгоритмов

[Pavlovsky]

У нас есть свойство: F(X3+Y3,X2+Y2,X1+Y1)=F (X3,X2,X1)+F(Y3,Y2,Y1).
Есть пример функции: F (X3,X2,X1)=X3+2*X2+3*X1
Пусть x3=0;x2=1;x1=1;y3=1;y2=0;y1=1.
Чему равно?
1) F (X3,X2,X1)
2) F(Y3,Y2,Y1)
3) X3+Y3
4) X2+Y2
5) X1+Y1
6) F(X3+Y3,X2+Y2,X1+Y1)?

Напонминаю x3;x2;x1;y3;y2;y1 :{0,1}.

[vicvolf]

Source of the post
У нас есть свойство: F(X3+Y3,X2+Y2,X1+Y1)=F (X3,X2,X1)+F(Y3,Y2,Y1).
Есть пример функции: F (X3,X2,X1)=X3+2*X2+3*X1
Пусть x3=0;x2=1;x1=1;y3=1;y2=0;y1=1.
Чему равно?
1) F (X3,X2,X1)
2) F(Y3,Y2,Y1)
3) X3+Y3
4) X2+Y2
5) X1+Y1
6) F(X3+Y3,X2+Y2,X1+Y1)?

Напонминаю x3;x2;x1;y3;y2;y1 :{0,1}.

Добрый день!
1) F (X3,X2,X1)=5
2) F(Y3,Y2,Y1)=4
3) X3+Y3=1
4) X2+Y2=1
5) X1+Y1=10 (в двоичной системе 2) - это не суммирование по модулю 2. a просто суммирование в двоичной системе - не надо путать!
6) F(X3+Y3,X2+Y2,X1+Y1)=9

Следовательно F(X3+Y3,X2+Y2,X1+Y1)= 9 и F (X3,X2,X1)+F(Y3,Y2,Y1)=5+4=9 ч.т.д

Это верно в любой системе счисления двоичной. троичной, десятичной!

Виктор B.

[Pavlovsky]

F(X3+Y3,X2+Y2,X1+Y1)=F(1,1,10)
10 это как? Мы вроде договорились, что F функция от булевых переменных :{0,1}.

[vicvolf]

Source of the post
F(X3+Y3,X2+Y2,X1+Y1)=F(1,1,10)
10 это как? Мы вроде договорились, что F функция от булевых переменных :{0,1}.

Добрый вечер!
Давайте рассмотрим Вашу линейную функцию F(X3,X2,X1)= X3+2X2+3X1
Она уже упорядочена F(0,0,1)=3>F(0,1,0)=2>F(1,0,0)=1 (1)
Поэтому на пожирающей последовательности достигается безусловный максимум
F(0,0,1)=3>F(0,1,0)=2>F(1,0,0)=1
F(0,1,1)=5>F(1,0,1)=4>F(1,1,0)=3
F(1,1,1)=6
При вашем условии X1+X2+X3<=2, удолетворяющему условию a1<=a2<=a3 (2)условный максимум также достигается на пожирающей последовательности F(0,1,1)=5Вы согласны, что если если ищется максимум линейной функции булевых переменных, у которой переменные упорядочены по условию (1) и для коеффициентов линейной функции ограничений выполняются условие (2), то условный максимум достигается на пожирающей последовательности?Виктор B.

[Pavlovsky]

Вы согласны, что если если ищется максимум линейной функции булевых переменных, у которой переменные упорядочены по условию (1) и для коеффициентов линейной функции ограничений выполняются условие (2), то условный максимум достигается на пожирающей последовательности?

Да согласен. Этот факт мы установили. Смотри пост №16.

[vicvolf]

Source of the post

Вы согласны, что если если ищется максимум линейной функции булевых переменных, у которой переменные упорядочены по условию (1) и для коеффициентов линейной функции ограничений выполняются условие (2), то условный максимум достигается на пожирающей последовательности?

Да согласен. Этот факт мы установили. Смотри пост №16.

Добрый вечер!
Вы согласны, что условный максимум линейной функции булевых переменных, у которой переменные упорядочены по условию (1) достигается на пожирающей последовательности. если линейных ограничений больше одного и для всех них выполняются условие (2)?

Виктор B.

[Pavlovsky]

Вы согласны, что условный максимум линейной функции булевых переменных, у которой переменные упорядочены по условию (1) достигается на пожирающей последовательности. если линейных ограничений больше одного и для всех них выполняются условие (2)?

A вот это утверждение надо доказать.

He могу понять, причем тут свойство аддитивности? Вы уводите обсуждение куда то в сторону. Я просил дать четкое определение аддитивной функции от N булевых переменных.

Определение:
F(X3+Y3,X2+Y2,X1+Y1)=F (X3,X2,X1)+F(Y3,Y2,Y1);
a так же определение в вашей статье:
Функция c булевыми переменными обладает свойством аддитивности, если
F (x1,…1,…1,…xn) = F(x1,…1,…0,… xn) + F(x1,…0,…1,… xn).

Вызывает множество вопросов и представляется непонятной строкой математических символов.

[vicvolf]

[quote name='Pavlovsky' post='128525' date='10.12.2009, 3:59']
У нас есть свойство: F(X3+Y3,X2+Y2,X1+Y1)=F (X3,X2,X1)+F(Y3,Y2,Y1).
Есть пример функции: F (X3,X2,X1)=X3+2*X2+3*X1
Пусть x3=0;x2=1;x1=1;y3=1;y2=0;y1=1.
Чему равно?
1) F (X3,X2,X1)
2) F(Y3,Y2,Y1)
3) X3+Y3
4) X2+Y2
5) X1+Y1
6) F(X3+Y3,X2+Y2,X1+Y1)?

Напонминаю x3;x2;x1;y3;y2;y1 :{0,1}.
[/quote]
Добоый день!
Этот пример не подходит, так как переменная при суммировании выходит из области своего определения, в данном случае булевых значений.
B данном случае при Х1=1 У1 может принимать только значение 0.

C уважением Виктор B.

так же определение в вашей статье:
Функция c булевыми переменными обладает свойством аддитивности, если
F (x1,…1,…1,…xn) = F(x1,…1,…0,… xn) + F(x1,…0,…1,… xn).

Вызывает множество вопросов и представляется непонятной строкой математических символов.
[/quote]
Добрый вечер!
Определение аддитивности в моей статье, как раз не выводит булевую переменную из своей области определения.

Виктор B.

[Pavlovsky]

Этот пример не подходит, так как переменная при суммировании выходит из области своего определения, в данном случае булевых значений.
B данном случае при Х1=1 У1 может принимать только значение 0.

Понятно. B такой редакции линейная функция от булевых переменных действительно является аддитивной. A можете привести еще пример аддитивной функции? Кроме линейной функции.

Определение аддитивности в моей статье, как раз не выводит булевую переменную из своей области определения.

Вот толко линейная функция не обладает свойством F (x1,…1,…1,…xn) = F(x1,…1,…0,… xn) + F(x1,…0,…1,… xn). Смотри пример в пост №36.

[vicvolf]

Source of the post

Этот пример не подходит, так как переменная при суммировании выходит из области своего определения, в данном случае булевых значений.
B данном случае при Х1=1 У1 может принимать только значение 0.

Понятно. B такой редакции линейная функция от булевых переменных действительно является аддитивной. A можете привести еще пример аддитивной функции? Кроме линейной функции.

Определение аддитивности в моей статье, как раз не выводит булевую переменную из своей области определения.

Вот толко линейная функция не обладает свойством F (x1,…1,…1,…xn) = F(x1,…1,…0,… xn) + F(x1,…0,…1,… xn). Смотри пример в пост №36.

Добрый вечер!
Вот пожалуйста пример аддитивной нелинейной функции булевых переменных:
F(0,0)=0
F(0,1)=1
F(1,0)=7
F(1,1)=8

F(0,0)+F(0,1)=F(0,1)=1
F(0,1)+F(1,0)=F(1,1)=8
F(0,0)+F(1,0)=F(1,0)=7

C уважением Виктор B.