Pull to refresh
14
0
dmitrygusev @dmitrygusev

User

Send message

Сведение решения NP-полной задачи «3-выполнимость» к алгоритму с полиномиальной сложностью

Reading time 2 min
Views 6.8K
По следам публикации P != NP (для которой, кстати, опубликовано опровержение), хочу поделиться ссылкой на статью В.Ф. Романова, в которой он показывает, как можно свести решение NP-полной задачи «3-ВЫП» к полиномиальному алгоритму.

Напомню, что любую задачу из класса NP можно «полиномиально свести» к любой из NP-полных задач. Значит если если существует полиномиальный алгоритм для решения хотя бы одной задачи, то потенциально любую NP-полную задачу можно также решить полиномиальным алгоритмом.

Читать дальше →
Total votes 22: ↑19 and ↓3 +16
Comments 38

AnjLab.SyncIT — синхронизируем свои задачи с Microsoft Outlook

Reading time 2 min
Views 1.6K
Коллективная работа немыслима без средств, позволяющих управлять задачами, распределять их между участниками команды, отслеживать изменения. Для этого используются модули трэкинга задач таких популярных систем коллективной работы, как Trac, Team Foundation Server, Salesforce и т.д. В то же время, человеку удобнее хранить все свои задачи, как личные, так и служебные, в персональном органайзере на своем компьютере или КПК. Для этой цели хорошо подходит MS Outlook 2007.

Между этими подходами нет противоречия, задача в том, чтобы синхронизировать «коллективное» и «персональное» хранилища задач. Эта проблема может быть решена с помощью нашей разработки SyncIT. Это маленькая программа, постоянно запущенная в system tray, которая периодически загружает информацию о новых \ изменившихся задачах из «коллективного» хранилища в «персональное» — список задач Outlook 2007. При этом, сам Outlook может быть не запущен.


Читать дальше →
Total votes 17: ↑16 and ↓1 +15
Comments 9

Работа с Java в командной строке

Reading time 11 min
Views 640K
Сейчас уже никто не создает программы в консоли. Используя любимую IDE, разработчик чувствует себя неуютно за чужим компьютером, где её нет.
Решив разобраться в работе Ant и Maven, я поймал себя на том, что не смогу собрать приложение без них в консоли.
В данной статье я постарался уместить все этапы проектирования демонстрационного приложения, чтобы не искать справку по каждой команде на просторах Интернета.
Читать дальше →
Total votes 75: ↑71 and ↓4 +67
Comments 25

Обсуждение работы алгоритма Романова на примере

Reading time 1 min
Views 2.8K
В продолжение вчерашнего обсуждения.

В прошлый раз остановились на том, чтобы объяснить как работают алгоритмы унификации и фильтрации на конкретном примере. Сам пример был построен особым образом, чтобы проверить определенные свойства алгоритмов.

Для дальнейшего обсуждения я написал небольшой unit-тест, который оперирует формулой из примера. Unit-тест нужен для того, чтобы пропустить шаг алгоритма Романова, где происходит декомпозиция исходной формулы на множество CTF. Вместо этого декомпозиция предлагается изначально автором вопроса.

Unit-тест и подробный лог работы приложения я выложил здесь:

gist.github.com/791064

Предлагаю по возможности ссылаться туда по номерам строк (там не совсем удобно, что нельзя дать прямую ссылку на номер строки, придется искать ее вручную; если кто-то предложит более удобный сервис, я перенесу лог туда).

Как видно из лога работы, тест заканчивается ситуацией, когда на очередном шаге построения гиперструктуры базисный граф оказался пустым множеством, что согласно алгоритму означает, что формула не выполнима (пункт 2b внизу страницы 11 в тексте статьи).

Чтобы не переписывать здесь еще раз статью, предлагаю в обсуждении задавать вопросы, которые требуют дополнительных разъяснений.
Total votes 26: ↑21 and ↓5 +16
Comments 24

