Blog
shark origami cp
Déplié du requin en origami

shark origami
Requin en origami (modèle de R.Lang)
Quand l'eau devient le requin dans laquelle il est censé nager.

Imaginez vous devant une feuille de papier sur laquelle sont tracées des lignes correspondant à des plis. Vous savez que cette feuille peut être pliée de manière à obtenir un pliage parfaitement plat. On vous l'a dit et vous voulez bien l'entendre. Mais vous êtes peut être comme moi, intrigué et même agité par cette idée. Vous vous demandez : à quel point est-il difficile d'assigner le sens des plis de cette feuille pour obtenir ce pliage plat ? Je m'étais longtemps posé la question. Et je viens d'avoir des éléments de réponse suite à un échange il y a quelques temps avec Robert Lang sur une liste de discussion. D'autres problèmes du même ordre sous-tendent l'origami comme : vous avez à nouveau une feuille de papier devant vous sur laquelle sont indiqués des plis et leur sens selon un code couleur. Les lignes noires désignent des plis montagnes (en relief) tandis que les lignes rouges désignent des plis vallée (en creux). Hors, nous savons que cet origami est pliable entièrement à plat comme le précédent. Mais quel ordre des plis faut-il respecter pour obtenir cette figure à plat ?

De telles questions me conduisent sur plusieurs terrains à la fois. Tout d'abord, de quel genre de problème mathématique s'agit-il ? Les mathématiciens ont-ils un nom pour désigner ce genre de problème et selon quels critères ? D'un point de vue beaucoup plus trivial : combien de temps met mon ordinateur pour calculer le résultat ? D'ailleurs, ce temps est-il calculable ? Qu'est ce qu'un temps calculable ? Et aurais je le temps ? Qui me donne ce temps au fond ?

En 1996, Marshall Bern et Barry Hayes publient un texte intitulé "la complexité des origamis à plat" (The complexity of flat origami) dans lequel ils prouvent deux choses :

  • Etant donné un déplié sans connaître le sens des plis, trouver un assignement correct des plis est dans certains cas un problème NP-complet.
  • Etant donné un déplié dont on connait le sens des plis, trouver l'ordre d'agencement de ces plis est dans certains cas un problème NP-complet également.
Que signifie NP-Complet ? Il s'agit d'une certaine classe de la théorie de la complexité. Et la théorie de la complexité est l'étude de la difficulté des problèmes en informatique. NP veut dire Non-déterministe polynomial. A partir de maintenant, je navigue à vue faute de connaissance théorique solide dans le domaine et me réfère à ce que j'ai compris de la discussion avec Robert Lang. Selon une définition profane, les problèmes NP-complet partagent les conditions suivantes:

  1. Une solution efficiente pour l'un d'entre eux peut être utilisée pour tous les autres problèmes NP-complets.
  2. Personne n'a trouvé une solution efficiente pour l'un d'entre eux.
  3. Même si la solution est dure, tester chaque solution potentielle est facile.
Par efficient, il faut entendre un problème qui ne croît pas de manière exponentiel avec la taille du problème. Le problème du vayageur de commerce est également un problème NP-complet connu. On ne connait pas de solutions exactes pour un temps raisonnable. C'est à dire qu'il faut souvent se contenter d'une solution approchée à mesure que la taille du problème augmente. Nos ordinateurs actuels sont dans ce contexte limités. Ce que Berns et Hayes montrent dans leur article, c'est que tout problème NP-complet peut être transcrit en problème de pliage, soit l'assignement correct de plis soit l'ordonnancement des plis. Si quelqu'un venait donc à découvrir un algorithme efficient pour un tel pliage, tous les autres problèmes NP-complets se trouveraient du même coup résolus... Ce qui vaudrait à coup sûr une médaille Fields à son inventeur, et produirait un cataclysme dans le milieu de la sécurité informatique, de la cryptologie et du commerce international... Chouette !

Comment se fait-il alors que nous arrivions à venir à bout de dépliés comme ceux là ? Parce que Berns et Hayes ne disent pas que tous les dépliés sont NP-complets mais certains d'entre eux le sont. D'ailleurs, ils donnent le mode d'emploi pour réaliser l'un d'entre eux : une sorte de pavage. Et encore une fois, de tels dépliés ne sont pas impossibles à resoudre si tant que leur taille ne dépasse pas un seuil critique...

22 janvier 2007
13-05-2017
02-04-2017
17-03-2017
24-01-2017
10-01-2017
09-01-2017
23-12-2016
13-09-2016
12-09-2016
19-08-2016
12-08-2016
10-08-2016
28-07-2016
20-07-2016
25-06-2016
11-06-2016
24-05-2016
26-04-2016
04-04-2016
05-02-2016
02-01-2016
16-01-2015
30-12-2014
22-12-2014
14-10-2014
10-10-2014
01-10-2014
27-09-2014
12-09-2014
09-09-2014
06-09-2014
31-08-2014
26-08-2014
20-08-2014
14-08-2014
07-08-2014
11-07-2014
26-06-2014
17-06-2014
11-06-2014
21-04-2014
13-04-2014
11-04-2014
28-03-2014
14-03-2014
12-03-2014
07-03-2014
24-02-2014
22-02-2014
09-02-2014
27-01-2014
13-01-2014
16-11-2013
10-11-2013
20-10-2013
12-10-2013
27-09-2013
07-09-2013
13-08-2013
11-08-2013
04-08-2013
02-08-2013
22-07-2013
14-06-2013
03-06-2013
28-05-2013
20-05-2013
14-05-2013
30-04-2013
26-04-2013
13-04-2013
09-04-2013
06-04-2013
22-03-2013
19-03-2013
06-03-2013
24-02-2013
18-02-2013
08-02-2013
03-02-2013
29-01-2013
30-12-2012
29-12-2012
28-12-2012
23-12-2012
14-12-2012
09-12-2012
26-11-2012
11-11-2012
28-10-2012
26-10-2012
23-10-2012
11-10-2012
09-10-2012
05-09-2011
04-07-2011
04-05-2011
26-03-2011
01-09-2010
08-08-2010
07-08-2010
06-08-2010
05-08-2010
04-08-2010
03-08-2010
02-08-2010
01-08-2010
31-07-2010
29-07-2010
28-07-2010
26-07-2010
25-07-2010
15-07-2010
26-06-2010
22-06-2010
08-06-2010
21-04-2010
15-04-2010
08-04-2010
05-04-2010
18-03-2010
14-03-2010
11-03-2010
27-02-2010
21-02-2010
13-12-2009
27-11-2009
23-11-2009
13-11-2009
06-11-2009
25-10-2009
11-10-2009
28-09-2009
27-09-2009
26-09-2009
25-09-2009
23-09-2009
22-09-2009
21-09-2009
13-09-2009
11-09-2009
08-09-2009
06-09-2009
04-09-2009
24-08-2009
20-08-2009
06-08-2009
01-08-2009
21-07-2009
12-07-2009
29-06-2009
23-06-2009
10-06-2009
21-05-2009
16-05-2009
13-05-2009
07-05-2009
01-05-2009
29-04-2009
26-04-2009
08-04-2009
27-03-2009
07-03-2009
01-03-2009
19-02-2009
09-02-2009
24-01-2009
16-01-2009
11-01-2009
20-12-2008
12-12-2008
25-11-2008
12-11-2008
02-11-2008
21-10-2008
30-09-2008
23-09-2008
11-09-2008
09-09-2008
07-09-2008
22-08-2008
17-08-2008
13-08-2008
09-08-2008
16-06-2008
15-06-2008
07-06-2008
28-05-2008
06-04-2008
21-03-2008
15-03-2008
07-03-2008
25-02-2008
15-02-2008
11-02-2008
22-01-2008
19-01-2008
18-01-2008
13-01-2008
10-01-2008
01-01-2008
30-12-2007
29-12-2007
12-12-2007
29-11-2007
23-11-2007
18-11-2007
17-11-2007
11-11-2007
26-10-2007
21-10-2007
30-09-2007
23-09-2007
19-09-2007
13-09-2007
09-09-2007
08-09-2007
29-08-2007
25-08-2007
08-08-2007
06-08-2007
22-07-2007
20-07-2007
17-07-2007
13-07-2007
12-07-2007
07-07-2007
29-06-2007
24-06-2007
11-06-2007
09-06-2007
06-06-2007
23-05-2007
22-05-2007
21-05-2007
17-05-2007
13-05-2007
11-05-2007
29-04-2007
22-04-2007
19-04-2007
04-04-2007
01-04-2007
18-03-2007
16-03-2007
15-03-2007
04-03-2007
01-03-2007
25-02-2007
02-02-2007
27-01-2007
22-01-2007
06-01-2007
30-12-2006
27-12-2006
18-12-2006
15-12-2006
09-12-2006
01-12-2006
26-11-2006
14-11-2006
06-11-2006
23-10-2006
10-10-2006
07-10-2006
03-10-2006
01-10-2006
09-09-2006
08-09-2006
20-08-2006
06-08-2006
27-07-2006
23-07-2006
17-07-2006
15-07-2006
03-07-2006
26-06-2006
09-06-2006
28-05-2006
19-05-2006
16-05-2006
23-04-2006
15-04-2006
02-04-2006
26-03-2006
20-03-2006
09-03-2006
07-02-2006