Новый конкурс программистов

[ogaman]

Zealint

Как и ожидалось, ответа не получил. Что касается качественного решения (минимум C, максимум N), то мне очевидно, что без кластера не обойтись. Но это мое личное мнение: я его никому не навязываю (косвенным подтверждением моей мысли являтся многолетние поиски решения за 200 с лишним баксов). Еще раз всем учавствующим в конкурсе желаю успехов и высоких мест.

[svb]

Немного о кластерах.
В. И. Арнольд : А. Н. Колмогоров и естествознание

Цитата:

Следующее описание эволюции математического образования составили американцы на основе анализа своих школьных учебников.
- В учебнике 60-х годов была такая задача: "Крестьянин продал мешок картошки за 10 долларов, затратив на это производство 4/5 этой суммы. Спрашивается, какова величина дохода".
- В семидесятые годы формулировка стала такой: "Крестьянин обменял множество $K$ картошек на множество $D$ денег. Мощность множества $D$ равна десяти, а каждый элемент из $D$ стоил 1. Нарисуйте 10 больших точек, представляющих элементы множества $D$. Множество $C$, изображающее стоимость производства, имеет на 2 точки меньше, чем $D$. Представьте $C$ как подмножество множества $D$ и найдите мощность множества 'Доход'".
- К 1980 году эта задача приобрела такой вид: "Мешок картошки продан за 10 долларов, затраты на его производство составили 8 долларов, доход от продажи - 2 доллара. Подчеркните слово 'картошка' и обсудите ситуацию с одноклассниками".
- В девяностые годы достигнут дальнейший прогресс: "Фермер продал мешок картошки за 10 долларов. Его или ее затраты составили 0.80 от его или ее оплаты. На компьютере составьте график зависимости дохода от цены. Дайте программе "КАРТОФ" определить доход. Обсудите с одноклассниками и напишите рассказ с анализом этой ситуации для журнала реальной экономики".
Да минет нас чаша сия!

[Nataly-Mak]

svb в сообщении #591937 писал(а):

Pavlovsky в сообщении #591929 писал(а):

То есть вы хотите сказать, что 25х25 и 36х36 это теоретический максимум?? Сдается мне, что это далеко не так.

Нет, конечно Уж, если для C=4 люди очень долго искали 18x18, то про последующие квадраты и говорить нечего. Но количество цветов все же маленькое (мелочь) и шансов получить бОльшие квадраты кроме перебора почти нет.

Почему же всё-таки только перебор?
Разве нет никаких аналитических методов?

Кстати, Pavlovsky сообщал, что на форуме конкурса обсуждают построение решения 26х26. И что же там конкретно предлагается? Тоже перебор?

Ну, скажем, первое, что пришло в голову всем, это достраивание готовых решений 25х25 именно перебором, то есть метод "вытряхивания" ошибок.
Как я уже говорила, dimkadimon сообщал, что ему удалось получить данным методом решение 26х26 всего с 2 ошибками. Получается, что вот эти 2 ошибки уже не "вытряхиваются", то есть это фатальные ошибки и "убить" их невозможно.
Возникает предположение, вроде бы очевидное: данный метод чаще всего ведёт в тупик.
И возникает естественный вопрос: возможно ли в принципе получить решение данным методом

Следовательно, нужен именно анализ ситуации. Что даёт добавление к готовому решению 25х25 строки и столбца?

Далее: если задачу уже давно решают учёные мужи, то, наверное, они задавались вопросом существования решения 26х26. Попытки доказательства существования/несуществования такого решения были?

Конечно, когда люди не могут доказать, существует какое-то решение или не существует, они хватаются за перебор
Это мне очень хорошо известно! По магическим квадратам. Сама вот уже больше месяца гоняю одну переборную программу, чтобы доказать минимальность найденного пандиагонального квадрата 6-го порядка их чисел Смита. Потому что доказать это без перебора мозгов не хватает.

Мой вчерашний эксперимент с достраиванием квадрата 25х25 5-coloring до квадрата 26х26 в программе Эда застопорился на количестве ошибок 66. Дальше тупик, сколько ни крутила, не "убивается" ни одна ошибка.
Мне удалось получить в программе Эда квадрат 37х37 6-coloring, в котором всего 36 ошибок.

-- Вс июл 08, 2012 06:38:27 --

Цитата:

Я работал почти исключительно на C5N26 и становятся достаточно убежден, что это возможно (возможно C5N27 тоже). Текущий код находит C4N18 решение (ы) с нуля в считанные секунды, но есть некоторые большие трудности, применяя тот же метод для C5. Мои поиски пространство взрывается по причинам, главным образом связанных с ней быть просто большой сетки, если они могут быть решены даже может открывать ближайшие Cs выше C ^ 2 барьер. На данный момент у меня еще одно улучшение в реализации (не было времени за последние 2 недели), и несколько других мелких доработок, которые не помогут C5, но может помочь напасть на другого дела дальше, и тогда я буду из идеи и, вероятно, с выцветанию мотивации / желающих поделиться своими идеями слишком
Это очень разочаровывает проблема ... работать на нем в течение недель и делать то, что кажется, достойные достижения, но до сих пор не получили фактического решения. Должен сказать, я немного удивлен, никто не нарушил C ^ 2 барьер выше C = 4 еще, пожалуй, я обманывать себя, что это почти в пределах досягаемости или, возможно, это просто невозможно

[цитата с форума конкурса; перевод сделан в Google]

Ха! Он удивлён, что "никто не нарушил C^2 барьер выше С=4".
Так это "в пределах досягаемости" или "возможно, это просто невозможно"

Есть или нет? - вот в чём вопрос!

[Nataly-Mak]

Pavlovsky
пропагандируете на форуме конкурса джентльменский набор решений
Правильно! Не понимаю, чего это иностранцы мух давят

А я опубликовала на их форуме нашу с svb лемму.
Лемма дала мне возможность построить решения C^2-C+2 для C=p^k+1, p - простое число, k>=1. Это неплохой результат применения леммы.
Собственно и решения C^2-C+1 тоже получаются здесь, но я их получила раньше по другому алгоритму.

[svb]

Nataly-Mak в сообщении #593299 писал(а):

Почему же всё-таки только перебор?
Разве нет никаких аналитических методов?

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

Цитата:

Кстати, Pavlovsky сообщал, что на форуме конкурса обсуждают построение решения 26х26. И что же там конкретно предлагается? Тоже перебор?

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

Цитата:

Далее: если задачу уже давно решают учёные мужи, то, наверное, они задавались вопросом существования решения 26х26. Попытки доказательства существования/несуществования такого решения были?

Наверняка были.

Цитата:

Конечно, когда люди не могут доказать, существует какое-то решение или не существует, они хватаются за перебор

Принцип "здесь и сейчас" не годится для любого исследования, он годится только для школьных задач. "Хватаются за перебор" только для знакомства с ситуацией в надежде выйти на некоторую идею. Нормальный исследователь решает только решаемые задачи - посмотрите на "любимую статью". Что удалось решить, то и изложено. Самое любопытное то, что такой подход почти всегда более ценен, чем решение основной задачи, которая часто не имеет самостоятельной ценности.

Цитата:

Ха! Он удивлён, что "никто не нарушил C^2 барьер выше С=4".
Так это "в пределах досягаемости" или "возможно, это просто невозможно"

Есть или нет? - вот в чём вопрос!

[Zealint]

ogaman в сообщении #593198 писал(а):

Как и ожидалось, ответа не получил.

На ваш вопрос я ответил, а больше вы ничего и не спросили : )
Кроме того, вы начинаете противоречить сами себе. Сначала говорите, что без кластера не выиграть, а потом, что без него не получить качественного решения. С такой логикой не удивительно, что непременно нужен кластер.

Кстати, для получения качественного решения он действительно будет нужен. Но только после разработки не менее качественной идеи.

[whitefox]

ogaman в сообщении #593198 писал(а):

мне очевидно, что без кластера не обойтись. Но это мое личное мнение: я его никому не навязываю (косвенным подтверждением моей мысли являтся многолетние поиски решения за 200 с лишним баксов).

Вы обратили внимание, что сами себе противоречите?
Если люди использующие кластер много лет искали решение C4N17, то уж тем более ни какой кластер не поможет найти решение C21N442.
Только ручной труд + "серые клеточки".

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

