OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 28 Март, 2024 12:54

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 103 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.
Автор Сообщение
СообщениеДобавлено: Понедельник, 29 Август, 2011 16:35 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2449
Откуда: Россия, Томск
albobin писал(а):
Александр Ильин писал(а):
В общем, чем жёстче условия на последовательность, тем меньше вероятность соответствия ей, и вероятности эти надо по-разному высчитывать.
Вероятность появления любой конкретной последовательности чисел одинакова и равна (1/N)^N
Да, это минимальная вероятность.

Я имел в виду условия вида: "Какова вероятность того, что среди выпавших неуникальных чисел сумма чётных будет равна 50?"


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 18:36 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
albobin писал(а):
Я тут было засомневался в том, а правильно ли делать вывод 2. сразу же из 1. , но потом на досуге не нашёл опровержений.

Наверное, не совсем правильно, но легко поправимо. Из 1 следует, что у нас биномиальное распределение, а для него матожидание = np, т.е n*(1+1/n)^n.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 20:01 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Я рассуждал так.
Пусть у нас есть N чисел.
Всего комбинаций без повторений - это перестановки - равно N!
Всего комбинаций с повторениями равно N^N.
Итого отношение N!/N^N дает вероятность выпадения N чисел без повторений.
Что не так?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 20:47 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Формула такая же, как и приведённая Trurl-ем на 2 странице. Только описка в трактовке числа N^N.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 21:14 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Valery Solovey писал(а):
Формула такая же, как и приведённая Trurl-ем на 2 странице. Только описка в трактовке числа N^N.

Ага, увидел... :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 30 Август, 2011 08:18 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Сергею Губанову.
Вот наткнулся на Tiger.
http://ru.wikipedia.org/wiki/Tiger_%28% ... 8%D1%8F%29
http://ru.wikipedia.org/wiki/TTH
C ним не пробовали поэкспериментировать?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 30 Август, 2011 18:49 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Валерий Лаптев писал(а):
Сергею Губанову.
Вот наткнулся на Tiger.
http://ru.wikipedia.org/wiki/Tiger_%28% ... 8%D1%8F%29
http://ru.wikipedia.org/wiki/TTH
C ним не пробовали поэкспериментировать?
Не пробовал и не собираюсь.

Сформулирую "достижение мысли" этой ветки форума. Эффективность (для построения хэштаблицы) идеальной хэшфункции равна 1-1/e. Около этого значения очень маленькая дисперсия. Поэтому при больших N совершенно бессмысленно брать сложную хэшфункцию с эффективностью, например, 0.632, если самая простая имеет эффективность 0.631 (всего на одну тысячную меньше).

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 30 Август, 2011 21:15 

Зарегистрирован: Воскресенье, 04 Ноябрь, 2007 23:01
Сообщения: 151
Валерий Лаптев писал(а):
..Tiger
Нечесна ;).
Tiger - это не хеш-функция, а способ применения оной.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 31 Август, 2011 06:21 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Сергей Губанов писал(а):
...
Сформулирую "достижение мысли" этой ветки форума. Эффективность (для построения хэштаблицы) идеальной хэшфункции равна 1-1/e. Около этого значения очень маленькая дисперсия. Поэтому при больших N совершенно бессмысленно брать сложную хэшфункцию с эффективностью, например, 0.632, если самая простая имеет эффективность 0.631 (всего на одну тысячную меньше).
...
Вот теперь интересно: а как объяснить эту очень маленькую дисперсию? Что здесь за закон природы такой действует?.. :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 31 Август, 2011 06:45 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Слово "искусство" применительно к выбору хеш-функции, конечно, есть элемент надувания щек, но внимательность, несомненно, нужна, когда речь о специфических данных, где много сильно скоррелированных элементов (фамилии, например, где коррелируют буквы и много одинаковых суффиксов; или в той же символической алгебре, где могут коррелировать показатели степеней переменных, которыми кодируются мономы, которые и надо хешировать).
Простодушный выбор х.ф. тогда может оказаться дико неудачным -- нерандомизирующим в силу коррелированности элементов данных.

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

