Description de la factorisation sur Z[×] et de ses problèmes, et des différentes formes de remontées série ou parallèle, linéaire ou quadratique. On donne un algorithme nouveau basé sur la décomposition d'une fraction rationnelle

Le théorème d'irréductibilité de Hilbert assure l'existence d'une spécialisation conservant l'irréductibilité d'un polynôme à plusieurs variables et à coefficients rationnels. Des versions effectives ont été données par P. Dèbes (1993) puis par U. Zannier et A. Schinzel (1995). Nous proposons ici diverses tentatives d'améliorer ces résultats effectifs : méthode de Dörge, méthode des congruences inspirée par un article de M. Fried et enfin une utilisation des résultats récents de R. Heath-Brown sur les points entiers d'une courbe algébrique. Cette dernière voie va nous permettre d'améliorer significativement les résultats connus. On finira par une application à la recherche d'un algorithme polynomial pour la factorisation d'un polynôme à deux indéterminées.

L'expérience BaBar a pour objectif de rechercher et de mesurer la violation de $CP$ dans le secteur des mésons $B$ et de contraindre les paramètres du modèle standard. Une des originalités de son dispositif expérimental est le DIRC, le détecteur à effet Cherenkov utilisé pour distinguer les pions des kaons chargés. Une table de correction est mise en place pour corriger ses défauts d'alignement, et permet au DIRC d'atteindre ses performances nominales, c'est à dire une séparation entre kaon et pion de $4\sigma$ pour une quantité de mouvement de $3\gevc$. La recherche de violation de $CP$ dans le canal de désintégration du $B^0$ en $\rho\pi$ devrait permettre de contraindre l'angle $\alpha$ du triangle d'unitarité, un des paramètres du modèle standard. L'objectif de cette analyse est de mesurer les paramètres de violation de $CP$ ainsi que les autres paramètres entrant dans la description de la distribution de probabilité du temps de désintégration. Une méthode de maximum de vraisemblance combine l'information temporelle et des variables discriminantes du bruit de fond du continuum $\e^+\e^-\to q\bar(q)$, dont certaines sont résumées dans un réseau de neurones. L'autre bruit de fond, constitué des autres modes de désintégration du $B$, est pris en compte par des termes correctifs dans l'ajustement. Cette analyse présente à ce jour les meilleures mesures pour ce canal, et semble donner une indication de la violation directe de $CP$. Pour interpréter ces mesures en termes de contraintes sur les paramètres du modèle standard, il est nécessaire d'utiliser un modèle pour prédire la contribution à longue distance des amplitudes de désintégration. Pour un exemple de tel modèle, la ``factorisation QCD'', un test de validation compare les prédictions aux données expérimentales sur les désintégrations non charmées du méson $B$. Ce test semble indiquer un désaccord, qui pourrait être réduit dans l'avenir par une meilleure connaissance expérimentale et théorique des désintégrations du $B$.

Cette thèse présente une méthode permettant d'améliorer un régulateur existant relativement à des spécifications multiples formulées en termes de normes de système L*, L2/H2 et H∞. Trois éléments clés distinguent l'approche proposée. Premièrement, un paramétrage des régulateurs à ordre fixé au moyen d'un facteur stable et observable de la boucle fermée. Deuxièmement, un paramétrage minimal de toutes les paires stables observables fondé sur la théorie des systèmes conservatifs et permettant un ajustement infinitésimal du régulateur à améliorer. Et troisièmement, l'utilisation d'une information de sensibilité pour calculer le sous gradient local du critère d'optimisation et construire une suite minimisante.

Cette thèse propose des améliorations aux problèmes de la multiplication et de la factorisation d'entier. <p> L'algorithme de Schönhage-Strassen pour la multiplication d'entier, publié en 1971, fut le premier à atteindre une complexité de O(n log (n) log(log(n))) pour multiplier deux entiers de n bits, et reste parmi les plus rapides en pratique. Il réduit la multiplication d'entier à celle de polynôme sur un anneau fini, en utilisant la transformée de Fourier rapide pour calculer le produit de convolution. Dans un travail commun avec Gaudry et Zimmermann, nous décrivons une implantation efficace de cet algorithme, basée sur la bibliothèque GNU MP; par rapport aux travaux antérieurs, nous améliorons l'utilisation de la mémoire cache, la sélection des paramètres et la longueur de convolution, ce qui donne un gain d'un facteur 2 environ. <p> Les algorithmes P-1 et P+1 trouvent un facteur p d'un entier composé rapidement si p-1, respectivement p+1, ne contient pas de grand facteur premier. Ces algorithmes comportent deux phases: la première phase calcule une grande puissance g₁ d'un élément g₀ d'un groupe fini défini sur F_p, respectivement F_p^2, la seconde phase cherche une collision entre puissances de g₁, qui est trouvée de manière efficace par évaluation-interpolation de polynômes. Dans un travail avec Peter Lawrence Montgomery, nous proposons une amélioration de la seconde phase de ces algorithmes, avec une construction plus rapide des polynômes requis, et une consommation mémoire optimale, ce qui permet d'augmenter la limite pratique pour le plus grand facteur premier de p-1, resp. p+1, d'un facteur 100 environ par rapport aux implantations antérieures. <p> Le crible algébrique (NFS) est le meilleur algorithme connu pour factoriser des entiers dont les facteurs n'ont aucune propriété permettant de les trouver rapidement. En particulier, le module du système RSA de chiffrement est choisi de telle sorte, et sa factorisation casse le système. De nombreux efforts ont ainsi été consentis pour améliorer NFS, de façon à établir précisément la sécurité de RSA. Nous donnons un bref aperçu de NFS et de son historique. Lors de la phase de crible de NFS, de nombreux petits entiers doivent être factorisés. Nous présentons en détail une implantation de P-1, P+1, et de la méthode ECM basée sur les courbes elliptiques, qui est optimisée pour de tels petits entiers. Finalement, nous montrons comment les paramétres de ces algorithmes peuvent étre choisis finement, en tenant compte de la distribution des facteurs premiers dans les entiers produits par NFS, et de la probabilité de trouver des facteurs premiers d'une taille donnée.

Cette thèse traite de l'estimation de la concentration dans le sang artériel de molécules marquées par un radioélément émettant des positons. Cette concentration est appelée « fonction d'entrée artérielle B+ ». Elle doit être déterminée dans de nombreuses analyses en pharmacocinétique. Actuellement, elle est mesurée à l'aide d'une série de prélèvements artériels, méthode précise mais nécessitant un protocole contraignant. Des complications liées au caractère invasif de la méthode peuvent survenir (hématomes, infections nosocomiales).L'objectif de cette thèse est de s'affranchir de ses prélèvements artériels par l'estimation non-invasive de la fonction d'entrée B+ à l'aide d'un détecteur externe et d'un collimateur. Cela permet la reconstruction des vaisseaux sanguins afin de discriminer le signal artériel du signal contenu dans les autres tissus avoisinants. Les collimateurs utilisés en imagerie médicale ne sont pas adaptés à l'estimation de la fonction d'entrée artérielle B+ car leur sensibilité est très faible. Pour cette thèse, ils sont remplacés par des collimateurs codés, issus de la recherche en astronomie. De nouvelles méthodes pour utiliser des collimateurs à ouverture codée avec des algorithmes statistiques de reconstruction sont présentées.Des techniques de lancer de rayons et une méthode d'accélération de la convergence des reconstructions sont proposées. Une méthode de décomposition spatio-temporelle est également mise au point pour estimer efficacement la fonction d'entrée artérielle à partir d'une série d'acquisitions temporelles.Cette thèse montre qu'il est possible d'améliorer le compromis entre sensibilité et résolution spatiale en tomographie d'émission à l'aide de masques codés et d'algorithmes statistiques de reconstruction ; elle fournit également les outils nécessaires à la réalisation de tellesreconstructions.

