-
Factoriser des nombres entiers avec des graphes
et autres idées liées.
Laurent Lyaudet 2022
[
.pdf]
Dans cet article, je propose d’aborder le problème de la factorisation des nombres
entiers comme un problème de comptage, puis de factoriser ou plus généralement
d’avoir un modèle de calcul à base de graphes et d’opérations matricielles non
triviales. Enfin, je présente une heuristique de factorisation amusante nommée Fibolous.
Attention : expression libre et style non-académique sur la forme.
Archive :
[
v1.pdf]
,
[
v2.pdf]
,
[
v3.pdf]
-
Diviser n'est pas régner ?.
Laurent Lyaudet 2022
[
.pdf]
En première année d’algorithmie, on découvre des exemples de schémas « Diviser pour régner »
où une bonne division de l’instance du problème algorithmique étudié
fournit aussi un algorithme de résolution efficace.
Dans cet article, je présente un moyen de diviser efficacement tous les graphes de degré borné.
Ce qui amène au fait intéressant que si P ≠ NP, alors « Diviser n’est pas régner. ».
Archive :
[
v1.pdf]
,
[
v2.pdf]
,
[
v3.pdf]
,
[
v4.pdf]
,
[
v4.php]
,
[
v5.pdf]
,
[
v5.php]
,
[
v6.pdf]
,
[
v6.php]
-
First difference principle applied to modular/questionable-width, clique-width, and rank-width of binary structures.
Laurent Lyaudet 2020
[
.pdf]
Dans cet article, nous étudions des largeurs/décompositions de structures binaires variées
à la lumière du principe de première différence.
Nous montrons l'égalité de la largeur modulaire et de la largeur questionnable,
bien que les représentations questionnables soient plus primitives/grossières
que les décompositions modulaires/de clan.
En utilisant le principe de première différence,
nous montrons que les décompositions de clique des structures binaires ont un équivalent séquentiel,
que nous appelons représentation questionnable de clique.
Enfin, nous donnons des remarques sur la vraie validité de la largeur de rang des structures binaires.
Archive :
[
v1.pdf]
,
[
v2.pdf]
,
[
v3.pdf]
,
[
v4.pdf]
,
[
v5.pdf]
-
On level-induced suborders.
Laurent Lyaudet 2020
[
.pdf]
Dans cet article, nous caractérisons les ordres qui sont des sous-ordres induits par niveau,
toutes les fois où ils sont des sous-ordres induits d'un sur-ordre.
Nous caractérisons aussi les ordres qui sont des sous-ordres induits par niveaux consécutifs,
toutes les fois où ils sont des sous-ordres induits par niveau d'un sur-ordre.
Ainsi nous caractérisons les ordres qui sont des sous-ordres induits par niveaux consécutifs,
toutes les fois où ils sont des sous-ordres induits d'un sur-ordre.
-
Erratum to “On Operations and Linear Extensions of Well Partially Ordered Sets”.
Laurent Lyaudet 2019
[
.pdf]
Dans cet article, nous donnons un contre-exemple au lemme 12 de l'article
“On Operations and Linear Extensions of Well Partially Ordered Sets”
par Maciej Malicki et Aleksander Rutkowski (2003).
-
On finite width questionable representations of orders.
Laurent Lyaudet 2019
[
.pdf]
Dans cet article, nous étudions les "représentations questionnables" des ordres (partiels ou totaux),
introduites dans notre article précédent "A class of orders with linear? time sorting algorithm".
(Plus tard, nous considérons des structures relationnelles ou fonctionnelles binaires arbitraires plutôt que des ordres.)
Une "question" est la première différence entre 2 suites (indexées par un ordinal) d'éléments d'ordres/ensembles.
Dans les "représentations questionnables" de largeur finie d'un ordre O,
la comparaison de deux éléments peut être résolue en regardant la "question" qui compare les éléments d'un ordre fini O'.
Un corollaire d'un théorème de Cantor (1895) est que tous les ordres totaux dénombrables ont une
représentation questionnable binaire (de largeur 2).
Nous trouvons de nouvelles classes d'ordres pour lesquelles tester l'isomorphisme de deux ordres
ou compter le nombre d'extensions linéaires peut être fait en temps polynomial.
Nous présentons aussi une généralisation de la largeur questionnable,
appelée largeur arborescente questionnable équilibrée,
et montrons que si une classe de structures binaires a une largeur arborescente ou une largeur de clique bornée, alors elle a une largeur arborescente questionnable équilibrée bornée.
Mais il y a des classes de graphes de largeur arborescente questionnable équilibrée bornée et largeur arborescente ou largeur de clique infinie.
-
A class of orders with linear? time sorting algorithm.
Laurent Lyaudet 2017
[
.pdf]
Dans cet article, nous donnons un sens mathématique précis à "linear? time"
qui correspond au comportement expérimental de l'algorithme.
L'algorithme de tri n'est pas le nôtre, il s'agit d'une variante de radix sort avec counting sort comme sous-routine.
Le vrai résultat de cet article est un résultat d'universalité efficiente de l'ordre lexicographique,
ou plus généralement pour certaines extensions linéaires de l'ordre partiel "Next" : "si les items courants sont égaux, comparer les items suivants".
Nous définissons de nouvelles classes d'ordres : (Finite width) Tree Structured Orders ou ordres arborescents (de largeur finie) en français.
Nous montrons qu'une instance d'un ordre arborescent de largeur finie peut être convertie en temps et espace linéaire en une instance d'ordre lexicographique.
Les constantes impliquées par l'algorithme de "nextification" sont petites (autour de 3 pour les ordres de la vie réelle).
La classe des ordres arborescents de largeur finie contient les ordres finis ({0, 1}, int32, int64, ..., float, double, ...),
ainsi que les ordres construits à partir des ordres finis sur une structure arborescente.
En particulier, les entiers de taille non bornée, les chaînes avec une collation arbitraire
et tous les ordres utilisés pour trier les requêtes SQL sont des ordres arborescents de largeur finie.
-
Distance preserving subtrees in minimum average distance spanning trees.
Laurent Lyaudet, Paulin Melatagia Yonta, Maurice Tchuenté et René Ndoundam
Publié dans Discrete Mathematics, Algorithms and Applications Volume 5 Issue 3 (2013) 1350010.
[
.pdf]
Étant donné un graphe non-orienté G = (V, E) avec n sommets et une longueur positive w(e)
sur chaque arête e ∈ E, nous considérons des arbres couvrants de Distance Moyenne Minimum (DMM, MAD en anglais),
c'est à dire des arbres qui minimisent la somme des longueurs des chemins entre toutes les paires de sommets.
L'un des premiers résultats sur ce problème est celui de Wong qui a montré en 1980 qu'un arbre couvrant
de Plus Courts Chemins (PCC, DP en anglais pour Distance Preserving) enraciné sur un sommet médian de G
est une solution approchée à un facteur 2 près.
D'un autre côté, Dankelmann a fourni en 2000 une classe de graphes où aucun arbre DMM n'est PCC depuis un sommet.
Nous établissons ici une nouvelle relation entre les arbres DMM et PCC.
Nous montrons que dans un arbre DMM de G, chaque sous-arbre T' = (V', E')
composé d'un sommet r et de l'union des branches de r qui sont chacunes de taille
au plus √(n/2w+), où w+ est la longueur maximum d'une arête dans G,
est un arbre PCC depuis r du sous-graphe de G induit par V'.
-
Partitions versus sets : a case of duality. Laurent Lyaudet, Frédéric Mazoit et Stéphan Thomassé
Publié dans European Journal of Combinatorics 31 (2010) 681–687.[
.pdf]
Dans un article récent, Amini et al. ont introduit un cadre de travail général pour prouver des théorèmes de dualité entre
divers types de décompositions arborescentes et leurs objets combinatoires duaux.
Ils unifient toutes les preuves particulières en un théorème de dualité basé sur les fonctions de partition sous-modulaires.
Ce théorème général reste néanmoins un peu technique et surtout reste limité à cette propriété de sous-modularité.
Au lieu de fonctions de partition, nous proposons ici une propriété combinatoire simple sur les ensembles de partitions qui a pour conséquence ces résultats de dualité.
Notre approche est à la fois plus simple et un petit peu plus générale.
Nous montrons aussi que, sous une hypothèse raisonnable, l'existence de cette dualité a pour conséquence la propriété combinatoire mise en évidence.
-
On the expressive power of permanents and perfect matchings of matrices of bounded
pathwidth/cliquewidth. Uffe Flarup et Laurent Lyaudet.
Publié dans le journal Theory of Computing Systems Volume 46, Issue 4 (2010) 761-791.[
.pdf]
Il y a 25 ans, Valiant a introduit un modèle algébrique de calcul afin d'étudier la complexité de l'évaluation de familles de polynômes.
Cette théorie fut introduite avec les classes de complexité VP et VNP qui sont des analogues algébriques des classes P et NP.
Parmi les familles de polynômes qui sont difficiles à évaluer (c.-à-d. VNP-complètes) figurent le permanent et le polynôme hamiltonien.
Dans un article précédent, les auteurs avec P. Koiran ont étudié l'expressivité du permanent et de l'hamiltonien de matrices de largeur arborescente bornée,
ainsi que l'expressivité des couplages parfaits de graphes planaires. Il fût établi que le permanent et l'hamiltonien de matrices de largeur arborescente bornée
sont équivalents aux formules arithmétiques.
De plus, il fût démontré que la somme des poids des couplages parfaits des graphes planaires est équivalente aux circuits (faiblements) asymétriques.
Dans cet article, nous poursuivons les recherches dans la direction décrite ci-dessus et étudions l'expressivité des permanent, hamiltonien et couplages parfaits
des matrices qui sont de largeur linéaire ou de largeur de clique bornée.
En particulier, nous prouvons que ces trois familles de polynômes sur les matrices de largeur linéaire bornée sont équivalentes aux formules arithmétiques.
C'est une amélioration de notre résultat précédent pour les matrices de largeur arborescente bornée.
Enfin, nous démontrons l'appartenance à VP de ces polynômes pour les matrices de largeur de clique bornée.
-
NP-hard and linear variants of hypergraph partitioning. Laurent Lyaudet.
Publié dans le journal Theoretical Computer Science 411(1) (2010) 10–21.[
.pdf]
Un commentaire sur cet article
ici.
Cet article présente une famille infinie de problèmes combinatoires
qui montre des changements de complexité extrêmement brusques entre problèmes
voisins.
Nous définissons le problème Pkl qui est une variante du partitionnement d'hypergraphes seulement exprimé sous forme de contraintes avec les paramètres k et l comme suit :
Étant donnés un hypergraphe à n sommets et k tailles de couleurs t1, ..., tk de somme n,
peut-on colorer les sommets avec k couleurs ayant les tailles spécifiées de telle sorte que
chaque hyperarête intersecte au plus l couleurs ?
Nous montrons que, pour des paramètres l et k fixés, Pkl est :
polynomial quand l = 1 et NP-complet quand l ≠ 1 sur la classe des hypergraphes ;
NP-complet quand l = 1 et linéaire quand l ≠ 1 sur la classe des hypergraphes avec des hyperarêtes disjointes.
Cette inversion de complexité est possible car les hypergraphes avec des hyperarêtes disjointes peuvent être encodés de manière plus compacte,
en l'occurence Θ(m log(n)) au lieu de Θ(mn) bits (n et m sont les nombres de sommets et arêtes de l'hypergraphe).
-
Partitions versus sets : a case of duality. Laurent Lyaudet, Frédéric Mazoit et Stéphan Thomassé. 2008.[
.pdf]
Dans un article récent, Amini et al. ont introduit un cadre de travail général pour prouver des théorèmes de dualité entre
divers types de décompositions arborescentes et leurs objets combinatoires duaux.
Ils unifient toutes les preuves particulières en un théorème de dualité basé sur les fonctions de partition sous-modulaires.
Ce théorème général reste néanmoins un peu technique et surtout reste limité à cette propriété de sous-modularité.
Au lieu de fonctions de partition, nous proposons ici une propriété combinatoire simple sur les ensembles de partitions qui a pour conséquence ces résultats de dualité.
Notre approche est à la fois plus simple et un petit peu plus générale.
Nous montrons aussi que, sous une hypothèse raisonnable, l'existence de cette dualité a pour conséquence la propriété combinatoire mise en évidence.
-
On the expressive power of permanents and perfect matchings of matrices of bounded
pathwidth/cliquewidth. Uffe Flarup, Laurent Lyaudet.
Rapport de recherche du LIP n° RR2008-05, ENS Lyon, 2008.[
.pdf]
Il y a 25 ans, Valiant a introduit un modèle algébrique de calcul afin d'étudier la complexité de l'évaluation de familles de polynômes.
Cette théorie fut introduite avec les classes de complexité VP et VNP qui sont des analogues algébriques des classes P et NP.
Parmi les familles de polynômes qui sont difficiles à évaluer (c.-à-d. VNP-complètes) figurent le permanent et le polynôme hamiltonien.
Dans un article précédent, les auteurs avec P. Koiran ont étudié l'expressivité du permanent et de l'hamiltonien de matrices de largeur arborescente bornée,
ainsi que l'expressivité des couplages parfaits de graphes planaires. Il fût établi que le permanent et l'hamiltonien de matrices de largeur arborescente bornée
sont équivalents aux formules arithmétiques.
De plus, il fût démontré que la somme des poids des couplages parfaits des graphes planaires est équivalente aux circuits (faiblements) asymétriques.
Dans cet article, nous poursuivons les recherches dans la direction décrite ci-dessus et étudions l'expressivité des permanent, hamiltonien et couplages parfaits
des matrices qui sont de largeur linéaire ou de largeur de clique bornée.
En particulier, nous prouvons que ces trois familles de polynômes sur les matrices de largeur linéaire bornée sont équivalentes aux formules arithmétiques.
C'est une amélioration de notre résultat précédent pour les matrices de largeur arborescente bornée.
Enfin, nous démontrons l'appartenance à VP de ces polynômes pour les matrices de largeur de clique bornée.
-
On the Expressive Power of Planar Perfect Matching and Permanents of
Bounded Treewidth Matrices. Uffe Flarup, Pascal Koiran, Laurent Lyaudet.
Rapport de recherche du LIP n° RR2007-20, ENS Lyon, 2007.[
.pdf]
Valiant a introduit, il y a 25 ans, un modèle algébrique de calcul avec les classes de complexité VP et VNP qui peuvent être vues comme des analogues algébriques des classes P et NP.
Les exemples les plus importants de problèmes difficiles (c.-à-d. VNP-complets) dans ce modèle incluent le permanent et le polynôme hamiltonien.
Dans cet article, nous étudions l'expressivité de cas spéciaux simples de ces polynômes.
Nous montrons que le permanent et l'hamiltonien de matrices de largeur arborescente bornée sont équivalents aux formules arithmétiques.
De plus, nous prouvons que les circuits (faiblements) asymétriques sont équivalents à la somme des poids des couplages parfaits des graphes planaires.
-
Threshold effect in algorithmic complexity: NP-hard and linear variants of
hypergraph partitioning. Laurent Lyaudet.
Rapport de recherche du LIP n° RR2005-46, ENS Lyon, 2005.[
.ps]
Cet article présente une famille infinie de problèmes combinatoires
qui montre des changements de complexité extrêmement brusques entre problèmes
voisins.
Nous définissons le problème Pkl qui est une variante du partitionnement d'hypergraphes seulement exprimé sous forme de contraintes avec les paramètres k et l comme suit :
Étant donnés un hypergraphe à n sommets et k tailles de couleurs t1, ..., tk de somme n,
peut-on colorer les sommets avec k couleurs ayant les tailles spécifiées de telle sorte que
chaque hyperarête intersecte au plus l couleurs ?
Nous montrons que, pour des paramètres l et k fixés, Pkl est :
polynomial quand l = 1 et NP-complet quand l ≠ 1 sur la classe des hypergraphes ;
NP-complet quand l = 1 et linéaire quand l ≠ 1 sur la classe des hypergraphes avec des hyperarêtes disjointes.
Cette inversion de complexité est possible car les hypergraphes avec des hyperarêtes disjointes peuvent être encodés de manière plus compacte,
en l'occurence Θ(m log(n)) au lieu de Θ(mn) bits (n et m sont les nombres de sommets et arêtes de l'hypergraphe).