Thèses sur le sujet « Calculs garantis »

Cette thèse se situe dans le contexte des systèmes (min,+)-linéaires incertains, contenus dans des intervalles dont seules les bornes sont connues. Dans un premier temps, puisque les calculs exacts - somme, inf-convolution, étoile de Kleene/clôture sous-additive - sont souvent coûteux en espace mémoire et en temps de calculs, des calculs approchés sont proposés à travers des fonctions d'inclusion. Les résultats obtenus sont des intervalles particuliers appelés conteneurs. La borne supérieure d'un conteneur est l'élément le plus grand de la classe d'équivalence du système approché selon la transformée de Legendre-Fenchel. La borne inférieure représente un minorant de cette classe d'équivalence et ainsi du système exact. Les caractéristiques de convexité de ces bornes permettent d'obtenir des algorithmes de calculs de complexité linéaire et quasi-linéaire. Dans un second temps, la commande des systèmes (min,+)-linéaires incertains est étudiée. Ces incertitudes peuvent apparaître suite aux calculs effectués sur les conteneurs proposés ci-dessus, mais également lorsque des paramètres incertains ou variables sont présents lors des modélisations. Des structures de contrôles existantes (précompensateur, retour de sortie) sont appliquées à ces systèmes incertains et les problèmes suivants sont ainsi traités : problème du Window Flow Control, réduction de l'incertitude en sortie du système contrôlé par un précompensateur, calcul d'un précompensateur neutre ralentissant les entrées sans dégrader la dynamique du système seul.

Pour développer les activités marines humaines, des groupes de robots sous-marins peuvent automatiser certaines tâches. Ces robots étant difficiles à localiser en raison de contraintes sous-marines, ils doivent se déplacer en formation pour être fiables. Bien que plusieurs contrôleurs théoriques aient été proposés pour faire face à ces contraintes, ils doivent encore s’adapter à des contraintes plus complexes et être testés sur des systèmes réels. Comme pour tout système autonome, la stabilité de la formation doit être vérifiée par une preuve mathématique. Cependant, la complexité de ces systèmes non linéaires rend la méthode de Lyapunov conventionnelle difficile à utiliser. Ainsi, l’objectif principal de cette thèse est de développer des méthodes numériques garanties, basées sur l’arithmétique des intervalles, qui peuvent assister la preuve de stabilité. Basée sur la propagation garantie ellipsoïdale, une première méthode est conçue pour les systèmes à temps discret afin de calculer un domaine d’attraction ellipsoïdal. Cette méthode est ensuite étendue aux systèmes à temps continu, puis aux systèmes hybrides synchrones, qui sont des modélisations plus réalistes. En outre, la propagation ellipsoïdale est étendue pour prendre en compte les applications singulières et les ellipsoïdes dégénérées. Enfin, des test de formation en situation réelle viennent illustrer la stabilité
In the development of human marine activity, groups of underwater robots can automate certain tasks. Since these robots are difficult to localise because of the underwater constrains, they must move in formation to be reliable. While various theoretical controllers have been proposed to challenge these constrains, they still need to consider more complex constrains and to be tested on real systems. As for every autonomous system, the stability of the formation must be verified by a mathematical proof. However, the complexity of these nonlinear systems makes conventional Lyapunov method difficult to use. Thus, this thesis’ main objective is to develop guaranteed numerical methods, based on interval arithmetic, that can assist the stability proof. Based on ellipsoidal guaranteed propagation, a first method is designed for discrete time systems to compute an ellipsoidal domain of attraction. This method is then extended to continuous-time systems and then to synchronous hybrid systems which are more realistic modellings. In addition, the ellipsoidal propagation is extended to consider singular mappings and degenerate ellipsoids. Finally, some real world underwater formation control was achieved to illustrate the stability

Nous nous proposons dans ce travail de développer des modèles mathématiques pour étudier l'opportunité apportée par la période de garantie étendue pour les deux cas unidimensionnel et bidimensionnel aussi bien pour le consommateur que pour le fabricant du produit pour différentes situations. Nous exprimerons pour cela le coût total moyen encouru le long du cycle de vie du produit, ceci pour les deux points de vue : celui du consommateur et celui du fabriquant. Nous considèrerons également différentes options concernant les politiques de maintenance à adopter (faire de la maintenance préventive ou non) pour le produit durant les périodes suivantes : la période de garantie de base, la période de garantie étendue et la période post-garantie se terminant à la fin du cycle de vie du produit. Nous exprimerons pour cela le coût total moyen encouru le long du cycle de vie du produit pour les points de vue consommateur et fabricant. Pour tester les performances du modèle analytique, des calculs numériques ont été effectués afin de déterminer la zone de compromis pour la garantie étendue
In this study mathematical models are developed to study the opportunity provided by the extended warranty period for both two-dimensional and one-dimensional case for the consumer and the manufacturer of the product for different situations. We will express the total average cost incurred along the life cycle of the product, this to the two points of view: the consumer and the manufacturer. Also we will consider various options regarding maintenance policies to adopt (performing preventive maintenance or not) for the product during the following periods: the basic warranty period, the extended warranty period and post-warranty at the end of the life cycle of the product. We will express the total average cost incurred along the life cycle of the product for the consumer and the manufacturer. To test the performance of the analytical model, numerical calculations were performed to determine the area of compromise for the extended warranty

Nous nous proposons dans ce travail de développer des modèles mathématiques pour étudier l'opportunité apportée par la période de garantie étendue pour les deux cas unidimensionnel et bidimensionnel aussi bien pour le consommateur que pour le fabricant du produit pour différentes situations. Nous exprimerons pour cela le coût total moyen encouru le long du cycle de vie du produit, ceci pour les deux points de vue : celui du consommateur et celui du fabriquant. Nous considèrerons également différentes options concernant les politiques de maintenance à adopter (faire de la maintenance préventive ou non) pour le produit durant les périodes suivantes : la période de garantie de base, la période de garantie étendue et la période post-garantie se terminant à la fin du cycle de vie du produit. Nous exprimerons pour cela le coût total moyen encouru le long du cycle de vie du produit pour les points de vue consommateur et fabricant. Pour tester les performances du modèle analytique, des calculs numériques ont été effectués afin de déterminer la zone de compromis pour la garantie étendue
In this study mathematical models are developed to study the opportunity provided by the extended warranty period for both two-dimensional and one-dimensional case for the consumer and the manufacturer of the product for different situations. We will express the total average cost incurred along the life cycle of the product, this to the two points of view: the consumer and the manufacturer. Also we will consider various options regarding maintenance policies to adopt (performing preventive maintenance or not) for the product during the following periods: the basic warranty period, the extended warranty period and post-warranty at the end of the life cycle of the product. We will express the total average cost incurred along the life cycle of the product for the consumer and the manufacturer. To test the performance of the analytical model, numerical calculations were performed to determine the area of compromise for the extended warranty

Dans cette thèse, nous introduisons le concept d'e-échantillon lâche, qui peut être vu comme une version faible de la notion d'e-échantillon. L'avantage majeur des e-échantillons lâches sur les e-échantillons classiques est qu'ils sont plus faciles à vérifier et à construire. Plus précisément, vérifier si un ensemble fini de points est un e-échantillon lâche revient à regarder si les rayons d'un nombre fini de boules sont suffisamment petits. Quand la surface S est lisse, nous montrons que les e-échantillons sont des e-échantillons lâches et réciproquement, à condition que e soit suffisamment petit. Il s'ensuit que les e-échantillons lâches offrent les mêmes garanties opologiques et géométriques que les e-échantillons. Nous étendons ensuite nos résultats au cas où la surface échantillonnée est non lisse en introduisant une nouvelle grandeur, appelée rayon Lipschitzien, qui joue un rôle similaire à lfs dans le cas lisse, mais qui s'avère être bien défini et positif sur une plus large classe d'objets. Plus précisément, il caractérise la classe des surfaces Lipschitziennes, qui inclut entre autres toutes les surfaces lisses par morceaux pour lesquelles la variation des normales aux abords des points singuliers n'est pas trop forte. Notre résultat principal est que, si S est une surface Lipschitzienne et E un ensemble fini de points de S tel que tout point de S est à distance de E au plus une fraction du rayon Lipschitzien de S, alors nous obtenons le même type de garanties que dans le cas lisse, à savoir : la triangulation de Delaunay de E restreinte à S est une variété isotope à S et à distance de Hausdorff O(e) de S, à condition que ses facettes ne soient pas trop aplaties. Nous étendons également ce résultat aux échantillons lâches. Enfin, nous donnons des bornes optimales sur la taille de ces échantillons. Afin de montrer l'intérêt pratique des échantillons lâches, nous présentons ensuite un algorithme très simple capable de construire des maillages certifiés de surfaces. Etant donné une surface S compacte, Lipschitzienne et sans bord, et un paramètre positif e, l'algorithme génère un e-échantillon lâche E de S de taille optimale, ainsi qu'un maillage triangulaire extrait de la triangulation de Delaunay de E. Grâce à nos résultats théoriques, nous pouvons garantir que ce maillage triangulaire est une bonne approximation de S, tant sur le plan topologique que géométrique, et ce sous des hypothèses raisonnables sur le paramètre d'entrée e. Un aspect remarquable de l'algorithme est que S n'a besoin d'être connue qu'à travers un oracle capable de détecter les points d'intersection de n'importe quel segment avec la surface. Ceci rend l'algorithme assez générique pour être utilisé dans de nombreux contextes pratiques et sur une large gamme de surfaces. Nous illustrons cette généricité à travers une série d'applications : maillage de surfaces implicites, remaillage de polyèdres, ondage de surfaces inconnues, maillage de volumes.

De nombreuses applications de calcul haute performance requièrent une part importante de ressources. L'utilisation pour leur exécution de support de type cluster ou grille est alors intéressante. Cette thèse vise l'étude et la mise en place d'applications parallèles et séquentielles sur des grappes d'ordinateurs en assurant une gestion fine des ressources afin de définir une qualité de service prédéfinie. Elle aborde la modélisation du support d'exécution, l'expression des besoins des applications et enfin le placement. Deux approches sont proposées : un mode déterministe où tout ce qui s'exécute sur la machine est supposé contrôlé et un mode stochastique où une part de la charge des machines est inconnue. Toute application appartient à une des quatre classes de services définies ce qui détermine le niveau de qualité de service demandé. Des algorithmes de placement sont proposés sur un support de type cluster avec garantie de la qualité de service. Ils sont basés sur des simulations événementielles et des équations différentielles déduites de modèles markoviens. Une extension de l'algorithme au niveau grille est présentée. Les applications sont modélisées par un graphe de tâches communicantes. Les algorithmes ont été validés par simulation et sont intégrés dans un gestionnaire de ressources (AROMA scAlable Resources Manager and wAtcher). Un modèle économique simple est proposé permettant la facturation des clients
Many high performance applications require lots of resources. Environment like clusters or grid is interesting for their execution. This thesis studies parallel or sequential applications on clusters with precise management of resources in order to define a level of quality of service. It deals with execution support model, applications needs expression and scheduling. Two approachs are proposed : one in a deterministic mode where every application running on a host is known and controled and the other one in a stochastic mode where some part of the load of the host is unknown. Every application belongs to one of the four classes of quality of service defined which determines the level of quality of service requested. Scheduling algorithms are proposed on clusters which guarantee quality of service. They are based on events simulation and differential equations deducted from markovian models. An extension of the algorithm on the grid level is presented. Applications are represented by a graph of communicating tasks. Algorithms are validated by simulation and are integrated in a resources manager (AROMA : scAlable Resources Manager and wAtcher). A model to invoice a client for the used resources is proposed

L'intérêt du codage réseau (network coding) pour améliorer le débit ou optimiser l'utilisation de la capacité du réseau a été clairement démontré dans différents contextes. Certains travaux ont notamment montré que le codage réseau permet de diminuer le délai (maximal et moyen) de transmission de bout-en-bout d'un paquet. Ceci est dû au fait que le traitement simultané de plusieurs paquets dans un noeud de codage permet de réduire le temps passé par les paquets dans les files d'attente par rapport au routage classique. Dans cette thèse, nous considérons l'application du codage réseau dans le contexte des réseaux proposant des garanties de qualité de service (QoS). Notre principale contribution est la proposition de trois stratégies de codage réseau assurant un niveau de QoS garantie exprimé en termes de délai de bout-en-bout. La première stratégie, appelée "stratégie orientée réseau" est une stratégie de codage aléatoire, en termes de dates d'arrivée des paquets, permettant de réduire au maximum le temps passé par les paquets dans les files d'attente des routeurs. Le point faible de cette approche, comme toute approche aléatoire, est qu'elle n'est pas totalement fiable. Les deux autres stratégies proposées implémentent une stratégie fiable en utilisant le concept de code en bloc. La première, appelée "stratégie orientée flux" est basée sur la définition classique du codage réseau alors que la seconde, appelée "stratégie de transfert rapide", permet de réduire les temps d'attente des paquets dans les files d'attente en les transférant sans attendre tous les paquets du même bloc. Les délais maximums engendrés par les différentes stratégies ont été évalués au niveau d'un noeud de codage en utilisant le calcul réseau (network calculus). Les bornes de délais de bout-de-bout ont ensuite été calculées pour plusieurs types de réseaux. Dans la plupart des cas, ces bornes sont meilleures que celles obtenues pour le routage classique. Les stratégies de codage réseau fiables et la stratégie de routage ont été implémentées et évaluées par simulation sur les réseaux étudiés précédemment. Les résultats obtenus montrent que les pires cas de délais de bout-en-bout observés ont les mêmes comportements que les bornes maximales théoriques calculées, validant ainsi les stratégies proposées
The Interest of network coding to improve the throughput or to optimize the use of the network capacity was clearly shown in various contexts. Certain work in particular showed that network coding allows to decrease the end-to-end transmission delay (maximum and average) of a package. This is due to the fact that the processing simultaneous of several packages in a coding node allows to reduce the maximum time spent by the packets in the buffers compared to a classical routing. In this thesis, we consider the application of network coding in the context of the networks providing quality-of-service (QoS) guarantees. Our contributions include the following. First, we propose three network coding strategies ensuring a level of QoS guaranteed expressed in terms of end-in-end delay. The first strategy, called "Network-Oriented Strategy (NOS)", is a random coding strategy. This coding strategy simply consists in combining the inputs packets present in the buffer of a node. It allows minimizing the time spent by the packets in the router's buffers. The weak point of this approach, as any random approach, is that it is not completely reliable. The two other strategies suggested implement a reliable strategy by using the concept of generation. The first, called "Flow-Oriented Strategy (FOS)" is based on the traditional definition of network coding whereas the second, called "Fast Forwarding Strategy (FFS)", allows reducing the packet's buffering delays by transferring them without awaiting all packets of the same generation. The maximum delays generated by different strategies have been evaluated at a coding node level by using network calculus. The end-to-end delay bounds have been then calculated for several types of networks. In most cases, these bounds are better than those obtained for the classical routing. The reliable network coding strategies and the routing strategy have been implemented and evaluated by simulation on networks studied previously. The results obtained show that the worst cases of end-in-end delays observed have the same behaviors as the calculated maximum theoretical bounds, thus validating the suggested strategies

La normativa di Basilea II prescrive che ai fini del calcolo dei requisiti patrimoniali delle banche gli immobili a garanzia delle esposizioni creditizie vengano valutati al valore di mercato. Tuttavia tale valore riflette le condizioni del mercato al momento dell’erogazione del credito e non considera le possibili fluttuazioni dei prezzi che possono verificarsi nel corso del tempo. Nel presente lavoro si analizza la sensitività dei Risk Weighted Assets alle variazioni del valore della garanzia e della probabilità di default e si propone l’utilizzo di una diversa misura per il valore dell’immobile: il Mortgage Lending Value. Tale misura consiste in una stima prudenziale della commerciabilità futura dell’immobile e rappresenta un valore sostenibile nel lungo periodo, indipendentemente dai movimenti di mercato.

De nombreuses applications de calcul haute performance requièrent une part importante de ressources. L'utilisation pour leur exécution de support de type cluster ou grille est alors intéressante. Cette thèse vise l'étude et la mise en place d'applications parallèles et séquentielles sur des grappes d'ordinateurs en assurant une gestion fine des ressources afin de définir une qualité de service prédéfinie. Elle aborde la modélisation du support d'exécution, l'expression des besoins des applications et enfin le placement. Deux approches sont proposées : un mode déterministe où tout ce qui s'exécute sur la machine est supposé contrôlé et un mode stochastique où une part de la charge des machines est inconnue. Toute application appartient à une des quatre classes de services définies ce qui détermine le niveau de qualité de service demandé. Des algorithmes de placement sont proposés sur un support de type cluster avec garantie de la qualité de service. Ils sont basés sur des simulations événementielles et des équations différentielles déduites de modèles markoviens. Une extension de l'algorithme au niveau grille est présentée. Les applications sont modélisées par un graphe de tâches communicantes. Les algorithmes ont été validés par simulation et sont intégrés dans un gestionnaire de ressources (AROMA scAlable Resources Manager and wAtcher). Un modèle économique simple est proposé permettant la facturation des clients.

