2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Частичная сумма латинского квадрата
Сообщение04.12.2012, 15:46 


18/05/09
109
Здравствуйте!
Задан латинский квадрат в виде матрицы $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 
Супермодератор
Аватара пользователя


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

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

 Профиль  
                  
 
 Posted automatically
Сообщение05.12.2012, 14:22 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: возвращено

 Профиль  
                  
 
 Re: Частичная сумма латинского квадрата
Сообщение14.12.2012, 12:48 


18/05/09
109
Палиндромы подобные нижеприведенному могут послужить решению поставленной задачи.
Чего-то у меня на экране не видны 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 


18/05/09
109
Для начала можно рассмотреть закономерности получения частичной суммы для строки вышеупомянутого латинского квадрата - одномерной последовательности $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 


18/05/09
109
Задан латинский квадрат в виде матрицы $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 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Хмм.
$\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 


18/05/09
109
Это формула для элемента.
Нужно получить сумму элементов частичного прямоугольника(не по модулю) из упомянутого латинского квадрата произвольного размера, включающего в себя элемент $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 
Заслуженный участник
Аватара пользователя


06/10/08
6422
А, я понял в чем проблема. Проблема в модуле.
$\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 


18/05/09
109
Вот пример квадрата. Остатки от деления на 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 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Упс, я ошибся, там верхний предел равен знаменателю дроби. Но приемы суммирования, вполне возможно, можно будет применить.

 Профиль  
                  
 
 Re: Частичная сумма латинского квадрата
Сообщение21.12.2012, 15:20 


18/05/09
109
$\sum_{j = 0}^b \lfloor \frac{aj + c}{b} \rfloor$? А если попробовать на участках $[0,2^m]$,$m<k$?

 Профиль  
                  
 
 Re: Частичная сумма латинского квадрата
Сообщение21.12.2012, 16:49 


18/05/09
109
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 


18/05/09
109
Похоже, направление решения бесперспективное :cry:

 Профиль  
                  
 
 Re: Частичная сумма латинского квадрата
Сообщение22.12.2012, 02:50 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Да, я тоже посидел с этими суммами, как-то они не считаются сильно быстрее, чем суммированием.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group