Мембранные вычисления
Мембранные вычисления (или MC ) — это область компьютерных наук , целью которой является открытие новых вычислительных моделей на основе изучения биологических клеток , особенно клеточных мембран . Это подзадача создания клеточной модели .
Мембранные вычисления имеют дело с моделями распределенных и параллельных вычислений , локализованно обрабатывая мультимножества символьных объектов. Таким образом, правила эволюции позволяют инкапсулировать развивающиеся объекты в отсеки, определяемые мембранами. Важную роль в этих процессах играют связи между отсеками и с окружающей средой. Различные типы мембранных систем известны как P-системы в честь Георгия Пауна , который впервые разработал эту модель в 1998 году. [1]
Существенным компонентом Р-системы является ее мембранная структура, которая может представлять собой иерархическое расположение мембран, как в клетке, или сеть мембран (размещенных в узлах графа), как в ткани или нейронной сети. П-системы часто изображаются графически с помощью рисунков.
Интуиция, лежащая в основе понятия мембраны, — это трехмерный пузырь из биологии. Однако сама концепция более общая, и мембрана рассматривается как разделитель двух областей. Мембрана обеспечивает избирательную связь между двумя областями. разделено Согласно Георге Пауну, евклидово пространство на конечное «внутри» и бесконечное «снаружи». Избирательная коммуникация — вот где на помощь приходят вычисления.
Графические представления могут иметь множество элементов в зависимости от варианта изучаемой модели. Например, правило может иметь специальный символ δ, и в этом случае содержащая его мембрана растворяется, и все ее содержимое перемещается вверх в иерархии регионов.
Разнообразие предложений биологии и диапазон возможностей определения архитектуры и функционирования мембранного многомножествового обрабатывающего устройства практически безграничны. Действительно, литература по мембранным вычислениям содержит очень большое количество моделей. Таким образом, MC — это не просто теория, связанная с конкретной моделью, это основа для разработки разрозненных моделей.
Химические вещества моделируются символами или, альтернативно, строками символов. Область, определяемая мембраной, может содержать другие символы или строки (совместно называемые объектами) или другие мембраны, так что P-система имеет ровно одну внешнюю мембрану, называемую кожной мембраной, и иерархические отношения, управляющие всеми ее мембранами. мембраны под кожной мембраной.
Если объекты являются символами, то их множественность в пределах региона имеет значение; однако мультинаборы также используются в некоторых струнных моделях. Регионы имеют связанные правила, которые определяют, как объекты производятся, потребляются, передаются в другие регионы и иным образом взаимодействуют друг с другом. Недетерминированное максимально параллельное применение правил во всей системе представляет собой переход между состояниями системы, а последовательность переходов называется вычислением. Конкретные цели могут быть определены для обозначения состояния остановки, в этот момент результатом вычислений будут объекты, содержащиеся в определенной области. В качестве альтернативы результат может состоять из объектов, отправленных из кожной мембраны в окружающую среду.
Было изучено множество вариантов моделей, и интерес был сосредоточен на доказательстве вычислительной универсальности для систем с небольшим количеством мембран с целью решения NP-полных задач, таких как задачи булевой выполнимости (SAT) и задача коммивояжера (TSP) . могут P-системы обменивать пространственные и временные сложности и реже использовать модели для объяснения естественных процессов в живых клетках. В ходе исследований разрабатываются модели, которые, по крайней мере теоретически, могут быть реализованы на аппаратном уровне. На сегодняшний день П-системы представляют собой почти все теоретические модели, которые никогда не применялись на практике, хотя практическая система дана. [2]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Паун, Георге. «Введение в мембранные вычисления» (PDF) .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Патент США 20 090 124 506.