Классический футбольный мяч шьётся по развёртке усечённого икосаэдра:

Фото: Sebastiano Calì

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

(Понятно, впрочем, что надутый мяч – не многогранник.)



Комментарии (2) »

Всё-таки довольно забавно начинает звучать текст, если автор называет псевдослучайные числа – случайными. Вот в “Компьютерре” статья, где как раз речь о псевдослучайных числах, но автор предпочитает уверенно называть их “случайные”. В статье пишут, например:


Скажем, генератор случайных чисел, встроенный в ОС Windows, автоматически используется во всех приложениях системы, связанных с защитой информации. И при этом конкретные алгоритмы генерации, используемые в Microsoft для данной цели, никогда открыто не публиковались[…]

…аналитики нашли уязвимость, позволяющую организовать атаку, эффективно отыскивающую предыдущие состояния генератора, а значит, и вычислять будущие числа на выходе.”

Вот такие случайные числа, генерируемые, тем не менее, “алгоритмом” и, тем не менее, вычисляемые на будущее аналитиками. По-моему, кошмар.

Как обстоит дело в реальности: в большинстве компьютерных приложений, о которых идёт речь, используются последовательности псевдослучайных чисел. Псевдослучайными они называются потому, что каждый следующий член последовательности вычисляется некоторым заранее известным способом. При этом хороший алгоритм генерации устроен таким образом, что последовательность (точнее, некоторый её фрагмент) обладает важными статистическими свойствами последовательностей случайных чисел. Вообще говоря, некоторый “участок” хорошей псевдослучайной последовательности может быть не отличим от действительно случайной.

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

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

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

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

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

Ссылка по теме: моя колонка про случайные числа на “Информационном буме”.



Комментарии (2) »

Кстати, первое опровержение известной гипотезы Эйлера насчёт обобщения большой теоремы Ферма появилось в 1966-ом:

1445 = 1335+1105+845+275

Опровержение просто вычислили. Это оказался один из первых замечательных вычислительных результатов, или даже вообще первый. И из последних самый нашумевший вычислительный результат – это задача об укладке апельсинов.



Comments Off on Эйлер и числа

Забавно (специально для arbuz.uz Скляревского):

31138+20128+19538+8618=28238+27678+25578+11288

Там же: 224955952840404+75924319813914+272397916926404=299998579386094

(via)



Comments Off on Числа

Между прочим, раз тут зашел разговор, то Том Хейлз (Thomas C. Hales), механистически разобравшийся в 1998 году со старинной задачей Кеплера о наиболее плотной упаковке сфер, поддерживает целый проект по обоснованию своего доказательства с помощью специального формализма.

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

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

Компьютерным программным кодам нет доверия.

Это правильно.

Но Хейлз поддерживает проект под названием Flyspeck. Вообще-то, flyspeck – английское название для “мушиного помета”, но по версии создателей проекта это всего лишь слово из словаря, подходящее под маску /f.*p.*k/ (где FPK – Formal Proof of Kepler).

Цель проекта – получение программной реализации некоего компьютерного “формализма”, оперирующего не какими-то “алгоритмами” и “данными”, а строгими теоремами (там есть и тип данных – theorem). Таким образом, планируется получение виртуально строгого, но, вместе с тем, компьютерного, вычислительного доказательства. Попутно обещают выкинуть все интуитивное из всех доказательств вообще. Вот так. Объем работы – двадцать человеко-лет.



Комментарии (2) »
Навигация по запискам: « Позже