Почему я не верю в простые алгоритмы для NP-полных задач

Reading time 3 min
Views 12K
На днях в этом блоге было опубликовано открытое письмо учёным по поводу предполагаемого полиномиального алгоритма для задачи 3-SAT. Обсуждение в том топике ещё далеко не закрыто и говорить о том, что в алгориме найдены ошибки пока преждевременно, но мне хочется написать почему «граждане учёные» не выстраиваются в очередь чтобы поскорее проверить это доказательство.

Примерно полгода назад, в августе 2010-го была опубликована попытка доказать что P≠NP. Тогда один математик-блогер, Скотт Оронсон, чтобы не казаться голословным в своём недоверии к этому доказательству поставил свой дом на то, что доказательство окажется ошибочным. Пожалуй, я ничего не потеряю если последую (с меньшим размахом) его примеру и поставлю на то, что нынешний алгоритм неправилен свой автомобиль (Auris 2008-го года выпуска).

По-моему, Оронсон немного рисковал. Винод Деолаликар, автор того доказательства — относительно известный математик, задача P≠NP входит в область его компетенции, и само доказательство использовало несколько принципиально новых идей, дающих надежду на то, что с помощью них удастся обойти трудности, с которыми сталкивались те кто пытался доказать этот факт до него. С нынешним доказательством ситуация немного иная.
Читать дальше →
Total votes 79: ↑58 and ↓21 +37
Comments 73

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

Reading time 3 min
Views 9.4K
С момента предыдущей публикации о полиномиальном алгоритме Романова для 3-ВЫП прошло 4,5 месяца.

За это время мы с Владимиром Федоровичем подготовили вариант статьи, чтобы отправить его коллегам-ученым и попутно реализовали эталонную реализацию этого алгоритма на Java.
Читать дальше →
Total votes 60: ↑52 and ↓8 +44
Comments 132

О проблеме продвижения научных работ и исследований

Reading time 3 min
Views 4.4K
По мотивам статьи «Сведение решения NP-полной задачи «3-выполнимость» к алгоритму с полиномиальной сложностью».

Кратко суть в том, что профессор одного из российских вузов не может добиться того, чтобы его статью опубликовали в зарубежном авторитетном журнале. И как всегда, находятся те, которые действуют по принципу «сам дурак», и вместо того, чтобы помочь советом пытаются написать что-то гневное в ответ. Так как мой комментарий в топике мало кто увидит из-за непопулярности статьи, поэтому беру на себя смелось опубликовать ответ отдельным постом.

Автор статьи, конечно же, мог бы более подробно описать суть работы, рассказать об авторе, привести ссылки на его другие работы, монографии и т.д. Но проблема, о которой он говорит, существует и о ней никто не говорит. У меня были похожие ситуации, поэтому немного поделюсь опытом и своими соображеними.
Читать дальше →
Total votes 32: ↑29 and ↓3 +26
Comments 14

Всё (или почти всё) о пробеле

Reading time 13 min
Views 133K
Как следует из заголовка, речь в статье пойдёт о неотъемлемой части любого русскоязычного (и не только) текста — о пробеле. Мы затронем историю пробела, виды пробелов, вопросы употребления пробела в веб-типографике.

Вообще говоря, пробел — это любое пустое место в рукописном, печатном или отображаемом на любом другом носителе тексте. Так что пробелы бывают разные:
  • спусковые (большие вертикальные пропуски в первой полосе издания) и концевые пробелы полосы,
  • абзацные отступы и концевые пробелы абзаца,
  • межстрочные пробелы (между строками текста),
  • межсловные пробелы (между словами в одной строке),
  • межбуквенные пробелы (между буквами в слове).
Далее речь пойдёт о межсловных пробелах, разделяющих слова, и функционально принадлежащих к знакам препинания.
Читать дальше →
Total votes 134: ↑130 and ↓4 +126
Comments 132

Information

Rating
Does not participate
Location
Россия
Date of birth
Registered
Activity