[Nataly-Mak]

В самом начале конкурса dimkadimon писал мне в ЛС:

Цитата:

Две недели назад вышли 3 научные статьи (в разных журналах) которые описывают как решать один из вариантов этой задачи. Более двух лет многие учёные мира бились над этим вариантом и никто не мог его решить...

Извиняюсь за цитирование ЛС, но эта информация представляет общий интерес.

dimkadimon
о каких научных статьях вы писали?

[whitefox]

Сложность задачи C21N442 можно оценить как $10^{258319}$ элементарных операций, что при использовании кластера выполняющего квинтиллион операций в секунду ($10^{18}$), может потребовать $10^{258285}$ миллиардов лет.

[Zealint]

whitefox в сообщении #593316 писал(а):

Сложность задачи C21N442 можно оценить как $10^{258319}$ элементарных операций, что при использовании кластера выполняющего квинтиллион операций в секунду ($10^{18}$), может потребовать $10^{258285}$ миллиардов лет.

Может тогда попросим немного продлить конкурс? : )

[Pavlovsky]

svb в сообщении #593304 писал(а):

расширяя стартовую площадку для следующих поколений - вариант волнового алгоритма .

Не это недетерменированная машина Тьюринга.

Nataly-Mak в сообщении #593299 писал(а):

на форуме конкурса обсуждают построение решения 26х26. И что же там конкретно предлагается?

Как я понял. Человек пытается реализовать следующий подход. Заполнить квадрат сначала числом 1. Затем два и так далее. Такой подход хорош тем, что на каждом этапе можем достаточно точно оценить возможность построения квадрата.

Цитата:

Though, I found some some ways to fill a grid with 1 color (with at least N*N/C cells filled): C=5 N=26, C=10 N=98, C=15 N=195.

Правда результаты у него какие то пока нылые. Не пробовал, но думаю что единицами я легко заполню и квадрат C=5 N=28.

[Pavlovsky]

Мама дорогая сколько немцев принимает участие в конкурсе! Наверняка где то тоже обсуждают коллективно текущие проблемы. Поискал в гугле немецкие форумы, не нашел.

[Nataly-Mak]

Pavlovsky в сообщении #593334 писал(а):

Как я понял. Человек пытается реализовать следующий подход. Заполнить квадрат сначала числом 1. Затем два и так далее. Такой подход хорош тем, что на каждом этапе можем достаточно точно оценить возможность построения квадрата.

Нарисовала на листе бумаги квадрат 4х4 и стала заполнять его, сначала единичками, потом двойками.
Единички нарисовала так:

1 1 x x
x 1 1 x
x x 1 1
1 x x 1

Потом вместо крестиков вставила двойки. Получилась диагональная раскраска.

То есть, как я понимаю, берём квадрат 26х26 и начинаем вписывать в него сначала только единички, чтобы не образовывалось запрещённых прямоугольников, потом двойки и т.д.
Правильно понимаю?

Кстати, подзабыла, вроде сообщали: диагонального решения 26х26 для С=5 не существует?

[Pavlovsky]

Nataly-Mak в сообщении #593434 писал(а):

То есть, как я понимаю, берём квадрат 26х26 и начинаем вписывать в него сначала только единички, чтобы не образовывалось запрещённых прямоугольников, потом двойки и т.д.Правильно понимаю?

Перебор нужен. Ведь единички можно расставить так, что двойки уже не войдут.

Ну и после каждого шага проверять условие:

Цитата:

with at least N*N/C cells filled

Например в квадрате 26х26 должно быть единиц не меньше чем 26*26/5=135,2

[Nataly-Mak]

Pavlovsky в сообщении #593441 писал(а):

Ведь единички можно расставить так, что двойки уже не войдут.

Пока не поняла.
Это как? В квадрате 4х4 можете показать такую расстановку единичек, что двойки уже не войдут?

Цитата:

Ну и после каждого шага проверять условие:

Цитата:

with at least N*N/C cells filled

Например в квадрате 26х26 должно быть единиц не меньше чем 26*26/5=135,2

То есть если единичек будет 135 или больше, то годится, а если меньше 135, то не годится.
А сколько должно быть двоек? Так же?