Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 20.04.2004, 20:24   #16
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

СЛучайный индексы получить как раз очень просто - хранишь список свободных позиций и каждый раз генерируешь случайное число в промежутке 0 - 255, 254, 253... 128 (например), и забираешь это число из индекса.
Reply With Quote
Old 21.04.2004, 08:36   #17
cares?..
 
who's Avatar
 
Join Date: 01 2004
Location: RA Army
Age: 47
Posts: 149
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Thumbs up

Дональд Кнут - "Сортировка и поиск".
Reply With Quote
Old 21.04.2004, 13:52   #18
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

Quote:
Originally Posted by Aram Hambardzumyan
интуиция подсказывает, что можно, не ограничивая общности, ограничиться случайной выборкой 128 элементов из данных 256. пусть нашему условию удовлетворяют элементы a и b. вероятность попадания хотя бы одного из них в нашу выборку - 75%.
интуиция тебя обманывает. Выделю время - укажу, в чем именно.
Reply With Quote
Old 21.04.2004, 18:32   #19
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

Quote:
Originally Posted by greka
интуиция тебя обманывает. Выделю время - укажу, в чем именно.
аргументы - в студи, интерестно все-таки ....
а ты - выделю время
Reply With Quote
Old 21.04.2004, 19:20   #20
Moderator
 
shatver's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 46
Posts: 450
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

действительно интересно.. ведь вроде по азам теории вороятности 75% и получается...
Reply With Quote
Old 22.04.2004, 12:59   #21
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

Quote:
Originally Posted by shatver
действительно интересно.. ведь вроде по азам теории вороятности 75% и получается...
для начала разговора я бы попросил привести эти самые "азы" на свет божий.
Reply With Quote
Old 22.04.2004, 14:23   #22
Moderator
 
shatver's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 46
Posts: 450
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Greka ты издеваешься или где?
Арам же вроде ясно написал:
"если случайным образом отобрать половину элементов, то вероятность того, что элемент a окажется в этой половине - 50%. вероятность того, что в данной половине окажутся оба элемента, равна 25%. если в качестве упоминаемой половины рассмотреть невыбранные 128 элементов, то получается, что мы 'промахиваемся' с вероятностью 25%, т. е. вроятность нахождения хотя бы одного элемента - 75%
"
Reply With Quote
Old 22.04.2004, 14:31   #23
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Default

Quote:
Originally Posted by shatver
Greka ты издеваешься или где?
Арам же вроде ясно написал:....
если я правильно понял, грека оспаривает 'легитимность' моей случайной выборки
Reply With Quote
Old 22.04.2004, 16:29   #24
ЙЦУКЕН
 
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 47
Posts: 3,118
Downloads: 0
Uploads: 0
Reputation: 5 | 0
Default

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

Гарик, еще раз -- выкладки в студию даже если они не правильные ....


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

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


так что, Гарик, постарайся уж ...
Reply With Quote
Old 26.04.2004, 10:13   #25
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

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

Итак.

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

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

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

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

а вы - делите пополам, говорите - веорятность удваивается, потом еще делите пополам - еще раз удвоилась вероятность - класс, теория вероятностей отдыхает
Reply With Quote
Old 26.04.2004, 10:32   #26
The Reloaded
 
Aram Hambardzumyan's Avatar
 
Join Date: 01 2002
Location: behind the flesh and gelatinе of soft dull eyes
Posts: 3,387
Downloads: 4
Uploads: 0
Reputation: 146 | 4
Default

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

Итак.

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

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

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

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

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

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

а какой результат получаешь ты для 128 шагов?
Reply With Quote
Old 26.04.2004, 10:33   #27
Moderator
 
shatver's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 46
Posts: 450
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

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

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


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

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

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

25% это 1/4, что есть умножение двух вероятностей (1/2) * (1/2)... то самое умножение, о котором мы по вашему мнению "забываем"..
Reply With Quote
Old 26.04.2004, 11:35   #28
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

2 shatver: "Greka ты издеваешься или где?", "менторский тон" - блин, пописай успокойся, что ли?
Reply With Quote
Old 26.04.2004, 11:41   #29
Moderator
 
shatver's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 46
Posts: 450
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

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

по сушеству давай....
Reply With Quote
Old 26.04.2004, 12:07   #30
Академик
 
greka's Avatar
 
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Downloads: 0
Uploads: 0
Reputation: 18 | 5
Default

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

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

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

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

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

Комментарии?
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 19:19.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.