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

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

Доказать это не так уж и сложно, особенно если вникнуть в совершенно простую задачу про ушки.

Доказывать я тут не буду, лишь скажу, что это правда, а решение очень простое (hint: попробуйте для начала подсчитать, сколько разных пар составляют 23 человека). Доказать можно как с помощью логики и теории вероятности, так и экспериментальным путем. Отсылаю к ДиаLOG’у, где все подробно теоретически расписано и даже есть программа на Бейсике, которая все считает — специально для тех, кто не верит в теорию.

Лирическое отступление. Кажется невероятным, что среди всего 23 человек скорее найдутся, чем не найдутся отмечающие день рождения в один день, учитывая, что в году их 365. Практически кажется, что «раскидать» 23-х по 365-и дням проще пареной репы. В общем, слабо верится в это все. Но.© Оттуда же.

Специально для тех, кто не верит в Бейсик, вот мой скромный вклад в науку (на php):


for ($z=1; $z<10000; $z++):
for ($i=1; $i<23; $i++) $a[$i]=rand (1,365);
if (count (array_unique ($a))!=22) $r++;
endfor;
echo ($r/100)."%";


Выводит процент несовпадений. Использовать count (array_unique ($a)), конечно же, весьма глупо, но я стремился не к оптимизации кода, а к тому, чтобы как меньше надо было его печатать. (Если array_fill работает с random’ными значениями, (хотя я не уверен) можно было бы и вторую строчку сделать короче). Зато при использовании array_unique этот код можно легко переделать под условие «более 2х человек».

Отсюда. Вероятность встретить человека, у которого День Рождения в один день с вами, все равно составляет 1/365, а вот вероятность того, что из 23 ваших друзей у кого-нибудь Дни Рождения совпадают — более 50%.

ОК. Объяснение этой задачи «на уровне понимания». Первое. Утверждение «Практически кажется, что „раскидать“ 23-х по 365-и дням проще пареной репы» — верное. Однако, верно и второе утверждение: «Раскидать 23х по 365-и дням как угодно (даже если они и повторяются) гораздо проще». Во-первых, нам не нужно следить, чтобы они не повторялись. Во-вторых — если хорошо подумать — оказывается, что вариантов такой «раскидки» несколько больше, чем вариантов раскидки «чтобы не повторялись».

Вот, собственно, и все.

Там же, на Диалоге, попытка теософского самоопределения:

Так вот. Верю ли я в Бога? Спрашивали тут некоторые. Отвечаю. Я открыл для себя тот факт, что вопрос о вере в Бога решается только на уровне определений. Этот вопрос пустой. Каждый по своему представляет себе, что такое Бог. С этой точки зрения не верить невозможно. Потому, что невозможно всё объяснить. Для меня Бог — это случайность. Все, в чем отсутствует очевидная закономерность — это Бог. Это не бородатый дедушка, который сидит на облаке, приказывая облакам пролиться дождем; Бог — это тот факт, что существуют случайности. В то, что существуют случайности я верю, а в бородатого дедушку — нет.
вот тут

Ну, «дедушка с бородой» — это конечно же, чистый антропоморфизм.

Антропоморфизм (от антропо... и греч. morpho — вид), уподобление человеку, наделение человеческими психическими свойствами предметов и явлений неживой природы, небесных тел, животных, мифических существ. Наивно-догматический А. представляет собой первоначальную форму мировоззрения и выражается в наделении неодушевлённых предметов способностью действовать, жить и умирать, испытывать переживания и т.д. (земля спит, небо хмурится и т.п.). Такой А. являлся господств. формой мировоззрения на ранних ступенях развития человеческого общества... Однако как способ мышления такой А. в настоящее время свойствен только психике ребёнка, у взрослых людей он является обычно признаком инфантилизма. Наивно-догматический А. перерастает в религиозный А. — перенесение облика и свойств человека на вымышленные предметы, присущее большинству религиозных представлений о богах и других сверхъестественных существах. Антропоморфными, в частности, являются обычно боги т. н. высших религий, хотя в теологии это обстоятельство отрицается.© БЭС

Но в эволюцию, как в генератор случайных чисел («мутации») и обратной связи («выживет — не выживет») верить тоже глупо. А так — я бы не сказал, что Бог это «случайности». Ибо случайностей не бывает, а бывают только неизвестные нам закономерности. Таким образом, Бог — это закон(ы). Законы жизни, вселенной и всего остального. Есть физические законы и они работают (не всегда, правда, есть же всякие квантовые уровни и проч., где законы совсем другие). Есть, вероятно, какие-то моральные законы (законы кармы) и они тоже работают (и тоже, вероятно, не всегда). Моральными и духовными законами интересуется в основном религия, причем некоторые религии действительно преуспели в этом. Есть законы развития жизни, то есть законы «эволюции». Мы их не знаем, поэтому нам проще объяснять все «случайностью». (Вот, на тему случайностей — доказательство бытия Божего от Священика Димитрия Каплуна).

Такие дела.

Pngcrush

По наводкам читателей — Pngcrush:

«Pngcrush is an excellent batch-mode compression utility for PNG images. Depending on the application that created the original PNGs, it can improve the file size anywhere from a few percent to 40% or more (completely losslessly)».

Pngcrush — утилитка, работающая из командной строки и заметно сжимающая файлы PNG практически без потери качества изображения. По крайней мере, разработчики обещают именно это.

И вы знаете, действительно жмет, причем гораздо лучше smart saver’а из ulead’а, и действительно без особых потерь в качестве. Просто удивительно. Единственный минус — командная строка. Удовольствие не для всех. Советую попробовать запускать с ключом -brute.

Все, теперь все скриншоты — только сжатые этой программой PNG. GUI’евую оболочку никто написать не хочет, дабы популяризировать программу в народных массах?..

Частота букв в русском языке

Написал забавный php-скрипт. Погонял через него все тексты на «Спектаторе» на предмет языка. Всего в текстах употребляется 39110 разных словоформ. Сколько именно разных слов — определить довольно сложно. Чтобы хоть как-то приблизиться к этой цифре, я брал только первые 5 букв слова и сравнивал их. Получилось 14373 таких комбинаций. С большой натяжкой это можно назвать словарным запасом «Спектатора».

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

о — 9.28%
а — 8.66%
е — 8.10%
и — 7.45%
н — 6.35%
т — 6.30%
р — 5.53%
с — 5.45%
л — 4.32%
в — 4.19%
к — 3.47%
п — 3.35%
м — 3.29%
у — 2.90%
д — 2.56%
я — 2.22%
ы — 2.11%
ь — 1.90%
з — 1.81%
б — 1.51%
г — 1.41%
й — 1.31%
ч — 1.27%
ю — 1.03%
х — 0.92%
ж — 0.78%
ш — 0.77%
ц — 0.52%
щ — 0.49%
ф — 0.40%
э — 0.17%
ъ — 0.04%

Тем, кто поедет на «Поле чудес», советую заучить эту таблицу наизусть. И называть слова в таком порядке. Так, например, казалось бы, такая «привычная» буква «б» употребляется реже, чем «редкая» буква «ы». Помнить надо также и то, что в слове не одни гласные. И что если вы угадали одну гласную, то нужно начинать идти по согласным. И кроме того, слово угадывается именно по согласным. Сравните: «**а**и*е» и «ср*вн*т*». И в том и в другом случае — это слово «сравните».

И еще одно соображение. Как вы учили английский? Помните? Э пен, э пенсил, э тэйбл. Что вижу — о том и пою. А смысл?.. Как часто вы в нормальной жизни говорите слово «карандаш»? Если задача — научить говорить как можно быстрее и эффективнее, то и учить надо соответствующе. Проводим анализ языка, выделяем самые употребимые слова. И учить начинаем именно с них. Чтобы более-менее говорить на английском языке, достаточно всего полторы тысячи слов.

Еще одно баловство: составлять слова из букв случайным образом, но учитывая частоту появления, чтобы было похоже на нормальные слова. В первой же десятке «случайных» четырехбуквенных слов выскочило «осел». В следующей полсотне — слова «мчим» и «нато». Но, увы, очень много неблагозвучных комбинаций, таких, как «блтт» или «нрро».

Поэтому — следующий шаг. Я разбил все слова на двухбуквенные сочетания и начал случайным образом (но с учетом частоты повторения) комбинировать их. Стали в больших количествах получатся слова, похожие на «нормальные». Например: «коивдиот», «воабма», «апый», «депоид», «дебяко», «орфа», «поеснавы», «озза», «ченя», «риторя», «урдеед», «утоичи», «стых», «сапоть», «гравда», «абабап», «обарто», «еелует», «лярезы», «мыни», «бромомер» и даже «тодебыст».

Куда применить... есть варианты. Например, написать генератор красивых фирменных игривых имен. Для йогуртов. Типа, «мемолисо» или «уторорерто». Или — генератор футуристических стихов «Бурлюк-php»: «опелдиий миатон, линоаз окмиая... деесопен одесон».

И есть еще один вариант. Надо попробовать...

Некоторые статистические данные об использовании русских слов:

• Средняя длина слова 5.28 символа.

• Средняя длина предложения 10.38 слов.

• 1000 наиболее частотных лемм покрывает 64.0708% текста.

