Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 17
Отличная статья! Теорема Ван дер Вардена чем то похожа на гипотезу (нерешенную) «Erdos discrepancy problem».
Есть бесконечная последовательность из {-1, 1}, гипотеза утверждает, что для любого C, найдется (конечная) однородная арифметическая прогрессия индексов, такая что сумма последовательности по этим индексам >C. Для неоднородного случая гипотеза вроде доказана.
Есть такой проект PolyMath — что то вроде коллективного решения сложных задач. Там эту гипотезу тоже пытались решить, много интересного можно почитать. Например экспериментальные результаты, там пытаются вычислять различные интересные последовательности и значения функций. И многие значения удалось вычислить тоже только для очень маленьких чисел, например масимальные длины последовательностей с определенными ограничениями на суммы.
Кстати, один из экспериментальных результатов по этой гипотезе тоже был получен с помощью SAT-солвера.
Есть бесконечная последовательность из {-1, 1}, гипотеза утверждает, что для любого C, найдется (конечная) однородная арифметическая прогрессия индексов, такая что сумма последовательности по этим индексам >C. Для неоднородного случая гипотеза вроде доказана.
Есть такой проект PolyMath — что то вроде коллективного решения сложных задач. Там эту гипотезу тоже пытались решить, много интересного можно почитать. Например экспериментальные результаты, там пытаются вычислять различные интересные последовательности и значения функций. И многие значения удалось вычислить тоже только для очень маленьких чисел, например масимальные длины последовательностей с определенными ограничениями на суммы.
Кстати, один из экспериментальных результатов по этой гипотезе тоже был получен с помощью SAT-солвера.
Да, кажется это про нее было недавно 13 Гб логов.
По ссылкам почитаю, походу будет хорошее развлечение на эти выходные)
По ссылкам почитаю, походу будет хорошее развлечение на эти выходные)
Почитал немного, у вас ошибка в определении: не просто сумма, а модуль суммы >C (иначе последовательность, где все элементы равны -1, все портит). И да, справедливость гипотезы для неоднородного случая напрямую следует из теоремы Ван дер Вардена.
Что получается. В неоднородном случае всегда можно найти прогрессию нужной длины. В однородном случае, неизвестно даже, можно ли найти прогрессию, чтобы один цвет в ней перевешивал на заданное кол-во точек. Напрашивается вопрос: есть ли контрпример для аналога утверждения теоремы ВдВ про однородный случай? Должен быть, иначе бы Эрдеш не формулировал бы излишне сильный вопрос.
Вы не в знаете этот контрпример?
Вы не в знаете этот контрпример?
Можно взять a_{(2*m-1)*2^k}=(-1)^k (т.е. для каждого индекса считаем, сколько двоек в его разложении на множители, и для чётного числа вхождений пишем 1, а для нечётного -1). Тогда для любого n будет a_n!=a_{2*n}, т.е. не найдётся даже однородной прогрессии длины 2. Если разрешается брать фрагменты однородной прогрессии (т.е. a_{d*n}, a{d*(n+1)}, a_{d*(n+2)},..., то в любом фрагменте длины 4 встретятся различные числа.
Я далек от математики, поэтому мой вопрос может показаться глупым. И все же, было бы интересно узнать, в чем важность этой проблемы для математики? Я сходил по ссылке, там написано:
Поясните, решение этой проблемы — оно позволит взломать все пароли, ответить на «главный вопрос Жизни, Вселенной и Всего Остального», или просто миллион долларов дадут, как Перельману? Понимаю, что такая постановка вопроса может вызвать неприятие у специалиста, но все-таки, все науки развиваются с прицелом на какой-то практический результат, было бы неплохо и эту проблему привязать к чему-то осязаемому.
Вообще статья очень понравилась. Отдельное спасибо за упоминание функции Аккермана. Можно ставить людей в тупик вопросом «продолжите ряд чисел: 1, 2, 3, 5, 13, ...».
P.S. Загуглил этот вопрос, наткнулся на вот такой троллинг. По рекомендации из ролика забил последовательность 1, 2, 3, 5, 13 на сайт oeis.org. Что бы вы думали? Нашлось ровно 42 ответа!
The conjecture has been referred to as one of the major open problems in combinatorial number theory and discrepancy theory.
Поясните, решение этой проблемы — оно позволит взломать все пароли, ответить на «главный вопрос Жизни, Вселенной и Всего Остального», или просто миллион долларов дадут, как Перельману? Понимаю, что такая постановка вопроса может вызвать неприятие у специалиста, но все-таки, все науки развиваются с прицелом на какой-то практический результат, было бы неплохо и эту проблему привязать к чему-то осязаемому.
Вообще статья очень понравилась. Отдельное спасибо за упоминание функции Аккермана. Можно ставить людей в тупик вопросом «продолжите ряд чисел: 1, 2, 3, 5, 13, ...».
P.S. Загуглил этот вопрос, наткнулся на вот такой троллинг. По рекомендации из ролика забил последовательность 1, 2, 3, 5, 13 на сайт oeis.org. Что бы вы думали? Нашлось ровно 42 ответа!
Как отличить кандидата технических наук от кандидата физ-мат наук? Первый обязательно спросит какой есть практический результат.
Для математики, вроде бы, эта проблема интересна сама по себе. Если посмотреть на раздел, в которую данная проблема входит, на Википедии, то там написано: позволяет показать, что в некоторых казалось бы однородных и абсолютно случайных структурах обязательно появятся неоднородности. Чуть ниже написано, что это используется, например, в методе Монте-Карло для большого числа размерностей. Т.е., как я понял, если размерностей очень много, то Монте-Карло будет гарантированно давать большие погрешности, если его криво настроить. Но я тут не специалист, лучше переадрессовать вопрос товарищу, который дал ссылку на эту статью.
Для математики, вроде бы, эта проблема интересна сама по себе. Если посмотреть на раздел, в которую данная проблема входит, на Википедии, то там написано: позволяет показать, что в некоторых казалось бы однородных и абсолютно случайных структурах обязательно появятся неоднородности. Чуть ниже написано, что это используется, например, в методе Монте-Карло для большого числа размерностей. Т.е., как я понял, если размерностей очень много, то Монте-Карло будет гарантированно давать большие погрешности, если его криво настроить. Но я тут не специалист, лучше переадрессовать вопрос товарищу, который дал ссылку на эту статью.
Кстати, программу можно заметно ускорить (на моей системе в 2.5 раза), если заменить
bitset на vector<int>Ого, не знал, что
Насчет ускорения — у меня сейчас есть более дикая идея, которая, вероятно, ускорит программу в сотню раз. Только для этого надо все переписать с 0. Если вдруг программа в итоге будет работать меньше 3 секунд (лучше — если сильно меньше) — можно будет потягаться с крутыми дядьками хотя-бы для случая K=6)
bitset работает медленнее, чем vector, если его использовать только как булевый массив. Видимо, bitset дает выигрыш, только если мы с ним еще делаем логические операции. Логично, но раньше мне такая мысль в голову не приходила.Насчет ускорения — у меня сейчас есть более дикая идея, которая, вероятно, ускорит программу в сотню раз. Только для этого надо все переписать с 0. Если вдруг программа в итоге будет работать меньше 3 секунд (лучше — если сильно меньше) — можно будет потягаться с крутыми дядьками хотя-бы для случая K=6)
Как же мне нравится видеть слова «побаловаться» и «результат развлечений» в таких статьях. Чувствуешь себя, кхм, неловко…
Когда мне нужно что-нибудь подобное на практике построить, я быстренько пишу сведение к сату и дёргаю чужие сат-солверы. =)
Во-первых, не всегда к SAT сводится, а во-вторых, алгоритм собственного написания иногда работает быстрее солверов, потому что можно найти крутые отсечения, свойственные конкретной задаче, которые не ловит солвер, написанный для общего случая.
Ну а вообще да, если к SAT сводится, то свой алгоритм имеет смысл городить только если после сведения чужие SAT солверы работают слишком долго.
Ну а вообще да, если к SAT сводится, то свой алгоритм имеет смысл городить только если после сведения чужие SAT солверы работают слишком долго.
Ладно, не буду я занудствовать про то, всё или не всё сводится. =)
Но сведение этой задачи к сату есть, например, у Кнута. Весь код состоит из пары методов из четырёх строчек. Строка длины 177 нашлась (солвером Кнута же!) за несколько секунд. Невыполнимость формулы для 178 доказалась на моём самом обычном ноуте за пару минут.
Но сведение этой задачи к сату есть, например, у Кнута. Весь код состоит из пары методов из четырёх строчек. Строка длины 177 нашлась (солвером Кнута же!) за несколько секунд. Невыполнимость формулы для 178 доказалась на моём самом обычном ноуте за пару минут.
bash-3.2$ ./sat-waerden 5 5 178 | ./sat13
(178 variables, 7744 clauses, 38720 literals successfully read)
~
UNSAT
Altogether 96953+18950937986 mems, 341878 bytes, 1000830 nodes, 921919 clauses learned (ave 18.6->11.9), 678634 memcells.
(374087 learned clauses were trivial.)
(352116 learned clauses were discarded.)
(1506 clauses were subsumed on-the-fly.)
Ну, я тоже в статье описал сведение задачи для 2 цветов к SAT (и даже выписал формулу для длины прогрессии 3). И я не спорю, что эту задачу можно решить с помощью SAT (причем быстрее и писать в итоге меньше).
В данной статье я скорее преследовал цель рассказать именно об алгоритмах расщепления и использовать вычисление числа Ван дер Вардена в качестве иллюстрации. А SAT там сбоку привязан для еще одной иллюстрации.
В данной статье я скорее преследовал цель рассказать именно об алгоритмах расщепления и использовать вычисление числа Ван дер Вардена в качестве иллюстрации. А SAT там сбоку привязан для еще одной иллюстрации.
Как связана работа с перечислением множеств на заданное число частей?
Если имеются данные сообщите, пожалуйста. Спасибо!
Если имеются данные сообщите, пожалуйста. Спасибо!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритмы расщепления и числа Ван-дер-Вардена