2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 67  След.
 
 Re: Prime Sums
Сообщение17.10.2012, 05:27 
Заслуженный участник


31/12/05
1530
Nataly-Mak в сообщении #631848 писал(а):
tolstopuz, это вы?
Да. Решил слегка почесать свой кластер, но серьезно заниматься задачей вряд ли буду.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 11:26 
Аватара пользователя


21/02/10
1594
Екатеринбург
Получить результат 498 для N=5, по представленной выше схеме невозможно. Делаем небольшое отступление. Будем искать минимум равный 500.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 11:40 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ищите сразу минимум 502 :D
Это вернее всего. Я почти уверена, что для N=5 502 является минимумом.
Для кластера квадрат 5х5 не проблема, полный перебор сделает за 5 минут.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 11:45 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #631925 писал(а):
Для кластера квадрат 5х5 не проблема, полный перебор сделает за 5 минут.


Не правда. Полный перебор ето 25! - огромное число, которое никакой кластер не возьмет!

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 12:03 
Аватара пользователя


21/02/10
1594
Екатеринбург
Результат пока не важен. Ищу критерии возможности (невозможности) заполнить квадрат, по заданным заранее свойствам.

Изображение

Утверждение. Минимально возможная сумма линии равна 1+2+3+9+10=25.
Утверждение. Максимально возможная сумма линии равна 7+8+19+20+21=75.

Все допустимые варианты суммы 498.
29,31,37,41,43,47,59,67,71,73 = 498
29,31,37,41,43,53,59,61,71,73 = 498
29,31,37,41,47,53,59,61,67,73 = 498
29,31,37,43,47,53,59,61,67,71 = 498

Заполнить две линии числами, по схеме, возможно с максимальной суммой 142. 142>67+71=138.
Заполнить три линии числами, по схеме, возможно с максимальной суммой 199. 199>=61+67+71=199.
Заполнить четыре линии числами, по схеме, возможно с максимальной суммой 256. 256<59+61+67+71=258.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 12:05 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dimkadimon в сообщении #631932 писал(а):
Не правда. Полный перебор ето 25! - огромное число, которое никакой кластер не возьмет!


Ну так ведь не совсем же тупой перебор :D Оптимизации-то должны быть в любом переборе. Есть критерии отсечения заведомо неперспективных вариантов.

Так что, кластер возьмёт не только 5х5, он вон у венгра уже до N=29 взял :D
Конечно, не все у него точно максимумы и минимумы, но зато все рекорды.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 13:09 
Заслуженный участник


31/12/05
1530
Nataly-Mak в сообщении #631938 писал(а):
Так что, кластер возьмёт не только 5х5, он вон у венгра уже до N=29 взял :D
Почитайте что-нибудь про комбинаторный взрыв, например, древнюю задачку про изобретателя шахмат и пшеничные зерна. Представьте себе, что один компьютер - это мешок с зерном, а кластер - это все амбары государства, и попробуйте оценить, на сколько клеток их хватит.

-- Ср окт 17, 2012 13:11:16 --

Nataly-Mak в сообщении #631938 писал(а):
Конечно, не все у него точно максимумы и минимумы, но зато все рекорды.
Кстати, у него нет максимума для 6 и минимума для 7. Кластер дал сбой? :)

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 13:12 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #631938 писал(а):
Конечно, не все у него точно максимумы и минимумы, но зато все рекорды.


Ето дело времени - многие его рекорды побиваемые. Тут дело не только в кластере. Кластер помогает, но не до такой степени. Нужна хорошая идея. Пока только у Pavlovsky есть хорошие идеи.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 13:20 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
tolstopuz в сообщении #631972 писал(а):
Почитайте что-нибудь про комбинаторный взрыв, например, древнюю задачку про изобретателя шахмат и пшеничные зерна. Представьте себе, что один компьютер - это мешок с зерном, а кластер - это все амбары государства, и попробуйте оценить, на сколько клеток их хватит.

Не поняла - это вы о чём?
Я недавно решала задачу, в которой такой комбинаторный взрыв: 5^50 вариантов.
Ну и что? Умело составленная программа (правда, не мной), и задача решена на обычном домашнем компьютере всего за 269 часов.

И до сих пор решаю задачу, в которой ещё бОльший комбинаторный взрыв. Над алгоритмами к этой задаче думали вместе со мной ещё трое программистов. Написаны неплохие программы. Но ни одна из них не справляется с этим взрывом даже и за неделю. Плохо подумали? Ну, те, кто умеет думать лучше и имеет кластеры, до таких задач не снисходят (фи, какие-то магические квадраты).

Американцы ещё в прошлом веке нашли все классические магические квадраты 5-го порядка всего за 100 часов. Они разве не сделали полный перебор? Конечно, перебор должен быть оптимизирован; и в данной конкурсной задаче тоже, я же не говорю, что на кластер надо загрузить программу тупого перебора.

-- Ср окт 17, 2012 14:27:13 --

dimkadimon в сообщении #631974 писал(а):
Ето дело времени - многие его рекорды побиваемые. Тут дело не только в кластере. Кластер помогает, но не до такой степени. Нужна хорошая идея. Пока только у Pavlovsky есть хорошие идеи.

Ой, ну не смешите, пожалуйста, мои тапочки.
Кластер помогает именно до такой степени!
Найти рекорды почти для всех N за три дня. Это он на обычном домашнем компьютере нашёл, да?
Не спорю, что у него есть хорошие идеи. У меня они тоже есть (если я их не выкладываю, это не значит, что у меня их нет). Ну и что? Вот у меня программа крутится для N=6, постоянно выдаёт улучшения:
max: 1308,1340, 1348, 1380, 1388
min: 1302, 1280, 1200, 1160

Давайте поставим мою программу на кластер. Наверное, улучшения будут появляться побыстрее. Нет?
Дело времени? Разумеется! Только время будет очень разное на моём компьютере и на кластере.

-- Ср окт 17, 2012 14:35:31 --

tolstopuz в сообщении #631972 писал(а):
Кстати, у него нет максимума для 6 и минимума для 7. Кластер дал сбой? :)

Идея для данных N подкачала :D

В подтверждение: последнее улучшение для максимума - 1388 (а то ещё не поверите, что у меня тоже программа работает и результаты находит):

Код:
26  5  1  32  36  30
11  7  14  18  22  25
29  31  35  2  6  10
13  17  33  23  8  19
12  3  20  24  15  27
16  28  9  4  34  21

При этом я реализовала в программе далеко не все свои идеи, написала её на скорую руку, так - тяп-ляп :D Потому что задача мне не интересна.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 13:59 
Заслуженный участник


31/12/05
1530
Nataly-Mak в сообщении #631617 писал(а):
Вот этим и плоха данная задача, что решается она, в основном, не умом, а машиной.

Nataly-Mak в сообщении #631980 писал(а):
Умело составленная программа (правда, не мной), и задача решена на обычном домашнем компьютере всего за 269 часов.

Американцы ещё в прошлом веке нашли все классические магические квадраты 5-го порядка всего за 100 часов. Они разве не сделали полный перебор? Конечно, перебор должен быть оптимизирован

Вот этим и хороши данные задачи, что решаются они в основном не машиной, а умом. Если хорошим алгоритмом удалось сократить время выполнения, скажем, на 20 порядков (посчитайте сами размер тупого перебора $5^{50}$, скажем, по микросекунде на вариант), а кластером из 1000 машин еще на 3 порядка, то вы легко можете оценить, какой тут вклад сделан умом, а какой кластером.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 14:07 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
tolstopuz
вы говорите совсем о другом, я не понимаю, в чём вы меня хотите убедить.

Давайте так:
представим, что конкурсант №1 и конкурсант №2 имеют одинаковый ум. Оба они могут написать хорошую программу с замечательными идеями и блестящей реализацией (для одной и той же задачи). Представили такой вариант?

Далее: конкурсант №1 будет крутить свою программу на обычном домашнем компьютере (ну, вот как у меня, 2.4 Ггц, два ядра), а конкурсант №2 будет крутить свою программу на кластере.

Теперь скажите: кто из этих двоих конкурсантов получит больше результатов за меньшее время?

Понятная задачка? :D

Замечательный программист написал отличную программу, которая на моём компьютере выполнялась 269 часов (с перерывами, которые были предусмотрены в программе по моей просьбе).
За сколько времени эта же программа выполнилась бы на кластере?
Даже на другом более мощном компьютере можно сократить время выполнения этой программы в 2-3 раза.

И поясню разницу между задачами этого конкурса и прошлого: в прошлом конкурсе задача была с богатыми математическими идеями. У меня, к примеру, программа перебора вообще почти не работала, так самую малость. Почти все решения были найдены по красивым алгоритмам, в которых вообще не присутствует никакой перебор.
Вот такие задачи мне нравятся.
В задаче текущего конкурса преобладает переборная составляющая. Так мне, по крайней мере, представляется. Возможно, и в этой задаче есть какие-то математические идеи и красивые алгоритмы, но я их не вижу.

-- Ср окт 17, 2012 15:32:24 --

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

dimkadimon в сообщении #631096 писал(а):
Пока что я вижу только один метод для её решения и он не очень интересный.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 14:36 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #632001 писал(а):
Теперь скажите: кто из этих двоих конкурсантов получит больше результатов за меньшее время?


Не забывайте что кроме Венгра есть еще 43 человека, которые коллективно могли бы взять больше рекордов. Кстати у других тоже могут быть кластеры. Факт что в основном рекорды принадлежат ему мне говорит о том что у него действительно лучше алгоритмы. Достаточно одной хорошой идеи чтобы ускорить метод во много десятков раз. Например мне недавно пришла идея которая позволила находить результат за 2 часа, когда раньше для него требовалось 3 полных дня!

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

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 14:38 
Заслуженный участник


31/12/05
1530
Nataly-Mak в сообщении #632001 писал(а):
Давайте так:
представим, что конкурсант №1 и конкурсант №2 имеют одинаковый ум. Оба они могут написать хорошую программу с замечательными идеями и блестящей реализацией (для одной и той же задачи). Представили такой вариант?
Не могу представить. Я четыре раза занимал первое место в Project Euler, хотя пишу на Python, который примерно в 100 раз медленнее C++. А много раз не занимал, потому что меня обгоняли другие люди, используя самые разные языки и самое разное железо. Из этого я делаю вывод, что все люди разные и в такого типа задачах разница в умственных усилиях важнее разницы в вычислительной мощности.

(Оффтоп)

Вон, скажем, задача 251. Не помню, когда именно задача была объявлена, но я отправил сообщение с решением в 9:03, Robert Gerbicz в 9:24, а следующий в 13:32.
Или задача 256. Я - 1:37, Loks - 1:57, Robert Gerbicz - 2:18, следующий - 3:37.
Или задача 295. Первые два места - Java, третье - C++, четвертое и пятое - Python. Время у всех от 3 до 4 с небольшим часов. А языки программирования отличаются по скорости в 100 раз!

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 14:58 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dimkadimon в сообщении #632008 писал(а):
Если взять ваш метод случайной генерации квадратов и разместить на кластер то результаты будут немного лучше, но рекордов все равно не будет. Опять же я хочу сказать что хороший метод гораздо важнее чем много компютеров.

Во-первых, у меня есть не только метод случайной генерации, это было в самом начале, и уже для N=5 я следом написала вторую программу, которая намного эффективнее случайной генерации.

Во-вторых, вы же сами писали (только что выше процитировала), что не видите в этой задаче интересных методов решения.

-- Ср окт 17, 2012 16:07:57 --

tolstopuz в сообщении #632009 писал(а):
Не могу представить.

Ну почему же? Я не говорю о всех людях сразу, а говорю только о двух конкурсантах.
И это представить вполне реально. Я могу назвать вам кандидатов с умом не хуже того венгра. Например, тот же А. Чернов, который победил в прошлом конкурсе.
Вот вам и два конкурсанта с одинаковым умом, то есть в такой степени одинаковым, что они способны сделать отличную программу. И что же мы видим: венгр на первом месте, а А. Чернов только на 5-ом. В чём же причина? И почему вы это не можете представить?

Давайте поставим программу А. Чернова на кластер (мою не будем ставить, она, конечно, плохая :D ). И на такой же точно кластер поставим программу венгра.
Прогоним обе программы. Помотрим на результаты!
Это тоже не можете представить?

А вот в прошлом конкурсе Чернову не нужен был кластер; как он писал в теме, у него вообще не было переборных алгоритмов. Вот тут были только умственные усилия, и он взял первое место! Без всяких кластеров, на обычном домашнем компьютере.

Кстати, у меня в прошлом конкурсе было 8-ое место, а в этом будет сорокпоследнее. А ум всё тот же :D

 Профиль  
                  
 
 Re: Prime Sums
Сообщение17.10.2012, 15:39 
Аватара пользователя


21/02/10
1594
Екатеринбург
Что такое компьютер? Железяка. Интеллекта у него как у молотка. Думать за человека он не может!

tolstopuz в сообщении #631849 писал(а):
Решил слегка почесать свой кластер


Кластеры они не в туалетах. Кластеры они в головах. (С) профессор Преображенский.

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

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



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

Сейчас этот форум просматривают: Dmitriy40


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

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