Dans cette thèse, nous étudions deux problèmes de théorie des graphes largement étudiés ces trois dernières décennies: les codes correcteurs d'erreur et la domination.<br />Nous étudions d'abord deux généralisations des codes correcteurs d'erreurs : les codes parfaits sur des alphabets mixtes et les codes pondérés de rayon un. Ces problèmes ont beaucoup été étudiés sur la métrique de Hamming.<br />Nous les étudions dans la métrique de Lee, et nous montrons des résultats aussi bien d'existence que d'inexistence.<br />Nous montrons aussi que le rapport de dualité entre la domination et les codes est fort pour la grille carrée lorsque l'on considère des boules sans le centre.<br />Puis, nous étudions la domination dans les produits de graphes. Depuis que Vizing a conjecturé en 1968 que la domination est surmultiplicative pour le produit cartésien de graphes, les relations entre des variantes du nombre de domination d'un produit de graphes et ses facteurs ont attiré beaucoup d'attention. Après avoir donné quelques bornes sur le nombre de domination totale du produit direct de graphes, nous déterminons le nombre de domination de puissance des produits de chemins.<br />Puis, nous montrons une conjecture ``à la Vizing'' pour le nombre de domination totale supérieure du produit cartésien.<br />Ensuite, nous étudions la domination avec une approche structurelle. En continuation de l'étude de Favaron et Henning, nous fournissons plusieurs bornes supérieures sur le nombre de paire-domination des graphes sans étoiles, pour chaque nombre de branches, et des graphes sans P_5. Nous proposons aussi des familles infinies de graphes pour lesquels ces bornes sont atteintes.<br />Enfin, nous comparons la domination totale supérieure et la paire-domination supérieure, deux variantes de la domination qui ont attiré l'attention récemment, et nous donnons des bornes précises pour les arbres.

Texte remanié de : PhD : Cambridge, MIT : 2001. / Bibliogr. p. [337]-347. Index.

La théorie des codes géométriques s'est développée au début des années 80 sur l'impulsion d'un article de V.D. Goppa publié en 1981. Etant donnée une courbe algébrique projective lisse X sur un corps fini, on dispose de deux constructions de codes correcteurs d'erreurs. Une construction dite fonctionnelle qui fait intervenir certaines fonctions rationnelles sur X et une construction différentielle qui fait appel à certaines 1-formes différentielles rationnelles sur X . L'étude de ces codes construits sur des courbes a donné lieu à la publication de plusieurs centaines d'articles. Parallèlement à ces travaux, une généralisation de la construction fonctionnelle à des variétés algébriques de dimension quelconque est proposée par Y. Manin dans un article publié en 1984. On dénombre quelques dizaines de travaux publiés portant sur l'étude de tels codes. Cependant, aucun développement n'a été effectué dans le sens d'une généralisation de la construction différentielle. Dans cette thèse nous proposons une construction différentielle de codes sur des surfaces algébriques. Nous étudions ensuite les propriétés de ces codes et plus particulièrement leurs relations avec les codes fonctionnels. De façon un peu surprenante, on observe l'apparition d'une différence majeure avec le cas des courbes. En effet, si sur une courbe l'orthogonal d'un code fonctionnel est différentiel, ce fait est en général faux sur une surface. Ce résultat motive l'étude des orthogonaux de codes fonctionnels. Des formules pour l'estimation de la distance minimale de tels codes sont données en utilisant des propriétés de systèmes linéaires sur une variété. On montre également que, sous certaines conditions sur la surface, ces codes sont somme de codes différentiels et que des réponses à certains problèmes ouverts de géométrie algébrique "à la Bertini" fourniraient des informations supplémentaires sur les paramètres de ces codes.

