2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Частичная сумма латинского квадрата
Сообщение04.12.2012, 15:46 
Здравствуйте!
Задан латинский квадрат в виде матрицы $M[ n,n]
$  M[i,j]=\frac{((2i+1)(2j+1) \mod 2^{k+1})-1}{2}$
$0\leqslant i \leqslant n -1$
$0\leqslant j\leqslant n -1$
$n =2^{k}$
$k \in \mathbb{N}$
Подскажите, пожалуйста,
известны ли какие-нибудь алгоритмы вычисления суммы элементов
частичного прямоугольника произвольного размера, включающего в себя
элемент $M[0,0]$.
Что касается попыток решения -
задачу можно свести к подсчету количества единичных значений булевых функций,
определяющих двоичные разряды $M[i,j]$,
но получается сложно очень,
нужны дополнительные свойства чтобы понизить сложность,
может быть решение уже кем-то найдено

 
 
 
 Posted automatically
Сообщение04.12.2012, 20:58 
Аватара пользователя
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены ТеХом, отсутствуют попытки решения.

Наберите формулы ТеХом, как написано здесь, приведите попытки решения, после чего сообщите в теме Сообщение в карантине исправлено и тогда тема будет возвращена.

 
 
 
 Posted automatically
Сообщение05.12.2012, 14:22 
Аватара пользователя
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: возвращено

 
 
 
 Re: Частичная сумма латинского квадрата
Сообщение14.12.2012, 12:48 
Палиндромы подобные нижеприведенному могут послужить решению поставленной задачи.
Чего-то у меня на экране не видны 4 последних столбца.
Латинский квадрат -это таблица Кэли, а что можно сказать по поводу идентификации этого палиндрома?


$\left(\begin{array}{ccccccccccccccccccccccccccc}
0&1&2&2&3&4&4&5&6&4&5&6&6&7&8&8&9&10&8&9&10&10&11&12&12&13&14\\
1&3&5&5&5&5&9&7&5&5&5&5&7&7&7&9&9&9&9&7&5&9&9&9&9&11&13\\
2&5&8&8&7&6&14&9&4&6&5&4&8&7&6&10&9&8&10&5&0&8&7&6&6&9&12\\
2&5&8&4&5&6&6&5&4&6&7&8&6&7&8&6&7&8&10&9&8&8&9&10&6&9&12\\
3&5&7&5&5&5&7&5&3&7&7&7&7&7&7&7&7&7&11&9&7&9&9&9&7&9&11\\
4&5&6&6&5&4&8&5&2&8&7&6&8&7&6&8&7&6&12&9&6&10&9&8&8&9&10\\
4&9&14&6&7&8&8&5&2&8&9&10&6&7&8&4&5&6&12&9&6&6&7&8&0&5&10\\
5&7&9&5&5&5&5&3&1&9&9&9&7&7&7&5&5&5&13&11&9&9&9&9&5&7&9\\
6&5&4&4&3&2&2&1&0&10&9&8&8&7&6&6&5&4&14&13&12&12&11&10&10&9&8\\
4&5&6&6&7&8&8&9&10&4&5&6&6&7&8&8&9&10&4&5&6&6&7&8&8&9&10\\
5&5&5&7&7&7&9&9&9&5&5&5&7&7&7&9&9&9&5&5&5&7&7&7&9&9&9\\
6&5&4&8&7&6&10&9&8&6&5&4&8&7&6&10&9&8&6&5&4&8&7&6&10&9&8\\
6&7&8&6&7&8&6&7&8&6&7&8&6&7&8&6&7&8&6&7&8&6&7&8&6&7&8\\
7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7&7\\
8&7&6&8&7&6&8&7&6&8&7&6&8&7&6&8&7&6&8&7&6&8&7&6&8&7&6\\
8&9&10&6&7&8&4&5&6&8&9&10&6&7&8&4&5&6&8&9&10&6&7&8&4&5&6\\
9&9&9&7&7&7&5&5&5&9&9&9&7&7&7&5&5&5&9&9&9&7&7&7&5&5&5\\
10&9&8&8&7&6&6&5&4&10&9&8&8&7&6&6&5&4&10&9&8&8&7&6&6&5&4\\
8&9&10&10&11&12&12&13&14&4&5&6&6&7&8&8&9&10&0&1&2&2&3&4&4&5&6\\
9&7&5&9&9&9&9&11&13&5&5&5&7&7&7&9&9&9&1&3&5&5&5&5&9&7&5\\
10&5&0&8&7&6&6&9&12&6&5&4&8&7&6&10&9&8&2&5&8&8&7&6&14&9&4\\
10&9&8&8&9&10&6&9&12&6&7&8&6&7&8&6&7&8&2&5&8&4&5&6&6&5&4\\
11&9&7&9&9&9&7&9&11&7&7&7&7&7&7&7&7&7&3&5&7&5&5&5&7&5&3\\
12&9&6&10&9&8&8&9&10&8&7&6&8&7&6&8&7&6&4&5&6&6&5&4&8&5&2\\
12&9&6&6&7&8&0&5&10&8&9&10&6&7&8&4&5&6&4&9&14&6&7&8&8&5&2\\
13&11&9&9&9&9&5&7&9&9&9&9&7&7&7&5&5&5&5&7&9&5&5&5&5&3&1\\
14&13&12&12&11&10&10&9&8&10&9&8&8&7&6&6&5&4&6&5&4&4&3&2&2&1&0
\end{array}\right)$

 
 
 
 Re: Частичная сумма латинского квадрата
Сообщение16.12.2012, 11:11 
Для начала можно рассмотреть закономерности получения частичной суммы для строки вышеупомянутого латинского квадрата - одномерной последовательности $A[n]$,
для которой
$  A[i]=\frac{((2i+1)(2j+1) \mod 2^{k+1})-1}{2}$
$0\leqslant i \leqslant n -1$
$0\leqslant j\leqslant n -1$
$n =2^{k}$
$k \in \mathbb{N}$

 
 
 
 Re: Частичная сумма латинского квадрата
Сообщение20.12.2012, 12:52 
Задан латинский квадрат в виде матрицы $M[ n,n]
$  M[i,j]=\frac{((2i+1)(2j+1) \mod 2^{k+1})-1}{2}$
$0\leqslant i \leqslant n -1$
$0\leqslant j\leqslant n -1$
$n =2^{k}$
$k \in \mathbb{N}$
При необходимости можно показать пример.

Нужно получить сумму элементов частичного прямоугольника из упомянутого латинского квадрата произвольного размера, включающего в себя элемент $M[0,0]$.
Один из способов
1. Предполагаем, что произвольный элемент латинского квадрата $M[X,Y]$ представлен в двоичном виде.
2. Представляем формулу каждого разряда $M[X,Y]$ в виде арифметического полинома.
3. Произвольный разряд $X_i$ числа $X$(для $Y$ то же самое) заменяем таким образом,
что $  X_i=\frac{x_i+1}{2}$. Чтобы аргумент $X_i$ принимал значения
$0,1$, аргумент $x_i$ должен принимать значения $-1,1$.
4.Полученные полиномы нужно представить в каноническом виде - учесть,
что $x_i^2=1$, и раскрыть все скобки.
Теперь множество принимаемых произвольным аргументом $x_i$ и $y_i$
можно расширить до $[-1,0,1]$.

Вот пример функции $P[x,y]$(некоего палиндрома) получаемой в итоге для $k=3$ сообщение #658250
Как ее использовать для получения суммы элементов частичного прямоугольника из упомянутого латинского квадрата при необходимости напишу, это по сути не сложный алгоритм.
Проблема в том, насколько отличаются минимальные размеры формулы для $P[x,y]$(и как их вообще искать) от минимальных размеров формулы для $M[X,Y]$

 
 
 
 Re: Частичная сумма латинского квадрата
Сообщение20.12.2012, 13:27 
Аватара пользователя
Хмм.
$\frac{(2i + 1)(2j +1) \mathop{\mathrm{mod}} 2^{k+1} - 1}{2} = \frac{(4ij + 2i + 2j + 1) \mathop{\mathrm{mod}} 2^{k+1} - 1}{2} = \frac{(4ij + 2i + 2j) \mathop{\mathrm{mod}} 2^{k+1}}{2} = (2ij + i + j) \mathop{\mathrm{mod}} 2^{k}.$
Просуммировать это не проблема.

 
 
 
 Re: Частичная сумма латинского квадрата
Сообщение20.12.2012, 13:51 
Это формула для элемента.
Нужно получить сумму элементов частичного прямоугольника(не по модулю) из упомянутого латинского квадрата произвольного размера, включающего в себя элемент $M[0,0]$, т.е. некоторую сумму остатков от деления.
К примеру квадрат $[16][16]$.Края частичного прямоугольника $M[0,0]$,$M[0,7]$,$M[5,7]$,$M[5,0]$. Можно просто сложить 48 чисел. Но если будет охвачена большая область большого квадрата...
0101 в сообщении #659039 писал(а):
Для начала можно рассмотреть закономерности получения частичной суммы для строки вышеупомянутого латинского квадрата - одномерной последовательности $A[n]$,
для которой
$  A[i]=\frac{((2i+1)(2j+1) \mod 2^{k+1})-1}{2}$
$0\leqslant i \leqslant n -1$
$0\leqslant j\leqslant n -1$
$n =2^{k}$
$k \in \mathbb{N}$

Тоже нужно суммировать не по модулю остатки от деления.

 
 
 
 Re: Частичная сумма латинского квадрата
Сообщение20.12.2012, 14:07 
Аватара пользователя
А, я понял в чем проблема. Проблема в модуле.
$\sum_{i = 0}^m \sum_{j = 0}^n 2ij + i + j  = \frac{mn(m+2)(n+2)-mn}{2}$.
Осталось посчитать, сколько раз надо вычесть $2^k$, то есть $\sum_{i = 0}^m \sum_{j = 0}^n \lfloor \frac{2ij+i+j}{2^k} \rfloor$.
При фиксированном $i$ выражение $\frac{2ij+i+j}{2^k}$ задает линейную функцию, вычисление суммы типа $\sum_{j = 0}^n \lfloor \frac{aj + c}{b} \rfloor$ можно посмотреть в "Конкретной математике", параграф 3.5.

 
 
 
 Re: Частичная сумма латинского квадрата
Сообщение20.12.2012, 14:31 
Вот пример квадрата. Остатки от деления на 32.
$\left(\begin{array}{cccccccccccccccc}\\0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\1&4&7&10&13&0&3&6&9&12&15&2&5&8&11&14\\2&7&12&1&6&11&0&5&10&15&4&9&14&3&8&13\\3&10&1&8&15&6&13&4&11&2&9&0&7&14&5&12\\4&13&6&15&8&1&10&3&12&5&14&7&0&9&2&11\\5&0&11&6&1&12&7&2&13&8&3&14&9&4&15&10\\6&3&0&13&10&7&4&1&14&11&8&5&2&15&12&9\\7&6&5&4&3&2&1&0&15&14&13&12&11&10&9&8\\8&9&10&11&12&13&14&15&0&1&2&3&4&5&6&7\\9&12&15&2&5&8&11&14&1&4&7&10&13&0&3&6\\10&15&4&9&14&3&8&13&2&7&12&1&6&11&0&5\\11&2&9&0&7&14&5&12&3&10&1&8&15&6&13&4\\12&5&14&7&0&9&2&11&4&13&6&15&8&1&10&3\\13&8&3&14&9&4&15&10&5&0&11&6&1&12&7&2\\14&11&8&5&2&15&12&9&6&3&0&13&10&7&4&1\\15&14&13&12&11&10&9&8&7&6&5&4&3&2&1&0\end{array}\right)$
Прямоугольник ширина 5, высота 3 от верхнего левого угла. Сумма 73. Совпадает?
По поводу пола и потолка из "Конкретной математики" очень интересно, только с ходу не вник.

 
 
 
 Re: Частичная сумма латинского квадрата
Сообщение20.12.2012, 14:31 
Аватара пользователя
Упс, я ошибся, там верхний предел равен знаменателю дроби. Но приемы суммирования, вполне возможно, можно будет применить.

 
 
 
 Re: Частичная сумма латинского квадрата
Сообщение21.12.2012, 15:20 
$\sum_{j = 0}^b \lfloor \frac{aj + c}{b} \rfloor$? А если попробовать на участках $[0,2^m]$,$m<k$?

 
 
 
 Re: Частичная сумма латинского квадрата
Сообщение21.12.2012, 16:49 
0101 в сообщении #661392 писал(а):
$\sum_{j = 0}^b \lfloor \frac{aj + c}{b} \rfloor$? А если попробовать на участках $[0,2^m]$,$m<k$?
Это и так легко считается. Лучше говорить об участках, кратных $2^m$,$m<k$.

 
 
 
 Re: Частичная сумма латинского квадрата
Сообщение21.12.2012, 23:04 
Похоже, направление решения бесперспективное :cry:

 
 
 
 Re: Частичная сумма латинского квадрата
Сообщение22.12.2012, 02:50 
Аватара пользователя
Да, я тоже посидел с этими суммами, как-то они не считаются сильно быстрее, чем суммированием.

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


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