В сфере ИТ такой просмотр меня не особо удивил бы, -- но Кнут человек скрупулезный, может, у него где-то это все-таки упоминается?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 31 Август, 2011 08:24 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Info21 писал(а):
...
Я не следил за диспутом, но было бы странно, если бы такой вероятностный закон не был известен. В физике, во всяком случае, это было бы странно (не случайно физик, столкнувшись с задачей, сразу в пунктик пальцем ткнул).
...
Ага... человек поставил эксперимент (вычислительный в данном случае), получил результат и задумался, как его объяснить. :) Вспоминается такая история. Л.Д. Ландау (кажется) спросили, что он может сказать об учёном Н. как о физике. Ландау ответил: "Физики получают результаты, а Н. доказывает теоремы." :) В то же время необязательна оппозиция мышлений. Так, тот же метод проверки моделей (систем алгопроцессов) можно, пожалуй, рассматривать как эксперимент по проверке логических утверждений на математической модели системы. Т.е. математика - однако принцип физический - так сказать, "экспериментальное доказательство теорем"... :wink:


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 31 Август, 2011 09:37 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Trurl писал(а):
albobin писал(а):
Я тут было засомневался в том, а правильно ли делать вывод 2. сразу же из 1. , но потом на досуге не нашёл опровержений.

Наверное, не совсем правильно, но легко поправимо. Из 1 следует, что у нас биномиальное распределение, а для него матожидание = np, т.е n*(1+1/n)^n.

Хоть вроде бы уже всё обсуждено, но есть некоторая неудовлетворённость.
Биномиальное распределение получится, если, наверное, всё таки "свольничать" и "нужным" образом эксперимент мысленно трансформировать.

Имеем.
1. N раз генерируем число из диапазона 1..N, для каждого числа вероятность появления в одной попытке одинакова и равна 1/N, и непоявления (1-1/N)
2. Для любого из чисел 1..N вероятность события "это число ни разу за N попыток не сгенерировано" равна (1-1/N)^N
3. После N попыток имеем итог, что какое-то кол-во чисел из 1..N так и ни разу не появилось. (Хотелось бы найти мат.ожидание этого кол-ва)

Начинаем "биномиализацию" :)
Опираемся на изложенное в п.2 п.3, отвлекаемся от конкретных чисел и представляем, что будто бы в процессе исходного
эксперимента неявно происходит и другой, в котором в каждой из N попыток имеем некое событие,назовём его - "нет числа", c вероятностью численно равной (1-1/N)^N (см. п.2)
Получаем мат.ожидание кол-ва событий "нет числа" после N попыток N((1-1/N)^N) (бином.распред.)
Следует заметить, что в этом неявном эксперименте результат значим только после окончания (N попыток), потому как эти попытки разворачиваются как бы "ортогонально" исходному процессу (N попыток, потому что N чисел)

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

PS.
Книжки почитать правильней, но ответ то хочется знать без приложения усилий :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 31 Август, 2011 11:59 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Драконограф писал(а):
... Л.Д. Ландау (кажется) спросили, что он может сказать об учёном Н. как о физике. Ландау ответил: "Физики получают результаты, а Н. доказывает теоремы." :) В то же время необязательна оппозиция мышлений. ...
А главное, оппозиция мышлений не соответствует оппозиции наук (физики<>математики).

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 31 Август, 2011 12:00 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
albobin писал(а):
Книжки почитать правильней, но ответ то хочется знать без приложения усилий :)
По-моему наоборот: из Кнута проще, но самому поупражняться -- правильней 8)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 31 Август, 2011 12:44 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
albobin писал(а):
1. N раз генерируем число из диапазона 1..N, для каждого числа вероятность появления в одной попытке одинакова и равна 1/N, и непоявления (1-1/N)
2. Для любого из чисел 1..N вероятность события "это число ни разу за N попыток не сгенерировано" равна (1-1/N)^N

