• Зачем нам всем нужен SAT и все эти P-NP (часть вторая)
    0
    Все правильно, да. Статья про полиномиальный алгоритм для 3-SAT.
    Если алгоритм правильный — это бы означало, что P == NP, но доказать равенство — не цель статьи.
  • Зачем нам всем нужен SAT и все эти P-NP (часть вторая)
    0
    Я чего-то не понимаю, но, мне кажется, эти утверждения противоречат друг другу?

    В чем противоречие? Может быть я не так выразился?
  • Зачем нам всем нужен SAT и все эти P-NP (часть вторая)
    0
    т.е. банально никто на самом деле не проверял, а не было ли предложено похожих и/или эквивалентных методов?


    Не могу отвечать за Романова. Я не проверял. Думаю он тоже, но это только мое мнение.

    Всех интересует, чем же она действительно отличается, иначе смысл заниматься её изучением?


    Ну вот вы же разобрались, чем один алгоритм отличается от другого и выше тут привели.
    Или это не вы разбирались, а прочитали в статье других авторов?
    Я не разбирался в чем отличие, потому что сначала надо разобраться в этом алгоритме, прежде чем его сравнивать.
    А чтобы хорошо разобраться, лучше его реализовать и протестировать. Мной пока этого сделано не было.
    От Владимира Федоровича я тоже не слышал этого.
  • Зачем нам всем нужен SAT и все эти P-NP (часть вторая)
    0
    Со стороны всегда просто рассуждать, почему одну работу ждет провал, а другую успех.

    Конечно, на весь ваш список «здравого смысла» у меня (и, я уверен, у Владимира Федоровича) есть положительные ответы, но дело даже не в этом.

    Статья не претендует на доказательства P ?= NP, в ней просто предлагается алгоритм решения 3-SAT и предлагается новый взгляд на представление этой задачи в виде структур компактных троек, который никто за 40 лет не предлагал, поэтому и нет ссылок — это новая работа, новый подход. И новая NP-полная задача. Искать сходства или различия с существующими подходами и алгоритмами — это не то, чем занимался автор.

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

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

    Я также соглашусь, что в статье нет формального описания алгоритма. Его не было и в прошлой работе, прототип для которой был написан несколько раз. Один, последний, написал я в свое свободное время, постоянно консультируясь с Владимиром Федоровичем в течение 3-х месяцев. Видимо, с этой статьей нужно работать так же… кто возьмется пока я занят? Контакты обеспечу.

    Если говорить о статье, в ней приводится именно конструктивное доказательство алгоритма и, кстати, solver от предыдущей работы ни разу не дал ложного решения с практической точки зрения — если формула выполнима он давал выполняемый набор, если нет — набора, соответственно, не выдавалось. И все это за полиномиальное время. 100% верно на всех наших экспериментах (включая формулы из SAT Comp). То есть всегда. Правда, во время своей работы он нарушал теорему из статьи, чего быть, конечно, не должно. Но это ошибка в теории, которая на практике не мешала никак. Еще одной проблемой этого solver'а (точнее самого алгоритма), являлась память — ее нужно было очень (полиномиально) много — поэтому на SAT Competitions с ним делать нечего.

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

    Я не могу утверждать, что новая работа 100% верна, но если новый solver будет работать качественно также как предыдущий, только быстрее и потреблять меньше памяти — это уже будет хорошо.
  • Алгоритмы и структуры данных поиска. Лекции и курсы от Яндекса
    0
    А можно как-то выложить эти видео на iTunesU?
  • Обсуждение работы алгоритма Романова на примере
    0
    Еще не закончилось:

    habrahabr.ru/post/207112/#comment_7169344
  • Зачем нам всем нужен SAT и все эти P-NP (часть первая)
    0
    Теоремы о невыразимости: почему статью Романова [3] ожидает reject

    [3] Открытое письмо ученым и эталонная реализация алгоритма Романова для NP-полной задачи 3-ВЫП

    Это не самая последняя версия работы Романова. Ошибку мы в ней нашли достаточно быстро после публикации. Очень помогла готовая реализация и тестовые наборы, которые мы нашли в SAT Competitions.

    Недавно Владимир Федорович опубликовал продолжение своей работы:

    romvf.wordpress.com/2013/09/25/development-of-the-concept/

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

    Готовой программной реализации этого подхода еще нет. Но, если хочется потратить время над исследованиями Романова, то лучше начать с актуальной работы.
  • Бесплатное программное обеспечение от JetBrains для образовательных учреждений
    0
    Это не совсем альтернатива, если Вы, конечно, не какой-нибудь Kohsuke Kawaguchi или один из тех парней, которые подходят под это описание:

    You are the project lead or a committer
    You have been working on your open source project for a minimum of 3 months
    Your community is active. This means that you have recent activity in your newsgroups or forums
    You have an updated News section on your site
    You release updated builds on a regular basis
  • Сколько стоит создать приложение или вся правда о деньгах
    0
    Хорошая статья, правда немного популяризированная, потому что все расчеты в деньгах.

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

    И еще интересно сколько на вашем проекте это получилось в календарных днях (на сколько вы смогли распараллелить работы и как праздники и выходные на срок повлияли).

    Еще тестирования не хватает в списке, оно, скорее всего, вошло в Программирование у вас, да?
  • Моделирование большого количества взаимодействующих друг с другом частиц
    0
    FYI

    Вышла статья: swsys.ru/index.php?page=article&id=3249
  • Вышел Twitter Bootstrap 2.1.0
    0
    Как обычно, порт для SAAS можно найти здесь:

    github.com/yury/bootstrap

    и gem для rails:

    github.com/anjlab/bootstrap-rails
  • Вышел AnjLab SQL Profiler 1.2
    0
    Затянул с ответом, конечно, но, насколько я знаю, у них в профайлере нет аналога Performance Dashboard.
  • История создания интерактивной книги для iPad
    0
    Уже здесь: habrahabr.ru/blogs/i_am_advertising/138552/
    Там еще есть видео, можно посмотреть как озвучка работает.
  • История создания интерактивной книги для iPad
    0
    Есть такая книжка в appstore.

    Попробуйте, скажите ваше мнение. Статью про историю создания книжки опубликуем со дня на день.
  • Моделирование большого количества взаимодействующих друг с другом частиц
    +2
    Фактическое количество операций можно посчитать, если делать counter++ на каждой итерации самого глубокого цикла (циклов, если их несколько на одном уровне). Например,

    counter = 0;

    for (int i...) {
    for (int j...) {

    if (...) {

    for (k...) {
    counter++;
    }

    } else {


    counter++;
    }
    }
    }

    Сделайте эту штуку только для части, где ведется поиск соседей. Если у вас моделируется поведение частиц в итераций — 1) найти соседей, 2) применить физику, 3) отрисовать, и опять сначала с шага 1) — то нужно сделать только замер первого прохода шага 1, т.е. когда частицы еще находятся в перемешанном состоянии. Можно, конечно, привести и замеры для второго и следующих проходах, но они будут не так показательны.

    Еще, третий алгоритм зависит не только от количества частиц, но и от площади распределения частиц и от плотности распределения. Можете эти цифры тоже привести?
  • Моделирование большого количества взаимодействующих друг с другом частиц
    +1
    По вашим результатам времена работы второго и третьего алгоритмов растут одинаково линейно (с небольшим различием линейного коэффициента).

    Можете привести сравнение скорости выполнения не в миллисекундах (тем более про железо ничего не сказано), а в количестве операций?

    Еще было бы интересно посмотреть как изменится производительность алгоритмов от плотности распределения частиц?

    Кстати, сложность алгоритма поиска соседей не может быть O(n), потому что количество пар соседей — это даже не линейная функция от n. То есть, чтобы найти все пары соседей среди n точек не достаточно n операций. Например, для четырех близко расположенных точек, количество пар соседей будет равно шести.

    FYI:
    Во втором или третьем номере журнала «Программные продукты и системы» (2012) выйдет статья «Алгоритм поиска ближайших соседей» применительно к SPH. Там будет алгоритм со сложностью O(N^2/k), где k > 2 зависит от распределения частиц в пространстве.

    Там, например, есть такой эксперимент, где показано, что для поиска очередной пары соседей требуется в среднем 1,3 операции (точки равномерно распределены в квадрате при плотности частиц от 40 до 98 процентов, сторона квадрата от 50 до 100 точек, то есть n было в диапазоне от 2500 до 10000, радиус взаимодействия равен 5, k получилось в диапазоне от 10 до 20). Интересно было бы посмотреть на ваши цифры.
  • Bookmarklet для Free-lance.ru
    0
    Ну можно посмотреть все сразу на одной странице, а не тыкать много раз по каждой ссылке :)
  • Использование Play! framework в Gedit
    0
    Rails — видел.
  • Использование Play! framework в Gedit
    –1
    Я вот тоже не совсем понял, о чем хотел сказать автор и о чем он мечтал.
  • Использование Play! framework в Gedit
    –1
    В день по нескольку раз :)
  • Использование Play! framework в Gedit
    –1
    Логи это конечно хорошо, если там есть предупреждение или можно по логам сориентироваться в контексте. Но все значения переменных, условия и циклы в логах не вывести.
  • Использование Play! framework в Gedit
    –1
    Отладчик поможет. Посмотрите, что не так — напишете patch и все.
  • К вопросу о Федеральных Университетах
    0
    В 7 раз больше тысячи рублей? Или в 7 раз больше ставки в 7 тыс. (что составляет в итоге 40-50 тыс., как у какого-нибудь junior-программиста)?
  • К вопросу о Федеральных Университетах
    +4
    200% от 800 рублей — это же всего 1600 рублей :)
    Пишите сколько получается, а не супер надбавку, которая даже не превышает прожиточного минимума.
  • К вопросу о Федеральных Университетах
    0
    Такие ставки не только в вашем вузе. По-крайней мере, во Владимирском госуниверситете такие же.
    Насколько я знаю это ставка только за аудиторные часы.

    Например,
    > профессора — 7260, зав.кафа — 7735
    Если зав. кафедрой еще и профессор, то у него ставка будет 7260+7735=14995. Первое — за лекции, второе за руководство кафедрой.

    С надбавками (работа с контрактниками, руководство дипломниками, кандидатами, курсовыми работами и пр.) получается 10-20 тыс; 20-30 тыс. — встречается крайне редко.

    Но помимо таких надбавок есть еще всякие НИР и прочая деятельность, которая приносит дополнительный доход, никак не связанный с учебным процессом. Автор топика, вот, например, на вторые полставки работает в другом месте. Тоже самое практически со всем профессорско-преподавательским составом.
  • Skype is down again
    +6
    Тэг не правильно закрыли… не понятно где смеяться
  • Очнитесь, на дворе XXI век
    0
    Пруфлинк не работает :)

    Fatal error: Uncaught exception 'Exception' with message 'DateTimeZone::__construct() [<a href='datetimezone.--construct'>datetimezone.--construct</a>]: Unknown or bad timezone ()' in /usr/local/data/www/data-segodnya.ru/index.php:54 Stack trace: #0 /usr/local/data/www/data-segodnya.ru/index.php(54): DateTimeZone->__construct('') #1 {main} thrown in /usr/local/data/www/data-segodnya.ru/index.php on line 54
  • Геометрия на Хабре
    +2
    Когда планируете запускать API?
    Например, чтобы можно было разместить у себя кнопку «я пойду».
  • Нужны эксперты
    +1
    Павел, я бы подписался под каждым пунктом, где речь идет о разработке.

    Но если говорить о первом запросе:

    Нам нужны специалисты в различных областях (в первую очередь, в области информационых технологий), которые могли бы грамотно и доходчиво написать экспертное заключение, поясняющее, почему тот или иной конкурс является распилом. Необходимо на конкретных примерах из ТЗ показать почему за положенное время невозможно выполнить необходимую работу.


    … работа с конкурсной документацией (КД) и написание экспертного заключения — это немного другая работа. По сути, чтобы сказать почему конкурс является роспилом, надо написать собственное предложение-заявку на каждый такой конкурс и посмотреть насколько отличаются рассчеты. А для этого уже нужно проанализировать КД (это может быть большой документ на десятки страниц), возможно, сделать запросы на разъяснение положений организатору конкурса, перебрать массу вариантов решений и выбрать один. Это не очень приятная работа, которую можно списать на open source just for fun.

    Если отвлечься от вопроса «бесплатных экспертов», то вроде бы и не нужно быть большим экспертом, чтобы заметить, что ИТ-конкурс является роспилом: там обычно просто несоизмеримо маленькие сроки при большом объеме работ.

    Я думаю можно даже какой-то коэффициент вывести среднеотраслевой (например, по моему мнению индикатором роспила будет проект, который стоит в среднем больше 500-800 тыс. рублей в месяц и при этом занимает по срокам меньше двух месяцев), хотя обычно достаточно здравого смысла, чтобы понять, что:

    Нельзя сделать большой ИТ-проект в сжатые сроки, если только речь не идет просто о закупке готового дорогостоящего ПО или оборудования по прайсу.
  • Обсуждение работы алгоритма Романова на примере
    0
    Я переговорил с Владимиром Федоровичем. По первому вопросу все так: если две переменные будут иметь разные значения — это приведет к противоречию и совместного выполняющего набора для них быть не может по построению. По второму — тройки переменных отдельно не нужно проверять, потому что такая проверка покрываются проверкой пар значений переменных. Если в двух тройках любая пара совпадает, значит и тройки тоже совпадают.
  • Обсуждение работы алгоритма Романова на примере
    0
    Насчет скорости: помимо n и m на время работы алгоритма влияет еще структура формулы. Некоторые формулы можно декомпозировать на 2 ФКТ, другие — на 10, третьи — на сотни. Время работы алгоритма будет также зависеть от числа k — количества ФКТ. Это число неявно присутствует в оценке сложности в качестве m: O(m * n^4). Соответственно, чем больше k, чем больше в базисной СКТ строк — тем дольше будет работать алгоритм.

    Еще один момент: в приложении реализованы два алгоритма, которые запускаются последовательно. Первый — построение системы гиперструктур. Если результатом его работы является напустая HSS, то формула считается выполнимой по теореме 1.
    Второй алгоритм — поиск выполняющего набора в HSS. Вообще говоря в статье этот алгоритм не рассматривается. Сейчас в реализации он работает так: в HSS последовательно из каждого уровня базисного графа отбрасываются все вершины кроме одной начиная с первого уровня и так далее вниз. Оставляется только одна вершина (любая), подструктура которой имеет непустое пересечение с любой подструктурой вершины последнего уровня. Строится новая система гиперструктур. Дальше со второго уровня выбрасываются все вершины, кроме смежных с вершиной первого уровня. Их максимум две. Какую оставить решает такое правило: оставляем первую вершину и строим систему HSS, если она построена — значит мы выбрали правильную вершину, если нет — значит оставляем вторую вершину. И так далее, пока HSS не станет элементарной, то есть будет содержать только одно j-пересечение.

    К чему я это, к тому, что при запуске алгоритма HSS может строиться несколько раз — что приводит к еще более длительному времени работы программы. Почему может — потому что сейчас не обязательно HSS сводить к элементарной для поиска выполняющего набора, так как там есть вспомогательный алгоритм (quickFindHSSRoute), который умеет находить выполняющий набор в системе гиперструктур. Не буду вдаваться в подробности этого алгоритма, можно считать сейчас, что это эвристика.

    Насчет второго вопроса, я уточню у Владимира Федоровича. Но вроде бы так:
    1. второе доказательство строится на одноименных j-пересечениях; унификация, как она определена, должна приводить к тому, чтобы в двух CTS убирались строки, которые не образуют совместного выполняющего набора.
      В алгоритме SEP пункт A concordance rules на стр. 15 говорит о том, что все одноименные подструктуры должны быть унифицированы в ходе построения HSS. Это приводит к тому, что все одноименные j-пересечения будут в себе заключать все совместные выполняющие наборы.

    2. тройки битов не проверяются, потому что подразумевается, что три переменных в одной тройке могут быть только в одной СКТ.
  • Обсуждение работы алгоритма Романова на примере
    0
    Минимальный набор сложно подобрать, наверное. Но какие-то тесты уже есть в проекте: github.com/anjlab/sat3/tree/master/3-sat-core/src/test/resources

    Конечно, там есть и большие формулы — они использовались в основном в начале разработки для тестирования алгоритма декомпозиции формулы. Но есть экземпляры и поменьше, например, article-example.cnf — это формула из статьи, cnf-v112-c418-100-sat.cnf — формула, которая нашим алгоритмом декомпозируется на 2 ФКТ, так что получается одна гиперструктура, и т.д. Большинство формул для тестов были взяты отсюда: www.cs.ubc.ca/~hoos/SATLIB/benchm.html

    Я не запускал регрессионные тесты на всех формулах, потому что есть набор unit-тестов, которые тестируют разные алгоритмы по-отдельности.

    Насчет решения — их обычно быть много, можно конечно привести одно, но зачем? Если вы получите свое — можете легко его проверить, подставив значения в формулу.
  • Обсуждение работы алгоритма Романова на примере
    0
    Очень может быть. Вообще, Романов сам постоянно говорит, что наверняка все можно сделать проще, найти какие-то свойства структур и алгоритмов, которые позволят сделать его эффективнее. Но для доказательства уже достаточно того, что есть сейчас. В статье про унификацию вообще приводятся только основные правила, суть которых показать какой должен быть результат. Как это будет реализовано — другой вопрос. Только я переписывал процедуру унификации несколько раз. Правда со стороны, которую предлагаете вы, я на эту проблему не смотрел. Интересно.
  • Почему я не верю в простые алгоритмы для NP-полных задач
    +1
    Просто для заметки.

    1. Подобного представления формул (в виде компактных троек) еще ни у кого не было — это оригинальный подход.
    2. Сама идея и алгоритм были придуманы и описаны 10 лет назад. Просто почему-то ее никто до этого не замечал. Владимир Федорович занимался решением этой задачи независимо от своей основной работы, ни в рамках какого-то научного проекта, а просто так — как хобби (кстати начал он ее еще в 90-х). У нас на кафедре про его работу знали, но за рамки кафедры эти знания так и не вышли, если не считать единичных публикаций в вузовских сборниках и переписок один-на-один с рецензентами, которые привели к статье в непрофильном журнале.

    Тот факт, что про эту статью узнали сейчас — это чистая случайность. Если бы не нашумевшая история о Деолаликаре, то прошло бы еще 10 лет и так ничего бы не изменилось. Именно эта история сыграла для меня решающую роль. Как так! Его статью обсудили и знают, а о статье Романова за 10 лет так никто и не узнал. Только из-за этого я решил потратить несколько месяцев работы, чтобы вместе с Романовым еще раз перечитать его статью, отредактировать английский вариант, сделать версию в LaTeX (это вообще отдельная история), разобраться в алгоритме, написать реализацию, написать письмо, найти адреса ученых и отправить это письмо им. Но это все было как хобби. Работа никем не спонсировалось, все делалось в свободное время. (Вообще-то я думал на это уйдет меньше времени.) А что получается в итоге? В итоге все уже сыты по-горло подобными доказательствами и я прекрасно понимаю, почему ни у кого нет желания разбираться в этой работе и понимаю скепсицизм с которым к работе относятся.

    Судить не мне, но я считаю, что лучше, чтобы о статье узнали поздно чем никогда. А уж верна она или нет — покажет время. Хорошо, что ее уже включили в знаменитый список The P-versus-NP page. Правда под номером 65 и с датой 20 ноября, хотя должны бы были включить в первую пятерку или десятку и с годом 2002.
  • Обсуждение работы алгоритма Романова на примере
    0
    С каким-то из утверждений Вы несогласны?

    Нет, наверное все так. Я просто не понимаю к чему это… :\
  • Обсуждение работы алгоритма Романова на примере
    0
    Я вижу вы здесь знаете больше меня. :)
  • Обсуждение работы алгоритма Романова на примере
    0
    Не уверен, что понял вопрос про унификацию.
    Унификация не имеет дело с тройками — только с парами переменных и с переменными, которые тождественно 1 или 0.
    Если переменные x1 и x2 встречаются в пределах одной тройки в двух и более структурах — значит при унификации нужно учитывать эту пару.
    Не понял про фиктивные переменные, зачем их добавлять? В любом случае, если вы добавляете «фиктивные» переменные, то они также участвуют в процедурах очищения и унификации.
  • Обсуждение работы алгоритма Романова на примере
    0
    Я переделал тест, теперь там явно указывается базисная структура, та которая (x10 | x11 | x12). Обновил лог и тест по ссылке.

    Тест был у меня в рабочей копии, сейчас я его закомитил: github.com/anjlab/sat3/commit/27e75ae4527f15ae0d6e3dedb98dccc948f1cc74

    Программа собирается maven3 (но я думаю можно и maven2), я запускаю тест из eclipse.

    Чтобы загрузить проект в эклипс делаете checkout, потом в этой папке запускаете (maven2/3 должен быть в переменной PATH):

    mvn clean test


    Все тесты должны пройти. После этого можно загрузить проект в IDE, чтобы загрузить в eclipse я делаю так:

    1)
    mvn eclipse:eclipse

    2) В eclipse делаю File -> Import -> Existing projects into workspace… -> Выбираю оба проекта 3-sat-core и 3-sat-experiment
    3) Дальше нужно будет добавить переменную билда M2_REPO. Для этого на проекте нужно щелкнуть правой кнопкой -> Properties -> Java Build Path -> На вкладке Libraries нажать кнопку Add Variable… -> Configure Variables… -> New… -> В качестве имени M2_REPO, значение — путь к папке с репозиторем maven2, по умолчанию он в <user-dir>/m2/repository (например, c:\Users\dmitrygusev\.m2\repository) -> Дальше везде Ok
  • Обсуждение работы алгоритма Романова на примере
    0
    Да, базисная структура там другая получилась.
    Алгоритм выбирает базисную структуру по простому правилу — где меньше строк.
    Если это принципиально (это сказывается только на потреблении памяти).
    Я могу переписать тест, чтобы можно было явно базисную структуру задавать.
    Как решим?
  • Обсуждение работы алгоритма Романова на примере
    0
    Поправил.