Из Википедии, бесплатной энциклопедии
  (Перенаправлен из треугольника Серпинского )
Перейти к навигации Перейти к поиску
Серпинский треугольник
Сгенерировано с использованием случайного алгоритма
Треугольник Серпинского в логике: Первые 16 конъюнкции из лексикографически упорядоченных аргументов. Столбцы, интерпретируемые как двоичные числа, дают 1, 3, 5, 15, 17, 51 ... (последовательность A001317 в OEIS )

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

Конструкции [ править ]

Есть много разных способов построения треугольника Серпинского.

Удаление треугольников [ править ]

Эволюция треугольника Серпинского

Треугольник Серпинского можно построить из равностороннего треугольника путем многократного удаления треугольных подмножеств:

  1. Начните с равностороннего треугольника.
  2. Разделите его на четыре равносторонних равносторонних треугольника меньшего размера и удалите центральный треугольник.
  3. Повторяйте шаг 2 с каждым из оставшихся меньших треугольников бесконечно.

Каждый удаленный треугольник (а трема ) является топологический открытым множеством . [3] Этот процесс рекурсивного удаления треугольников является примером правила конечного подразделения .

Сжатие и дублирование [ править ]

Та же последовательность фигур, сходящаяся к треугольнику Серпинского, также может быть создана с помощью следующих шагов:

  1. Начните с любого треугольника на плоскости (подойдет любая замкнутая ограниченная область на плоскости). В каноническом треугольнике Серпинского используется равносторонний треугольник с основанием, параллельным горизонтальной оси (первое изображение).
  2. Уменьшите треугольник до 1/2 высота и 1/2ширину, сделайте три копии и расположите три сморщенных треугольника так, чтобы каждый треугольник касался двух других треугольников в углу (изображение 2). Обратите внимание на появление центрального отверстия, потому что три сморщенных треугольника между ними могут закрывать только3/4площади оригинала. (Отверстия - важная особенность треугольника Серпинского.)
  3. Повторите шаг 2 с каждым из меньших треугольников (изображение 3 и так далее).

Обратите внимание, что этот бесконечный процесс не зависит от того, является ли начальная форма треугольником - это просто яснее. Первые несколько шагов, начинающиеся, например, с квадрата, также имеют тенденцию к треугольнику Серпинского. Майкл Барнсли использовал изображение рыбы, чтобы проиллюстрировать это в своей статье «Фракталы с V-переменной и суперфракталы». [4] [5]

Итерация с квадрата

Фактический фрактал - это то, что можно получить после бесконечного количества итераций. Более формально его можно описать в терминах функций на замкнутых множествах точек. Если обозначить через d A расширение в раз1/2вокруг точки А, то Серпинский треугольник с углами А, В, и С представляет собой фиксированный набор преобразования д  ∪  d B  ∪  d C .

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

Игра хаос [ править ]

Анимированное создание треугольника Серпинского с помощью игры хаос

Если взять точку и применить к ней каждое из преобразований d A , d B и d C случайным образом, результирующие точки будут плотными в треугольнике Серпинского, поэтому следующий алгоритм снова будет генерировать произвольно близкие приближения к ней: [6 ]

Начните с обозначения p 1 , p 2 и p 3 как углов треугольника Серпинского и случайной точки v 1 . Установите v n +1 =1/2( v n + p r n ) , где r n - случайное число 1, 2 или 3. Нарисуйте точки от v 1 до v ∞ . Если первая точка v 1 была точкой на треугольнике Серпинского, то все точки v n лежат на треугольнике Серпинского. Если первая точка v 1, лежащая в пределах периметра треугольника, не является точкой на треугольнике Серпинского, ни одна из точек v n не будет лежать на треугольнике Серпинского, однако они будут сходиться на треугольнике. Если v 1находится за пределами треугольника, единственный способ, которым v n приземлится на настоящий треугольник, - это если v n находится на том, что было бы частью треугольника, если бы треугольник был бесконечно большим.

Анимированное построение треугольника Серпинского
Треугольник Серпинского очерчен фрактальным деревом с тремя ветвями, образующими угол 60 ° между собой. Если угол уменьшать, треугольник можно непрерывно трансформировать во фрактал, напоминающий дерево.
Каждый подтреугольник n- й итерации детерминированного треугольника Серпинского имеет адрес на дереве с n уровнями (если n = ∞, то дерево также является фракталом); T = сверху / по центру, L = слева, R = справа, и эти последовательности могут представлять как детерминированную форму, так и «серию ходов в игре хаоса» [7]

Или проще:

  1. Возьмите три точки на плоскости, чтобы получился треугольник, рисовать его не нужно.
  2. Произвольно выберите любую точку внутри треугольника и считайте это вашей текущей позицией.
  3. Случайным образом выберите любую из трех вершинных точек.
  4. Переместитесь на половину расстояния от вашего текущего положения до выбранной вершины.
  5. Постройте текущую позицию.
  6. Повторите с шага 3.

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

Треугольник Серпинского с использованием системы повторяющихся функций

Конструкция наконечника стрелы прокладки Серпинского [ править ]

Анимированная конструкция наконечника стрелы прокладки Серпинского
Конструкция наконечника стрелы прокладки Серпинского

Другая конструкция прокладки Серпинского показывает, что ее можно построить в виде кривой на плоскости. Он образуется путем многократного изменения более простых кривых, аналогичного построению снежинки Коха :

  1. Начните с одного отрезка на плоскости
  2. Неоднократно заменяйте каждый линейный сегмент кривой тремя более короткими сегментами, образуя углы 120 ° на каждом стыке между двумя последовательными сегментами, причем первый и последний сегменты кривой либо параллельны исходному линейному сегменту, либо образуют с ним угол 60 °.

На каждой итерации это построение дает непрерывную кривую. В пределе они приближаются к кривой, которая очерчивает треугольник Серпенского одним непрерывным направленным (бесконечно извилистым) путем, который называется наконечником стрелы Серпинского . [8] Фактически, цель исходной статьи Серпинского 1915 года состояла в том, чтобы показать пример кривой (канторовской кривой), как заявляет само название статьи. [9] [2]

Клеточные автоматы [ править ]

Треугольник Серпинского также появляется в некоторых клеточных автоматах (например, в Правиле 90 ), в том числе в тех, которые относятся к «Игре жизни» Конвея . Например, подобный жизни клеточный автомат B1 / S12 при применении к отдельной клетке сгенерирует четыре приближения треугольника Серпинского. [10] Очень длинная линия толщиной в одну клетку в стандартной жизни создаст два зеркальных треугольника Серпинского. Пространственно-временная диаграмма паттерна репликатора в клеточном автомате также часто напоминает треугольник Серпинского, такой как обычный репликатор в HighLife. [11] Треугольник Серпинского также можно найти в автомате Улама-Уорбертона и в автомате Хекса-Улама-Уорбертона.[12]

Треугольник Паскаля [ править ]

Приближение уровня 5 к треугольнику Серпинского, полученное путем закрашивания первых 2 5 (32) уровней треугольника Паскаля белым цветом, если биномиальный коэффициент четный, и черным в противном случае.

Если взять треугольник Паскаля с 2 n строками и окрасить четные числа в белый цвет, а нечетные числа в черный, результатом будет приближение к треугольнику Серпинского. Точнее говоря, предел в п приближается к бесконечности этого соотношения -colored 2 п -строка Паскаля треугольник Серпинского треугольник. [13]

Башни Ханоя [ править ]

В Башни Ханоя головоломка включает в себя перемещение дисков различных размеров между тремя колышками, сохраняя свойство , что диск не всегда помещается в верхней части меньшего диска. Состояния головоломки с n- дисками и допустимые переходы из одного состояния в другое образуют неориентированный граф , граф Ханоя , который может быть представлен геометрически как граф пересечений множества треугольников, оставшихся после n- го шага в построение треугольника Серпинского. Таким образом, в пределе, когда n стремится к бесконечности, эту последовательность графов можно интерпретировать как дискретный аналог треугольника Серпинского. [14]


Свойства [ править ]

Для целого числа измерений d при удвоении стороны объекта создаются 2 d копии, т.е. 2 копии для одномерного объекта, 4 копии для двухмерного объекта и 8 копий для трехмерного объекта. Для треугольника Серпинского удвоение его стороны создает 3 копии самого себя. Таким образом, треугольник Серпинского имеет размерность Хаусдорфа журнал (3)/журнал (2) = log 2  3 ≈ 1,585, что следует из решения 2 d  = 3 относительно d . [15]

Площадь треугольника Серпинского равна нулю (по мере Лебега ). Площадь, остающаяся после каждой итерации, равна3/4площади из предыдущей итерации, а бесконечное количество итераций приводит к тому, что площадь приближается к нулю. [16]

Точки треугольника Серпинского имеют простую характеристику в барицентрических координатах . [17] Если точка имеет координаты (0. u 1 u 2 u 3 …, 0. v 1 v 2 v 3 …, 0. w 1 w 2 w 3 …), выраженные двоичными числами , то точка находится в Треугольник Серпинского тогда и только тогда, когда u i + v i + w i = 1 для всех i .

Обобщение на другие модули [ править ]

Обобщение треугольника Серпинского также можно сгенерировать с помощью треугольника Паскаля, если используется другой модуль Modulo. Итерация п может быть получена путем принятия треугольника Паскаля с P п строками и окраской числа их значениями для й по  модулю  P . Когда n приближается к бесконечности, образуется фрактал.

Тот же самый фрактал может быть получен путем разделения треугольника на мозаику из P 2 похожих треугольников и удаления треугольников, которые перевернуты из оригинала, а затем повторения этого шага с каждым меньшим треугольником.

И наоборот, фрактал также можно создать, начав с треугольника, продублировав его и расположив п ( п + 1)/2новых фигур в той же ориентации в более крупный подобный треугольник с соприкасающимися вершинами предыдущих фигур, затем повторяя этот шаг. [18]

Аналоги в высших измерениях [ править ]

Пирамида Серпинского с квадратным основанием и ее `` обратная ''
Прогрессия рекурсии пирамиды Серпинского (7 шагов)
Пирамида на основе треугольника Серпинского, вид сверху (выделены 4 основных участка). Обратите внимание на самоподобие в этом двумерном проекционном виде, так что получившийся треугольник сам по себе может быть двумерным фракталом.

Тетраэдр Серпинского или Тетрис является трехмерным аналогом треугольника Серпинского, образованный путем многократного сокращения регулярного тетраэдра до половины своего первоначального роста, поставив вместе четыре копии этого тетраэдра с углами прикосновения, а затем повторить процесс.

Тетрикс, построенный из исходного тетраэдра со стороной L, обладает тем свойством, что общая площадь поверхности остается постоянной при каждой итерации. Начальная площадь поверхности тетраэдра (итерация-0) с длиной стороны L равна L 2 √ 3 . Следующая итерация состоит из четырех копий с длиной стороныL/2, поэтому общая площадь равна 4 (L/2) 2 √ 3  = 4 L 2 ·√ 3/4 = L 2 √ 3 снова. При этом объем конструкции на каждом этапе уменьшается вдвое и поэтому приближается к нулю. Предел этого процесса не имеет ни объема, ни поверхности, но, как и прокладка Серпинского, представляет собой сложную кривую. Его размерность Хаусдорфа равнажурнал (4)/журнал (2) = 2. Если все точки проецируются на плоскость, параллельную двум внешним краям, они точно заполняют квадрат со стороной. L/√ 2без нахлеста. [19]

Анимация вращающейся тетрисы уровня 4, показывающая, как некоторые ортогональные проекции тетрисы могут заполнять плоскость - в этом интерактивном SVG перемещайтесь влево и вправо по тетрисе, чтобы повернуть 3D-модель

История [ править ]

Вацлав Серпинский описал треугольник Серпинского в 1915 году. Однако аналогичные узоры появляются уже в мозаиках Космати 13-го века в соборе Ананьи , Италия , [20] и других местах центральной Италии, для ковров во многих местах, таких как неф Римская базилика Санта-Мария-ин-Космедин , [21] и для отдельных треугольников, расположенных по кругу в нескольких церквях и базиликах. [1] [2] В случае изолированного треугольника итерация состоит как минимум из трех уровней.

Недавно был изучен средневековый треугольник с исторически достоверной датировкой [2] . Он сделан из порфирия и сусального золота, изолирован, итерация 4 уровня.

Прокладка аполлоническое была впервые описана Apollonius Пергского (третий век до н.э.) и далее анализировали с помощью Готфрида Лейбница (17 век), и представляет собой изогнутый предшественник 20-го века Серпинский треугольника. [22]

Этимология [ править ]

Использование слова «прокладка» для обозначения треугольника Серпинского относится к прокладкам , которые используются в двигателях , и которые иногда имеют ряд отверстий уменьшающегося размера, подобно фракталу; это использование было придумано Бенуа Мандельбротом , который думал, что фрактал похож на «часть, предотвращающую утечки в двигателях». [23]

См. Также [ править ]

  • Аполлоновская прокладка , набор касательных друг к другу окружностей с той же комбинаторной структурой, что и треугольник Серпинского.
  • Список фракталов по размерности Хаусдорфа
  • Ковер Серпинского , еще один фрактал, названный в честь Серпинского и образованный путем многократного удаления квадратов из большего квадрата.
  • Triforce , реликвия из серии Legend of Zelda

Ссылки [ править ]

  1. ^ a b Конверсано, Элиза; Тедескини-Лалли, Лаура (2011), «Треугольники Серпинского в камне на средневековых полах в Риме» (PDF) , APLIMAT Journal of Applied Mathematics , 4 : 114, 122
  2. ^ a b c d Брунори, Паола; Магроне, Паола; Лалли, Лаура Тедескини (2018-07-07), « Имперский Порфирий и Золотой Лист: Треугольник Серпинского в средневековом римском монастыре », Достижения в области интеллектуальных систем и вычислений , Springer International Publishing, стр. 595–609, doi : 10.1007 / 978 -3-319-95588-9_49 , ISBN 9783319955872 Внешняя ссылка в |title=( помощь )
  3. ^ "Прокладка Серпинского от Trema Removal"
  4. ^ Майкл Барнсли ; и другие. (2003), "V-переменные фракталы и суперфракталы", arXiv : math / 0312314
  5. ^ NOVA (программа общественного телевидения). Странная новая наука хаоса (эпизод). Станция общественного телевидения WGBH Бостон. Вышла в эфир 31 января 1989 года.
  6. ^ Фельдман, Дэвид П. (2012), «17.4 Игра хаоса» , Хаос и фракталы: элементарное введение , Oxford University Press, стр. 178–180, ISBN 9780199566440.
  7. ^ Пайтген, Хайнц-Отто; Юргенс, Хартмут; Саупе, Дитмар; Малецкий, Эван; Perciante, Терри; и Юнкер, Ли (1991). Фракталы для класса: стратегические действия Том первый , с.39. Спрингер-Верлаг, Нью-Йорк. ISBN 0-387-97346-X и ISBN 3-540-97346-X .  
  8. ^ Прусинкевич, П. (1986), "Графические приложения L-систем" (PDF) , Proceedings of Graphics Interface '86 / Vision Interface '86 , стр. 247–253 .
  9. ^ Серпинский, Вацлав (1915). "Sur une courbe dont tout point est un point de ramification". Компт. Ренд. Акад. Sci. Париж . 160 : 302–305 - через https://gallica.bnf.fr/ark:/12148/bpt6k31131 .
  10. ^ Румпф, Томас (2010), «Игра жизни Конвея, ускоренная с помощью OpenCL» (PDF) , Труды одиннадцатой Международной конференции по мембранным вычислениям (CMC 11) , стр. 459–462 .
  11. ^ Bilotta, Eleonora; Пантано, Pietro (лето 2005), "паттерна явления Возникающие в 2D - клеточных автоматов", Artificial Life , 11 (3): 339-362, DOI : 10,1162 / 1064546054407167 , PMID 16053574 , S2CID 7842605  .
  12. ^ Хованова, Таня; Не, Эрик; Пураник, Алок (2014), «Треугольник Серпинского и автомат Улама-Уорбертона», Math Horizons , 23 (1): 5–9, arXiv : 1408.5937 , doi : 10.4169 / mathhorizons.23.1.5 , S2CID 125503155 
  13. ↑ Стюарт, Ян (2006), « Как разрезать торт: и другие математические головоломки» , Oxford University Press, стр. 145, ISBN 9780191500718.
  14. ^ Ромик, Дэн (2006), «Кратчайшие пути в графе Ханойской башни и конечных автоматах», Журнал SIAM по дискретной математике , 20 (3): 610–62, arXiv : math.CO/0310109 , doi : 10,1137 / 050628660 , Руководство по ремонту 2272218 , S2CID 8342396  .
  15. Перейти ↑ Falconer, Kenneth (1990). Фрактальная геометрия: математические основы и приложения . Чичестер: Джон Вили. п. 120 . ISBN 978-0-471-92287-2. Zbl  0689.28003 .
  16. ^ Helmberg, Gilbert (2007), знакомясь с фракталы , Вальтер де Gruyter, стр. 41, ISBN 9783110190922.
  17. ^ «Много способов сформировать прокладку Серпинского» .
  18. ^ Shannon & Bardzell, Кэтлин и Майкл, «Закономерности в треугольнике Паскаля - с твист - Первый Twist: Что это такое?» , maa.org , Mathematical Association of America , данные получены 29 марта 2015 г.
  19. ^ Джонс, Хью; Кампа, Аурелио (1993), «Абстрактные и естественные формы из повторяющихся функциональных систем», в Thalmann, NM; Тельмана, Д. (ред.), Общаясь с виртуальными мирами , CGS CG International Series, Токио:. Springer, С. 332-344, DOI : 10.1007 / 978-4-431-68456-5_27
  20. Перейти ↑ Wolfram, Stephen (2002), A New Kind of Science , Wolfram Media, pp. 43, 873
  21. ^ "Геометрическая мозаика пола (треугольники Серпинского), неф Санта-Мария-ин-Космедин, Форум Бычий собор, Рим" , 5 сентября 2011, Flickr
  22. Перейти ↑ Mandelbrot B (1983). Фрактальная геометрия природы . Нью-Йорк: WH Freeman. п. 170 . ISBN 978-0-7167-1186-5.
    Асте Т., Вир Д. (2008). В погоне за идеальной упаковкой (2-е изд.). Нью-Йорк: Тейлор и Фрэнсис. С. 131–138. ISBN 978-1-4200-6817-7.
  23. ^ Бенедетто, Джон; Войцех, Чая. Интеграция и современный анализ . п. 408.

Внешние ссылки [ править ]

  • "Прокладка Серпинского" , Математическая энциклопедия , EMS Press , 2001 [1994]
  • Вайсштейн, Эрик В. "Сито Серпинского" . MathWorld .
  • Ротемунд, Пол В.К .; Пападакис, Ник; Уинфри, Эрик (2004). "Алгоритмическая самосборка треугольников Серпинского ДНК" . PLOS Биология . 2 (12): e424. DOI : 10.1371 / journal.pbio.0020424 . PMC  534809 . PMID  15583715 .
  • Прокладка Серпинского от Trema Удаление в разрубленном состоянии
  • Прокладка Серпинского и Ханойская башня на распутье
  • Графический процессор в реальном времени сгенерировал треугольник Серпинского в 3D
  • Треугольники Пифагора , Вацлав Серпинский, Courier Corporation, 2003 г.
  • A067771 Количество вершин в треугольнике Серпинского порядка n. в OEIS