• 2000 наиболее частотных лемм покрывают 71.9521% текста.

• 3000 наиболее частотных лемм покрывают 76.5104% текста.

• 5000 наиболее частотных лемм покрывают 82.0604% текста.
  

Отсюда.

После заметки мне пришло вот такое письмо:

Здравствуйте, Дмитрий !

Проанализировав статью «Язык до Киева доведет» и ту ее часть, где Вы описываете свою программу, возникла идея.
Вами написанный скрипт кажется мне предназначенным абсолютно не для «Поля чудес» в большей мере, а для другого.
Первое самое разумное применение результатов работы Вашего скрипта — определение порядка букв при программировании кнопок для мобильных устройств. Да, да — именно в мобильниках и нужно все это.

Я распределил это по волнам (см. рисунок)

Далее распределение по кнопкам:
1. Все буквы из первой волны уходят на 4 кнопки в первый ряд
2. Все буквы из второй волны тоже на остальные 4 кнопки в тот же первый ряд
3. Все буквы из третьей волны туда же на оставшиеся две кнопки
4. 4,5 и 6 волны уходят во второй ряд
5. 7,8,9 волны уходят на третий ряд, причем 9-я волна уходит вся полностью (не смотря на кажущееся большое количество букв) в третий ряд 9-й кнопки, что-бы 10 кнопку оставить под всякие там знаки препинания (точка, запятая и прочее).

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

1. Л. Н. Толстой. «Анна Каренина» (лучше конечно «Войну и мир», но я не нашел на www.lib.ru) -http://www.lib.ru/LITRA/TOLSTOJ/anna_kar.txt
2. Ф. М. Достоевский. «Игрок» — www.lib.ru/LITRA/DOSTOEWSKIJ/igrok.txt
3. Леонид Филатов. «Про Федота Стрельца» — www.lib.ru/ANEKDOTY/fedot.txt
4. Вильям Шекспир. Сонеты (перевод С. Я. Маршака) www.lib.ru/SHAKESPEARE/sonets.txt
5. Б. И А.Стругацкие. Пикник на обочине. www.lib.ru/STRUGACKIE/picnic.txt

А потом выложить статистику? Мне показалось? что тексты максимально отражают нашу современную речь, а ведь мы как говорим, так и пишем sms.

Заранее большое спасибо.

Итак, анализировать частоту повторения букв можно двумя способами. Способ 1. Взять текст, найти в нем уникальные (не повторяющиеся) словоформы и анализировать их. Способ хорош для построения статистики по словам русского языка, а не по текстам. Способ 2. Не искать в тексте уникальные слова, а сразу перейти к подсчету частоты повторения букв. Получаем частоту букв в русском тексте, а не в русских словах. Для создания клавиатур и прочего нужно использовать именно этот способ: на клавиатуре набираются именно тексты.

Клавиатуры должны учитывать не только частоту букв, но и самые упортебимые слова (словоформы). Не так уж и трудно догадаться, какие именно слова самые употребимые: это, во-первых, служебные части речи, ибо роль у них такая — служить всегда и везде, и местоимения, роль у которых не менее важная: заменять в речи любую вещь/человека (это, он, она). Ну и основные глаголы (быть, сказать). По результатам анализа перечисленных выше текстов я получил такие самые «популярные» слова: «и, не, в, что, он, я, на, с, она, как, но, его, это, к, а, все, ее, было, так, же, то, сказал, за, ты, о, у, ему, мне, только, по, меня, бы, да, вы, от, был, когда, из, для, еще, теперь, они, сказала, уже, него, нет, была, ей, быть, ну, ни, если, очень, ничего, вот, себя, чтобы, себе, этого, может, того, до, мы, их, ли, были, есть, чем, или, ней» и так далее.

Возвращаясь к клавиатурам — очевидно, что в клавиатуре буквосочетания «не», «что», «он», «на» идругие должны находится как можно ближе друг к другу, или если не вплотную, то каким-то наиболее оптимальным образом. Нужно провести исследования, каким именно образом пальцы движутся по клавиатуре, найти самые «удобные» позиции и поместить в них самые употребляемые буквы, не забывая, однако, про буквосочетания.

Проблема, как всегда, одна: даже если и получиться создать Уникальную Клавиатуру, куда деть миллионы людей, которые уже привыкли к qwerty/йцукен?

Насчет же мобильных устройств... Наверное, it makes sense. По крайней мере, буквы «о», «а», «е» и «и» должны точно находиться на одной клавише. Знаки препинания в порядке частоты употребления : , . - ? ! " ; : ) (

Запятая употребляется в 2 раза чаще, чем точка. А точка на стандартной русской клавиатуре расположена удобней...

Статистика по приведенным выше текстам: