2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Конкурс Изящные Графы
Сообщение30.09.2013, 13:45 
Аватара пользователя


22/09/09

1907
Позвольте небольшое терминологическое уточнение: согласно книге Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004, С. 558, graceful graph переводится как грациозный граф. На конкурсе Intel® Threading Challenge 2008 (о котором я недавно упоминал в другой теме) одно из заданий было на такие графы, может, в архивах интеловских сайтов сохранились обсуждения и тексты программ-лидеров того конкурса. Желаю успехов!

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение30.09.2013, 15:46 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
bin в сообщении #769348 писал(а):
Позвольте небольшое терминологическое уточнение: согласно книге Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004, С. 558, graceful graph переводится как грациозный граф. На конкурсе Intel® Threading Challenge 2008 (о котором я недавно упоминал в другой теме) одно из заданий было на такие графы, может, в архивах интеловских сайтов сохранились обсуждения и тексты программ-лидеров того конкурса. Желаю успехов!


Спасибо за уточнение. А вы можете дать ссылки?

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение30.09.2013, 20:29 
Заслуженный участник
Аватара пользователя


19/12/10
1546
dimkadimon в сообщении #768683 писал(а):
Вот у нас линейка (а1, а2, ..., а8, а9), мы соединим а1 и а9. Какое теперь растояние от а9 до а1?

Метка $a_1$ имеет значение $0$, а метка $a_9$ имеет значение $\mathrm L$. Теперь свернём линейку в кольцо, совместив метки $a_1$ и $a_9$, расстояние от $a_1$ до $a_9$ равно $a_9-a_1=(\mathrm L - 0)\bmod \mathrm L=0$, а также $a_1-a_9=(0-\mathrm L)\bmod \mathrm L=0$.
В общем же случае расстояние между двумя точками на циклической линейке будет иметь два значения $d$ и $\mathrm L-d$. Именно по этому я писал
whitefox в сообщении #768601 писал(а):
Очевидно, что всякая полная линейка одновременно является и полной циклической линейкой. Обратное, скорее всего, не верно.


Scryer в сообщении #768695 писал(а):
I assumed he meant that each pair now has either one or two differences. For example if a1=0 and a9=9, this pair covers differences {1,9}: 9 in the usual direction, and 1 in the new direction.
Именно это я и имел ввиду :D

-- 30 сен 2013, 21:39 --

bin в сообщении #769348 писал(а):
Позвольте небольшое терминологическое уточнение: согласно книге Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004, С. 558, graceful graph переводится как грациозный граф.

Цитата:
graceful [ˈgreɪsfʊl]
/прилагательное/

  1. изящный, стройный, элегантный
    (elegant, slender)
    graceful art — изящное искусство
  2. грациозный, благодатный
    (gracious)
    graceful dances — грациозные танцы

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

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение01.10.2013, 03:26 
Аватара пользователя


22/09/09

1907
dimkadimon в сообщении #769361 писал(а):
Спасибо за уточнение. А вы можете дать ссылки?
Посмотрите в Википедии (рувики) статью: Intel Software Network - там ссылки на сайты, где искать. Они менялись и точных ссылок у меня нет - если не найдете, но очень нужно, сообщите - посмотрю свои архивы.

-- Вт окт 01, 2013 03:42:43 --

whitefox в сообщении #769459 писал(а):
Насколько я понимаю, в русском языке перевод этого термина ещё не устоялся. Имхо, перевод "изящный граф" лучше передаёт суть понятия.
ИМХО спор о терминах м.б. инфинитен, но если в солидной книге уже приведен термин, то какие основания его менять? Чисто практически люди набирают поиск по сетке "Изящные Графы" и получают почти ничего, а в терминах Зыкова м.б. что-то и найдут... Но м.б. Вы знаете другую солидную книгу с термином "Изящные Графы"? ;-)

whitefox

(Оффтоп)

Все еще жду Ваших замечаний по изоморфизму графов ;-)

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение01.10.2013, 04:34 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Значит на даный момент мы не можем обойти линейки Wichmann. Мы даже не можем сравняться с ними (для N>14). А как насчёт хороших приближений? Предлагаю небольшой неофициальный конкурс без призов просто для интереса. Задача найти самые лучшие не-Wichmann линейки для N=24, 25, 26, 27 и 28. Я специально выбрал эти значения N чтобы они никак не повлияли на настоящий конкурс.

Вот мои лучшие результаты:

Код:
N=24, Wichmann=198
191: 0, 1, 2, 11, 20, 22, 29, 31, 40, 57, 74, 91, 108, 125, 142, 159, 167, 175, 178, 183, 186, 189, 190, 191
191: 0, 1, 2, 3, 8, 16, 24, 32, 40, 57, 74, 91, 108, 125, 142, 151, 160, 169, 178, 187, 188, 189, 190, 191

N=25, Wichmann=213
207: 0, 2, 4, 13, 17, 22, 26, 35, 51, 67, 83, 99, 115, 131, 147, 163, 179, 186, 193, 199, 200, 203, 205, 206, 207

N=26, Wichmann=232
220: 0, 1, 2, 3, 4, 5, 6, 7, 97, 103, 109, 118, 120, 128, 136, 144, 152, 160, 168, 176, 184, 192, 200, 206, 213, 220

N=27, Wichmann=251
241: 0, 1, 2, 3, 4, 8, 16, 24, 32, 40, 57, 74, 91, 108, 125, 142, 159, 176, 193, 202, 211, 220, 229, 238, 239, 240, 241

N=28, Wichmann=270
259: 0, 1, 2, 3, 4, 13, 22, 31, 40, 57, 74, 91, 108, 125, 142, 159, 176, 193, 210, 227, 235, 243, 251, 255, 256, 257, 258, 259

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение01.10.2013, 09:11 
Заслуженный участник
Аватара пользователя


19/12/10
1546

(bin)

bin в сообщении #769571 писал(а):
ИМХО спор о терминах м.б. инфинитен, но если в солидной книге уже приведен термин, то какие основания его менять?

Основания следующие:
  • Тот кто пожелает ознакомиться с теорией графов по Зыкову, скорее всего, скачает из сети его издание 1987 года (просто по причине их подавляющего численного превосходства), где нет ни грациозных ни изящных графов, а потому зыковская версия перевода ему не будет знакома;
  • Тот кто пожелает писать на русском о теории graceful graphs, скорее всего, переведёт этот термин как "изящные графы", если не знаком с последним изданием Зыкова, например http://np-soft.ru/npproject/projects/graphs/graceful/index.htm

P.S. Возможно я ещё вернусь к теме изоморфизма графов, она довольно интересна, но сейчас её вытеснили другие задачи, надеюсь временно :-)

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение01.10.2013, 10:01 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Друзья, интересные новости. Я нашёл патерн очень похожий на Wichmann, который всегда даёт результаты на один меньше. Я его называю near-Wichmann:

Код:
W'(r,s) = 1:r, (r+1):1, (2r+1):(r+1), (4r+3):s, (2r+2):r, 1:r

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение01.10.2013, 10:07 
Аватара пользователя


21/02/10
1594
Екатеринбург
Уже было
dmd в сообщении #767266 писал(а):
Интересно, что патерн 1^r, r+1, (2r+1)^(r+1), (4r+3)^s, (2r+2)^r, 1^r тоже работает, только все максимумы на единичку меньше получаются.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение01.10.2013, 15:48 
Аватара пользователя


22/09/09

1907

(whitefox)

whitefox в сообщении #769593 писал(а):
bin в сообщении #769571 писал(а):
ИМХО спор о терминах м.б. инфинитен, но если в солидной книге уже приведен термин, то какие основания его менять?

Основания следующие:
  • Тот кто пожелает ознакомиться с теорией графов по Зыкову, скорее всего, скачает из сети его издание 1987 года (просто по причине их подавляющего численного превосходства), где нет ни грациозных ни изящных графов, а потому зыковская версия перевода ему не будет знакома;
  • Тот кто пожелает писать на русском о теории graceful graphs, скорее всего, переведёт этот термин как "изящные графы", если не знаком с последним изданием Зыкова, например http://np-soft.ru/npproject/projects/graphs/graceful/index.htm
Это напоминает казус в рувики, где line graphs перевели как линейные графы (уже исправлено) :-) Последнее издание Зыкова найти не труднее, чем предыдущее. Оно сильно полнее. Общеизвестно правило, что если переиздание нестереотипное, то руководствоваться нужно этим переизданием. Прогресс все же движется, и новые книги исправляют недочеты предыдущих. Может, найдутся оригиналы, которые будут учить основы по арифметике Магницкого, но уверен, таких будет меньшинство. Стоит также отметить давно известный подход, согласно которому учебников по одной дисциплине нужно несколько. Например, этот подход широко используется в МГУ. Тот, кто пожелает ознакомиться с теорией графов, прочтет скорее всего не одну книгу, и вполне возможно, что и Зыков (в полном издании) окажется в числе этих книг.

whitefox в сообщении #769593 писал(а):
P.S. Возможно я ещё вернусь к теме изоморфизма графов, она довольно интересна, но сейчас её вытеснили другие задачи, надеюсь временно :-)
Вот и все так говорят. Лучше решать безобидные задачи, чем страшные-ужасные открытые проблемы. Согласиться с моим доказательством боязно, а опровергнуть не получается ;-)

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение06.10.2013, 14:12 
Аватара пользователя


21/02/10
1594
Екатеринбург
Изучаю статью
Л. Редей (Сегед) и А. Реньи (Будапешт) О представлении чисел 1,2,...,N посредством разностей
http://www.mathnet.ru/links/8a122709abb ... sm5985.pdf

В ней доказывается оценка $\sqrt{2+\frac{4}{3\pi}}\le \lim \limits_{L \to \infty} {\frac{N}{\sqrt{L}}}$.

Возникли проблемы с пониманием доказательства. Может кто поможет? У меня радиотехническое образование, где комплексные числа активно используются. Но с удивлением понял, что у меня огромные пробелы в знании комплексных чисел.

Не понимаю как получилось неравенство (17). У меня получается странная формула:
$e^{ib_rx}e^{ib_sx}=e^{i(b_r-b_s)x}$. Откуда взялся минус? Рациональное(действительное, целочисленное) сознание говорит, что должен быть плюс.

К тому же не понимаю элементарной вещи, что означает сравнение комплексного числа с нулем:
$a+ib \ge 0$??

Так же не понимаю откуда следует, что
$e^{ib_rx} \le 1$

Главное не могу понять "физического смысла" доказательства. Использование комплексных чисел для доказательств в теории чисел (привет от Дирихле), для меня выглядит каким то шулерским фокусом.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение06.10.2013, 16:34 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Pavlovsky в сообщении #771431 писал(а):
Не понимаю как получилось неравенство (17).
Из равенств $|f(x)|^2 = f(x)\overline{f(x)}$ и $\overline{e^{ibt}} = e^{-ibt}$

Pavlovsky в сообщении #771431 писал(а):
К тому же не понимаю элементарной вещи, что означает сравнение комплексного числа с нулем:
$a+ib \ge 0$??
$|f(x)|^2$ по определению модуля действительное неотрицательное число.

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение07.10.2013, 06:28 
Аватара пользователя


21/02/10
1594
Екатеринбург
Xaositect

Спасибо, небольшое прояснение наступило. Может вы дадите ссылку, где описаны эти аспекты комплексных чисел. Но чтобы материал сильно не напрягал умственные способности. :D

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение19.10.2013, 14:34 
Аватара пользователя


20/01/10
766
Нижний Новгород
Определение 1. Множеством разностей некоторого конечного множества чисел $B$ называется множество всевозможных $x-y$, где $x \in B$ , $y \in B$ . Обозначим это множество так $def(B)$.

Определение 2. Если $H = def\left( B \right)$ , то множество $B$ называется базисом (базой) множества $H$ .

В дальнейшем нас будут интересовать базы множества $H = \left( {0,1,...,L} \right)$. Эти базы можно задавать в виде набора чисел, но часто их удобно задавать в виде набора разностей соседних чисел базы после упорядочивания чисел базы по возрастанию. Например,

${\rm .1}{\rm .2}{\rm .3}{\rm .7}{\rm .7}{\rm .7}{\rm .4}{\rm .4}{\rm .1}{\rm .} $

это база $\left( {{\rm 0}{\rm ,1}{\rm ,3}{\rm ,6}{\rm ,13}{\rm ,20}{\rm ,27}{\rm ,31}{\rm ,33}{\rm ,36}} \right)$ для множества $\left( {0,1,...,36} \right) $

Теорема 1. Пусть база $.a_1 .a_2 ....a_k .x/s.b_1 ....b_m .$ множества $H_s  = \left( {0,1,...,L} \right)$ удовлетворяет условиям:
1. $x > a_i$ , $x > b_i$ ,
2. $H_s  = def\left( {.a_1 ....a_k .x/s.} \right)\bigcup {def\left( {.x/s.b_1 ....b_m .} \right)}$,
тогда множество $.a_1 .a_2 ....a_k .x/\left( {s + 1} \right).b_1 ....b_m .$ является базой множества $H_{s + 1}  = \left( {0,1,...,L + x} \right)$. Кроме того $\left( {0,1,...,x - 1} \right) \in def\left( {.a_1 ....a_k .} \right)\bigcup {def\left( {.b_1 ....b_m .} \right)} $

Доказательство.
Последнее утверждение очевидно, т.к. $x > x - 1$.
При добавлении числа $x$ в базу все прежние представления чисел меньших или равных $L$ сохраняются, что следует из условия 2. Любое число, большее $L$ , входит в одно из множеств $def\left( {.a_1 ....a_k .x/\left( {s + 1} \right).} \right)$ или $def\left( {.x/\left( {s + 1} \right).b_1 ....b_m .} \right)$. Таким образом, для любого $p > s$ множество $.a_1 .a_2 ....a_k .x/p.b_1 ....b_m .$ также является базой.

Дополнительно приведу пример линейки $.1/3r-2.r.5r/s.1/r-1.3r.1/r.$, которая хуже линейки Вихмана.

Последовательность $s$ элементов $a$ в тексте обозначена через $a/s$

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение19.10.2013, 19:30 
Заслуженный участник
Аватара пользователя


19/12/10
1546
svb в сообщении #777148 писал(а):
Определение 2. Если $H = def\left( B \right)$ , то множество $B$ называется базисом (базой) множества $H$
Имхо, так:
Определение 2. Если $H \subseteq def\left( B \right)$ , то множество $B$ называется базисом (базой) множества $H$

 Профиль  
                  
 
 Re: Конкурс Изящные Графы
Сообщение19.10.2013, 19:57 
Аватара пользователя


20/01/10
766
Нижний Новгород
whitefox в сообщении #777297 писал(а):
Имхо, так:
Определение 2. Если $H \subseteq def\left( B \right)$ , то множество $B$ называется базисом (базой) множества $H$
Спасибо. Согласен.

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

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



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

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


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

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