Category: праздники

Category was added automatically. Read all entries about "праздники".

with Cat The Cat

Парадокс дней рождения.

Статья на Википедии.

В общем, чтобы вероятность совпадения дней рождения пришедшего на вечеринку человека и любого из уже веселящихся, превысила 50%, надо, чтобы оттягивающихся было всего 23 человека.

Когда ещё никого нет, вероятность совпадения с только что пришедшим 0/365. Когда скучает всего один - 1/365. Когда беседуют двое - 1093/3652. Когда веселятся N - 1-(1-(вероятность для (N-1)))*(1-N/365).

При увеличении N число M, для которого вероятность переваливает за 0,5, можно аппроксимировать путём нехитрой формулы M=1,1774106*sqrt(N), выведенной эмпирически.

Этот парадокс непосредственно связан с хешированием данных. Вероятность коллизии - появления данных с уже зарегистрированным ключом, - описывается процессом выше. Для оптимальной работы хэш-таблицы требуется число ячеек, равное квадрату от планируемого количества хранимых элементов. Из-за него же криптографические хэш-функции (MD4/5, например) имеют размер дайджеста вдвое больше, чем размер ключа современных им шифров (56 битов DES - 128 у MD5, 128 у AES и 256 у SHA2).

А ещё очень интересно смотреть на случайные идентифицирующие числа. Например, на GUID.

Или вот такое: сколько надо битов, чтобы случайный цифровой идентификатор не совпал для, допустим, всех жителей Земли? Количество людей на Земле укладывается в 233, значит, нам понадобится 66 бит и больше.