информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
За кого нас держат?Где водятся OGRыПортрет посетителя
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / miscellaneous
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
странные мысли по поводу NP-полноты 08.05.03 22:44  
Автор: tdes <jin> Статус: Member
<"чистая" ссылка> <обсуждение закрыто>
возьмем, скажем, прямоугольную сетку сосотящую из проволочек, соединенных в узлах, создадим разнось потенциалов между двумя краями сетки. теперь начнем произвольно разрезать проволочки между двумя узлами. сетка описывает граф и задача нахождения , кратчайшего расстояния между двумя сторонами является NP-сложной, однако до тех пор, пока существует такой путь ток будет течь по сетке, при этом как бы сама “природа” решает эту задачу, при этом такое чувство, что полиномиально.
интересно что вы думаете по этому поводу :)))
странные мысли по поводу NP-полноты 13.05.03 14:08  
Автор: ilnar Статус: Незарегистрированный пользователь
<"чистая" ссылка> <обсуждение закрыто>
> возьмем, скажем, прямоугольную сетку сосотящую из
> проволочек, соединенных в узлах, создадим разнось
> потенциалов между двумя краями сетки. теперь начнем
> произвольно разрезать проволочки между двумя узлами. сетка
> описывает граф и задача нахождения , кратчайшего расстояния
> между двумя сторонами является NP-сложной, однако до тех
> пор, пока существует такой путь ток будет течь по сетке,
> при этом как бы сама “природа” решает эту задачу, при этом
> такое чувство, что полиномиально.
> интересно что вы думаете по этому поводу :)))

подождите, если вы о задаче нахождения кратчайшего пути между двумя пунктами в графе - так эта задача полиномиальная!! Алгоритмы дейкстры, Флойда-Уоршелла на то пример
согласен )) 14.05.03 11:18  
Автор: tdes <jin> Статус: Member
<"чистая" ссылка> <обсуждение закрыто>
Мы живем в виртуальной вселенной. 13.05.03 06:28  
Автор: Zef <Alloo Zef> Статус: Elderman
<"чистая" ссылка> <обсуждение закрыто>
Вселенную следует рассматривать как клеточный автомат типа "жизнь" с внешними возмущениями. (см. http://www.bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=18&m=77316, к вопросу о весе винчестера.)
Вот только, юмористического взгляда на эту гипотезу с Автором я не разделяю; с аналогичной идеей я ношусь с 96го года и набрал уйму аргументов в ее пользу.

Пространство на с.д. представляет собой одномерное непрерывное множество нумированных ячеек; все многообразие видимых (и невидимых) нами измерений обусловленно его топологией. (Как видеопамять: 1й ячейке соответствует 1024я, 2048я и т.д., но никто ведь на с.д. память на барабан окружностью 1024 ячейки не "наматывал")

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

В некоторые ячейки пространства что-то (или кто-то), извне вводит новые, (с нашей точки зрения "абсолютно случайные") значения. Это обуславливает необратимость процессов во времени. (кто экспериментировал с "жизнью", знает) Тот момент, что необратимость процессов во времени можно объяснить только поступающим в нашу вселенную потоком внешней, никак не связанной с внутренними процессами и никак "изнутри" не управляемой информации очень хорошо в своих работах обосновал наш соотечественник, лауреат Нобелевской премии Илья Романович Пригожин.

Кого заинтересовала данная гипотеза, предлагаю подискутировать. Если ответов окажется достаточно много, готов открыть специальный форум на сервере ИДСТУ СО РАН.
а адрес этого сервера можно? 13.05.03 15:17  
Автор: vh <Дмитрий> Статус: Member
<"чистая" ссылка> <обсуждение закрыто>
Взломать сервер Господа Бога и установить вечную жизнь и бесконечные деньги? 14.05.03 06:25  
Автор: Zef <Alloo Zef> Статус: Elderman
<"чистая" ссылка> <обсуждение закрыто>
Увы, я действительно постепенно вынужден приходить к мнению, что этот Мир, результат чьего-то сознательного эксперимента.
Закон больших чисел и причинно-следственные связи в нем нарушаются. А это ни чем другим, кроме "сознательной запланированности" и внешнего управления с целью получить желаемый результат объяснить не возможно.

Ну, а после Пригожинских доказательств наличия внешнего информационного потока...
Мои мысли 14.05.03 13:00  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка> <обсуждение закрыто>
> Увы, я действительно постепенно вынужден приходить к
> мнению, что этот Мир, результат чьего-то сознательного
> эксперимента.
Запросто можно допустить что человечество создано кем-то (неважно как называть инопланетяне, бог и т.д.) или даже наша вселенная. Но так или иначе в конце концов должно существовать нечто что самоорганизовалось в самом начале, причем совершенно случайно. Аргументы типа бог был всегда и вообще все началось с его слова не принимаются, потому как точно так же я могу постулировать просто некий закон мироздания который неизбежно приводит к самоорганизации любых систем (ну ее на фиг эту термодинамику - она только для идеальниых газов :-)))) )

