Pr sentation MOCANA .pdf



Nom original: Pr_sentation_MOCANA.pdfTitre: Membrane computing and complexity theory: A characterization of PSPACEAuteur: Charly Finette

Ce document au format PDF 1.5 a été généré par LaTeX with Beamer class / pdfTeX-1.40.20, et a été envoyé sur fichier-pdf.fr le 15/04/2020 à 11:10, depuis l'adresse IP 77.206.x.x. La présente page de téléchargement du fichier a été vue 51 fois.
Taille du document: 544 Ko (27 pages).
Confidentialité: fichier public
🎗 Auteur vérifié


Aperçu du document


Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Membrane computing and complexity theory: A
characterization of PSPACE
Charly Finette

Février 2020

Charly Finette

Seminar

1 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Table of contents

1

Introduction

2

P systèmes avec membranes actives

3

Classes de complexités des P systèmes

4

Caractérisation de PSPACE

5

Conclusion

Charly Finette

Seminar

2 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

C’est quoi un P système ?
Modèle de calcul inspiré de la biologie cellulaire.
On veut capturer l’aspect computationnel du métabolisme
cellulaire et des échanges d’information.

Charly Finette

Seminar

3 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

C’est quoi un P système ?
Modèle de calcul inspiré de la biologie cellulaire.
On veut capturer l’aspect computationnel du métabolisme
cellulaire et des échanges d’information.

Charly Finette

Seminar

3 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Transport contrôlé par canaux de protéines

Charly Finette

Seminar

4 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Division cellulaire

Charly Finette

Seminar

5 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Objectif des P systèmes
Ces processus sont modélisés dans les P systèmes.
Le but de ces modèles est d’identifier les opérations qui
donnent aux systèmes cellulaires leur puissance en terme de
traitement de l’information.
Une fois ces opérations identifiés, on pourrait possiblement
les implanter in vitro (dans un tube à essai) or in silico (sur
un ordinateur).
Les P systèmes permettent aussi de modéliser des
phénomènes biologiques comme la photosynthèse, ou la
respiration bactérienne.

Charly Finette

Seminar

6 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Puissance de calcul des P systèmes
Cet article étudie les P systèmes avec membranes actives i.e les
modèles où les membranes peuvent se diviser, se dissoudre et
sont polarisées.
Opérations autorisées

Problèmes calculables en temps polynomiale

Sans division

P

Sans polarisation
Sans dissolution

P

Avec division de
membrane élémentaire

⊃ NP et coNP

Sans restrictions

⊃ PSPACE

Charly Finette

Seminar

7 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Objectif de l’article

L’article montre que la classe des problèmes que les P systèmes
confluents avec membranes actives résolvent en temps
polynomiale est égale à PSPACE.

Par conséquent les P systèmes satisfont la thèse du calcul
parallèle :
M − P T IM E = M − N P T IM E = P SP ACE

Charly Finette

Seminar

8 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Définition

Definition
Un P système avec membranes actives c’est un tuple
Π = (V, H, µ, w1 , ..., wm , R) avec :
V un alphabet
H un ensemble d’étiquettes pour les membranes
µ une structure de membrane, avec m membranes
w1 , ..., wm des mots fini sur l’alphabet V
R un ensemble de règles

Charly Finette

Seminar

9 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Structure membranaire µ

Ici, on a étiqueté les membranes par des entiers.
H = {1, 2, 3, 4, 5, 6, 7, 8}
Charly Finette

Seminar

10 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Structure membranaire µ

La membrane 1 est appelée “épiderme”.
Les membranes qui n’en contiennent pas d’autres sont dites
“élémentaires”. (Les membranes 3, 5, 6, 8)
Charly Finette

Seminar

11 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Structure membranaire µ

Notons que l’on peut associer une polarisation à chaque
membrane. Une membrane peut être positive, négative ou
neutre. On note alors [...]p avec p ∈ {+, −, 0}
Charly Finette

Seminar

12 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Les règles R
Les règles modélisent des transformations chimiques de la forme
suivante.

Un élément de l’alphabet V représente donc une certaine
molécule.
Il existe différentes sortes de règles.

Charly Finette

Seminar

13 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

(a) Règles d’évolution d’objet

a est une lettre de V mais v est un mot sur V

Charly Finette

Seminar

14 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

(b) Règles de communication IN

Peut induire un changement de polarisation.

Charly Finette

Seminar

15 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

(c) Règles de communication OUT

Peut induire un changement de polarisation.

Charly Finette

Seminar

16 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

(d) Règles de dissolution

Charly Finette

Seminar

17 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

(e) Règles de division pour membrane élémentaire

Peut induire un changement de polarisation.

Charly Finette

Seminar

18 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

(f) Règles de division pour membrane non-élémentaire

Charly Finette

Seminar

19 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Fonctionnement du système

Toutes les règles sont appliquées en parallèle.
A chaque étape, un objet ne peut être sujet que à une seule
règle de type (a)-(e)
A chaque étape, une membrane ne peut être sujet que à
une seule règle de type (b)-(f)
A chaque étape, on applique le maximum de règles
possibles.
L’épiderme ne peut ni être dissoute ni divisé.

Charly Finette

Seminar

20 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Calcul d’un P système

Dans cette article, on s’intéresse à la variante des P systèmes
qui :
résolvent des problèmes de décision : On entre une instance
du problème dans une région, si un objet “oui” sort de
l’épiderme, le résultat du calcul est oui ; sinon le résultat est
non.
sont confluents i.e les systèmes qui s’arrêtent toujours et
qui renvoient toujours la même réponse si la configuration
initiale est la même.

Charly Finette

Seminar

21 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

La classe PMCSAM
On note AM la classe des P systèmes avec membranes
actives.
On note PMCSAM la classe des des problèmes résolus par
une famille semi-uniformes de P systèmes de type AM en
temps polynomial.
Theorem
PSPACE ⊆ PMCSAM
La suite de l’article consiste a prouver l’inclusion inverse pour
obtenir la caractérisation de PSPACE.
Theorem
PSPACE = PMCSAM
Charly Finette

Seminar

22 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Démonstration du théorème
L’état d’une membrane est le couple (M, p) où M est le contenu
d’une membrane (un mot sur V ) et p est la polarisation.
La démonstration repose sur l’algorithme State. Étant
donné une membrane h et un entier n, State renvoie l’état
de h à la n-ième étape.
State est récursif et il utilise deux sous-procédures
Contributions-from-children (récursif aussi) et Parent.
Parent renvoie la membrane parente de h à l’état n (il
regarde la configuration initiale, et vérifie juste si elle n’a
pas été dissoute pendant les n-premières étapes.
Contributions-from-children calcule les interactions de la
membrane h avec ses enfants à l’état n (règles (b), (c) et
(d))
Charly Finette

Seminar

23 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

La fonction State

State est de complexité polynomiale en espace.

Charly Finette

Seminar

24 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Raisonnement
On considère un problème de décision X qui est résolu par
un P système confluent Π = (V, H, µ, w1 , ..., wm , R) (X
∈ P M C SAM )
On peut calculer la réponse à ce problème de décision grâce
à la fonction State. Soit h0 l’épiderme de Π, il suffit de
calculer State(h0 ,n) jusqu’à ce que l’objet oui soit expulsé
de h0
Comme State est polynomiale en espace, on a décidé notre
problème X avec une compléxité en espace polynomiale.
(X ∈ PSPACE )
PMCSAM ⊆ PSPACE
Charly Finette

Seminar

25 / 26

Introduction
P systèmes avec membranes actives
Classes de complexités des P systèmes
Caractérisation de PSPACE
Conclusion

Interprétation du résultat
D’autres modèles de calcul biologique comme le calcul basé
sur l’ADN caractérisent de la même façon PSPACE.
L’auteur interprète ses résultats plus comme une limite au
potentiel du calcul biologique que comme un guide pour la
construction d un ordinateur biologique.
Certaines opérations (comme la division de membrane
non-élémentaire) sont très difficilement utilisable en
pratique.
Par contre, si on implémente ces systèmes en "bio", ils
pourraient quand même être plus performants que les
supercalculateurs en silicone, grâce à leur parallélisme
massif et à leur utilisation minimale d’énergie.
Charly Finette

Seminar

26 / 26


Aperçu du document Pr_sentation_MOCANA.pdf - page 1/27
 
Pr_sentation_MOCANA.pdf - page 2/27
Pr_sentation_MOCANA.pdf - page 3/27
Pr_sentation_MOCANA.pdf - page 4/27
Pr_sentation_MOCANA.pdf - page 5/27
Pr_sentation_MOCANA.pdf - page 6/27
 




Télécharger le fichier (PDF)


Pr_sentation_MOCANA.pdf (PDF, 544 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


prsentationmocana
sminaire2020imd 4
prsentationvrification
soutenancememoirecharlyfinette
memoirecharlyfinette 3
fascicule 2 1

Sur le même sujet..