Category: математика

Хотел написать про то, как мне лично было непонятно, чем так гордится группа исследователей Массачуссетского Технологического, которая нашла значения x, y, и z, при которых x³ + y³ + z³ = 42.

Набросал для расчётов свою прогу на Джаве. И не могу сказать, что она не работала. Она прекрасно работала для многих цифр, в том числе, и для любимого числа Шелдона Купера (73). Но дальше, имея на руках порядки полученных в MIT цифр для 42, прикинул вычислительную сложность, и охренел — т.к. решать данную проблему, как говорится, “в лоб” на самом ультрасовременном суперкомпьютере с его двумя сотнями петафлопсов с лихером придётся э…. не намного меньше, чем возраст наблюдаемой Вселенной.

Устыдился, пошёл читать про алгоритм, которым раньше было решено уравнение x³ + y³ + z³ = 33. Оказалось, что там, мягко говоря, очень не в лоб решали. Устыдился окончательно. Полезно вот так иногда, рожей об стол, для скромности и смиренности.

По интернету гуляет математическая загадка — каков результат выражения 8 / 2(2+2)?

У одних получается 16, у других 1. Сломаны уже тысячи виртуальных копий.

Очевидно, что ответ получается разным из-за разной интерпретации последовательности математических действий. Что делать первым — делить 8 на 2 или умножать 2 на (2 + 2)?

Ответ, что характерно, может быть разным в отличие от страны. В США и России, например, подразумеваемое умножение (как тут, 2(2 + 2)) — стоит по приоритету выше, чем умножение обычное или деление, поэтому ответ должен быть 1.

А в других странах (ИМХО, в Британии) у подразумеваемого умножения нет специального статуса, и, соответственно, в таких случая мы просто проводим операции слева направо, и ответ — 16.

Американо-российский вариант мне кажется более логичным: ведь 2(2 + 2), используя дистрибутивность, можно записать как 4 + 4, и выражение примет вид 8 / (4 + 4), и ответ, естественно, будет 1.

А вообще эта загадка, как и множество других головоломок (например, про тот несчастный самолёт на беговой дорожке), не стоит выеденного яйца. Потому что выражение записано через одно место, и интерпретировать его можно по-разному, отсюда и интернетные битвы. Если записать его так, чтобы исключить возможность другого прочтения, то и спорить было бы не о чем.

Кстати, если запрограммировать это выражение (я использовал Питон, Джаву, Сишарп) — то выдаётся один и тот же ответ — 16. Потому что нет подразумеваемого умножения в этих языках (а в каких есть?), и оно тупо делает операции слева направо, по-английски.

Интересно, как пропоненты идеи того, что мы живём внутри симуляции разрешают проблему того, что некоторые вычисления, связанные с симуляцией, имеют чрезвычайно высокую вычислительную стоимость?

Вот, например, гравитация. Она описывается уравнениями гравитационной задачи N тел. Наша планета взаимодействует с Солнцем, Луной, и всеми остальными планетами солнечной системы. Даже если не принимать во внимание луны остальных планет и астероиды, то N в данном случае будет равно 10 (количество планет плюс Солнце и Луна). Проблема в том, что для N > 3 гравитационная задача не является решаемой. К решению можно только приблизиться, сиречь, действовать численными методами, сходящимися рядами. Потом, даже в такой простой задаче мы принимаем такие упрощения, что планеты являются дискретыми точками, не имеющими размеров, сложной формы, масконов, как на Луне, и так далее. Численные методы решения гравитационной задачи также имеют вычислительную сложность N². То-есть, при увеличении количества тел в два раза, придётся произвести в четыре раза больше вычислений. Очевидно, что количество вычислений очень быстро улетает в бесконечность.

В реальности же гравитационное взаимодействие есть между моим пальцем и какой-нибудь чёрной незабудкой, растущей на планете в далёкой галактике. Да, оно ничтожно. Но оно, блин, есть. И как это возможно симулировать — решительно непонятно.

Если есть возможность научить компьютер что-то делать — он это будет делать намного лучше человека. В том числе — и играть в игры.

Большинство игр типа шашек, шахмат, домино и даже крестиков-ноликов компьютер играет через постройку дерева решений. Для крестиков-ноликов это вполне тривиальная задача, так как количество возможных игр в крестиках-ноликах равно факториалу 9 или примерно 363 тысячам. Для современных компьютеров это ерунда. Шашки уже посложнее — там 500 квинтиллионов (500 000 000 000 000 000 000) возможных игр. И полное дерево решений для шашек таки было построено. Число возможных игр в шахматах же несколько превышает… кгм… количество атомов в наблюдаемой Вселенной, поэтому с построением полного дерева ожидаемо возникает затык. Да и с шашками, вообще-то, тоже, так как 500 квинтиллионов поместятся далеко не во всякий компьютер 🙂 Ну, полное дерево, в принципе, и не нужно. Чтобы выиграть в шахматы, например, у меня, достаточно построить дерево ну хотя бы в четыре уровня, потому что я архихреново в них играю. Чтобы выиграть у гроссмейстера, понадобится дерево пошЫрше и поглЫбже; но это тоже не является проблемой — компьютер теперь с гарантией выигрывает у лучших в мире гроссмейстеров, тема, по сути, закрыта.

Но есть игры, не пользующиеся деревьями решений. Например, морской бой. По сути своей, задача выигрыша в морском бое состоит в поиске нужных данных по несортированному, случайному двоичному массиву. Казалось бы, если массив не сортирован и случаен, значит, оптимальной стратегии в морском бое нет. Но реальность немного интереснее 🙂

Чуваки из конторы DataGenetics провели математический разбор “Морского боя”:

http://www.datagenetics.com/blog/december32011/

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

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

И что характерно, рассчитать карту плотностей вероятностей у компьютера получается значительно лучше человека.

Карта плотностей вероятностей на 12 ходу после 5 попаданий:

Хотя люди тоже пользуются примерно такой же стратегией — статистически компьютер всё же будет выигрывать. Вот такие пироги с кремниевыми котятами.

Большинство моих ЖЖ-друзей, наверное, в курсе, что это, и как это работает. Но вдруг кто не знает или не понимает.

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

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

Теперь построим свой собственный примитивный блокчейн. Блокчейн — это block chain, т.е. цепь из блоков. Каждым блоком внутри нашей цепи будут 5 кусков текста, разделённых запятыми: хеш предыдущего блока, три куска “полезной нагрузки”, и хеш для этого блока. Хранить в блокчейне можно любые данные, но допустим у нас будет хранится информация о финансовых транзакциях. Использовать будем алгоритм хеширования MD5 (2)

Построим первый блок. Так как это начальный блок в цепи блоков, у него не может быть хеша предыдущего блока. Ну и плевать, придумаем свой. abcdefghijklmopqrstuvwxyz1234567 — вполне сгодится. Далее указываем транзакцию, кто кому заплатил, и сколько: Маша,Олег,5 рублей. И хешируем всё это вместе:

md5sum <<< "abcdefghijklmopqrstuvwxyz1234567,Маша,Олег,5 рублей", получаем хеш a61d142c8be7fac8b41da05d11c9f76e.

Всё, вот первый блок в нашем блокчейне:

abcdefghijklmopqrstuvwxyz1234567,Маша,Олег,5 рублей,a61d142c8be7fac8b41da05d11c9f76e

Строим второй блок, где Серёжа заплатил Тане 3 рубля:

md5sum <<< "a61d142c8be7fac8b41da05d11c9f76e,Серёжа,Таня,3 рубля", получаем хеш 20e22c43963d6ee9bbc71d65c4251492, и, соответственно, блок:

a61d142c8be7fac8b41da05d11c9f76e,Серёжа,Таня,3 рубля,20e22c43963d6ee9bbc71d65c4251492

И теперь наш блокчейн выглядит так:

abcdefghijklmopqrstuvwxyz1234567,Маша,Олег,5 рублей,a61d142c8be7fac8b41da05d11c9f76e
a61d142c8be7fac8b41da05d11c9f76e,Серёжа,Таня,3 рубля,20e22c43963d6ee9bbc71d65c4251492

Ну, и так далее, блоков можно добавлять до окончания места на жёстком диске.

Чем это круто? Тем, что блокчейн лежит в свободном доступе, и ЛЮБОЙ человек, взяв этот блокчейн, может собственноручно перевычислить все хеши и проверить все записи: если хеши совпадают, значит, информации можно доверять. Именно этим и занимаются майнеры — они перепроверяют транзакции для криптовалют, то-есть, обеспечивают функционирование платёжной системы, за что им отстёгивают денег.

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

1. 100% гарантии, разумеется, быть не может, но если алгоритм шифрования нормальный и не имеет коллизий (это когда два разных набора данных дают один и тот же хеш), то вероятность совпадения будет примерно 1/количество возможных хешей, т.е. для хеша длиной 128 бит это 2.94E-39, или пренебрежительно мало. Для хеша длиной 512 бит это вообще число со 150+ символами после десятичной точки.
2. Алгоритм хеширования MD5 достаточно хреновый по современным меркам, и имеет коллизии. Правда, для реально читаемого человеком текста можно пренебречь — все существующие примеры коллизий это хеши специально сгенерированных двоичных данных. Но в реально рабочих приложениях, тем не менее, рекомендуется использовать более коллизионноустойчивые алгоритмы, типа SHA-256 (используется в блокчейне для биткоина) или SHA-3.

Откуда в цифровом звуке берётся шум? Он берётся из не вполне точного представления аналогового сигнала, так как для того, чтобы описать синусоиду, у нас имеется конечное количество координат по оси Y. В случае с компакт-дисками это 65536 возможных значений, так как у нас есть 16 бит — 15 бит на описание уровня плюс один бит на знак. 8-битные звуковые файлы, кстати, беззнаковые (во бардак!) Ось Х проблемы не представляет, в полном соответствии с теоремой Найквиста-Шеннона-Котельникова

Зависимость в децибелах отношения сигнал/шум от того, каким количеством уровней описывается сигнал, линейная, и рассчитывается как 20log₁₀(2^{количество бит}), или примерно 6.02 × количество бит.

Стойкие апологеты аналоговых носителей напирают на то, что, мол на цифровом носителе всего 65536 уровней, а на нашем-то тёплом ламповом виниле (или на магнитной плёнке) количество уровней аналоговое, т.е. неограниченное!!! Ага, ага. А вот хрен вам. С аналогового носителя точно так же можно достать конечное количество уровней сигнала, и для хорошего “дореволюционного” винила это число составляет примерно 2000 или 11 бит. Это даст предельное отношение сигнал/шум в районе 70 дБ — что, вообще-то, не так уж плохо. Это заметно лучше MP3-шек, например =))) Только винил надо хорошенько помыть-почистить, чтобы не было слышно пыли — она сильно портит впечатление.

В случае с плёнкой уже надо говорить более предметно — тут смотря какая плёнка. Наилучшее качество в домашних условиях давали катушечные магнитофоны — с них можно было тоже достать примерно 11 бит. Кассеты, когда только появились, были полное и окончательное говно, и давали где-то 6-битный звук. Этого было вполне достаточно для применения в диктофонах (для коих, их, собственно, и разработали), но недостаточно для качественного воспроизведения музыки. Тем не менее, их растущая популярность и сопутствующие постоянные улучшения в области электроники привели к тому, что постепенно они вышли на уровень катушечных магнитофонов, а с введением технологий типа Dolby и прочих улучшайзеров, даже немного превзошли их (катушечные магнитофоны к этому времени уже, ясен пень, никто не улучшал). Но — это при наличии хорошей кассетной деки, качественной студийной компакт-кассеты, и т.д. А восхищаться аналоговым носителем МК-60, сунутым в Электронику-302 можно разве что после третьей бутылки.

Что имеем с гуся? С гуся имеем то, что аналоговый носитель тоже, по сути, цифровой — количество вытаскиваемой с него информации конечно. Это для любого носителя справедливо — даже для 35mm фотографической плёнки. С неё — в идеале — можно достать 10 мегапикселей. Повторюсь — в идеале. Со снимков на советскую ч/б плёнку середины 1960х годов я вытягивал примерно 1 мегапиксель, не более.

Таки доделал програмку на Питоне, рисующую спектр сигнала и автоматически считающую КНИ+шум и ОСШ. Попутно узнал, как водится, много нового. За что люблю Питон — так это за то, что программа занимает менее 40 строк. На тех же Сях я бы усрался это рисовать. Даже на Шарпах бы усрался.

Программе скармливается звуковой файл с сигналом частотой в 1 kHz, сгенерированный программой Adobe Audition (в девичестве Syntrillium CoolEdit). Но можно взять и бесплатный Audacity, результат будет точно такой же. Программа читает файл, берёт значение с наибольшим пиком и даёт ему обозначение в 0 децибел. Остальное, соответственно, отрицательные величины. Подсчитывается среднеквадратичное значение всего, что не сигнал, и делится на уровень сигнала. Получается КНИ+шум (THD+N). Потом считаем ОСШ (отношение сигнал/шум, SNR) в децибелах: 20log₁₀(сигнал / шум)

Вот так выглядит анализ звукового файла с сигналом 1 kHz, разрешением 16-бит, частота дискретизации — 48 kHz:

Это весьма близко к теоретическому идеалу — в идеале, разрешение 16 бит может дать ОСШ в 96.3 dB. Но у меня не идеал, так как я использую чуть менее, чем 16 бит — ибо если генерировать синусоиду с уровнем в 0 dB (т.е. по-максимуму), то почему-то уже лезут нелинейные искажения. Так что я создаю её с уровнем в -0.1 dB, минимальным отступлением от максимума, которое мне даёт делать Audition. В любом случае, 94 dB — это дохрена.

КНИ в 2 тысячных процента это тоже прекрасно. Без приборов этого никто никогда не увидит, искажения начинают быть слышимыми, когда уже вплотную приближаются к 1%, хотя это сильно зависит от того, что именно слушаем: если чистые синусоиды, то искажения начинают быть заметными гораздо раньше, а если в качестве тестового материала брать альбомы фифтисентов и прочих, то там можно и 10% искажений не услышать. Что не означает, что аппаратура, дающая КНИ в 0.05%, ничем не лучше аппаратуры, дающей 0.1% — она лучше; просто в реальности ушами этого ни один живой человек не услышит.

А теперь — снова пнём формат MP3 🙂 Никто как-то вот не задумывается о том, что они слушают в тысячедолларовых деревянных наушниках, подключённых к внешним усилителям класса А за семьсот долларов, обещающим КНИ в 0.00045%

А между тем это реалии MP3 с битрейтом в 192 килобита/сек:

А это — 320 килобит/сек:

Получше, конечно, чем 192 kbps, но всё равно проседание качества очень налицо — происходит серьёзное ужимание динамического диапазона (я в курсе, что ДД и ОСШ это не вполне одно и то же, но они связаны). На некотором материале (например, классическая музыка, обладающая большим динамическим диапазоном) это может быть очень заметно. На 192 килобитах так это точно заметно, тихая партия скрипки сопровождается скрежетом артефактов сжатия с потерями — собственноушно, так сказать, слышал. Дальнейшее увеличение битрейта после 320 килобит/с, кстати, уже ничего не даёт — ОСШ так и остаётся в районе 55 децибел.

Ещё надо будет попинать винилофильство и прочее плёнколожество, но это в другой раз 🙂

По совету ув. ny-quant попробовал использовать формулу x = r * x (1 – x) в качестве генератора случайных величин. Одного преобразования мне показалось мало, так что делал два кряду.

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

Ну, как грица, pics or it didn’t happen.

Результат использования функции NumPy.random.random():

И результаты, полученные из двойного применения x = r * x (1 – x) с двумя разными значениями r:

Вообще — неплохо, должен признать.

Но если приблизить и рассмотреть детальнее, становится заметной разница. Справа — x = r * x (1 – x), слева — NumPy.random.random()

Как видно, x = r * x (1 – x) чаще принимает граничные значения, там много белого и много чёрного, и мало серого. Из-за этого, кажется, что есть узоры, как на булатной стали. Я не математик, но мне кажется, что большая равномерность является желательной.

Но вообще — для такой простой формулы должен признать, впечатляет.