Sur une partition polynômiale des bijections dans {0,1}^N : OPEN1 & OPEN1'
Sur la confluence de certaines opérations sur les noeuds : OPEN2
Sur des généralisations de la conjecture du 2nd voisinage : OPEN3
Sur la complexité d'un problème de chemins dans les graphes dirigés : OPEN4 Résultat de NP-Complétude lié à cette dernière question : RES4
MAITRISES MATH/INFO : cours de calculabilité : "(PDF)"
MAITRISES MATH/INFO : cours de cryptographie : "(PDF)"
LICENCE MATH : cours d'algorithmique et de MUPAD : "(PDF)"
MAITRISES MATH/INFO : sujets d'examens de combinatoire : "(DOC)"
MAITRISE INFO : sujets d'examens d'optimisation combinatoire : "(DOC)"
MAITRISES MATH/INFO : sujets d'examens de cryptographie: "(DOC)"
LICENCE IUP/GMI : sujet d'examens d'optimisation linéaire : "(DOC03)" "(RTF04)" "(CORTF04)"
Indicateur d'avancement des travaux : (*) : débuté (**) : recherche en cours (***): achevé-publié
soutenue le 16 décembre 1994 à Caen.
"Calculs en Combinatoire et Combinatoire des Calculs"
soutenue le 10/11/2005 à l'Université de la Réunion ...PPT
Etude d'une relation sur les tresses définie par Dehornoy et Laver. Représentation des suites d'entiers par des arbres pour définir un bon ordre sur les tresses positives qui coincide avec la relation de départ. Cette approche permet de décrire le bon ordre et de prouver l'unicité d'une relation sur les tresses possédant quelques propriétés algébriques simples. Par ailleurs, cette représentation par des arbres donne une nouvelle forme normale des tresses et un algorithme pour le problème de mots.
Calcul du rang d'une tresse positive dans le bon ordre défini sur les tresses positives à partir d'une représentation par des arbres.
Présentation d'un algorithme efficace pour le probleme de mot de la relation 121=212 et un système de réécriture canonique ainsi que le calcul de la fonction rationnelle de croissance.
On démontre l'unicité de la représentation d'une tresse positive à trois brins terminant par un nombre maximal de sigma_1 et la coïncidence de cette expression avec la forme normale définie par le bon ordre.
Les diagrammes de noeuds sont codés par des mots de Gauss. Le problème est de déterminer quels sont les mots qui correspondent à un diagramme et de les énumérer. Un jeu sur les mots résout ce problème.
Les diagrammes de noeuds sont codés par des mots de Gauss. Un système de règles formelles sur les mots s'applique sur ces mots afin de rechercher sa plus petite représentation dans un bon ordre syntaxique. Cette approche permet pour le moment de factoriser les noeuds et d'obtenir les tables de noeuds premiers dans une limite de 10 croisements.
Formalisation d'une classe de mouvements des entrelacs.
Un algorithme sous-linéaire pour mettre une tresse en une forme positive-négative (retournement) ce qui conduit à une réduction en temps linéaire du problème du mot du groupe de tresses à celui du monoide des tresses positives. Comme corollaire, une algorithme linéaire pour le problème du mot du groupe B_3.
Une généralisation des coloriages d'entrelacs de Joyce.
Des mouvements monotones pour les noeuds et les entrelacs.
Réductions Linéaires des problèmes de mots et de conjugaisons des groupes de tresses vers les monoides de tresses positives positivement représentées.
Preuve constructive de l'existence d'une méthode itérative de calcul de toute application booléenne utilisant uniquement comme espace d'écriture les paramètres d'entrée.
Calcul itératif des fonctions booléennes avec un espace d'écriture minimal et un nombre minimal de fonctions simples utilisées.
Calcul itératif des fonctions booléennes avec un espace d'écriture minimal et un nombre quadratique d'étapes de calculs.
Introduction informelle au travail suivant.
Représentation des programmes par des diagrammes qui sont ensuites normalisés en un seul type d'objets. Puis modélisation des calculs par des fonctions booléennes.
Décomposition effective des calculs d'applications linéaires sur n bits en une séquence de 2n-1 opérations.
Interprétation et Décomposition Séquentielle des Applications Linéaires et des Graphes Dirigés.
Preuve d'indécidabilite de la convergence des itérations de fonctions définies par congruences (du genre Syracuse). Extension a des questions analytiques sur l'existence de solutions non triviales à des équations fonctionnelles.
Version française de l'article précédent plus une fonction congruentielle qui définie la suite infinie des nombres premiers et une autre qui est universelle au sens des machines de Turing.
Algorithme de calcul des vecteurs courts (de norme inférieure à un nombre M donné) dans un réseau dont une base est donnée.
Développement avec Emeric Gioan du travail précédent.
Approche simpliste du fameux problème pour formuler un énoncé d'une conjecture plus forte.
Lien combinatoire entre le nombre de décompositions en sommes (partition) et la somme des diviseurs (primalité).
Seymour conjecture que dans tout graphe orienté antisymétrique, il existe un sommet X dont le nombre D2(X) de sommets à distance 2, est supérieur ou égal au nombre D1(X) de sommets à distance 1. Je montre que si cette conjecture était fausse, alors il existerait un graphe dont tout sommet X vérifierait D1(X)=D2(X)+1 ou +2.
Un algorithme, des preuves dans le cas des tournois et des conjectures pour le problème précédent.
Généralisation de l'opérateur NAND du calcul booléen pour des ensembles finis quelconques basée sur la comparaison, le zéro et le successeur. Applications en arithmétique : primalité, fonctions polynomiales. Extension aux ensembles dénombrables.
Travail précédent plus une généralisation à un opérateur complet pour toute application sur des ensembles finis
Une variante de la notion de noyau correspondant à un schéma de preuve par récurrence. Résultats de NP-Complétude.
On présente un algorithme de décision pour le problème SAT qui consiste à estimer une borne du nombre de modèles d'une formule par des arguments combinatoires reposant sur le principe d'inclusion-exclusion.
On présente un algorithme pour le problème SAT qui est polynomial pour 2-SAT et souvent efficace pour 3-SAT. Le principe consiste a effacer successivement des lettres dans la formule jusqu'à obtenir une formule triviale. La possibilité d'effacer des littéraux est decidée par récurence.
Preuves de NP-Complétude de problèmes de chemins dans les graphes dirigés acycliques et le cas particulier des ordres totaux.
Une variante de 2-SAT où l'on demande des certificats par Modus Ponens de certaines variables. Nous prouvons la NP-Complétude de cette variante.
On présente un outil de preuve de terminaison qui utilise des ordinaux, des applications affines et de la programmation linéaire. Il est explicitement décrit pour le fameux exemple de la fonction d'Ackermann. Ce travail a été présenté dans cti:bottom-up termination inference for logic programs au Workshop WLP 2000 de Berlin.
Présentation sommaire de quelques principes de base du brevet précédent.
_________________________________
Serge BURCKEL
INRIA-LORIA
Equipe CASSIS
Campus Scientifique
BP 239
54506 Vandoeuvre-lès-Nancy Cedex
_________________________________
_________________________________
Serge BURCKEL
Laboratoire ERMIT
Université de la Réunion
15 avenue René Cassin BP 7151
97715 SAINT-DENIS messag cedex 9
_________________________________