Dans la plupart des entreprises de fabrication mécanique, le réglage des machines-outils est une tâche déléguée au régleur qui cherche à garantir les tolérances. Cela a pour conséquence d'augmenter le temps de réglage pour une qualité qui n'est pas au niveau souhaité. Au cours de ces six dernières années, le laboratoire SYMME a élaboré des méthodes de pilotage (Copilot-Pro® et Pilotage inertiel) pour résoudre le problème de réglage des machines-outils. Fondés sur ces deux méthodes, les travaux présentés en font une synthèse et présentent des nouvelles avancées dans le pilotage de commande numériques afin d'obtenir la meilleure qualité possible quelle que soit la complexité de la pièce. L'apport de ce travail est présenté en cinq chapitres. Le premier chapitre présente le contexte général des travaux de recherche et fait un état de l'art des travaux existants, d'une part sur le pilotage et d'autre part sur la conformité. Le pilotage consiste à réduire la variabilité autour de la cible des produits et la conformité consiste à s'assurer que la dispersion d'une caractéristique est contenue dans l'intervalle de tolérance de celle-ci. Le second chapitre revient sur les méthodes de pilotage qui consistent à établir les relations entre les caractéristiques de la pièce et les correcteurs et propose des solutions pour améliorer le calcul de la correction en tenant compte à la fois des tolérances et des nombres de points palpés sur les surfaces de la pièce. Le troisième chapitre présente les stratégies de pilotage et met en évidence les limites des méthodes classiques de détection des situations hors contrôle qui sont la carte de contrôle de Shewhart et la carte T² de Hotelling. Le quatrième chapitre fait une synthèse des méthodologies pour faciliter le déploiement des méthodes dans l'industrie. Le cinquième chapitre présente une application expérimentale du pilotage inertiel et un témoignage de l'utilisation du pilotage matriciel dans une entreprise d'horlogerie. Une conclusion rappelle les principaux apports de ce travail.

Dans la plupart des entreprises de fabrication mécanique, le réglage des machines-outils est une tâche déléguée au régleur qui cherche à garantir les tolérances. Cela a pour conséquence d'augmenter le temps de réglage pour une qualité qui n'est pas au niveau souhaité. Au cours de ces six dernières années, le laboratoire SYMME a élaboré des méthodes de pilotage (Copilot-Pro® et Pilotage inertiel) pour résoudre le problème de réglage des machines-outils. Fondés sur ces deux méthodes, les travaux présentés en font une synthèse et présentent des nouvelles avancées dans le pilotage de commande numériques afin d'obtenir la meilleure qualité possible quelle que soit la complexité de la pièce. L'apport de ce travail est présenté en cinq chapitres. Le premier chapitre présente le contexte général des travaux de recherche et fait un état de l'art des travaux existants, d'une part sur le pilotage et d'autre part sur la conformité. Le pilotage consiste à réduire la variabilité autour de la cible des produits et la conformité consiste à s'assurer que la dispersion d'une caractéristique est contenue dans l'intervalle de tolérance de celle-ci. Le second chapitre revient sur les méthodes de pilotage qui consistent à établir les relations entre les caractéristiques de la pièce et les correcteurs et propose des solutions pour améliorer le calcul de la correction en tenant compte à la fois des tolérances et des nombres de points palpés sur les surfaces de la pièce. Le troisième chapitre présente les stratégies de pilotage et met en évidence les limites des méthodes classiques de détection des situations hors contrôle qui sont la carte de contrôle de Shewhart et la carte T² de Hotelling. Le quatrième chapitre fait une synthèse des méthodologies pour faciliter le déploiement des méthodes dans l'industrie. Le cinquième chapitre présente une application expérimentale du pilotage inertiel et un témoignage de l'utilisation du pilotage matriciel dans une entreprise d'horlogerie. Une conclusion rappelle les principaux apports de ce travail.

Th. doct.--Électronique et communications--Paris--ENST, 1991. / Textes en français et en anglais. Bibliogr. p. 102-108.

En 1978, McEliece introduit un schéma de chiffrement à clé publique issu de la théorie des codes correcteurs d’erreurs. L’idée du schéma de McEliece est d’utiliser un code correcteur dont lastructure est masquée, rendant le décodage de ce code difficile pour toute personne ne connaissant pas cette structure. Le principal défaut de ce schéma est la taille de la clé publique. Dans ce contexte, on se propose d'étudier l'utilisation de codes dont on connaît une représentation compacte, en particulier le cas de codes quais-cyclique ou quasi-dyadique. Les deux familles de codes qui nous intéressent dans cette thèse sont: la famille des codes alternants et celle des sous--codes sur un sous--corps de codes géométriques. En faisant agir un automorphisme $sigma$ sur le support et le multiplier des codes alternants, on saitqu'il est possible de construire des codes alternants quasi-cycliques. On se propose alors d'estimer la sécurité de tels codes à l'aide du textit{code invariant}. Ce sous--code du code public est constitué des mots du code strictement invariant par l'automorphisme $sigma$. On montre ici que la sécurité des codes alternants quasi-cyclique se réduit à la sécurité du code invariant. Cela est aussi valable pour les sous—codes sur un sous--corps de codes géométriques quasi-cycliques. Ce résultat nous permet de proposer une analyse de la sécurité de codes quasi-cycliques construit sur la courbe Hermitienne. En utilisant cette analyse nous proposons des clés compactes pour la schéma de McEliece utilisant des sous-codes sur un sous-corps de codes géométriques construits sur la courbe Hermitienne. Le cas des codes alternants quasi-dyadiques est aussi en partie étudié. En utilisant le code invariant, ainsi que le textit{produit de Schur}et le textit{conducteur} de deux codes, nous avons pu mettre en évidence une attaque sur le schéma de McEliece utilisant des codes alternants quasi-dyadique de degré $2$. Cette attaque s'applique notamment au schéma proposé dans la soumission DAGS, proposé dans le contexte de l'appel du NIST pour la cryptographie post-quantique. / In 1978, McEliece introduce a new public key encryption scheme coming from errors correcting codes theory. The idea is to use an error correcting code whose structure would be hidden, making it impossible to decode a message for anyone who do not know a specific decoding algorithm for the chosen code. The McEliece scheme has some advantages, encryption and decryption are very fast and it is a good candidate for public-key cryptography in the context of quantum computer. The main constraint is that the public key is too large compared to other actual public-key cryptosystems. In this context, we propose to study the using of some quasi-cyclic or quasi-dyadic codes. In this thesis, the two families of interest are: the family of alternant codes and the family of subfield subcode of algebraic geometry codes. We can construct quasi-cyclic alternant codes using an automorphism which acts on the support and the multiplier of the code. In order to estimate the securtiy of these QC codes we study the em{invariant code}. This invariant code is a smaller code derived from the public key. Actually the invariant code is exactly the subcode of code words fixed by the automorphism $sigma$. We show that it is possible to reduce the key-recovery problem on the original quasi-cyclic code to the same problem on the invariant code. This is also true in the case of QC algebraic geometry codes. This result permits us to propose a security analysis of QC codes coming from the Hermitian curve. Moreover, we propose compact key for the McEliece scheme using subfield subcode of AG codes on the Hermitian curve. The case of quasi-dyadic alternant code is also studied. Using the invariant code, with the em{Schur product} and the em{conductor} of two codes, we show weaknesses on the scheme using QD alternant codes with extension degree 2. In the case of the submission DAGS, proposed in the context of NIST competition, an attack exploiting these weakness permits to recover the secret key in few minutes for some proposed parameters.

De nombreux systèmes de communication sans fil ont adopté les codes turbo et les codes convolutifs comme schéma de codes correcteurs d'erreurs vers l'avant (FEC) pour les données et les canaux généraux. Toutefois, certaines versions proposent les codes LDPC pour la correction d'erreurs en raison de la complexité de l'implémentation des décodeurs turbo et le succès de certains codes LDPC irréguliers dans la réalisation des mêmes performances que les codes turbo les dépassent dans certains cas avec une complexité de décodage plus faible. En fait, les nouvelles versions des standards de ces systèmes travaillent côte à côte dans des dispositifs réels avec les plus anciennes qui sont basées sur les codes turbo et les codes convolutifs. En effet, ces deux familles de codes offrent toutes deux d'excellentes performances en termes de taux d'erreur binaire (TEB). Par conséquent, il semble être une bonne idée d'essayer de les relier de manière à améliorer le transfert de technologie et l'hybridation entre les deux méthodes. Ainsi, la conception efficace de décodeurs universels des codes convolutifs, turbo, et LDPC est critique pour l'avenir de l'implémentation des systèmes sans fil. En outre, un décodeur efficace pour les codes turbo et codes convolutifs est obligatoire pour la mise en oeuvre de ces systèmes sans fil. Cela pourrait se faire par l'élaboration d'un algorithme de décodage unifié des codes convolutifs, turbo et LDPC par des simulations et des études analytiques suivies d'une phase de mise en oeuvre. Pour introduire ce décodeur universel, il existe deux approches, soit sur la base de l'algorithme du maximum a posteriori (MAP) ou l'algorithme de propagation de croyance (BP). D'une part, nous étudions une nouvelle approche pour décoder les codes convolutifs et les turbo codes au moyen du décodeur par propagation de croyances (BP) décodeur utilisé pour les codes de parité à faible densité (codes LDPC). En outre, nous introduisons un système de représentation général pour les codes convolutifs par des matrices de contrôle de parité. De plus, les matrices de contrôle de parité des codes turbo sont obtenus en traitant les codes turbo parallèles comme des codes convolutifs concaténés. En effet, l'algorithme BP fournit une méthodologie très efficace pour la conception générale des algorithmes de décodage itératif de faible complexité pour toutes les classes des codes convolutifs ainsi que les turbo-codes. Alors qu'une petite perte de performance est observée lors du décodage de codes turbo avec BP au lieu du MAP, cela est compensé par la complexité moindre de l'algorithme BP et les avantages inhérents à une architecture unifiée de décodage. En outre, ce travail exploite la représentation tail-biting de la matrice de contrôle de parité des codes convolutifs et des codes turbo, ce qui permet le décodage par un algorithme de propagation de croyance unifiée (BP) pour les nouveaux systèmes de communication sans fils tels que le WiMAX (Worldwide Interoperability for Microwave Access) et le LTE (Long Term Evolution). D'autre part, comme solution alternative, une recherche est effectuée sur la façon de produire un décodeur combiné de ces deux familles de codes basé sur l'algorithme MAP. Malheureusement, cette seconde solution nécessite beaucoup de calculs et de capacité de stockage pour sa mise en oeuvre. En outre, ses récurrences en avant et en arrière résultent en de longs délais de décodage. Entre temps, l'algorithme MAP est basé sur le treillis et la structure en treillis du code LDPC est suffisamment compliquée en raison de la matrice de contrôle de parité de grande taille. En conséquence, cette approche peut être difficile à mettre en oeuvre efficacement car elle nécessite beaucoup de calculs et une grande capacité de stockage. Enfin, pour prédire le seuil de convergence des codes turbo, nous avons appliqué la méthode de transfert d'information extrinsèque (EXIT) pour le décodeur correspondant en le traitant comme une concaténation de noeuds de variable et de contrôle.

Nous étudions les mots de poids minimal des codes correcteurs d'erreurs cycliques. Les fonctions symétriques élémentaires et les fonctions puissances des localisateurs de ces mots vérifient les identités de Newton. Dans le premier chapitre celles-ci sont étudiées comme un système d'équations algébriques, dont les solutions sont étudiées par transformation de Fourier. Dans le chapitre II, le lien est fait avec les codes correcteurs d'erreurs cycliques. Sur quelques exemples, il est montré comment étudier les mots de poids minimal sur la donnée d'une base standard de l'idéal engendré par les équations de Newton. Dans le chapitre III, les relations de Newton sont utilisées d'un point de vue théorique, et des résultats sur les mots de poids minimal de certains codes BCH sont obtenus. Ces calculs se placent dans le contexte de la théorie des corps finis. Dans le chapitre IV, un algorithme est développé pour calculer une base normale sur un corps fini. Un point de vue d'algèbre linéaire est choisi, et d'autres problèmes sont abordés (calcul du polynôme minimal, de la forme de Frobenius d'une matrice, lorsque la factorisation du polynôme caractéristique est connue).

Les bases de Gröbner constituent un outil important pour la résolution de systèmes d'équations algébriques, et leur calcul est souvent la partie difficile de la résolution. Cette thèse est consacrée à des analyses de complexité de calculs de bases de Gröbner pour des systèmes surdéterminés (le nombre m d'équations est supérieur au nombre n d'inconnues). Dans le cas générique (”aléatoire”), des outils existent pour analyser la complexité du calcul de base de Gröbner pour un système non surdéterminé (suites régulières, borne de Macaulay). Nous étendons ces résultats au cas surdéterminé, en définissant les suites semi-régulières et le degré de régularité dont nous donnons une analyse asymptotique précise. Par exemple dès que m > n nous gagnons un facteur 2 sur la borne de Macaulay, et un facteur 11,65 quand m = 2n (ces facteurs se répercutent sur l'exposant de la complexité globale). Nous déterminons la complexité de l'algorithme F5 (J-C. Faugère) de calcul de base de Gröbner. Ces résultats sont appliqués en protection de l'information, où les systèmes sont alors considérés modulo 2 : analyse de la complexité des attaques algébriques sur des cryptosystèmes, algorithmes de décodage des codes cycliques. Dans ce dernier cas, une remise en équation complète du problème conduit à utiliser des systèmes de dimension positive dont la résolution est de manière surprenante plus rapide. Nous obtenons ainsi un algorithme de décodage efficace de codes précédemment indécodables, permettant un décodage en liste et applicable à tout code cyclique.