Математический форум 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 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Матрица
в форуме Линейная и Абстрактная алгебра |
1 |
334 |
25 сен 2017, 20:09 |
|
Матрица
в форуме Ряды |
1 |
210 |
07 окт 2014, 15:47 |
|
Матрица
в форуме Линейная и Абстрактная алгебра |
1 |
400 |
14 июн 2019, 21:16 |
|
Матрица
в форуме Линейная и Абстрактная алгебра |
5 |
473 |
02 янв 2017, 16:15 |
|
Матрица | 1 |
232 |
18 май 2015, 14:19 |
|
Матрица | 1 |
424 |
20 сен 2014, 19:50 |
|
Матрица
в форуме Линейная и Абстрактная алгебра |
6 |
665 |
23 сен 2017, 18:09 |
|
Матрица
в форуме Линейная и Абстрактная алгебра |
7 |
523 |
20 ноя 2015, 22:05 |
|
Матрица
в форуме Линейная и Абстрактная алгебра |
3 |
157 |
22 сен 2021, 20:13 |
|
Матрица
в форуме Линейная и Абстрактная алгебра |
1 |
318 |
03 ноя 2015, 11:51 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 32 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |