Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Depuis 1960 et le résultat fondateur de Karatsuba, on sait que la complexité de la multiplication (d’entiers ou de polynômes) est sous-quadratique : étant donné un anneau R quelconque, le produit sur R[X] des polynômes a_0 + a_1 X et b_0 + b_1 X, pour tous a_0, a_1, b_0 et b_1 dans R, peut être calculé en seulement trois et non pas quatre multiplications sur R : (a_0 + a_1 X)(b_0 + b_1 X) = m_0 + (m_2 - m_0 - m_1)X + m_1 X^2, avec les trois produits m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). De la même manière, l’algorithme de Strassen permet de multiplier deux matrices 2nx2n en seulement sept produits de matrices nxn. Les deux exemples précédents tombent dans la catégorie des applications bilinéaires : des fonctions de la forme Phi : K^m x K^n -> K^l, pour un corps donné K, linéaires en chacune des deux variables. Parmi les applications bilinéaires les plus classiques, on trouve ainsi la multiplication de polynômes, de matrices, ou encore d’éléments d’extensions algébriques de corps finis. Étant donnée une application bilinéaire Phi, calculer le nombre minimal de multiplications nécessaires au calcul de cette application est un problème NP-difficile. L'objectif de cette thèse est de proposer des algorithmes minimisant ce nombre de multiplications. Deux angles d'attaques ont été suivis. Un premier aspect de cette thèse est l'étude du problème du calcul de la complexité bilinéaire sous l'angle de la reformulation de ce problème en termes de recherche de sous-espaces vectoriels de matrices de rang donné. Ce travail a donné lieu à un algorithme tenant compte de propriétés intrinsèques aux produits considérés tels que les produits matriciels ou polynomiaux sur des corps finis. Cet algorithme a permis de trouver toutes les décompositions possibles, sur F_2, pour le produit de polynômes modulo X^5 et le produit de matrices 3x2 par 2x3. Un autre aspect de ma thèse est celui du développement d’algorithmes asymptotiquement rapides pour la multiplication entière. Une famille particulière d'algorithmes récents ont été proposés suite à un article de Fürer publié en 2007, qui proposait un premier algorithme, reposant sur la transformée de Fourier rapide (FFT) permettant de multiplier des entiers de n bits en O(n log n 2^{O(log^* n)}), où log^* est la fonction logarithme itéré. Dans cette thèse, un algorithme dont la complexité dépend d'une conjecture de théorie des nombres est proposé, reposant sur la FFT et l'utilisation de premiers généralisés de Fermat. Une analyse de complexité permet d'obtenir une estimation en O(n log n 4^{log^* n}) / Since 1960 and the result of Karatsuba, we know that the complexity of the multiplication (of integers or polynomials) is sub-quadratic: given a ring R, the product in R[X] of polynomials a_0 + a_1 X and b_0 + b_1 X, for any a_0, a_1, b_0 and b_1 in R, can be computed with three and not four multiplications over R: (a_0 + a_1X)(b_0 + b_1X) = m_0 + (m_2 - m_0 - m_1)X + m_1X^2, with the three multiplications m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). In the same manner, Strassen's algorithm allows one to multiply two matrices 2nx2n with only seven products of matrices nxn. The two previous examples fall in the category of bilinear maps: these are functions of the form Phi : K^m x K^n -> K^l, given a field K, linear in each variable. Among the most classical bilinear maps, we have the multiplication of polynomials, matrices, or even elements of algebraic extension of finite fields. Given a bilinear map Phi, computing the minimal number of multiplications necessary to the evaluation of this map is a NP-hard problem. The purpose of this thesis is to propose algorithms minimizing this number of multiplications. Two angles of attack have been studied. The first aspect of this thesis is to study the problem of the computation of the bilinear complexity under the angle of the reformulation of this problem in terms of research of matrix subspaces of a given rank. This work led to an algorithm taking into account intrinsic properties of the considered products such as matrix or polynomial products over finite fields. This algorithm allows one to find all the possible decompositions, over F_2, for the product of polynomials modulo X^5 and the product of matrices 3x2 by 2x3. Another aspect of this thesis was the development of fast asymptotic methods for the integer multiplication. There is a particular family of algorithms that has been proposed after an article by Fürer published in 2007. This article proposed a first algorithm, relying on fast Fourier transform (FFT), allowing one to multiply n-bit integers in O(n log n 2^{O(log^* n)}), where log^* is the iterated logarithm function. In this thesis, an algorithm, relying on a number theoretical conjecture, has been proposed, involving the use of FFT and generalized Fermat primes. With a careful complexity analysis of this algorithm, we obtain a complexity in O(nlog n 4^{log^* n})

Réalisation d'un logiciel pour micro-ordinateur, destiné à permettre l'amélioration d'un service de collecte par modification de secteurs

