Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
| Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
|
Страница 1 из 2 |
[ Сообщений: 20 ] | На страницу 1, 2 След. |
|
| Автор | Сообщение | |
|---|---|---|
| novichok |
|
|
|
Есть вопрос по определителям в двоичной системе. Я не математик, пожалуйста отнестись к моему описанию с пониманием. Дано выражение Где + = 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] или сложения Посоветуйте, какую литературу почитать. Кол-во слагаемых и множителей может быть любым. |
||
| Вернуться к началу | ||
| Sonic |
|
|
|
Вы хотите упростить выражение [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] никак не связаны кроме имени? |
||
| Вернуться к началу | ||
| novichok |
|
|
|
Да мне нужно максимально упростить выражение исключая четные повторяющиеся слагаемые.
Кол-во переменных может очень большим и в этом случае простой метод перебора становиться не практичным. Вот еще пример выражения для примера для оптимизации [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] Вопрос в каком виде представить данное выражением для оптимизации ? Подходит ли для этой задачи - определитель ? |
||
| Вернуться к началу | ||
| 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] два раза повторен). И еще я не понял - откуда тут у Вас определители? |
||
| Вернуться к началу | ||
| novichok |
|
|
|
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] реальные выражения и раскрыв скобки мы получим в сокращенной форме выражение - которое и есть решение (множество) данного уравнения. Проблема в том, что кол-во слагаемых и множителей в реально задаче будет гораздо больше. Вопрос как оптимизировать процесс решения. Возможно все эти выражения можно записать в виде матриц и найти решение с помощью матриц (определителей), а не выражений? Я не математик и не знаком со всеми инструментами. Поэтому ищу совет у знающих людей. Что вы можете предложить, для уменьшения числа операций умножений, сложений и исключения повторяющихся значений? |
||
| Вернуться к началу | ||
| Sonic |
|
|
|
Так, ну 1-й пример я написал, как делать (выписывать решение явно я не буду - непедагогично, сам сейчас выписал - у меня все упростилось (в определенном смысле))
Цитата: [math]f[0]=a[0]b[0][/math] - значение 0 бита Вот это как-то странно выглядит. Из 1-го соотношения следует [math]f[0]\in\{0,1\}[/math], из этого и 2-го следует, что [math]p[0]=0[/math].[math]p[0]=f[0]|2= 0[/math]- перенос. значение f деленное на два Так. Нет. Вы берете задачу и пытаетесь мне ее выписать "на низком уровне". Наверное, зря Вы пытаетесь выписывать длинные выражения, думаю, проще будет сказать, чего Вы хотите. У Вас дано 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 раз. |
||
| Вернуться к началу | ||
| novichok |
|
|
|
Sonic писал(а): Так, ну 1-й пример я написал, как делать (выписывать решение явно я не буду - непедагогично, сам сейчас выписал - у меня все упростилось (в определенном смысле)) Цитата: [math]f[0]=a[0]b[0][/math] - значение 0 бита Вот это как-то странно выглядит. Из 1-го соотношения следует [math]f[0]\in\{0,1\}[/math], из этого и 2-го следует, что [math]p[0]=0[/math].[math]p[0]=f[0]|2= 0[/math]- перенос. значение f деленное на два Так. Нет. Вы берете задачу и пытаетесь мне ее выписать "на низком уровне". Наверное, зря Вы пытаетесь выписывать длинные выражения, думаю, проще будет сказать, чего Вы хотите. У Вас дано 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] - неизвестные |
||
| Вернуться к началу | ||
| Sonic |
|
|
|
novichok писал(а): Задача на высоком уровне - факторизация чисел Ага! Теперь я понял Описанный метод - подход, который требует доработки. Есть A * B = F, где A и B целые неизвестные и F - известное число Пример A*B = 15 Суть подхода - составит систему уравнений Жегалкина для каждого бита F[i] из значений битов A и B. Далее решить систему уравнений. Правда скажу сразу, что эту задачу без мозга слепо формально не решить. Но давайте подумаем... |
||
| Вернуться к началу | ||
| novichok |
|
|
|
Sonic писал(а): novichok писал(а): Задача на высоком уровне - факторизация чисел Ага! Теперь я понял Описанный метод - подход, который требует доработки. Есть A * B = F, где A и B целые неизвестные и F - известное число Пример A*B = 15 Суть подхода - составит систему уравнений Жегалкина для каждого бита F[i] из значений битов A и B. Далее решить систему уравнений. Правда скажу сразу, что эту задачу без мозга слепо формально не решить. Но давайте подумаем...Я предлагаю новый подход к этой задаче. У меня есть уже наработки по оптимизации, но они пока не столь эффективны. |
||
| Вернуться к началу | ||
| Sonic |
|
|
|
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 раз(а). |
||
| Вернуться к началу | ||
|
На страницу 1, 2 След. | [ Сообщений: 20 ] |
| Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
|---|---|---|---|---|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
7 |
561 |
20 ноя 2015, 22:05 |
|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
1 |
355 |
25 сен 2017, 20:09 |
|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
1 |
434 |
14 июн 2019, 21:16 |
|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
3 |
191 |
22 сен 2021, 20:13 |
|
| Матрица | 1 |
255 |
18 май 2015, 14:19 |
|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
6 |
707 |
23 сен 2017, 18:09 |
|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
1 |
336 |
03 ноя 2015, 11:51 |
|
|
Матрица
в форуме Линейная и Абстрактная алгебра |
5 |
493 |
02 янв 2017, 16:15 |
|
|
Матрица Якоби
в форуме Численные методы |
0 |
305 |
23 ноя 2016, 20:43 |
|
|
Матрица перехода
в форуме Линейная и Абстрактная алгебра |
12 |
390 |
05 ноя 2020, 16:15 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 6 |
| Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |