Задачка по поиску... - Page 2

shatver · Apr 19, 2004, 18:33

Есть массив из 256 значений, из которых два достоверно удовлетворяют некому условию... Узнать какие именно можно лишь подставив данные значения в это условие... требуется найти любое одно из этих двух значений... есть ли какая нибудь методика перебора(окромя простого последовательного перебора) чтоб найти одно из двух значений хотя бы не более чем за 128 проверок (если еще меньше то еще лучше ) с очень высокой долей вероятности
(80-90 %)... Или хотя бы убедиться что это невозможно..

Другой дополнительной инфы нету, типа отсортированности для бинарного поиска и т.д.

Agregat · Apr 20, 2004, 19:24

СЛучайный индексы получить как раз очень просто - хранишь список свободных позиций и каждый раз генерируешь случайное число в промежутке 0 - 255, 254, 253... 128 (например), и забираешь это число из индекса.

who · Apr 21, 2004, 07:36

Дональд Кнут - "Сортировка и поиск".

greka · Apr 21, 2004, 12:52

Quote:

Originally Posted by Aram Hambardzumyan

интуиция подсказывает, что можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. пусть нашему условию удовлетворяют элементы a и b. вероятность попадания хотя бы одного из них в нашу выборку - 75%.

интуиция тебя обманывает. Выделю время - укажу, в чем именно.

nm · Apr 21, 2004, 17:32

Quote:

Originally Posted by greka

интуиция тебя обманывает. Выделю время - укажу, в чем именно.

аргументы - в студи, интерестно все-таки ....
а ты - выделю время

shatver · Apr 21, 2004, 18:20

действительно интересно.. ведь вроде по азам теории вороятности 75% и получается...

greka · Apr 22, 2004, 11:59

Quote:

Originally Posted by shatver

действительно интересно.. ведь вроде по азам теории вороятности 75% и получается...

для начала разговора я бы попросил привести эти самые "азы" на свет божий.

shatver · Apr 22, 2004, 13:23

Greka ты издеваешься или где?
Арам же вроде ясно написал:
"если случайным образом отобрать половину элементов, то вероятность того, что элемент a окажется в этой половине - 50%. вероятность того, что в данной половине окажутся оба элемента, равна 25%. если в качестве упоминаемой половины рассмотреть невыбранные 128 элементов, то получается, что мы 'промахиваемся' с вероятностью 25%, т. е. вроятность нахождения хотя бы одного элемента - 75%
"

Aram Hambardzumyan · Apr 22, 2004, 13:31

Quote:

Originally Posted by shatver

Greka ты издеваешься или где?
Арам же вроде ясно написал:....

если я правильно понял, грека оспаривает 'легитимность' моей случайной выборки

nm · Apr 22, 2004, 15:29

Quote:

Originally Posted by greka

для начала разговора я бы попросил привести эти самые "азы" на свет божий.

Гарик, еще раз -- выкладки в студию

даже если они не правильные ....

п.с. к делу не относится, но вспомнилось. ...

академик - это человек, который может объяснить 5 летнему ребенку за что он получил это звание...

так что, Гарик, постарайся уж ...

greka · Apr 26, 2004, 09:13

>интуиция подсказывает, что можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. пусть нашему условию удовлетворяют элементы a и b. вероятность попадания хотя бы одного из них в нашу выборку - 75%.

Итак.

"можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. "

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

Но не надо забывать, что вероятность двух событий нужно перемножать - именно потому я и хотел проверить, кто и как знает эти самые "азы", о которых так уверенно рассуждалось.

Вероятность нахождения элемента не увеличивается, если исходное множество делить - ибо она должна быть ПОМНОЖЕНА на вероятность того, что СРЕДИ ОТБРАСЫВАЕМЫХ ЭЛЕМЕНТОВ НЕТ ТЕХ, КОТОРЫЕ НАМ НУЖНЫ.

а вы - делите пополам, говорите - веорятность удваивается, потом еще делите пополам - еще раз удвоилась вероятность - класс, теория вероятностей отдыхает

Aram Hambardzumyan · Apr 26, 2004, 09:32

Quote:

Originally Posted by greka

>интуиция подсказывает, что можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. пусть нашему условию удовлетворяют элементы a и b. вероятность попадания хотя бы одного из них в нашу выборку - 75%.

Итак.

"можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. "

случайная выборка - это не есть "поиск", не так ли?

в условии было ослаблено определение поиска и предлагалось получить какой-то результат за 128 шагов. можешь ли ты дать более действенный алгоритм при отсутсвии какой-либо закономерноси между элементами последовательности?

Quote:

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

Но не надо забывать, что вероятность двух событий нужно перемножать - именно потому я и хотел проверить, кто и как знает эти самые "азы", о которых так уверенно рассуждалось.

Вероятность нахождения элемента не увеличивается, если исходное множество делить - ибо она должна быть ПОМНОЖЕНА на вероятность того, что СРЕДИ ОТБРАСЫВАЕМЫХ ЭЛЕМЕНТОВ НЕТ ТЕХ, КОТОРЫЕ НАМ НУЖНЫ.

это всё я учитываю.

Quote:

а вы - делите пополам, говорите - веорятность удваивается, потом еще делите пополам - еще раз удвоилась вероятность

я такого не говорил, и из моих вылкадок это не следует. иначе на выборке 128 элементов я бы получил 100%

а какой результат получаешь ты для 128 шагов?

shatver · Apr 26, 2004, 09:33

"Но не надо забывать, что вероятность двух событий нужно перемножать - именно потому я и хотел проверить, кто и как знает эти самые "азы", о которых так уверенно рассуждалось."

У меня впечатление что либо ты не внимательно читаешь, либо стоит проверить свои собственные знания азов.. А то менторский тон так и хлышет за край...

Повторим еще раз

"если случайным образом отобрать половину элементов, то вероятность того, что элемент a окажется в этой половине - 50%."
50 % означает 1/2 ...

Далее
" вероятность того, что в данной половине окажутся оба элемента, равна 25%."

25% это 1/4, что есть умножение двух вероятностей (1/2) * (1/2)... то самое умножение, о котором мы по вашему мнению "забываем"..

greka · Apr 26, 2004, 10:35

2 shatver: "Greka ты издеваешься или где?", "менторский тон" - блин, пописай успокойся, что ли?

shatver · Apr 26, 2004, 10:41

"блин, пописай успокойся, что ли?"...
А что... помогает? тебе виднее наверное...

по сушеству давай....

greka · Apr 26, 2004, 11:07

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

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

AH, ты предлагаешь вдвое сократить множество возможных значений, и утверждаешь, что вероятность нахождения элемента увеличится. Абсолютная вероятность действительно "увеличивается". И с вероятностью 100% ты найдешь элементы, если "поделишь" множество еще 128 раз.

Если учтем относительную вероятность - т.е. вер-сть того, что за предыдущие 128 шагов ты не найдешь, и найдешь на 129-м:
1/2 * 2/128.

Т.е. меньше, чем 50%.

Комментарии?

Apr 20, 2004, 19:24	#16
Agregat Грустно... Join Date: Aug 2002 Location: Там, где всегда идут дожди Posts: 21,637 Rep Power: 11 Reputation: 211	СЛучайный индексы получить как раз очень просто - хранишь список свободных позиций и каждый раз генерируешь случайное число в промежутке 0 - 255, 254, 253... 128 (например), и забираешь это число из индекса. __________________ http://аvitya.livejournal.com Хотели, как лучше, а получилось даже хуже... Лозунг шахматиста: На каждый шах - ответим матом!

Apr 21, 2004, 07:36	#17
who cares?.. Join Date: Jan 2004 Location: RA Army Posts: 149 Rep Power: 5 Reputation: 10	Дональд Кнут - "Сортировка и поиск". __________________ "...She will love them when she sees them, they will lose her if they follow. And she only means to please them, and her heart is full and hollow like a cactus tree. While she's so busy being free. ..."