Les travaux de cette thèse concernent la conception et l'optimisation de lignes de transfert reconfigurables. L'objectif principal est de concevoir une ligne d'usinage à moindre coût tout en respectant les contraintes techniques, technologiques et économiques du problème. Le problème d'optimisation correspondant est un problème d'équilibrage de lignes d'usinage sujet à des contraintes spécifiques. Il consiste à affecter les opérations aux stations de travail en minimisant les coûts d'installation. En plus des contraintes habituelles de ce type de problème, à savoir, les contraintes de précédence, d'inclusion et d'exclusion, nous avons dû considérer des contraintes d'accessibilité. De plus, la spécificité principale des lignes reconfigurables par rapport aux lignes de transfert dédiées, vient de la réalisation en série des opérations. Celle-ci rend souvent nécessaire la mise en place de stations équipées de plusieurs centres d'usinage travaillant en parallèle pour obtenir les volumes de production souhaités. Enfin, l'utilisation d'une tête d'usinage mono-broche induit la prise en compte de temps inter-opératoire de déplacements et de changement d'outils qui dépendent de la séquence d'opérations. Dans un premier temps, nous avons proposé une modélisation mathématique du problème à l'aide d'un programme linéaire en nombres mixtes. Nous avons aussi développé des méthodes de calcul de bornes inférieures ainsi qu'une procédure de prétraitement. Cependant, les contraintes additionnelles rendent la résolution du problème d'équilibrage plus difficile que dans le cas des lignes dédiées, et l'approche proposée ne permet généralement pas de résoudre des instances de taille industrielle. Pour répondre à ce besoin, nous avons donc développé plusieurs méthodes de résolution approchées du problème en nous inspirant de métaheuristiques efficaces sur des problèmes d'optimisation combinatoire.

Cette thèse porte sur la modélisation et l'apprentissage automatique des préférences, dans le contexte industriel de l'impression en grand format. En particulier, nous nous intéressons à l'automatisation de la configuration d'impression. De par la palette des comportements possibles, cette fonctionnalité n'est triviale, ni à concevoir, ni à utiliser. Nous proposons une nouvelle approche pour en améliorer les deux aspect complémentaires : évolutivité et utilisabilité. Notre réalisation principale est un système de recommandation adaptatif, basé sur trois contributions originales : une modélisation de la configuration d'impression grand format à partir d'un modèle de préférence, sous la forme de problèmes d'optimisation sous contraintes, un modèle des préférences de l'imprimeur, sous la forme de fonctions d'utilité additive linéaires par morceaux, basée sur une famille d'attributs adaptée, un algorithme d'apprentissage automatique d'ordonnancements à partir de données comparatives. Basé sur l'algorithme rankSVM (noyau linéaire), notre méthode d'apprentissage permet d'adapter la complexité de l'espace de description des données, tout en conservant la linéarité

Ce travail s'attache à décrire l'intérêt de l'analyse d'intervalles en ordonnancement. L'analyse d'intervalles considère les relations d'ordres existantes (algèbre de Allen) entres certains intervalles caractéristiques des tâches à ordonnancer. On montre comment, pour certains problèmes particuliers, elle permet de définir des conditions de dominance ou des conditions suffisantes d'optimalité, caractérisant des ensembles remarquables de solutions. Dans le cas de certains problèmes à une machine réputés difficiles, nous montrons comment de telles conditions peuvent être utiles pour déduire des nouvelles formulations de programmation linéaire en nombres entiers très efficaces. De plus, les conditions étant relativement indépendantes des valeurs numériques du problème, on montre aussi leur intérêt pour la caractérisation d'ensembles flexibles et robustes de solutions. D'autres travaux seront également évoqués dans lesquels la notion d'intervalle est centrale.

Les travaux présentés dans cette thèse sont lies aux problèmes de vérification de l'atteignabilité et de la terminaison de programmes qui manipulent des données entières non-bornées. On décrit une nouvelle méthode de vérification basée sur une technique d'accélération de boucle, qui calcule, de manière exacte, la clôture transitive d'une relation arithmétique. D'abord, on introduit un algorithme d'accélération de boucle qui peut calculer, en quelques secondes, des clôtures transitives pour des relations de l'ordre d'une centaine de variables. Ensuite, on présente une méthode d'analyse de l'atteignabilité, qui manipule des relations entre les variables entières d'un programme, et applique l'accélération pour le calcul des relations entrée-sortie des procédures, de façon modulaire. Une approche alternative pour l'analyse de l'atteignabilité, présentée également dans cette thèse, intègre l'accélération avec l'abstraction par prédicats, afin de traiter le problème de divergence de cette dernière. Ces deux méthodes ont été évaluées de manière pratique, sur un nombre important d'exemples, qui étaient, jusqu'a présent, hors de la portée des outils d'analyse existants. Dernièrement, on a étudié le problème de la terminaison pour certaines classes de boucles de programme, et on a montré la décidabilité pour les relations étudiées. Pour ces classes de relations arithmétiques, on présente un algorithme qui s'exécute en temps au plus polynomial, et qui calcule l'ensemble d'états qui peuvent générer une exécution infinie. Ensuite on a intégré cet algorithme dans une méthode d'analyse de la terminaison pour des programmes qui manipulent des données entières.

Cette thèse est centrée autour de la monogénéité de corps de nombres en situation relative puis à la conjecture de Collatz.\newline Premièrement on détermine l'ensemble de classes des générateurs de l'anneau des entiers des certaines extensions relatives de corps de nombres, en utilisant l'algorithme de Gaál & Phost et le logiciel PARI/GP. La deuxième partie propose différents formulations d'une généralisation de la conjecture de Collatz, aux entiers p-adiques. On étudie ensuite le comportement de suites analogues dans le cadre d'anneaux d'entiers de corps de nombres. / This thesis are centered around the monogeneity of number fields in a relative situation and the Collatz conjecture. Firstly, we determine the set of generator classes of the ring of integers of some relative extensions of number fields, using the Gaál& Phost algorithm and the PARI/GP software. The second part proposes different formulations of a generalization of the Collatz conjecture to p-adic integers. We then study the behavior of similar sequences in the framework of rings of integers of number fields.

Le problème de commande motrice de systèmes exécutant des activités multi-objectifs et fortement contraintes est à résoudre pour permettre l’émergence de comportements performants et robustes ; l’élaboration de stratégies complexes de coordination motrice est critique pour en assurer les performances, faisabilité et sécurité.Bien que les approches de commande prédictive multi-objectifs permettent la définition de stratégies complexes et sous contraintes coordonnant l’activité motrice du système, leur coût de calcul est un inconvénient critique à leur application.Le travail présenté dans ce manuscrit vise à considérer des techniques de commande prédictive multi-objectifs pour des applications pratiques à la robotique humanoïde.Une architecture de commande est alors proposée sous la forme d’un contrôleur multi-objectif à deux niveaux, exploitant les avantages respectifs des formulations prédictive et instantanée.La contribution de ce travail prend la forme de la validation des avantages d’une telle approche dans son développement pour des défis pratiques, en simulation et implémentation temps-réel, sur les robots iCub et TORO ainsi que sur des modèles d’humain.Le coût de calcul du niveau prédictif est contenu par l’introduction de problèmes réduits, permettant la formulation avantageuse de problèmes de commande au travers de programmes en nombres entiers mixtes et de distributions séquentielles et parallèles.Malgré les approximations sur la dynamique du système au niveau prédictif, des comportements complexes émergent, exploitant des stratégies de coordination entre objectifs et contraintes conflictuels pour augmenter les performances et robustesse face à des perturbations. / Rising to the challenge of motor control for systems involved in multi-objective and highly-constrained activities is a requirement to enable the emergence of efficient and robust behaviors; the elaboration of complex motor coordination strategies is critical in ensuring performance, feasibility and safety.Although multi-objective predictive approaches enable the definition of complex and constrained strategies coordinating the motor activity of the system, their computational cost is a critical drawback from practical applications.The work presented in this dissertation aims at considering multi-objective predictive control for feasible and practical applications to humanoid robotics.A control architecture is proposed to this purpose as a multi-objective, two-layered controller exploiting the respective advantages of predictive and instantaneous formulations.The contribution of this work takes the form of the validation of the benefits from such an approach in its development for practical challenges and applications, in simulation and real-time implementation, on the iCub and TORO robots and virtual human models.Computational demand of the predictive level is contained with the introduction of reduced multi-objective predictive problems, enabling computationally-favorable formulations of the control problem using mixed-integer programming and sequential and parallel distributions.Despite the resulting approximations on the dynamics of the system at the predictive level, complex behaviors are emerging, exploiting elaborate coordination strategies between conflicting objectives and constraints to increase performance and robustness against disturbances.

Nous étudions ici deux problèmes diophantiens distincts. Le premier concerne les points entiers sur les courbes modulaires associées au normalisateur de sous-groupe de Cartan non déployé. Le deuxième concerne la recherche de point de multiplication complexe sur les droites. Dans les deux cas la méthode de résolution est algorithmique. On utilise la méthode de Baker sur les formes linéaires en logarithmes ainsi que des méthodes de réduction effectives. En particulier cette méthode permet d’obtenir les points entiers sur la courbe associée au normalisateur de sous-groupe de Cartan non déployé pour les niveaux compris entre 7 et 71. / We study here two diophantine problem. The first one deals with integral point on modular curves associated to normalizer of non-split Cartan subgroup. The second one is about finding singular moduli on straight line. In both cases, we solve theproblem in an algorithmic way. We use Baker’s method on linear form in logarithm and some effective technical of reduction. In particular this method gives integral points on the curve associated to normalizer of non-split Cartan subgroup for level between 7 and 71.