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
788
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
1539
dimkadimon в сообщении #1079825 писал(а):
Что если взять решение finite planes и его улучшить отжигом? У меня правда не получилось.

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

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


01/06/12
788
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
1539
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
788
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
1539
Разделим формулу (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
96
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
788
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  След.

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



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

Сейчас этот форум просматривают: Yahoo [Bot]


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

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