> Закон больших чисел и причинно-следственные связи в нем
> нарушаются. А это ни чем другим, кроме "сознательной
Вселенная НЕ ОБЯЗАНА подчиняться НАШИМ законам. Наоборот наши законы - суть просто попытка обобщения эмпирических данных. Если новые данные не вписываются в наши законы, значит наши законы еще недостаточно точно отражают ИСТИННОЕ положение вещей и все.

> запланированности" и внешнего управления с целью получить
> желаемый результат объяснить не возможно.
"Многие вещи нам непонятны не потому, что наши понятия слабы; но потому, что сии вещи не входят в круг наших понятий."
Невозможно сейчас, но это не значит что невозможно в принципе.

> Ну, а после Пригожинских доказательств наличия внешнего
> информационного потока...
Я бы мир изменил - но Бог не дает исходников. 14.05.03 13:19  
Автор: Wud <Леха> Статус: Member
<"чистая" ссылка> <обсуждение закрыто>
Оффтоп конечно, но там хотелось вставить эту фразу сюда.
-
Из собрания анекдотов от Sandy на 13.05.03
---

тут
"Мичуринец"! Не менять, хотя б понять...8-( 15.05.03 07:11  
Автор: Zef <Alloo Zef> Статус: Elderman
<"чистая" ссылка> <обсуждение закрыто>
господа, идея была следующая: 12.05.03 13:06  
Автор: tdes <jin> Статус: Member
<"чистая" ссылка> <обсуждение закрыто>
в месте кратчайшего пути всегда наблюдается самая большая сила тока, при этом переходные процессы в сетке достаточно быстро приводят систему к устойчивому состоянию и время, за которое это происходит, мало зависит от размеров сетки. таким образом “ток” знает как решать NP-сложную задачу полиномиально, хотелось бы понять как “он” это делает и доказать P=NP :)))
Физикам - не читать ! Поберегите свои нервы ;)) 12.05.03 16:42  
Автор: PS <PS> Статус: Elderman
<"чистая" ссылка> <обсуждение закрыто>
У нас есть ОДИН проводник, на его краях (торцах) есть разнозначный заряд.
Каким образом электрончики знают что где-то там есть протончики ? Откуда они знают что им вообще надо куда то двигаться ?

Давай на пальцах, диплома по физики нет, только курс средней школы и первого-второго курса института.

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

+ + + + + + +
==========
- - - - - - - - - -


+ + + + + + +
+========== -
- - - - - - - - - -

+ + + + + + +
+- ========== -
0 - - - - - - - -


+ + + + + + +
+- ========== -
- 0 - - - - - - -

......

+ + + + + + +
+- ========== 0
- - - - - - - - - -