Для простоты обозначим эту вероятность p.
Для любых k чисел вероятность события "за N попыток ни разу не сгенерированы эти и только эти числа" равна p^k*(1-p)^(N-k).
Всего множеств по k чисел - C(k,N). Соотсветственно вероятность события "за N попыток ни разу не сгенерированы ровно k чисел" - C(k,N)*p^k*(1-p)^(N-k).

Другими словами: "процесс" состоит в том, что мы перебираем числа от 1 до N и смотрим, не попало ли число в категорию "ни разу не сгенерированных".


Последний раз редактировалось Trurl Среда, 31 Август, 2011 14:32, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 31 Август, 2011 13:26 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Trurl писал(а):
... Другими словами ...

"Другие слова" гораздо лучше выражают мысль. :)

PS.
Но опять что-то не то :(


Последний раз редактировалось albobin Четверг, 01 Сентябрь, 2011 07:02, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 01 Сентябрь, 2011 06:57 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Trurl писал(а):
albobin писал(а):
1. N раз генерируем число из диапазона 1..N, для каждого числа вероятность появления в одной попытке одинакова и равна 1/N, и непоявления (1-1/N)
2. Для любого из чисел 1..N вероятность события "это число ни разу за N попыток не сгенерировано" равна (1-1/N)^N

Для простоты обозначим эту вероятность p.
Для любых k чисел вероятность события "за N попыток ни разу не сгенерированы эти и только эти числа" равна p^k*(1-p)^(N-k) ...


Опять возражаю.
Нельзя применять перемножение вероятностей, события не независимы :(
Ведь в одной попытке генерится только одно значение. Определяя вероятность негенерации конкретных чисел комбинаторным способом как отношение всех возможных вариантов развития событий за N попыток к числу всех возможных (N^N) получим то, что есть комбинации для разных чисел, которые вступают в противоречие из-за ограничение на единственность значения в конкретной попытке.
Самое смешное но формула N((1-1/N)^N) для мат.ожидания интуитивно понятна, а формализьм пока не поддаётся. Хочется же быстренько, одним махом без погружения в теории :)


Последний раз редактировалось albobin Четверг, 01 Сентябрь, 2011 09:15, всего редактировалось 3 раз(а).

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 01 Сентябрь, 2011 07:22 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
albobin писал(а):
...
Опять возражаю.
Нельзя применять перемножение вероятностей, события не независимы :(
Мы можем строить сложные события вовлекающие несколько значений только с условием непересечения их в пределах каждой попытки.
...
Не понял... имеется в виду, что алгоритм генерации как бы обладает данными, какие числа из интервала уже были сгенерированы?..


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 01 Сентябрь, 2011 07:26 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Драконограф писал(а):
albobin писал(а):
...
Опять возражаю.
Нельзя применять перемножение вероятностей, события не независимы :(
Мы можем строить сложные события вовлекающие несколько значений только с условием непересечения их в пределах каждой попытки.
...
Не понял... имеется в виду, что алгоритм генерации как бы обладает данными, какие числа из интервала уже были сгенерированы?..

Язык моя - враг ...
Мысль уточнил уже.
PS.
Боюсь, уточнил всё таки не точно.
Рассмотрим ситуацию.
событие A: негенерация числа A за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа B.
событие B: негенерация числа B за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа А.
Отсюда и отсутствие независимости.
из A может следовать 'не B' и наоборот.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 01 Сентябрь, 2011 10:20 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
albobin писал(а):
Рассмотрим ситуацию.
событие A: негенерация числа A за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа B.
событие B: негенерация числа B за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа А.
Отсюда и отсутствие независимости.
из A может следовать 'не B' и наоборот.

А давайте упростим.;)
событие A: генерация числа A за 1 попыткe, означает негенерацию любого из остальных, в том числе и числа B.
событие B: генерация числа B за 1 попыткe, означает негенерацию любого из остальных, в том числе и числа A.
Однако A и B независимы, в чём легко убедиться: P(A|B)=P(AB)/P(B), поскольку P(A|B)=0,P(AB)=0.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 103 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB