Etant donné trois entiers k, s et a, nous prouvons dans le premier chapitre qu'il existe un graphe k-régulier fini (resp. un graphe k-régulier connexe fini) dont le groupe d'automorphismes a exactement s orbites sur l'ensemble des sommets et a orbites sur l'ensemble des arêtes si et seulement si (s,a)=(1,0) si k=0, (s,a)=(1,1) si k=1, s=a>0 si k=2, 0< s <= 2a <= 2ks si k>2. (resp. (s,a)=(1,0) si k=0, (s,a)=(1,1) si k=1 ou 2, s-1<=a<=(k-1)s+1 et s,a>0 si k>2.) Nous étudions les polyèdres convexes de R³ dans le second chapitre. Pour tout polyèdre convexe P, nous notons Isom(P) l'ensemble des isométries de R³ laissant P invariant. Si G est un sous-groupe de Isom(P), le f_G-vecteur de P est le triple d'entiers (s,a,f) tel que G ait exactement s orbites sur l'ensemble sommets de P, a orbites sur l'ensemble des arêtes de P et f orbites sur l'ensemble des faces de P. Remarquons que (s,a,f) est le f_{id}-vecteur (appelé f-vecteur dans la littérature) d'un polyèdre si ce dernier possède exactement s sommets, a arêtes et f faces. Nous généralisons un théorème de Steinitz décrivant tous les f-vecteurs possibles. Pour tout groupe fini G d'isométries de R³, nous déterminons l'ensemble des triples (s,a,f) pour lesquels il existe un polyèdre convexe ayant (s,a,f) comme f_G-vecteur. Ces résultats nous permettent de caractériser les triples (s,a,f) pour lesquels il existe un polyèdre convexe tel que Isom(P) a s orbites sur l'ensemble des sommets, a orbites sur l'ensemble des arêtes et f orbites sur l'ensemble des faces. La structure d'incidence I(P) associée à un polyèdre P consiste en la donnée de l'ensemble des sommets de P, l'ensemble des arêtes de P, l'ensemble des faces de P et de l'inclusion entre ces différents éléments (la notion de distance ne se trouve pas dans I(P)). Nous déterminons également l'ensemble des triples d'entiers (s,a,f) pour lesquels il existe une structure d'incidence I(P) associée à un polyèdre P dont le groupe d'automorphismes a exactement s orbites de sommets, a orbites d'arêtes et f orbites de sommets.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

On présente un algorithme, pour retrouver la représentation surfacique d'un polyèdre convexe a partir de la donnée de son image gaussienne généralisée, notée e.g.i. Cet algorithme base sur un théorème de Minkowski, est du a J. J. Little (1983). Cette reconstruction d'un polyèdre a partir de son e.g.i., se fera via la resolution d'un probleme d'optimisation convexe. Après avoir défini l'e.g.i. Comme mode de représentation d'objets convexes, ainsi que les propriétés qu'elle possède, nous détaillons la methode de reconstruction. Des améliorations sont introduites, allant dans le sens de rendre l'algorithme suffisamment efficace. Le schéma général de l'algorithme est présenté, avec des commentaires sur le traitement numérique. Enfin, quelques exemples sont fournis, pour illustrer la methode

Étant donnes un graphe g=(v,e) et une fonction cout définie sur les arêtes de ce graphe, cette thèse étudie le problème du voyageur de commerce relaxe qui consiste a trouver une tournée sur G, de longueur minimum, telle que chaque sommet soit visite au moins au fois

Définitions et résultats fondamentaux sur les polyèdres convexes. Opérations sur les polyèdres convexes. contextes abstraits. Système d'équations en avant associe à un programme. Analyse approchée en avant des programmes. Analyse approchée en arrière des programmes. Primitives évoluées. Application de la méthode. Note sur l'implémentation et les performances. comparaison avec des travaux voisins.

En analyse de tolérances géométriques, une approche consiste à manipuler des polyèdres de R' issus d’ensembles de contraintes linéaires. La position relative entre deux surfaces quelconques d'un mécanisme est déterminée par des opérations (somme de Minkowski et intersection) sur ces polyèdres. Ces polyèdres ne sont pas bornés selon les déplacements illimités dus aux degrés d’invariance des surfaces et aux degrés de liberté des liaisons.Dans une première partie sont introduits des demi-espaces "bouchons" destinés à limiter ces déplacements afin de transformer les polyèdres en polytopes. Cette méthode implique de maîtriser l’influence des demi-espaces bouchons sur la topologie des polytopes résultants. Ceci est primordial pour garantir la traçabilité de ces demi-espaces dans le processus d’analyse de tolérances.Une seconde partie dresse un inventaire des problématiques de mise en oeuvre numérique des polytopes. L’une d’entre elles repose sur le choix d’une configuration de calcul (point et base d’expression, coefficients d’homogénéisation) pour définir un polytope. Après avoir montré que le changement de configuration de calcul est une transformation affine, plusieurs stratégies de simulations sont déclinées afin d’appréhender les problèmes de précision numérique et de temps de calculs. / In geometric tolerancing analysis area, a classical approach consists in handling polyhedrons coming from sets of linear constraints. The relative position between any two surfaces of a mechanism is determined by operations (Minkowski sum and intersection) on these polyhedrons. The polyhedrons are generally unbounded due to the inclusion of degrees of invariance for surfaces and degrees of freedom for joints defining theoretically unlimited displacements.In a first part are introduced the cap half-spaces to limit these displacements in order to transform the polyhedron into polytopes. This method requires controlling the influence of these additional half-spaces on the topology of calculated polytopes. This is necessary to ensure the traceability of these half-spaces through the tolerancing analysis process.A second part provides an inventory of the issues related to the numerical implementation of polytopes. One of them depends on the choice of a computation configuration (expression point and base, homogenization coefficients) to define a polytope. After proving that the modification of a computation configuration is an affine transformation, several simulation strategies are listed in order to understand the problems of numerical precision and computation time.

Étude de certains problèmes d'optimisation combinatoire. Le premier concerne un problème de régulation de trafic pour lequel on donne une formulation mathématique et on propose une méthode permettant de le résoudre. Le deuxième problème traité est un des problèmes de la physique statistique qui relève de la combinatoire et de l'optimisation, celui du fondamental d'un verre de spins (modèle d'Ising). Enfin on étudie, deux autres problèmes d'optimisation combinatoire: l'absorbant et le Ki-recouvrement de poids minimum

On étudie dans le corps des séries formelles de Puiseux, la résolution des équations algébriques de 2 et 3 variables. Le développement des solutions dépend de la nature du point au voisinage duquel on développe la fonction algébrique associée à cette équation algébrique. Pour les points réguliers on développe un algorithme basé sur la méthode itérative de Newton: xk+1=xk−f(xk)/f'(xk). Pour les points singuliers une méthode constructive appelée polygone de Newton permet de déterminer de proche en proche les approximants des solutions. On donne une application de la méthode du polygone de Newton à la détermination des polynômes facteurs déterminants d'un opérateur différentiel à singularité irrégulière à l'origine

.

Un germe équidimensionnel réduit d'espace analytique est dit quasi-odinaire s'il admet une projection finie sur un espace lisse, dont le lieu discriminant est un diviseur à croisements normaux. Le thème de ce travail est la généralisation aux germes quasi-ordinaires de liens connus entre divers invariants des germes de courbes planes. Dans le premier chapitre nous présentons une vision d'ensemble du concept de racine approchée d'un polynôme. Nous insistons sur les applications à l'étude des germes de courbes planes, en montrant que pour la plupart de ces applications, le concept plus général de semi-racine est suffisant. Au début du deuxième chapitre nous utilisons la géométrie torique pour construire une normalisation des germes quasi-ordinaires. Pour les germes irréductibles, de dimension 2 et dimension de plongement 3, nous donnons un algorithme explicite de normalisation, puis nous leur associons de manière intrinsèque un semi-groupe. Nous en déduisons une nouvelle preuve de l'invariance des exposants caractéristiques normalisés. Le concept de semi-racine est essentiel dans notre démarche. Dans le troisième chapitre nous donnons un théorème de factorisation pour la dérivée d'un polynôme quasi-ordinaire, lorsque cette dérivée est elle-même quasi-ordinaire. Ceci généralise un théorème connu sur la structure des courbes polaires des germes de courbes planes. Pour le formuler, nous introduisons l'arbre d'Eggers-Wall, qui permet de factoriser les germes comparables en fonction de leur contact avec le germe étudié. Dans le dernier chapitre nous interprétons topologiquement l'arbre d'Eggers-Wall et la factorisation des germes comparables, dans le cas des germes de courbes planes. Pour cela, nous prouvons un théorème général sur la localisation à isotopie près des noeuds isolables et sédentaires dans les variétés compactes, orientables et irréductibles de dimension 3, dont le bord est formé uniquement de tores.