Apr 26, 2004, 09:13	#25
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	>интуиция подсказывает, что можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. пусть нашему условию удовлетворяют элементы a и b. вероятность попадания хотя бы одного из них в нашу выборку - 75%. Итак. "можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. " случайная выборка - это не есть "поиск", не так ли? т.е. случайная выборка не меняет абсолютной вероятности, только относительную: относительно вдвое уменьшенного кол-ва элементов вероятность нахождения нужных нам элементов, конечно же, возрастает. Но не надо забывать, что вероятность двух событий нужно перемножать - именно потому я и хотел проверить, кто и как знает эти самые "азы", о которых так уверенно рассуждалось. Вероятность нахождения элемента не увеличивается, если исходное множество делить - ибо она должна быть ПОМНОЖЕНА на вероятность того, что СРЕДИ ОТБРАСЫВАЕМЫХ ЭЛЕМЕНТОВ НЕТ ТЕХ, КОТОРЫЕ НАМ НУЖНЫ. а вы - делите пополам, говорите - веорятность удваивается, потом еще делите пополам - еще раз удвоилась вероятность - класс, теория вероятностей отдыхает __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Apr 26, 2004, 11:07	#30
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	shatver, нужно учитывать не только вероятность нахождения во второй половине каждого из элементов, но и вероятность нахождения этих двух элементов в одной и той же выборке. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - AH, ты предлагаешь вдвое сократить множество возможных значений, и утверждаешь, что вероятность нахождения элемента увеличится. Абсолютная вероятность действительно "увеличивается". И с вероятностью 100% ты найдешь элементы, если "поделишь" множество еще 128 раз. Если учтем относительную вероятность - т.е. вер-сть того, что за предыдущие 128 шагов ты не найдешь, и найдешь на 129-м: 1/2 * 2/128. Т.е. меньше, чем 50%. Комментарии? __________________ И повешенные могут качаться в неположенную сторону. /С.Е.Лец/

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Apr 19, 2004, 18:33
shatver Moderator Join Date: Jul 2002 Location: Yerevan Posts: 450 Rep Power: 7 Reputation: 10	Задачка по поиску... Есть массив из 256 значений, из которых два достоверно удовлетворяют некому условию... Узнать какие именно можно лишь подставив данные значения в это условие... требуется найти любое одно из этих двух значений... есть ли какая нибудь методика перебора(окромя простого последовательного перебора) чтоб найти одно из двух значений хотя бы не более чем за 128 проверок (если еще меньше то еще лучше ) с очень высокой долей вероятности (80-90 %)... Или хотя бы убедиться что это невозможно.. Другой дополнительной инфы нету, типа отсортированности для бинарного поиска и т.д.

Apr 21, 2004, 18:20	#20
shatver Moderator Join Date: Jul 2002 Location: Yerevan Posts: 450 Rep Power: 7 Reputation: 10	действительно интересно.. ведь вроде по азам теории вороятности 75% и получается...

Apr 22, 2004, 13:23	#22
shatver Moderator Join Date: Jul 2002 Location: Yerevan Posts: 450 Rep Power: 7 Reputation: 10	Greka ты издеваешься или где? Арам же вроде ясно написал: "если случайным образом отобрать половину элементов, то вероятность того, что элемент a окажется в этой половине - 50%. вероятность того, что в данной половине окажутся оба элемента, равна 25%. если в качестве упоминаемой половины рассмотреть невыбранные 128 элементов, то получается, что мы 'промахиваемся' с вероятностью 25%, т. е. вроятность нахождения хотя бы одного элемента - 75% "

Apr 26, 2004, 09:33	#27
shatver Moderator Join Date: Jul 2002 Location: Yerevan Posts: 450 Rep Power: 7 Reputation: 10	"Но не надо забывать, что вероятность двух событий нужно перемножать - именно потому я и хотел проверить, кто и как знает эти самые "азы", о которых так уверенно рассуждалось." У меня впечатление что либо ты не внимательно читаешь, либо стоит проверить свои собственные знания азов.. А то менторский тон так и хлышет за край... Повторим еще раз "если случайным образом отобрать половину элементов, то вероятность того, что элемент a окажется в этой половине - 50%." 50 % означает 1/2 ... Далее " вероятность того, что в данной половине окажутся оба элемента, равна 25%." 25% это 1/4, что есть умножение двух вероятностей (1/2) * (1/2)... то самое умножение, о котором мы по вашему мнению "забываем"..

Apr 26, 2004, 10:35	#28
greka Administrator Join Date: Sep 2001 Location: @work Posts: 5,347 Rep Power: 10 Reputation: 23	2 shatver: "Greka ты издеваешься или где?", "менторский тон" - блин, пописай успокойся, что ли?

Apr 26, 2004, 10:41	#29
shatver Moderator Join Date: Jul 2002 Location: Yerevan Posts: 450 Rep Power: 7 Reputation: 10	"блин, пописай успокойся, что ли?"... А что... помогает? тебе виднее наверное... по сушеству давай....

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
задачка на тему Самолет	mk	General	186	Dec 23, 2004 17:07
Задачка	Shirinyan	Fun	13	Oct 22, 2003 13:41
Задачка от Альберта, самого Энштейна	R0nIn	General	34	Aug 19, 2003 19:24
Еще одна задачка	Agregat	Languages, Compilers and Interpreters	15	Oct 8, 2002 19:22
Задачка	Amph	Algorithms	1	May 29, 2002 04:02