Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Матрица для XOR
СообщениеДобавлено: 18 май 2013, 17:19 
Не в сети
Начинающий
Зарегистрирован:
23 фев 2013, 14:38
Сообщений: 16
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Всем привет!

Есть вопрос по определителям в двоичной системе. Я не математик, пожалуйста отнестись к моему описанию с пониманием.

Дано выражение
Где + = xor в двоичном представлении
a[0], b[0], c[0] - переменные с возможным значением 0 или 1.
f[] - результат
Возможно ли ниже приведенную выражение как-то привести к матричному ввиду (определителю), чтобы в более простой и легкой форме производить операции умножения или сложения (исключающие или) с аналогичными выражениями.

[math](a[0]+b[0]+c[0])(b[0]+c[0])(c[0])[/math]

Возможны операции
умножение
[math](a[0]+b[0]+c[0])(b[0]+c[0])(c[0]) (a[1]+b[1]+c[1])(b[1]+c[1])(c[1])=f[0][/math]
или сложения
[math](a[0]+b[0]+c[0])(b[0]+c[0])(c[0]) (a[1]+b[1]+c[1])(b[1]+c[1])(c[1])=f[1][/math]
или сложения


Посоветуйте, какую литературу почитать. Кол-во слагаемых и множителей может быть любым.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 07:38 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Вы хотите упростить выражение [math]x_0(x_0+x_1)(x_0+x_1+x_2)...(x_0+x_1+...+x_n)[/math] над полем вычетов по модулю 2?
Если да, то его проще явно вычислять, оно очевидно, чему равно.
У Вас [math]a(0)[/math] и [math]a(1)[/math] никак не связаны кроме имени?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 10:09 
Не в сети
Начинающий
Зарегистрирован:
23 фев 2013, 14:38
Сообщений: 16
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Да мне нужно максимально упростить выражение исключая четные повторяющиеся слагаемые.
Кол-во переменных может очень большим и в этом случае простой метод перебора становиться не практичным.

Вот еще пример выражения для примера для оптимизации
[math]((a[1]b[0]+a[0]b[1])+f[1]+1)(a[1]b[0]a[0]b[1](a[2]b[0]+a[1]b[1]+a[0]b[2])+a[1]b[1]+f[2]+1).......()=1(mod 2)[/math]

Вопрос в каком виде представить данное выражением для оптимизации ? Подходит ли для этой задачи - определитель ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 11:02 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Давайте сначала с первым примером разберемся.
Обозначим [math]y_k=x_1+...+x_k[/math], получим [math]y_1y_2...y_n[/math]. Чему может быть равно это выражение по модулю 2? Либо 0, либо 1. [math]y_1y_2...y_n\equiv 1\pmod 2[/math] только в одном очевидном случае (найдите его). Теперь, когда мы нашли [math]y_k[/math], мы можем найти [math]x_k[/math]: [math]x_1=y_1, x_k=y_k-y_{k-1}[/math] и все. После этого можете просто восстановить СДНФ или СКНФ (или полином Жегалкина - что удобнее покажется) по значениям, может быть упростить ее, если получится.

Со вторым примером: все [math]a_j,b_j,f_j[/math] независимы? Или [math]f_j[/math] - те, что определены выше. И закон выписывания выражения я не понял - поясните (у Вас там [math]a[1]b[1][/math] два раза повторен).

И еще я не понял - откуда тут у Вас определители?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 12:36 
Не в сети
Начинающий
Зарегистрирован:
23 фев 2013, 14:38
Сообщений: 16
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Sonic писал(а):
Давайте сначала с первым примером разберемся.
Обозначим [math]y_k=x_1+...+x_k[/math], получим [math]y_1y_2...y_n[/math]. Чему может быть равно это выражение по модулю 2? Либо 0, либо 1. [math]y_1y_2...y_n\equiv 1\pmod 2[/math] только в одном очевидном случае (найдите его). Теперь, когда мы нашли [math]y_k[/math], мы можем найти [math]x_k[/math]: [math]x_1=y_1, x_k=y_k-y_{k-1}[/math] и все. После этого можете просто восстановить СДНФ или СКНФ (или полином Жегалкина - что удобнее покажется) по значениям, может быть упростить ее, если получится.

Со вторым примером: все [math]a_j,b_j,f_j[/math] независимы? Или [math]f_j[/math] - те, что определены выше. И закон выписывания выражения я не понял - поясните (у Вас там [math]a[1]b[1][/math] два раза повторен).

И еще я не понял - откуда тут у Вас определители?


Кол-во переменных и выражений в скобках может быть больше > 100. Полимон Жегалкина, это то что мне нужно получить и исключив повторяющиеся (четные) слагаемые после раскрытия скобок.

Второй пример не зависит от первого и соответственно значения f[i]. Повторяющиеся значения a[1]b[1] не случайность. Такое может быть при решении реальной задачи и мне как-то надо отслеживать повторяющиеся значения и удалять их.

Поясню для чего все это мне нужно
Наверняка вы знакомы с умножением чисел в двоичном виде.
Вот пример умножения двух чисел результат которого составляет 4 бита


[math]a[0]=1[/math]
[math]b[0]=1[/math]

[math]f[0],f[1],f[2],f[3][/math] - известные

[math]s[0]=a[0]b[0][/math]
[math]f[0]=a[0]b[0][/math] - значение 0 бита
[math]p[0]=f[0]|2= 0[/math] - перенос. значение f деленное на два

[math]s[1]=a[1]b[0]+a[0]b[1][/math]
[math]f[1]=s[1]+p[0]=a[1]b[0]+a[0]b[1][/math] - значение первого бита результат
[math]p[1]=f[1]|2=a[1]b[0]a[0]b[1][/math]

[math]s[2]=a[2]b[0]+a[1]b[1]+a[0]b[2][/math]
[math]f[2]=s[2]+p[1]=a[2]b[0]+a[1]b[1]+a[0]b[2]+a[1]b[0]a[0]b[1][/math]-значение второго бита результата
[math]p[2]=f[2]|2=a[2]b[0](a[1]b[1]+a[0]b[2]+a[1]b[0]a[0]b[1])+a[1]b[1](a[0]b[2]+a[1]b[0]a[0]b[1])+a[0]b[2](a[1]b[0]a[0]b[1])[/math]

[math]s[3]=a[0]b[3]+a[1]b[2]+a[2]b[1]+a[3]b[0][/math]
[math]f[3]=s[3]+p[2]=a[0]b[3]+a[1]b[2]+a[2]b[1]+a[3]b[0]+a[2]b[0](a[1]b[1]+a[0]b[2]+a[1]b[0]a[0]b[1])+a[1]b[1](a[0]b[2]+a[1]b[0]a[0]b[1])+a[0]b[2](a[1]b[0]a[0]b[1])[/math]-значение третьего бита результата

[math]s[n]+p[n-1]=f[n][/math]
[math]s[n]+p[n-1]+1=f[n]+1[/math]
[math]s[n]+p[n-1]+1+f[n]=1[/math]

[math](s[0]+1+f[0])(s[1]+p[0]+1+f[1])(s[2]+p[1]+1+f[2])(s[3]+p[3]+1+f[2])=1[/math]

Подставив вместо [math]s[n],p[n-1],f[n][/math] реальные выражения и раскрыв скобки мы получим в сокращенной форме выражение - которое и есть решение (множество) данного уравнения.
Проблема в том, что кол-во слагаемых и множителей в реально задаче будет гораздо больше. Вопрос как оптимизировать процесс решения.
Возможно все эти выражения можно записать в виде матриц и найти решение с помощью матриц (определителей), а не выражений?
Я не математик и не знаком со всеми инструментами. Поэтому ищу совет у знающих людей.
Что вы можете предложить, для уменьшения числа операций умножений, сложений и исключения повторяющихся значений?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 16:46 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Так, ну 1-й пример я написал, как делать (выписывать решение явно я не буду - непедагогично, сам сейчас выписал - у меня все упростилось (в определенном смысле))

Цитата:
[math]f[0]=a[0]b[0][/math] - значение 0 бита
[math]p[0]=f[0]|2= 0[/math]- перенос. значение f деленное на два
Вот это как-то странно выглядит. Из 1-го соотношения следует [math]f[0]\in\{0,1\}[/math], из этого и 2-го следует, что [math]p[0]=0[/math].

Так.
Нет.
Вы берете задачу и пытаетесь мне ее выписать "на низком уровне". Наверное, зря Вы пытаетесь выписывать длинные выражения, думаю, проще будет сказать, чего Вы хотите. У Вас дано 2 [math]N[/math]-битных числа и Вы хотите выписать полином Жегалкина их суммы и произведения?

Сейчас буду по мелочи писать, что понял. Квадратные скобки я писать не буду, ибо многабукаф.
[math]s_k=\sum\limits_{j=0}^ka_jb_{k-j}[/math]

[math]a_j,b_j[/math] известные или нет?

Не, дальше я не понял: с одной стороны Вы пишите, что [math]f_j[/math] известные, с другой стороны - выражаете их через [math]a_j,b_j[/math] неясно как.


Последний раз редактировалось Sonic 19 май 2013, 17:02, всего редактировалось 1 раз.
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 17:01 
Не в сети
Начинающий
Зарегистрирован:
23 фев 2013, 14:38
Сообщений: 16
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Sonic писал(а):
Так, ну 1-й пример я написал, как делать (выписывать решение явно я не буду - непедагогично, сам сейчас выписал - у меня все упростилось (в определенном смысле))

Цитата:
[math]f[0]=a[0]b[0][/math] - значение 0 бита
[math]p[0]=f[0]|2= 0[/math]- перенос. значение f деленное на два
Вот это как-то странно выглядит. Из 1-го соотношения следует [math]f[0]\in\{0,1\}[/math], из этого и 2-го следует, что [math]p[0]=0[/math].

Так.
Нет.
Вы берете задачу и пытаетесь мне ее выписать "на низком уровне". Наверное, зря Вы пытаетесь выписывать длинные выражения, думаю, проще будет сказать, чего Вы хотите. У Вас дано 2 [math]N[/math]-битных числа и Вы хотите выписать полином Жегалкина их суммы и произведения?

Сейчас буду по мелочи писать, что понял. Квадратные скобки я писать не буду, ибо многабукаф.
[math]s_k=\sum\limits_{j=0}^ka_jb_{k-j}[/math]


При умножение двух чисел в двоичном виде, значение переноса для нулевого разряда равно 0.

Задача на высоком уровне - факторизация чисел
Описанный метод - подход, который требует доработки.

Есть A * B = F, где A и B целые неизвестные и F - известное число
Пример
A*B = 15

Суть подхода - составит систему уравнений Жегалкина для каждого бита F[i] из значений битов A и B.
Далее решить систему уравнений.

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

Сразу не заметил

[math]s_k=\sum\limits_{j=0}^ka_jb_{k-j}[/math][/quote]
a[i] и b[k] - неизвестные

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 17:05 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
novichok писал(а):
Задача на высоком уровне - факторизация чисел
Описанный метод - подход, который требует доработки.

Есть A * B = F, где A и B целые неизвестные и F - известное число
Пример
A*B = 15

Суть подхода - составит систему уравнений Жегалкина для каждого бита F[i] из значений битов A и B.
Далее решить систему уравнений.
Ага! Теперь я понял :) Правда скажу сразу, что эту задачу без мозга слепо формально не решить. Но давайте подумаем...

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 17:12 
Не в сети
Начинающий
Зарегистрирован:
23 фев 2013, 14:38
Сообщений: 16
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Sonic писал(а):
novichok писал(а):
Задача на высоком уровне - факторизация чисел
Описанный метод - подход, который требует доработки.

Есть A * B = F, где A и B целые неизвестные и F - известное число
Пример
A*B = 15

Суть подхода - составит систему уравнений Жегалкина для каждого бита F[i] из значений битов A и B.
Далее решить систему уравнений.
Ага! Теперь я понял :) Правда скажу сразу, что эту задачу без мозга слепо формально не решить. Но давайте подумаем...


Я предлагаю новый подход к этой задаче.

У меня есть уже наработки по оптимизации, но они пока не столь эффективны.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Матрица для XOR
СообщениеДобавлено: 19 май 2013, 17:19 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
novichok писал(а):
Я предлагаю новый подход к этой задаче.
У меня есть уже наработки по оптимизации, но они пока не столь эффективны.
Не, я Вас понимаю :) Я Вас просто предупреждаю сразу, что это серьезная теоретическая задача, на которую легко убить кучу времени, вряд ли она решается так "насильно".
Но что и как делать - решать, конечно, Вам.

upd: я вот только не могу понять, как составляется выражение для [math]p_k[/math]. [math]p_k[/math] - это число добавляемых разрядов, т.е. [math]p_k=\frac{s_k-f_k}{2}[/math], а вот как выражать через [math]a_j,b_j[/math]...
Т.е. понятно, что [math]s_1=a_0b_1+a_1b_0\leqslant 2[/math], причем равенство достигается, если все биты равны 1, значит [math]p_1=a_0a_1b_0b_1[/math]. А в общем...
upd2:
[math]f_k+s_k+p_{k-1}\equiv 0 \pmod 2[/math] - это верно, но можно ли отбрасывать соотношение [math]p_k=\frac{s_k-f_k}{2}[/math]? Просто если нельзя, то его еще надо суметь переписать в виде сравнения по модулю 2.


Последний раз редактировалось Sonic 19 май 2013, 17:37, всего редактировалось 5 раз(а).
Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2  След.  Страница 1 из 2 [ Сообщений: 20 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Матрица

в форуме Линейная и Абстрактная алгебра

maksim-maksim

1

334

25 сен 2017, 20:09

Матрица

в форуме Ряды

roza96

1

210

07 окт 2014, 15:47

Матрица

в форуме Линейная и Абстрактная алгебра

Matematic123

1

400

14 июн 2019, 21:16

Матрица

в форуме Линейная и Абстрактная алгебра

kicultanya

5

473

02 янв 2017, 16:15

Матрица

в форуме Дискретная математика, Теория множеств и Логика

Lera25802580

1

232

18 май 2015, 14:19

Матрица

в форуме Дискретная математика, Теория множеств и Логика

illona

1

424

20 сен 2014, 19:50

Матрица

в форуме Линейная и Абстрактная алгебра

maksim-maksim

6

665

23 сен 2017, 18:09

Матрица

в форуме Линейная и Абстрактная алгебра

Nas_tya+-

7

523

20 ноя 2015, 22:05

Матрица

в форуме Линейная и Абстрактная алгебра

Ra1DeX

3

157

22 сен 2021, 20:13

Матрица

в форуме Линейная и Абстрактная алгебра

BusinkaAnna

1

318

03 ноя 2015, 11:51


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved