2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 6, 7, 8, 9, 10, 11  След.
 
 Re: Al Zimmermann - Sums and Products
Сообщение05.12.2015, 19:01 
Аватара пользователя


21/02/10
1594
Екатеринбург
Похоже ничего лучшего не придумать.
Линейка Голомба + adding an offset to the sequence

А при поиске линейки Голомба ничего лучшего чем finite affine planes и finite projective planes не найти. Хотя эти алгоритмы не дают оптимального результата.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение06.12.2015, 01:03 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #1079764 писал(а):
Похоже ничего лучшего не придумать.
Линейка Голомба + adding an offset to the sequence

А при поиске линейки Голомба ничего лучшего чем finite affine planes и finite projective planes не найти. Хотя эти алгоритмы не дают оптимального результата.

Ведь все таки есть лучше решения. Что если взять решение finite planes и его улучшить отжигом? У меня правда не получилось.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение06.12.2015, 10:18 
Заслуженный участник
Аватара пользователя


19/12/10
1546
dimkadimon в сообщении #1079825 писал(а):
Что если взять решение finite planes и его улучшить отжигом? У меня правда не получилось.

Каким образом вы выбираете соседей?

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение06.12.2015, 12:13 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
whitefox в сообщении #1079856 писал(а):
Каким образом вы выбираете соседей?

Пробовал два метода:

1. Менять отметки на линейке.
2. Представить линейку в форме разниц между отметками. Каждая разница должна быть уникальна. Можно обменивать разницы или менять одну конкретную разницу.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение06.12.2015, 12:25 
Аватара пользователя


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1079825 писал(а):
взять решение finite planes и его улучшить отжигом?


Боюсь что это невозможно. В решениях полученных finite planes, все числа плотно подогнаны друг к другу. Частичная замена некоторых чисел ничего не даст, кроме исходного решения.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение06.12.2015, 12:55 
Заслуженный участник
Аватара пользователя


19/12/10
1546
dimkadimon в сообщении #1079875 писал(а):
Можно обменивать разницы или менять одну конкретную разницу.

Имхо, единственное что можно сделать — взять разности в обратном порядке. Все прочие перестановки разностей, а равно замена одной конкретной разности, ничего не дадут. По причине указанной Pavlovsky.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение07.12.2015, 09:04 
Аватара пользователя


21/02/10
1594
Екатеринбург
Может кто выложит оттранслированные exe файлы двух алгоритмов на конечных полях?

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение07.12.2015, 15:03 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #1080203 писал(а):
Может кто выложит оттранслированные exe файлы двух алгоритмов на конечных полях?

Я компилировал через gfortran.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение07.12.2015, 15:14 
Аватара пользователя


21/02/10
1594
Екатеринбург
У меня нет gfortran. И если честно, нет желания разбираться как с ним работать.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение08.12.2015, 09:51 
Аватара пользователя


21/02/10
1594
Екатеринбург
A REVIEW OF THE AVAILABLE CONSTRUCTION METHODS FOR GOLOMB RULERS
http://eeme.ucd.ie/~kdrakaka/work/publi ... Rulers.pdf

Продолжаю изучение этой статьи.

Теорема 2. Доказательство. Не понимаю, как были выведены формулы (4) и (5). Может кто поможет?

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение08.12.2015, 12:01 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Разделим формулу (3)$$2p(x+y) + (x^2\bmod p) + (y^2\bmod p) =a$$на $2p$ и возьмём целую часть, получим$$\left\lfloor x+y+\frac12\left(\frac{x^2\bmod p}p+\frac{y^2\bmod p}p\right)\right\rfloor=\left\lfloor\frac a{2p}\right\rfloor$$Так как $x$ и $y$ целые, а выражение в круглых скобках меньше двух, то получаем формулу (4)$$x+y=\left\lfloor\frac a{2p}\right\rfloor$$То есть $x+y$ есть константа, которую обозначим как $A.$

Теперь приведём формулу (3) по модулю $p,$ получим $$x^2+y^2\equiv a\pmod p$$и так как $x^2+y^2=(x+y)^2-2xy,$ то $$(x+y)^2-2xy\equiv a\pmod p$$из чего следует формула (5)$$xy\equiv b(A^2-a)\pmod p$$где $b$ такое, что $2b\equiv1\pmod p.$ Такой выбор $b$ возможен так как $p$ по условию нечётное простое. Следовательно $xy\bmod p$ есть константа, обозначенная как $B.$

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение08.12.2015, 12:06 
Аватара пользователя


21/02/10
1594
Екатеринбург
Спасибо. Ваше объяснение очень простое и понятное.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение09.12.2015, 03:09 
Аватара пользователя


25/08/12
171
Germany
To get good results it is necessary to generate all possibilities. For p = 5 and the projective case there are for example 60 cases:

{{0,1,3,8,12,18},{0,1,3,10,14,26},{0,1,4,6,13,21},{0,1,4,10,12,17},{0,1,6,18,22,29},{0,1,8,11,13,17},{0,1,11,19,26,28},{0,1,14,20,24,29},{0,1,15,19,21,24},{0,1,15,20,22,28},{0,2,3,8,20,24},{0,2,3,16,22,26},{0,2,5,6,16,24},{0,2,5,12,13,27},{0,2,6,20,21,28},{0,2,7,11,17,30},{0,2,7,21,22,25},{0,2,8,11,12,26},{0,2,9,13,25,30},{0,2,9,17,27,28},{0,3,4,14,22,29},{0,3,4,18,23,25},{0,3,5,9,23,24},{0,3,5,12,20,30},{0,3,9,11,16,30},{0,3,10,11,25,29},{0,4,6,9,16,17},{0,4,9,11,12,25},{0,4,10,23,24,26},{0,4,11,13,14,19},{0,4,16,21,22,24},{0,4,18,19,26,29},{0,5,6,8,15,19},{0,5,7,8,21,27},{0,5,7,13,16,17},{0,5,9,15,28,29},{0,5,17,21,28,30},{0,5,19,20,23,29},{0,6,8,13,27,28},{0,6,9,10,24,29},{0,6,10,15,17,18},{0,6,19,20,22,27},{0,7,8,22,26,28},{0,7,9,10,15,27},{0,7,9,12,13,23},{0,7,10,12,16,30},{0,7,11,23,28,29},{0,7,15,25,26,29},{0,8,15,17,20,21},{0,8,18,19,22,24},{0,10,11,14,16,23},{0,10,18,25,27,30},{0,12,16,23,25,26},{0,12,17,18,20,27},{0,13,14,16,21,25},{0,13,19,23,28,30},{0,14,15,18,24,26},{0,14,15,22,25,27},{0,14,18,20,23,30},{0,14,19,21,27,30}}

I did not examine the cases with prime p a bit larger than the problem size N yet (for example for N=1009 also p=1013 and p=1019 should be examined), but I am quite sure that all the top solutions for the larger N can be found in this way.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение09.12.2015, 07:52 
Аватара пользователя


21/02/10
1594
Екатеринбург
Herbert Kociemba в сообщении #1080806 писал(а):
To get good results it is necessary to generate all possibilities.


Этот подход даст в лучшем случае 30,0000 в текущем конкурсе. Чтобы удивить лидеров, надо искать линейку Голомба лучше чем дают алгоритмы на основе конечных полей.

-- Ср дек 09, 2015 10:03:58 --

Чего то вдруг возник вопрос. До сих пор считал, что алгоритмы affine plane construction и projective plane construction не дают теоретически минимальных результатов. Вдруг засомневался в этом.
Вот таблица рекордов:
http://www.research.ibm.com/people/s/shearer/grtab.html

Практически все рекорды получены этими алгоритмами, в том числе для N минимальность полученных решений, для которых, доказана.

 Профиль  
                  
 
 Re: Al Zimmermann - Sums and Products
Сообщение09.12.2015, 09:34 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Herbert Kociemba в сообщении #1080806 писал(а):
To get good results it is necessary to generate all possibilities. For p = 5 and the projective case there are for example 60 cases:


Yep I thought this was the case, but couldn't find an easy way to generate them all. I tried using the sub-optimal rulers generated by the fortran programs, but it wasn't enough.

-- 09.12.2015, 15:21 --

Pavlovsky в сообщении #1080820 писал(а):
Практически все рекорды получены этими алгоритмами, в том числе для N минимальность полученных решений, для которых, доказана.


Ну это только первые 27, а дальше не известно что будет. Все таки хочется удивить лидеров.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 165 ]  На страницу Пред.  1 ... 6, 7, 8, 9, 10, 11  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

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