La transcription automatique de la musique est l'opération qui consiste, partant du seul contenu audio, à produire une représentation symbolique (par exemple un fichier MIDI) d'un morceau de musique. Si la transcription de musique monodique est aujourd'hui bien maîtrisée, le cas de la musique polyphonique est en revanche un problème largement ouvert. Les décompositions de matrices en valeurs propres et en valeurs singulières sont des techniques classiques d'algèbre linéaire utilisées dans un grand nombre d'applications de traitement du signal. Elles permettent de représenter efficacement les données observées en utilisant un nombre limité d'atomes élémentaires. Contrairement à d'autres techniques de représentations du signal, ces atomes ne sont pas recherchés au sein d'un dictionnaire pré-défini, mais sont extraits des données elles-mêmes. La factorisation en matrices non-négatives (NMF) est une technique analogue d'algèbre linéaire, qui réduit le rang tout en fournissant des atomes à valeurs exclusivement positives, plus facilement interprétables. Elle fournit conjointement un dictionnaire extrait des données et la décomposition de ces mêmes données dans ce dictionnaire. Ce mémoire est consacré à l'étude théorique et expérimentale détaillée de ces méthodes. Il poursuit plusieurs objectifs : l'amélioration des performances des systèmes de transcription qui les utilisent, de la pertinence sémantique des représentations mi-niveau produites, et du contrôle des propriétés théoriques et pratiques des algorithmes existants et originaux mis en œuvre au cours de la thèse.

The hierarchical (<i>H-</i>) matrix format allows storing a variety of dense matrices from certain applications in a special data-sparse way with linear-polylogarithmic complexity. Many operations from linear algebra like matrix-matrix and matrix-vector products, matrix inversion and LU decomposition can be implemented efficiently using the <i>H</i>-matrix format. Due to its importance in solving many problems in numerical linear algebra like least-squares problems, it is also desirable to have an efficient QR decomposition of <i>H</i>-matrices. In the past, two different approaches for this task have been suggested. We will review the resulting methods and suggest a new algorithm to compute the QR decomposition of an <i>H</i>-matrix. Like other <i>H</i>-arithmetic operations the <i>H</i>QR decomposition is of linear-polylogarithmic complexity. We will compare our new algorithm with the older ones by using two series of test examples and discuss benefits and drawbacks of the new approach.

La duplication de code source a de nombreuses origines : copie et adaptation inter-projets ou clonage au sein d'un même projet. Rechercher des correspondances de code copié permet de le factoriser dans un projet ou de mettre en évidence des situations de plagiat. Nous étudions des méthodes statiques de recherche de similarité sur du code ayant potentiellement subi des opérations d'édition telle que l'insertion, la suppression, la transposition ainsi que la factorisation et le développement de fonctions. Des techniques d'identification de similarité génomique sont examinées et adaptées au contexte de la recherche de clones de code source sous forme lexemisée. Après une discussion sur des procédés d'alignement de lexèmes et de recherche par empreintes de n-grams, est présentée une méthode de factorisation fusionnant les graphes d'appels de fonctions de projets au sein d'un graphe unique avec introduction de fonctions synthétiques exprimant les correspondances imbriquées. Elle utilise des structures d'indexation de suffixes pour la détermination de facteurs répétés. Une autre voie d'exploration permettant de manipuler de grandes bases indexées de code par arbre de syntaxe est abordée avec la recherche de sous-arbres similaires par leur hachage et leur indexation selon des profils d'abstraction variables. Des clones exacts de sous-arbres de forte proximité dans leurs arbres d'extraction peuvent alors être consolidés afin d'obtenir des correspondances approchées et étendues. En amont et en aval de la recherche de correspondances, des métriques de similarité sont définies afin de préselectionner les zones d'examen, affiner la recherche ou mieux représenter les résultats

Cette thèse s'articule autour des problèmes d'optimisation à grande échelle, et plus particulièrement autour des méthodes de factorisation matricielle sur des problèmes de grandes tailles. L'objectif des méthodes de factorisation de grandes matrices est d'extraire des variables latentes qui permettent d'expliquer les données dans un espace de dimension réduite. Nous nous sommes intéressés au domaine d'application de la recommandation et plus particulièrement au problème de prédiction de préférences d'utilisateurs. Dans une contribution nous nous sommes intéressés à l'application de méthodes de factorisation dan un environnement de recommandation contextuelle et notamment dans un contexte social. Dans une seconde contribution, nous nous sommes intéressés au problème de sélection de modèle pour la factorisation où l'on cherche à déterminer de façon automatique le rang de la factorisation par estimation de risque.