Soutenance mémoire
REPRÉSENTATION DES POLYOMINOS À PARTIR D’UNE IMAGE BINAIRE
Lorsque nous manipulons des régions discrètes, il en existe plusieurs modes de représentations possibles. Pour les polyominos, en plus de la représentation par mot de contour, nous pouvons également utiliser des matrices binaires (voir figure 2.15). Elle présente l’avantage de pouvoir décrire des régions non connexes et avec trou, ce qui est moins naturel dans le cas des mots de contour. Pour un polyomino quelconque, on identifie un pixel par le bit 0 pour signifier qu’il est vide et par le bit 1 pour signifier qu’il est occupé.
L’étiquetage en composantes connexes est donc généralement présent lorsqu’il faut regrouper des pixels connexes. Il est à la base de la plupart des chaines algorithmiques en traitement d’images analysant des régions dans une scène. Plusieurs types d’algorithmes standard sont utilisés pour coder l’information et leur efficacité varie suivant la nature des données. On trouvera ci-dessous une description sommaire de quelques techniques courantes.
L’approche pixel est une approche de comparaison de l’étiquette courante avec les étiquettes du voisinage (voir figure 2.16).
Le codage par arbre quaternaire est une méthode de représentation permettant de minimiser l’information nécessaire pour coder des zones homogènes. C’est une forme de compactage qui divise l’image en quatre quadrants (voir figure 2.17). Chaque quadrant est à son tour divisé en 4 sous quadrants et ainsi de suite.
En balayant l’image ligne par ligne, il est possible d’appliquer l’encodage de plage sur toutes les séquences de points qui ont la même couleur. Le codage par longueur de plage (RLC) est utilisé pour rechercher des segments adjacents pour déterminer la connectivité des segments.
Pour réduire la complexité algorithmique et le rendre plus compacte, le codage par arbre quaternaire est généralement associé à RLC.
Cependant ces approches utilisent un grand nombre de tests. Ce qui se traduit au niveau du processeur par une importante consommation de ressource [Lacassagne et al., 1998]. Nous proposons de représenter de façon compacte une image par une matrice binaire, à l’aide d’une liste d’entiers, où chaque ligne (ou, de façon équivalente, chaque colonne) correspond à la représentation binaire de l’entier en question (voir figure 2.18). Par exemple, pour des tétraminos, on se limite à des entiers (voir figure 2.19) allant de 1 à 15.
Les tuiles admettant deux factorisations distinctes non triviales sont appelées doubles parallélogrammes et ont été décrites dans [Blondin Massé et al., 2013]. De plus, il n’existe aucun polyomino parallélogramme décrit par plus de deux morphismes [Blondin Massé et al., 2012].
Nous sommes maintenant prêts à définir les polyominos premiers et composés. Il devrait être noté que nous présentons une définition équivalente à celle donnée dans [Provençal, 2008] qui repose sur la notion de morphisme parallélogramme.
Définition
Soit Q un polyomino quelconque et j un morphisme parallélogramme. Alors la composition de j et Q, dénotée par j(Q), est le polyomino unique de mot de contour j(u), où u est un mot de contour de Q.
En d’autres termes, un polyomino est premier si et seulement s’il ne peut pas être décomposé non trivialement comme le produit d’un morphisme parallélogramme et d’un autre polyomino.
Il est utile de noter que le problème de décider si un polyomino est premier est au moins aussi difficile que le problème de décider si un nombre est premier. En effet, on peut remarquer que le rectangle 1n ayant le mot de contour 0n12n3 est premier si et seulement si n est premier. Dans le même esprit, un mot de contour u est appelé premier si POLY(u) et un polyomino premier et un morphisme parallélogramme j est appelé premier si POLY(0123) est un polyomino premier.
THÉORÈME DE DÉCOMPOSITION EN FACTEURS PREMIERS
GÉNÉRATION ET FACTORISATION DE NOMBRES PREMIERS
Dans la cryptographie traditionnelle, en vigueur avant les années 1970, les opérations de chiffrement et de déchiffrement étaient effectuées avec une même clé unique (voir figure 3.5).
Il n’est pas toujours facile de déterminer si un nombre est premier. En fait, il semblerait que pour tester la primalité d’un nombre, on aurait besoin de déterminer tous les facteurs du nombre pour voir s’il existe un diviseur autre que le nombre en question et 1. Des méthodes plus rapides pour les tests de primalité découvertes dans les années 1970 permettent de déterminer des nombres premiers en exploitant certaines de leurs propriétés [Miller, 1976]. Sans ces résultats de détection de nombres premiers, beaucoup de clés publiques cryptographiques actuelles ne seraient pas pratiques voire obsolètes du fait que les méthodes efficaces de génération de grands nombres premiers permettent de construire de longues paires de clés publiques/privées.
Conséquemment aux longues paires de clés publiques/privées, les méthodes de calcul actuels pour déterminer si un grand nombre est premier sont lentes et coûteuses. Par exemple, il a été récemment estimé que la récupération des facteurs premiers d’un nombre de 1024 bits prendrait une année sur une machine coûtant 10 millions de dollars US [Franke et al., 2005].
Un nombre de 2048 bits nécessiterait plusieurs billiards de fois plus de travail. Ces estimations actuelles sont ce à quoi on aurait pu s’attendre dans les années 1970 lorsque le problème a été proposé [Rivest et al., 1978]. Parallèlement, la taille recommandée des clés de chiffrement devient de plus en plus importante en raison d’une puissance de calcul en croissance constante, soit de plus en plus d’outils puissants de cryptanalyse. Ainsi, personne ne sait si on pourra découvrir des longueurs de clés plus importantes dans les années à venir.
THÉORÈME FONDAMENTAL DE L’ARITHMÉTIQUE
S’il existe un algorithme simple à mettre en place pour décomposer un nombre de taille raisonnable, cet algorithme se révèle rapidement inefficace, en termes de temps, pour de très grands nombres. La recherche d’algorithmes performants est donc très pertinente. En outre, si une méthode rapide était trouvée pour résoudre le problème de la factorisation des nombres entiers, alors plusieurs systèmes cryptologiques importants seraient cassés, incluant l’algorithme à clé publique RSA.
Après la définition 6, on est naturellement amené à se demander si le théorème fondamental de l’arithmétique peut être étendu aux polyominos. Il y a deux conditions qui doivent être vérifiées : l’existence d’une factorisation en nombres premiers et l’unicité de cette factorisation.
ALGORITHMES DE FACTORISATION
Afin de déterminer si un polyomino P est composé, il suffit de trouver un morphisme parallélogramme j 6= Id et un mot de contour u 62 [0123] tel que j(u) soit le mot de contour de P. Si un tel morphisme est inexistant, alors nous pouvons en conclure que le polyomino est premier.
VERSION NAÏVE
L’approche directe et simple consiste à essayer chaque factorisation possible jusqu’à ce qu’on trouve un morphisme parallélogramme capable de factoriser le mot de contour du polyomino. Cette approche brute de stockage d’occurrences, bien que coûteuse, présente un niveau raisonnable d’efficacité et nous garantit entre autres de couvrir tous les morphismes homologues existants appliqués au pas élémentaire si celui-ci est composé.
Pour réduire le nombre de cas à prendre en compte, on se limite à des facteurs commençant et se terminant par la même lettre. Plus précisément, soit P un polyomino et w l’un de ses mots de contour, pour tout a 2 F, soit Fa l’ensemble des facteurs de w2 commençant et se terminant par a. Les étapes ci-dessous peuvent être utilisées pour factoriser P :
Théorème
Tout polyomino P peut-être factorisé en produit de polyominos premiers en O(n7) où n est le périmètre de P.
Démonstration
Soit w tout mot de contour de P. L’étape 1 est realisée en O(n2) puisqu’il y a O(n2) facteurs commençant et se terminant par le même pas élémentaire dans tout mot de F. Donc, il y a au plus n2 valeurs possibles. Les étapes 24 sont alors répetées en O(n4) puisqu’il y a au plus n2 comparaisons possibles considérant les chemins horizontaux et verticaux. La construction de j à l’étape 3 est alors faite en temps constant alors que l’étape 4 prend O(n) puisque celle-ci doit être effectuée pour chaque conjugué de w. En conséquence, décomposer P par j(u), pour un quelconque morphisme parallélogramme j et un mot de contour u est fait en O(n5). Finalement, quand la liste des j(u) est formée pour chaque a 2F, il reste à vérifier si w est décodé par j, en fissurant w, considérant ainsi la longueur du morphisme homologue pour les chemins horizontaux et verticaux. Cette opération est faite au plus en temps linéaire.
Dès lors que cela doit être répété aussi longtemps que j ou u n’est pas premier, la complexité globale est O(n7).
AMÉLIORATION DE L’ALGORITHME NAÏF
Une complexité de O(n7) est plutôt grande et il est raisonnable d’espérer la réduire. Plus spécifiquement, au lieu d’énumérer tous les facteurs possibles u dans F0 et v dans F1, le choix devrait plutôt s’opérer selon que u et v surviennent de façon contiguë dans le mot en traitement. Dès lors, cela donne l’approche améliorée suivante.
Comme première étape, nous choisissons n’importe quel mot de contour w commençant par 0. La première idée consiste à essayer de diviser w par des blocs commençant et se terminant par le même pas élémentaire, conformément à la proposition 2. Il suffit donc de regarder toutes les occurrences de 0 pour déterminer un j(0). Quand un tel bloc est choisi, alors j(0) et j(2) sont complètement déterminés.
L’étape suivante consiste à vérifier le pas élémentaire suivant le premier bloc. Si celui-ci est 0 ou 2 alors nous vérifions si les lettres suivantes ou le bloc suivant correspondent à j(0). Si tel n’est pas le cas, alors nous devons choisir une autre valeur j(0). D’autre part, s’il y a une correspondance, alors on passe au bloc suivant. Nous répétons les étapes précédentes jusqu’à ce que nous atteignions la lettre 1 ou 3. De la même manière que pour la lettre 0, nous essayons ensuite chaque bloc possible pour chaque 1 ou 3. Quand un tel bloc est choisi, alors j(1) et j(3) sont complètement déterminés. Quand les quatre images de j sont choisies, il ne reste plus qu’à vérifier si le mot de contour peut être factorisé comme un produit des quatre blocs (cette étape est appelée étape de décodage).
Théorème
Tout polyomino P peut-être factorisé en produit de polyominos premiers en O(n5) avec n étant le périmètre de P.
Démonstration
Soit w le mot de contour de P commençant par 0. En choisissant chaque occurrence de 0 en w pour construire j(0), il y a au plus n valeurs possibles (et puis j(2) est déterminé). Une fois j(0) est choisi, il y a au plus n valeurs possibles pour j(1) (et puis j(3) est déterminé). Enfin, quand j(a) est connu pour chaque a 2F, il reste à vérifier si w pourrait être décodé de j, ce qui se fait en temps linéaire tout au plus. Par conséquent, il peut être décidé dans O(n3) si w est décodable selon certains morphismes parallélogrammes j. Le test doit être effectué pour chaque conjugué de w commençant par 0, on obtient alors O(n4).
Enfin, en répétant cette réduction jusqu’à ce que les objets ne soient plus décomposables, on obtient la complexité affirmée O(n5).
EXPLORATION INFORMATIQUE
Dans ce chapitre, nous nous intéressons à l’évaluation pratique des deux algorithmes de factorisation décrits au chapitre précédent. Nous expliquons de quelle façon un banc d’essai est généré, puis nous proposons une analyse comparative de nos deux algorithmes de factorisation des polyominos.
MÉTHOLOGIE
JAVA
Pour l’évaluation expérimentale, notre choix s’est porté sur le langage de programmation Java. Afin de visualiser les objets construits, nous avons choisi le langage de programmation Python avec son module graphique « Turtle », très adapté pour illustrer les figures discrètes. L’interface entre les deux langages s’est faite par l’intermédiaire du langage Jython, qui est un interpréteur Python écrit en Java. Pour chronométrer les différents temps de calcul, nous utilisons la bibliothèque java.lang. management, qui offre la fonction currenttime() (voir algorithme 4.1), c’est-à-dire l’heure du 53 système actuel qui est déterminée immédiatement avant et après l’exécution de l’algorithme.
On atténue ainsi l’impact des tâches de traitement de fond sur le temps de fonctionnement. La valeur retournée en minutes, secondes, millisecondes ou nanosecondes représente le temps fixe d’exécution. Typiquement, pour une étude comparative de la complexité en temps, la plupart des programmes sont codés similairement en introduisant des fragments de code ressemblant à ce qui se trouve à l’algorithme 4.1.
BANC D’ESSAI
À l’instar des graphes (orientés et non orientés), l’énumération de polyominos est un problème très difficile et il semble très peu probable qu’il existe un algorithme efficace permettant de tirer de façon complètement aléatoire un polyomino de périmètre p, pour une valeur de p donnée.
Nous devons donc nous rabattre sur une stratégie de génération qui ne garantit par l’uniformité. Nous avons choisi de générer 250 polyominos premiers de longueur de mot de contour allant de 10 à 200 et 1000 polyominos composés de longueur de mot de contour allant de 100 à 900. Les polyominos premiers sont générés pseudo-aléatoirement. Les polyominos composés sont générés sur la base de polyominos premiers, auxquels on applique un morphisme parallélogramme j lui aussi généré de façon aléatoire.
À cet effet, nous développons deux générateurs aléatoires :
1. un générateur pseudo-aléatoire de polyominos, que nous dénotons par GPoly ;
2. un générateur pseudo-aléatoire de polyominos parallélogrammes, que nous dénotons par GPara.
GÉNÉRATION DE POLYOMINOS
Il s’avère nécessaire de concevoir un générateur de polyominos premiers. En effet, on ne peut énumérer les polyominos de façon manuelle ou déterministe puisqu’il y en a un nombre dont la croissance est exponentielle. Notre banc d’essai est donc pseudo-aléatoire à défaut d’être complètement aléatoire.
Il y a différentes façons de résoudre le problème de la construction du générateur. Il convient de commencer par la solution la plus intuitive. L’idée de base de cette méthode simple est la suivante : étant donné un polyomino P, soit un générateur aléatoire G qui prend en entrée un nombre entier n qui correspond au nombre de cellules à générer des polyominos.
Comme le montre la figure 4.2 ci-dessus, on construit un polyomino de n cellules en lui ajoutant au hasard une cellule sur son contour. Cette opération est effectuée jusqu’à ce qu’on ait placé le bon nombre de cellules. L’ensemble de cellules ainsi généré est clairement connexe. Clairement, un polyomino ainsi généré peut être premier ou composé, mais, dans la plupart des cas, il s’agit d’un polyomino premier. Pour cette raison, nous proposons un deuxième générateur dans la sous-section suivante, qui nous permet de construire un échantillon de polyominos composés.
ANALYSE DES RÉSULTATS EMPIRIQUES
On note les caractéristiques et conclusions suivantes sur le comportement local des algorithmes de factorisation pour des mots de contour :
1. Pour des polyominos premiers et composés, dans les deux cas, on a des fonctions linéaires globalement croissantes en fonction de la longueur du mot de contour.
2. Pour des polyominos premiers ou composés, l’algorithme amélioré est beaucoup plus efficace en temps de factorisation que l’algorithme naïf.
3. L’indicateur a dénote d’une meilleure performance de l’algorithme de factorisation amélioré par rapport à l’algorithme de factorisation naïf.
4. Pour des polyominos premiers ou composés, l’algorithme naïf et amélioré ne suivent pas de règle de puissance empirique locale. On en déduit que la la borne empirique n’est pas atteinte puisque a varie selon les données d’entrées. On en conclut que les données générées sont insuffisantes pour atteindre la borne empirique.
CONCLUSION
En clair, nous savons que la borne empirique pour nos deux algorithmes de factorisation est loin d’être atteinte. Il nous faut beaucoup plus de données en entrée. Il est probable également que les algorithmes de génération génèrent trop rarement les cas les plus défavorables. Au niveau empirique local, on n’a pas pu atteindre la borne empirique mais clairement, la comparaison empirique locale nous montre que l’algorithme amélioré est plus performant en temps
d’exécution, ce qui est cohérent avec les bornes théoriques démontrées.
L’explication de la performance empirique locale de l’algorithme amélioré est la suivante :
1. En choisissant chaque occurrence de 0 en w pour construire j(0), soit k0 le premier conjugé de w commençant par 0 et construisant d images pour j(0).
2. Soit k0 determiné en choisissant chaque occurrence de 1 en w pour construire j(1), soit k1 le premier conjugé de w commençant par 1 et construisant d images pour j(1).
3. Soit N le nombre de tentatives globales pour construire les k conjugués et leur images de w commençant par 0 et 1.
65 La fonction skip(), avec comme séquence d’entrée le mot de contour w, retourne une séquence qui ignore N lettres de la séquence sous-jacente. Pour que l’algorithme soit le plus rapide possible, supposons que les quatre images de j sont choisies, la probabilité prob(k0;1) que le premier essai factorise P et que u et v surviennent de façon contiguë est très forte puisque N skip(jwj;k0;1) pour un certain ` < 60. Dès lors, on obtient un temps global constant de factorisation t des polyominos composés pour des longueurs de contour ` < 60.
En conclusion, l’évaluation expérimentale nous a permis de mieux comprendre certaines caractéristiques spécifiques du fonctionnement des algorithmes de factorisation des polyominos au niveau empirique que l’analyse théorique ne peut déceler.
CONCLUSION
L’objet de ce mémoire concernait les polyominos qui pavent le plan par translation et, en particulier le problème de leur factorisation. En présentant une solution sur la primalité des figures discrètes, nous avons mis en lumière l’intérêt de nos recherches et sa potentielle application dans le domaine de la cryptographie à clé publique/privée. En effet, de futures recherches dans cette direction permettront l’application de la primalité des figures discrètes par leurs mots de contour à la cryptographie asymétrique. Cependant, il faudra se pencher sur l’application de notions mathématiques propres à l’arithmétique élémentaire.
Dans ce mémoire, pour la génération de notre banc d’essai, nous avons également implémenté deux générateurs pseudo-aléatoires de polyominos et de polyominos composés. Nous avons aussi fourni deux algorithmes permettant d’exprimer, en temps polynomial, tout polyomino comme le produit de polyominos premiers. En conséquence, il s’ensuit que nous pouvons décider si un polyomino est premier ou composé en temps polynomial.
L’algorithme amélioré est actuellement le meilleur algorithme connu pour résoudre le problème de la factorisation de figures discrètes. On note aussi comme mentionné ci-dessus que la limite O(n5) est plutôt grande et il ne serait pas surprenant de concevoir dans un futur proche des algorithmes plus efficaces pour résoudre le problème de la factorisation de façon plus efficace.
Par exemple, on pourrait essayer de factoriser le mot de contour en trouvant de manière récursive les plus longues paires de facteurs homologues et en cassant ainsi le mot de contour du polyomino en plus petits morceaux jusqu’à ce qu’une factorisation soit trouvée.
Il reste de nombreux problèmes à résoudre dans les domaines étudiés comme la notion de congruence et de division euclidienne de polyominos mais nous sommes convaincus que les outils présents dans ce mémoire favoriseront la résolution de certains d’entre eux.
Les travaux presentés dans ce mémoire ont fait l’objet d’un article à la conférence LATA 2014.
Le lecteur soucieux de découvrir et d’exécuter nos algorithmes de factorisation, nos générateurs de polyominos et le banc d’essai, est invité à regarder les codes source à la disposition du public hébergé sur Bitbucket 1, qui ne nécessite qu’une installation de la plateforme Java SE (Edition Standard).
|
Table des matières
REMERCIEMENTS
Table des matières
Table des figures
Liste des tableaux
Résumé
1 Introduction
1.1 Revue de littérature
1.2 Problématique
2 Définitions et notations
2.1 Mots
2.2 Polyominos
2.3 Mot de contour
2.4 Virages et enroulements
2.5 Représentation des polyominos à partir d’une image binaire
3 Arithmétique des polyominos
3.1 Polyominos parallélogrammes
3.2 Polyominos premiers et composés
3.3 Théorème de décomposition en facteurs premiers
3.4 Algorithmes de factorisation
3.5 Discussion
4 Exploration informatique
4.1 Méthologie
4.2 Banc d’essai
4.3 Résultats empiriques
4.4 Analyse des résultats empiriques
4.5 Conclusion
Conclusion
Bibliographie
Télécharger le rapport complet