Ce travail présente une méthode générale fournissant des bornes garanties de l'erreur de discrétisation sur une quantité locale issue d'un calcul éléments finis. Formulée dans un cadre général, la méthode est illustrée sur un cas 2D d'élastoplasticité. Le cadre non-linéaire de cette implémentation a soulevé des problèmes d'un type nouveau au sein de la thématique de vérification. Après avoir défini les problèmes miroir et central, nous proposons des solutions pour les résoudre.La mise en place de l'outil introduit est détaillée. Ainsi, des bornes garanties de l'erreur locale sur une composante de la déformation plastique sont calculées. Une première étude sur des cas académiques est présentée avant de s'intéresser à un cas plus complexe. Enfin une amélioration de la méthode est introduite, permettant l'obtention de bornes plus pertinentes.

L'objectif de cette thèse est d'appliquer, aux problèmes de fusion de données, les techniques de résolution des CSP (Problèmes de Satisfaction de Contraintes) sur des pavés réels avec comme application réelle la localisation dynamique d'un véhicule à l'aide des capteurs odométriques, d'un gyromètre de lacet et d'un GPS différentiel.
Après avoir mené cette étude et tiré des conclusions, deux contributions sont faites pour améliorer les techniques de satisfaction de contraintes utilisées. Dans un premier temps, la notion de "domaine de consistance" est introduite. Les propriétés qui lui sont associées permettent de résoudre de manière formelle des exemples de cycles. Grâce à cet outil, on améliore la précision des pavés obtenus tout en ayant une information précieuse du temps de calcul a priori. Dans un second temps, l'algorithme de propagation connu sous le nom de FALL/CLIMB permettant de résoudre de façon optimale un CSP ayant une représentation graphique sous forme de graphe est généralisé aux CSP vectorisés appelés "VCSP".

L'ordonnancement de paquets est une des clés de la garantie de qualité de service dans les réseaux. On s'intéresse à une technique d'ordonnancement appelée CBQ (Class Based Queueing) dont la particularité est de permettre de partager les ressources d'un lien entre des flux regroupés en classes de trafic hiérarchisées. CBQ présente de nombreux avantages mais n'est pas adaptée à la gestion de flux ayant des contraintes de délai strictes. On étudie les méthodes qui permettent l'analyse des propriétés d'une discipline d'ordonnancement, puis on applique ces méthodes à l'étude de CBQ. Cette étude révèle les principales lacunes de la discipline, auxquelles on remédie en mettant au point une variante de CBQ. Finalement, on obtient une version de CBQ qui permet de garantir une limite de temps stricte. On propose ensuite une adaptation de CBQ pour le domaine non filaire, et plus spécifiquement pour les réseaux IEEE 802. 11e
Packet scheduling is one of the keys to the guarantee of quality of service in networks. We focus on the CBQ (Class Based Queueing) scheduling discipline which enables to share link resources among hierarchicaly organized traffic classes. CBQ has many advantages but is not fitted to deal with strict delay constraints. We review the methods that enable the analysis of a scheduling discipline properties, and we use these methods on CBQ. As this work highlights the main hindering points to deal with real-time traffic, we devise a variant of CBQ better fitted to such needs. We then propose another adaptation of CBQ for IEEE 802. 11e networks

Cette thèse traite de la localisation de véhicule. Plusieurs méthodes sont utilisées pour résoudre ce type de problème. Elles peuvent être classées en deux grandes catégories d’approches : les approches probabilistes et les approches déterministes.Ce travail aborde les approches déterministes et plus précisément l'approche ensembliste basée sur l'analyse par intervalles. Les travaux ont été conduits sur des jeux de données réelles collectées en environnements d'extérieur comprenant des capteurs proprioceptifs et extéroceptifs.Lorsque l'on met en jeu plusieurs capteurs fournissant des informations complémentaires ou redondantes, il est important de fusionner les données afin d'améliorer la pose estimée. L'approche détaillée dans ce document utilise les méthodes intervalles et présente le problème de la localisation sous la forme d'un problème de satisfaction de contraintes.La résolution se fait à l'aide d’un solveur à intervalles. Plusieurs algorithmes ont été comparés. Un constat s'est dégagé : les algorithmes de consistance locale ne corrigent pas l'incertitude sur l’orientation. Cette thèse propose une méthode de localisation utilisable dans des applications temps réel et qui corrige l'incertitude sur le cap du véhicule. Nous avons comparé nos résultats à ceux du filtre de Kalman étendu (méthode probabiliste de référence) et mis en avant un des intérêts de notre méthode : l'assurance d'une consistance de la pose (position et orientation du mobile).Cette thèse propose deux contributions. La première est d'ordre méthodologique. Dans l'état de l'art tous les travaux affirment la nécessité (voire l'obligation) d'une décomposition préalable des contraintes du problème avant l'étape de résolution. Nos travaux permettent de prouver le contraire. La deuxième contribution concerne la réduction du domaine de l'incertitude en orientation en couplant la propagation de contraintes et une approche de bissection
This thesis deals with the vehicle locationand addresses the problem of SLAM (simultaneous localization and mapping). Several methods are used to solve this kind of problem. They can be classified into two broad categories of approaches: probabilistic approach and deterministic approaches. This work addresses the deterministic approaches and more precisely the approach based on interval analysis. The work has been conducted on real data sets collected in outdoor environments with proprioceptive and exteroceptive sensors.When multiple sensors providing complementary or redundant information are put into play, it is important to merge the data to improve the estimated pose. The approach detailed in this document uses the intervals methods and presents the localization problem as a constraint satisfaction problem.The resolution is done using a solver interval. Several solvers were compared. One thing is clear: local consistency algorithms do not address the uncertainty of the orientation. This thesis proposes a method of locating usable in real time applications and corrects the uncertainty in the heading of the vehicle. We compared our results with those of the extended Kalman filter (probabilistic reference method) and highlighted one of the interests of our method: the assurance of consistency of the pose (position and orientation of the mobile).This thesis proposes two contributions. The first is methodological. In the state of the art all works affirm the need (or obligation) to pre-decompose the constraints of the problem before the resolution step. Our work allows to prove otherwise. The second contribution relates to the reduction of the orientation uncertainty by combining constraint propagation and a bisection approach

Ce travail de recherche vise à contribuer au développement de nouveaux outils d'estimation d'erreur globale et locale en ingénierie mécanique. Les estimateurs d'erreur globale étudiés reposent sur le concept d'erreur en relation de comportement à travers des techniques spécifiques de construction de champs admissibles, assurant l'aspect conservatif ou garanti de l'estimation. Une nouvelle méthode de construction de champs admissibles est mise en place et comparée à deux autres méthodes concurrentes, en matière de précision, coût de calcul et facilité d'implémentation dans les codes éléments finis. Une amélioration de cette nouvelle méthode hybride fondée sur une minimisation locale de l'énergie complémentaire est également proposée. Celle-ci conduit à l'introduction et à l'élaboration de critères géométriques et énergétiques judicieux, permettant un choix approprié des régions à sélectionner pour améliorer localement la qualité des champs admissibles. Dans le cadre des estimateurs d'erreur locale basés sur l'utilisation conjointe des outils d'extraction et des estimateurs d'erreur globale, deux nouvelles techniques d'encadrement de l'erreur en quantité d'intérêt sont proposées. Celles-ci sont basées sur le principe de Saint-Venant à travers l'emploi de propriétés spécifiques d'homothétie, afin d'améliorer la précision des bornes d'erreur locale obtenues à partir de la technique d'encadrement classique fondée sur l'inégalité de Cauchy-Schwarz. Les diverses études comparatives sont menées dans le cadre des problèmes d'élasticité linéaire en quasi-statique. Le comportement des différents estimateurs d'erreur est illustré et discuté sur des exemples numériques tirés d'applications industrielles. Les travaux réalisés constituent des éléments de réponse à la problématique de la vérification dans un contexte industriel.

Le travail présenté dans cette thèse concerne d'une part, l'étude qualitative d'ensembles et d'autre part, celui de l'étude de la stabilité d'un système dynamique. Les méthodes numériques proposées combinent le calcul par intervalles et la théorie des graphes.

De nombreux problèmes, comme l'étude de l'espace des configurations d'un robot, se ramènent à une étude qualitative d'ensembles. Ici, la ``taille'' de l'ensemble importe peu, ce qui compte, c'est sa ``topologie''. Les méthodes proposées calculent des invariants topologiques d'ensembles. Les ensembles considérés sont décrits à l'aide d'inégalités $\mathcal{C}^{\infty}$. L'idée maîtresse est de décomposer un ensemble donné en parties contractiles et d'utiliser l'homologie de \v Cech.

La seconde partie de la thèse concerne l'étude de point
asymptotiquement stables des systèmes dynamiques (linéaires ou non). Plus largement, on propose une méthode pour approcher le bassin d'attraction d'un point asymptotiquement stable. Dans un premier temps, on utilise la théorie de Lyapunov et le calcul par intervalle
pour trouver effectivement un voisinage inclus dans le bassin d'attraction d'un point prouvé asymptotiquement stable. Puis, on combine, une fois de plus, la théorie des graphes et les méthodes d'intégration d'équations différentielles ordinaires pour améliorer ce voisinage et ainsi construire un ensemble inclus dans le bassin
d'attraction de ce point.

Nous présentons deux contributions dans le domaine de la programmation parallèle.La première est théorique : nous introduisons l'analyse SIPS, une approche nouvelle pour dénombrer le nombre d'opérations de synchronisation durant l'exécution d'un algorithme parallèle ordonnancé par vol de travail.Basée sur le concept d'horloges logiques, elle nous permet,: d'une part de donner de nouvelles majorations de coût en moyenne; d'autre part de concevoir des programmes parallèles plus efficaces par adaptation dynamique de la granularité.La seconde contribution est pragmatique: nous présentons une parallélisation générique d'algorithmes pour la génération déterministe de nombres pseudo-aléatoires, indépendamment du nombre de processus concurrents lors de l'exécution.Alternative à l'utilisation d'un générateur pseudo-aléatoire séquentiel par processus, nous introduisons une API générique, appelée Par-R qui est conçue et analysée grâce à SIPS.Sa caractéristique principale est d'exploiter un générateur séquentiel qui peut "sauter" directement d'un nombre à un autre situé à une distance arbitraire dans la séquence pseudo-aléatoire.Grâce à l'analyse SIPS, nous montrons qu'en moyenne, lors d'une exécution par vol de travail d'un programme très parallèle (dont la profondeur ou chemin critique est très petite devant le travail ou nombre d'opérations), ces opérations de saut sont rares.Par-R est comparé au générateur pseudo-aléatoire DotMix, écrit pour Cilk Plus, une extension de C/C++ pour la programmation parallèle par vol de travail.Le surcout théorique de Par-R se compare favorablement au surcoput de DotMix, ce qui apparait aussi expériemntalement.De plus, étant générique, Par-R est indépendant du générateur séquentiel sous-jacent
We present two contributions to the field of parallel programming.The first contribution is theoretical: we introduce SIPS analysis, a novel approach to estimate the number of synchronizations performed during the execution of a parallel algorithm.Based on the concept of logical clocks, it allows us: on one hand, to deliver new bounds for the number of synchronizations, in expectation; on the other hand, to design more efficient parallel programs by dynamic adaptation of the granularity.The second contribution is pragmatic: we present an efficient parallelization strategy for pseudorandom number generation, independent of the number of concurrent processes participating in a computation.As an alternative to the use of one sequential generator per process, we introduce a generic API called Par-R, which is designed and analyzed using SIPS.Its main characteristic is the use of a sequential generator that can perform a ``jump-ahead'' directly from one number to another on an arbitrary distance within the pseudorandom sequence.Thanks to SIPS, we show that, in expectation, within an execution scheduled by work stealing of a "very parallel" program (whose depth or critical path is subtle when compared to the work or number of operations), these operations are rare.Par-R is compared with the parallel pseudorandom number generator DotMix, written for the Cilk Plus dynamic multithreading platform.The theoretical overhead of Par-R compares favorably to DotMix's overhead, what is confirmed experimentally, while not requiring a fixed generator underneath

Tout comportement défectueux d’un système temps-réel critique, comme celui utilisé dans le réseau avionique ou le secteur nucléaire, peut mettre en danger des vies. Par conséquent, la vérification et validation de ces systèmes est indispensable avant leurs déploiements. En fait, les autorités de sécurité demandent d’assurer des garanties déterministes. Dans cette thèse, nous nous intéressons à obtenir des garanties temporelles, en particulier nous avons besoin de prouver que le temps de réponse de bout-en-bout de chaque flux présent dans le réseau est borné. Ce sujet a été abordé durant de nombreuses années et plusieurs approches ont été développées. Après une brève comparaison entre les différentes approches existantes, une semble être un bon candidat. Elle s’appelle l’approche par trajectoire; cette méthode utilise les résultats établis par la théorie de l'ordonnancement afin de calculer une limite supérieure. En réalité, la surestimation de la borne calculée peut entrainer la rejection de certification du réseau. Ainsi une première partie du travail consiste à détecter les sources de pessimisme de l’approche adoptée. Dans le cadre d’un ordonnancement FIFO, les termes ajoutant du pessimisme à la borne calculée ont été identifiés. Cependant, comme les autres méthodes, l’approche par trajectoire souffre du problème de passage à l’échelle. En fait, l’approche doit être appliquée sur un réseau composé d’une centaine de commutateur et d’un nombre de flux qui dépasse les milliers. Ainsi, il est important qu’elle soit en mesure d'offrir des résultats dans un délai acceptable. La première étape consiste à identifier, dans le cas d’un ordonnancement FIFO, les termes conduisant à un temps de calcul important. L'analyse montre que la complexité du calcul est due à un processus récursif et itératif. Ensuite, en se basant toujours sur l’approche par trajectoire, nous proposons de calculer une limite supérieure dans un intervalle de temps réduit et sans perte significative de précision. C'est ce qu'on appelle l'approche par trajectoire scalable. Un outil a été développé permettant de comparer les résultats obtenus par l’approche par trajectoire et notre proposition. Après application sur un réseau de taille réduite (composé de 10 commutateurs), les résultats de simulations montrent que la durée totale nécessaire pour calculer les bornes des milles flux a été réduite de plusieurs jours à une dizaine de secondes
In critical real-time systems, any faulty behavior may endanger lives. Hence, system verification and validation is essential before their deployment. In fact, safety authorities ask to ensure deterministic guarantees. In this thesis, we are interested in offering temporal guarantees; in particular we need to prove that the end-to-end response time of every flow present in the network is bounded. This subject has been addressed for many years and several approaches have been developed. After a brief comparison between the existing approaches, the Trajectory Approach sounded like a good candidate due to the tightness of its offered bound. This method uses results established by the scheduling theory to derive an upper bound. The reasons leading to a pessimistic upper bound are investigated. Moreover, since the method must be applied on large networks, it is important to be able to give results in an acceptable time frame. Hence, a study of the method’s scalability was carried out. Analysis shows that the complexity of the computation is due to a recursive and iterative processes. As the number of flows and switches increase, the total runtime required to compute the upper bound of every flow present in the network understudy grows rapidly. While based on the concept of the Trajectory Approach, we propose to compute an upper bound in a reduced time frame and without significant loss in its precision. It is called the Scalable Trajectory Approach. After applying it to a network, simulation results show that the total runtime was reduced from several days to a dozen seconds

Bien que la commande prédictive fasse appel à des paramètres ayant une signification concrète, la valeur de ces derniers impacte fortement les performances obtenues du système à contrôler. Leur réglage n’étant pas trivial, la littérature fait état d’un nombre conséquent de méthodes de réglage. Celles-ci ne garantissent cependant pas des valeurs optimales. L’objectif de cette thèse est de proposer une approche analytique et originale de réglage de ces paramètres. Initialement applicable aux systèmes MIMO linéaires, l’approche proposée a été étendue aux systèmes non linéaires avec ou sans contraintes et pour lesquels il existe un modèle Takagi-Sugeno (T-S). La classe des systemès non linéaires considérés ici est écrite sous la forme quasi-linéaire paramétrique (quasi-LPV). Sous l’hypothese que le système soit commandable et observable, la méthode proposée garantit la stabilité optimale de ce système en boucle fermée. Pour ce faire, elle s’appuie, d’une part, sur une technique d’amélioration du conditionnement de la matrice hessienne et, d’autre part, sur le concept de rang effectif. Elle présente également l’avantage de requérir une charge calculatoire moindre que celle des approches identifiées dans la littérature. L’intérêt de l’approche proposée est montré à travers l’application en simulation à différents systèmes de complexité croissante. Les travaux menés ont permis d’aboutir à une stratégie de commande prédictive auto-adaptative dénommée "ATSMPC" (Adaptive Takagi-Sugeno Model-based Predictive Control)
Even though predictive control uses concrete parameters, the value of these latter has a strong impact on the obtained performances from the system to be controlled. Their tuning is not trivial. That is why the literature reports a number of adjustment methods. However, these ones do not always guarantee optimal values. The goal of this thesis is to propose an analytical and original tuning tuning approach of these parameters. Initially applicable to linear MIMO systems, the proposed approach has been extended to non-linear systems with or without constraints and for which a Takagi-Sugeno (T-S) model exists. The class of nonlinear systems considered here is written in quasi-linear parametric form (quasi-LPV). Assuming that the system is controllable and observable, the proposed method guarantees the optimal stability of this closed-loop system. To do this, it relies, on the one hand, on a conditioning improving technique of the Hessian matrix and, on the other hand, on the concept of effective rank. It also has the advantage of requiring a lower computational load than the approaches identified in the literature. The interest of the proposed approach is shown through the simulation on different systems of increasingcomplexity. The work carried out has led to a self-adaptive predictive control strategy called "ATSMPC" (Adaptive Takagi-Sugeno Model-based Predictive Control)