Итак, что мы имеем в такой модели: заряд перемещается по самому кратчайшему пути, т.е. никакой задачи нахождения кратчайшего пути просто не существует.
Другими словами СУММА( кратчайших перемещений ) = кратчайшему пути.
Может возникнуть вопрос: а как же электрон "знает" что он находится ближе всего, и что именно ему надо перемещаться ? Да никак не знает !
Допустим два электронна отрываются от своих (плохо держащих) их протонов и несутся к одному одинокому протону. Один из этих электронов достигнет цели первым. Все, напряженность исчезла и втрой электрон остался не у дел. Но ! Он отрицателен, а где то рядом аж ДВА одиноких положительных заряда. Опять напряженность. Он ломанется туда где напряженность больше, может быть и на старое место.
Вот и выходит что двигаются тогда когда есть возможность двигаться. Когда энергия поля больше энергии необходимой для отрыва. (так это уже не из той оперы). И двигаются по кратчайшему растоянию, а кратчайшее у того, кто первый достигнет цели.

Еще раз повторю, что бы понятней было: в системе
A n1 n2 n3 n4 n5 B
Движение происходить не от B к A, а от n1 к A, после от n2 к n1, после от n3 к n2 и т.д. до от B к n5

Фуф, вот тебе и способ нахождения кратчайшего пути безо всякой математики :)))
На пальцах для таких .... вроде меня :) 13.05.03 05:39  
Автор: vh <Дмитрий> Статус: Member
<"чистая" ссылка> <обсуждение закрыто>
физику не знаю практически вообще :(

Можно ли это выразить грубо так?

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

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

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

А вообще что я несу такое? :) пойду делать rftm по этому делу.
если честно, не понял... 12.05.03 19:58  
Автор: tdes <jin> Статус: Member
<"чистая" ссылка> <обсуждение закрыто>
От физика - а чего, нормально описано, кстати :) 12.05.03 17:06  
Автор: Ktirf <Æ Rusakov> Статус: Elderman
<"чистая" ссылка> <обсуждение закрыто>
А природа решает это не через граф и не через перебор 11.05.03 15:11  
Автор: PS <PS> Статус: Elderman
<"чистая" ссылка> <обсуждение закрыто>
А "волновым" методом :)
С точки зрения компьютерного вычисления волновой метод очень ресурсоемкий.
А вот в прероде много чего именно им и решается, например движение заряда в проводниках, движение воды или воздушных потоков.
Типа, пойдем туда куда можно, а как только достигнем цели - создадим путь.
Согласен. Но все равно, 12.05.03 06:42  
Автор: Zef <Alloo Zef> Статус: Elderman
<"чистая" ссылка> <обсуждение закрыто>
это вариация на тему последовательных приближений, а не "решение системы линейных уравнений"
странные мысли по поводу NP-полноты 11.05.03 00:44  
Автор: vh <Дмитрий> Статус: Member
<"чистая" ссылка> <обсуждение закрыто>
помню вроде б в компьютерре писали об устройстве действующем на этом же св-ве. Такая небольшая пластинка в помощью туристу на которой схематически изображалась карта местности. Тима зажимаешь два конца и получается самый короткий путь.

Я в физике полный ноль (стыдно конечно признаться), но если кто что знает, объясните плиз за счет чего проявляется это сво-во, ведь благодаря ему можно наверное придумать массу интересных вещей. Или это на самом деле давно уже придумано? :))
Есть еще пример со стопкой перфокарт 09.05.03 12:37  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка> <обсуждение закрыто>
Стопка перфокарт со случайными прорезями. Есть ли в стопке сквозная прорезь. Тоже NP-полная. Но в этом случае она решается за линейное (от высоты стопки) время потому как перебор производится по всей поверхности перфокарты
Последовательное приближение 09.05.03 08:16  
Автор: Zef <Alloo Zef> Статус: Elderman
<"чистая" ссылка> <обсуждение закрыто>
Процесс "перебалансировки" токов в сетке можно рассматривать двояко:

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

2. Тот же колебательный процесс можно рассматривать с позиций инерции электронов и конечной скорости распространения электромагнитного поля в проводнике.
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach