Биотехнологии →
L-Systems — математическая красота растений
Красота растений привлекала внимание математиков веками. Активнее всего изучались интересные геометрические свойства растений, такие как симметрия листьев относительно центральной оси, радиальная симметрия цветов, и спиральное расположение семечек в шишках. «Красота связана с симметрией» (H. Weyl. Symmetry). Во время роста живых организмов, особенно растений, можно четко видеть регулярно повторяющиеся многоклеточные структуры. В случае составных листьев, например, маленькие листочки, которые являются частью большого взрослого листа, имеют ту же форму, что весь лист имел на раннем этапе формирования. [1]
В 1968г. Венгерский биолог и ботаник Аристид Линденмайер (Aristid Lindenmayer) предложил математическую модель для изучения развития простых многоклеточных организмов, которая позже была расширена и используется для моделирования сложных ветвящихся структур — разнообразных деревьев и цветов. Эта модель получила название Lindenmayer System, или просто L-System.
Для тех, кто в теме и не хочет все читать целиком, проскрольте вниз, есть вопрос.
Я буду сокращать L-System до L в тексте.
Основная идея L — постоянная перезапись (rewriting) элементов строки. О чем это? Вкратце, rewriting — это способ получения сложных объектов путем замены частей простого начального объекта по некоторым правилам. Классическим примером является снежинка. На рисунке initiator — это начальный объект, грани которого заменяются на generator. Далее с новым объектом проделывается то же самое. В данном случае обычный фрактал.
Возвращаясь к L и проводя аналогию с фракталами, можно сказать, что L оперирует со строкой символов по специальным правилам, начиная с первоначальной простой аксиомы. Люди, знакомые с понятием грамматики, сразу заметят, что по сути L ей и является. Но фундаментальное отличие L от формальных грамматик состоит в том, что правила применяются одновременно ко всей строке, к каждому символу, плюс, нет понятий терминальных и нетерминальных символов. То есть «вывод» по этой грамматике может продолжаться бесконечно. Одновременность применения правил очень быстро становится понятна, если учесть откуда пришла эта модель. В биологии каждая клетка растет, делится и развивается параллельно во времени. На следующей картинке видно соотношение между контекстносвободными (OL), контекстнозависимыми (IL) L и другими формальными грамматиками в иерархии Хомского.
Также, как и в классификации Хомского, L имеют и свою классификацию от простых до сложных и мощных.
Самым простым примером являются детерминированные контекстносвободные L или сокращенно DOL. Я не люблю формальные определения грамматик, так что скажу просто своими словами. Есть некоторый набор символов — алфавит. Этим алфавитом записывается строка, с которой работает L. Есть аксиома — первоначальная строка из одной или более буквы и набор правил вида a
В 1968г. Венгерский биолог и ботаник Аристид Линденмайер (Aristid Lindenmayer) предложил математическую модель для изучения развития простых многоклеточных организмов, которая позже была расширена и используется для моделирования сложных ветвящихся структур — разнообразных деревьев и цветов. Эта модель получила название Lindenmayer System, или просто L-System.
Для тех, кто в теме и не хочет все читать целиком, проскрольте вниз, есть вопрос.
Я буду сокращать L-System до L в тексте.
Rewriting.
Основная идея L — постоянная перезапись (rewriting) элементов строки. О чем это? Вкратце, rewriting — это способ получения сложных объектов путем замены частей простого начального объекта по некоторым правилам. Классическим примером является снежинка. На рисунке initiator — это начальный объект, грани которого заменяются на generator. Далее с новым объектом проделывается то же самое. В данном случае обычный фрактал.
Возвращаясь к L и проводя аналогию с фракталами, можно сказать, что L оперирует со строкой символов по специальным правилам, начиная с первоначальной простой аксиомы. Люди, знакомые с понятием грамматики, сразу заметят, что по сути L ей и является. Но фундаментальное отличие L от формальных грамматик состоит в том, что правила применяются одновременно ко всей строке, к каждому символу, плюс, нет понятий терминальных и нетерминальных символов. То есть «вывод» по этой грамматике может продолжаться бесконечно. Одновременность применения правил очень быстро становится понятна, если учесть откуда пришла эта модель. В биологии каждая клетка растет, делится и развивается параллельно во времени. На следующей картинке видно соотношение между контекстносвободными (OL), контекстнозависимыми (IL) L и другими формальными грамматиками в иерархии Хомского.
Самые простые L-Systems.
Также, как и в классификации Хомского, L имеют и свою классификацию от простых до сложных и мощных.
Самым простым примером являются детерминированные контекстносвободные L или сокращенно DOL. Я не люблю формальные определения грамматик, так что скажу просто своими словами. Есть некоторый набор символов — алфавит. Этим алфавитом записывается строка, с которой работает L. Есть аксиома — первоначальная строка из одной или более буквы и набор правил вида a
18.09.2009 03:09+0400