Дисертації з теми "Paramétrée"
Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Paramétrée.
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-50 дисертацій для дослідження на тему "Paramétrée".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
1
Chamseddine, Najla. "Analyse quantitative paramétrée d'automates temporisés probabilistes." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2009. http://tel.archives-ouvertes.fr/tel-00626062.
Анотація:
Nous considérons une sous classe d'automates temporisés probabilistes où les contraintes temporelles au niveau des gardes et des invariants sont exprimées par des paramètres. Cette sous classe est appelée la classe des automates Temporisés Probabilistes Paramétrés Semi Déterminés (ATPP Semi Déterminés). Cette classe d'automates se définit en particulier par l'attribution d'une unique distribution à chaque état et par des gardes de la forme x<=a où a est un paramètre ou un entier naturel. Nous imposons de plus deux propriétés sur ces automates qui sont celles de non blocage et fortement non zenon. Notre travail vise à calculer le temps moyen maximal de convergence vers un état dit absorbant q_end dans ce type d'automates. L'unique méthode traitant déjà ce type de problème fait appel à la discrétisation du temps et à l'application de techniques de programmation linéaire. Elle est cependant exponentielle car elle dépend du nombre d'horloges et de la plus grande constante à laquelle sont comparées les horloges, lors de la discrétisation. Le graphe résultant peut être de taille exponentielle. Pour tout ATPP Semi Déterminé, on définit un automate totalement déterministe, appelé ATPP Déterminé, en remplaçant toute garde de la forme x<=a par une garde de la forme x=a. Le temps d'attente en chaque état est ainsi fixé par la valuation de l'état initial qui remet toutes les horloges à zéro. Nous démontrons que le temps moyen de convergence vers q_end dans l'ATPP Déterminé est égal au temps moyen maximal de convergence dans l'ATPP Semi Déterminé dont il découle. Pour calculer le temps moyen de convergence vers q_end nous construisons à partir de l'ATPP Déterminé un graphe appelé "graphe des macro-steps" qui contient de façon concise l'information nécessaire au calcul du coût moyen de convergence vers q_end. Ce graphe est de taille polynomiale et se construit en temps polynomial. Le calcul du temps moyen de convergence dans le graphe des macro-steps est solution d'un système linéaire, comme dans le cas des chaînes de Markov avec coûts. On résout ce système linéaire en temps polynomial, ce qui permet d'obtenir finalement le temps moyen maximal de convergence vers q_end dans l'ATPP Semi Déterminé. Nous appliquons enfin cette méthode à certains protocoles de communication, notamment BRP (Bounded Retransmission Protocol) et CSMA/CD (Carrier Sense Multiple Access with Collision Detection).
2
Fradin, Julien. "Graphes complexes en biologie : problèmes, algorithmes et évaluations." Thesis, Nantes, 2018. http://www.theses.fr/2018NANT4093/document.
Анотація:
Afin de mieux comprendre le fonctionnement d'un système biologique, il est nécessaire d'étudier les différentes entités qui le composent. Pour cela, on peut modéliser ces interactions biologiques sous la forme de graphes. Pour certains de ces graphes, les sommets sont colorés afin d'apporter une information supplémentaire sur la couleur qui leur est associée. Dans ce cadre, une problématique courante consiste à y rechercher un sous-graphe d'intérêt appelé motif. Dans la première partie de ce manuscrit, on présente un état de l'art d'un point de vue algorithmique sur le problème GRAPH MOTIF, qui consiste à rechercher des motifs dits fonctionnels dans ce type de graphes. La modélisation de systèmes biologiques sous la forme de graphes peut également être appliquée em spectrométrie de masse. Ainsi, on introduit le problème MAXIMUM COLORFUL ARBORESCENCE (MCA) dans le but de déterminer de novo la formule moléculaire de métabolites inconnus. Dans la deuxième partie de ce manuscrit, on réalise une étude algorithmique du problème MCA. Alors que MCA est algorithmiquement difficile à résoudre même dans des classes de graphes très contraintes, notre modélisation nous permet notamment d'obtenir de nouveaux algorithmes d'approximation dans ces mêmes classes, ainsi que de déterminer une nouvelle classe de graphes dans laquelle MCA se résout en temps polynomial. On montre également des résultats de complexité paramétrée pour ce problème, que l'on compare ensuite à ceux de la littérature sur des instances issues de données biologiquesLn order to better understand how a biological system works, it is necessary to study the interactions between the different entities that compose it. To this aim, these biological interactions can be modelled in the form of graphs. ln some of these graphs, the vertices are colored in order to provide additional information on the entity which is associated with them. ln this context, a common subproblem consists in searching for a subgraph of interest, called a motif, in these graphs. ln the first part of this manuscript, we present a state of the art from an algorithmical point of view of the GRAPH MOTIF problem, which consists in searching for so-called functional motifs in vertex-colored graphs. The modeling of biological systems in graphs form can also be applied in mass spectrometry. Thus, we introduce the MAXIMUM COLORFUL ARBORESCENCE problem (MCA) in order to de novo determine the molecular formula of unknown metabolites. ln the second part of this manuscript, we carry out an algorithmic study of the MCA problem. While MCA is algorithmically difficult to solve even in very constrained graph classes, our modeling allows us to obtain new approximation algorithms in these same classes, as well as to determine a new graph class in which MCA is solved in polynomial time. Parameterized complexity results for this problem are also shown, which are then compared to those in the literature on instances from biological data
3
Dailler, Sylvain. "Extension paramétrée de compilateur certifié pour la programmation parallèle." Thesis, Orléans, 2015. http://www.theses.fr/2015ORLE2071/document.
Анотація:
Les applications informatiques sont de plus en plus présentes dans nos vies. Pour les applications critiques (médecine, transport, . . .), les conséquences d’une erreur informatique ont un coût inacceptable, que ce soit sur le plan humain ou financier. Une des méthodes pour éviter la présence d’erreurs dans les programmes est la vérification déductive. Celle-ci s’applique à des programmes écrits dans des langages de haut-niveau transformés, par des compilateurs, en programmes écrits en langage machine. Les compilateurs doivent être corrects pour ne pas propager d’erreurs au langage machine. Depuis 2005, les processeurs multi-coeurs se sont répandus dans l’ensemble des systèmes informatiques. Ces architectures nécessitent des compilateurs et des preuves de correction adaptées. Notre contribution est l’extension modulaire d’un compilateur vérifié pour un langage parallèle ciblant des architectures parallèles multi-coeurs. Les spécifications des langages (et leurs sémantiques opérationnelles) présents aux divers niveaux du compilateur ainsi que les preuves de la correction du compilateur sont paramétrées par des modules spécifiant des éléments de parallélisme tels qu’un modèle mémoire faible et des notions de synchronisation et d’ordonnancement entre processus légers. Ce travail ouvre la voie à la conception d’un compilateur certifié pour des langages parallèles de haut-niveau tels que les langages à squelettes algorithmiquesNowadays, we are using an increasing number of computer applications. Errors in critical applications (medicine, transport, . . .) may carry serious health or financial issues. Avoiding errors in programs is a challenge and may be achieved by deductive verification. Deductive verification applies to program written in a high-level languages, which are transformed into machine language by compilers. These compilers must be correct to ensure the nonpropagation of errors to machine code. Since 2005, multicore processors have spread in all electronic devices. So, these architectures need adapted compilers and proofs of correctness. Our work is the modular extension of a verified compiler for parallel languages targeting multicore architectures. Specifications of these languages (and their operational semantics) needed at all levels of the compiler and proofs of correctness of this compiler are parameterized by modules specifying elements of parallelism such as a relaxed memory model and notions of synchronization and scheduling between threads. This work is the first step in the conception of a certified compiler for high-level parallel languages such as algorithmic skeletons
4
Bonnet, Edouard. "Résultats Positifs et Négatifs en Approximation et Complexité Paramétrée." Thesis, Paris 9, 2014. http://www.theses.fr/2014PA090040/document.
Анотація:
De nombreux problèmes de la vie réelle sont NP-Difficiles et ne peuvent pas être résolus en temps polynomial. Deux paradigmes notables pour les résoudre quand même sont: l'approximation et la complexité paramétrée. Dans cette thèse, on présente une nouvelle technique appelée "gloutonnerie-Pour-La-Paramétrisation". On l'utilise pour établir ou améliorer la complexité paramétrée de nombreux problèmes et également pour obtenir des algorithmes paramétrés pour des problèmes à cardinalité contrainte sur les graphes bipartis. En vue d'établir des résultats négatifs sur l'approximabilité en temps sous-Exponentiel et en temps paramétré, on introduit différentes méthodes de sparsification d'instances préservant l'approximation. On combine ces "sparsifieurs" à des réductions nouvelles ou déjà connues pour parvenir à nos fins. En guise de digestif, on présente des résultats de complexité de jeux comme le Bridge et HavannahSeveral real-Life problems are NP-Hard and cannot be solved in polynomial time.The two main options to overcome this issue are: approximation and parameterized complexity. In this thesis, we present a new technique called greediness-For-Parameterization and we use it to improve the parameterized complexity of many problems. We also use this notion to obtain parameterized algorithms for some problems in bipartite graphs. Aiming at establishing negative results on the approximability in subexponential time and in parameterized time, we introduce new methods of sparsification that preserves approximation. We combine those "sparsifiers" with known or new reductions to achieve our goal. Finally, we present some hardness results of games such as Bridge and Havannah
5
Chopin, Morgan. "Problèmes d'optimisation avec propagation dans les graphes : complexité paramétrée et approximation." Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00933769.
Анотація:
Dans cette thèse, nous étudions la complexité algorithmique de problèmes d'optimisation impliquant un processus de diffusion dans un graphe. Plus précisément, nous nous intéressons tout d'abord au problème de sélection d'un ensemble cible. Ce problème consiste à trouver le plus petit ensemble de sommets d'un graphe à "activer" au départ tel que tous les autres sommets soient activés après un nombre fini d'étapes de propagation. Si nous modifions ce processus en permettant de "protéger" un sommet à chaque étape, nous obtenons le problème du pompier dont le but est de minimiser le nombre total de sommets activés en protégeant certains sommets. Dans ce travail, nous introduisons et étudions une version généralisée de ce problème dans laquelle plus d'un sommet peut être protégé à chaque étape. Nous proposons plusieurs résultats de complexité pour ces problèmes à la fois du point de vue de l'approximation mais également de la complexité paramétrée selon des paramètres standards ainsi que des paramètres liés à la structure du graphe.
6
Rinaudo, Philippe. "Algorithmique de l'alignement structure-séquence d'ARN : une approche générale et paramétrée." Phd thesis, Université Paris Sud - Paris XI, 2012. http://tel.archives-ouvertes.fr/tel-00847745.
Анотація:
L'alignement de macromolécules biologiques comme les protéines, l'ADN ou encore l'ARN est une problématique biologique et bio-informatique qui a pour but de révéler une partie des mystères du fonctionnement des cellules, constituants des êtres vivants. Les ARN non-codant sont des macromolécules intervenant dans le métabolisme de tout être vivant et les deux problématiques majeurs les concernant sont: la prédiction de leur structure pour mieux comprendre leur fonctionnement et leur détection dans des bases de données ou des génomes. L'une des approches: l'alignement structure-séquence d'ARN, répond à ces deux problématiques. Le problème d'alignement structure-séquence consiste à aligner une structure connue d'un premier ARN avec la séquence d'un deuxième ARN.La structure est représentée sous la forme d'un graphe ou de façon équivalente sous la forme d'une séquence arc-annotées et la séquence représente la suite des nucléotides de l'ARN.Pour résoudre ce problème, nous cherchons à optimiser l'alignement selon une fonction de coût. C'est donc un problème d'optimisation, qui malheureusement se révèle NP-Difficile.En conséquence différents travaux définissent des classes d'instances réduites pour lesquelles ils proposent des algorithmes spécifiques mais à complexités polynomiales.Les travaux de ma thèse unifient et la généralisent les approches précédentes par la construction d'un algorithme à complexité paramétrée non spécifique à une classe d'instances. En utilisant cet algorithme, il est possible de résoudre le problème d'alignement structure-séquence pour toutes les instances possibles, et aussi efficacement que les précédentes approches sur leur domaine de résolution respectif. Cet algorithme utilise une technique empruntée à la théorie des graphes: la décomposition arborescente, c'est-à-dire qu'il transforme la structure donnée en une décomposition arborescente et c'est ensuite cette décomposition qui est alignée avec la séquence donnée. L'alignement entre une décomposition arborescente et une séquence se fait par programmation dynamique.Sa mise en place a nécessité une reformulation du problème ainsi qu'une modification importante de l'utilisation classique de la programmation dynamique pour les décompositions arborescentes. Au final, cela conduit à un algorithme paramétré dont le paramètre est entièrement lié à la décomposition arborescente. La construction des décompositions arborescentes pour lesquelles l'alignement s'effectuera plus le efficacement possible est malheureusement un problème lui aussi NP-Difficile. Néanmoins, nous avons créé une heuristique de construction de décompositions adaptée aux structures d'ARN.Nous avons alors défini des nouvelles classes de structures pour lesquelles notre algorithme (décomposition et alignement) possède une faible complexité. Ces classes incluent notamment toutes les autres classes précédemment définies et la complexité de notre algorithme est au moins aussi faible que celles des algorithmes spécifiques sur leurs classes de structures respectives. Ces classes de structures représentent la majorité des structures connues et contiennent de nombreux éléments importants jusqu'alors non pris en compte (tel que les motifs tertiaires d'ARN). Le problème de l'alignement structure-séquence tente de répondre aux problématiques de prédictions de structures et de recherche d'ARN. Néanmoins, la qualité des résultats obtenus par sa résolution dépendent de la fonction de coût utilisée. Durant ma thèse j'ai commencé la mise place de la construction par apprentissage d'une nouvelle fonction de coût, adaptée aux nouvelles classes de structures que nous avons défini. Enfin de par la nature de l'algorithme, le travail réalisé permet des améliorations non négligeables, en terme de qualité des résultats et de rapidité de calcul comme la recherche de solution sous-optimales ou l'utilisation de l'algorithme au sein d'heuristiques dérivées d'heuristiques classiques.
7
Morançay, Lionel. "Représentation paramétrée et modélisation des systèmes physiques pour la conception optimale." Compiègne, 1993. http://www.theses.fr/1993COMP582S.
Анотація:
Ce document présente une étude des problèmes liés à la description informatique de systèmes physiques pour l'optimisation des performances de produits industriels. Dans une première partie, les problèmes d'architecture de logiciels pour la conception et la fabrication assistées par ordinateur sont abordés et l'architecture du système interactif de conception logiciel de modélisation par éléments finis est introduite. Dans une deuxième partie, les problèmes liés à la génération de maillages dans un contexte auto-adaptatif nécessaire à l'automatisation du processus d'optimisation sont considérés et notre contribution à la réalisation d'outils pour l'adaptation de maillages est développée (une étude bibliographique, de la méthode de Delaunay et des méthodes de maillage frontales en particulier, est présentée en annexe). La troisième partie rapporte les méthodes de paramétrage des formes utilisées jusqu'à présent dans le domaine de la synthèse optimale, ainsi que l'approche que nous avons adoptée : l'historique de construction. Les outils développés pour le calcul de gradients par différences finies (en l'occurrence, des techniques de repositionnement des nœuds d'un maillage lorsque la géométrie du domaine évolue) et l'organisation générale des problèmes d'optimisation dans l'environnement du système interactif de conception sont également exposés. Un exemple d'application industriel a été traite. Il concerne l'optimisation de la forme d'une bielle. Enfin, de nouveaux axes de recherche sont dégages, en ce qui concerne la représentation paramétrée et le maillage de formes tri-dimensionnelles, notamment.
8
Duvillié, Guillerme. "Approximation, complexité paramétrée et stratégies de résolution de problèmes d'affectation multidimensionnelle." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT321/document.
Анотація:
Au cours de la thèse, nous nous sommes intéressés aux problèmes d'empilement de wafers. Ces problèmes apparaissent lors de la fabrication de processeurs en 3 dimensions. Au cours du processus de fabrication, les puces électroniques doivent être empilées les unes sur les autres. Jusqu'à peu, ces dernières, une fois gravées sur des plaques de silicium appelées wafers, étaient découpées, puis triées afin d'écarter les puces défectueuses et enfin assemblées les unes entre elles.Cependant empiler les wafers plutôt que les puces présente de nombreux avantages techniques et financiers. Naturellement, étant impossible d'écarter les puces défectueuses sans découper la plaque de silice, le problème de la superposition d'une puce viable avec une puce défectueuse se pose. Une pile de puces, étant considérées comme défectueuse si elle contient ne serait-ce qu'une puce défectueuse, la superposition non réfléchie des wafers entre eux mènerait à un rendement désastreux.Afin de générer un nombre minimum de piles défectueuses, une "cartographie" de chaque wafer candidat à la superposition est réalisée lors d'une phase de test, permettant de situer les puces défectueuses sur le wafer. Une fois cette cartographie réalisée, l'objectif est de sélectionner les wafers qui seront assemblés ensembles de manière à faire correspondre les défauts de chacun des wafers.Ce problème peut être modélisé à l'aide d'un problème d'affectation multidimensionnelle. Chaque wafer est représenté par un vecteur comportant autant de composantes que de puces sur le wafer qu'il représente. Une composante égale à zéro matérialise une puce défectueuse tandis qu'un un matérialise une puce viable. Chaque lot de wafers est représenté par un lot de vecteurs. Formellement, une instance d'empilement de wafers est représenté par m ensembles de n vecteurs binaires p-dimensionnels. L'objectif est alors de réaliser n m-uplets disjoints contenant exactement un vecteur par ensemble. Ces m-uplets représenteront les piles. Chaque m-uplet peut être représenté par un vecteur binaire p-dimensionnels, chaque composante étant calculée en réalisant le ET binaire des composantes correspondantes des vecteurs qui composent le m-uplet. Autrement dit, une composante du vecteur représentant le m-uplet est égale à un si et seulement si tous les vecteurs ont cette composante égale à un. Et donc une pile de puces est viables si toutes les puces qui la composent sont viables. L'objectif est alors de minimiser le nombre de zéros ou de maximiser le nombre de un.La thèse comporte deux grandes parties. Une partie théorique abordant la complexité des différentes versions du problèmes en fonction de certains paramètres tels que m, n, p ou encore le nombre maximum de zéros par vecteurs. Nous montrons entre autre que ces problèmes peuvent être utilisés pour modéliser des problèmes plus classiques tels que Maximum Clique, Minimum Vertex Cover ou encore k-Dimensional Matching, permettant de prouver un certain nombre de résultats négatifs que ce soit d'un point de vue de la complexité classique, l'approximabilité ou la complexité paramétrée. Nous fournissons également des résultats positifs pour des cas particuliers du problème.Dans un second temps, nous nous intéressons à la résolution pratique du problème en fournissant et comparant un certain nombre de formulations en Programmation Linéaire en Nombres Entiers. Mais nous nous intéressons également aux performances en pratique de certaines heuristiques à garantie de performances détaillées dans la partie théoriqueIn this thesis, we focused in the Wafer-to-Wafer integration problems. These problems come from IC manufacturing. During the production of three-dimensional processors, dies have to be superimposed. Until recent, the dies were engraved on a silicon disk called wafer, then were cut, tested and sorted to suppress faulty dies and lastly superimposed one to each other.However superimposing wafers instead of dies presents several technical and financial advantages. Since faulty dies can only be dismissed when cutting the wafer, superimpose two wafers can lead to superimpose a faulty die with a viable one. In this case, the resulting stack of dies is considered as faulty. It follows that a bad assignment between the wafers can lead to a disastrous yield.In order to minimize the number of faulty dies stacks, a "failure map" of each wafer is generated during a test phase. This map gives location of the faulty dies on the wafers. The objective is then to take advantage of this map to define an assignment of the wafers to each other in order to match as many failures as possible.This problem can be modelized with Multidimensional Assignment problems. Each wafer can be seen as a vector with as many dimensions as the number of dies engraved on it. A coordinate set to zero marks a faulty die while a coordinate set to one indicates a viable one. Each seat of wafers is represented by a set of vector. Formally, an instance of a Wafer-to-Wafer integration problem is represented by m sets of n p-dimensional vectors. The objective is then to partition the vectors into n disjoint m-tuples, each tuple containing exactly one vector per set. An m-tuple represents a stack of wafers. Every m-tuple can be represented by a p-dimensional vector. Each coordinate is computed by performing the bitwise AND between the corresponding coordinates of the vectors that compose the m-tuple. In other words, a coordinate of the representative vector is equal to one if and only if this coordinate is equal to one in every vector composing the tuple. It follows that a dies stack is viable if and only if all the dies composing the stack are viable. The objective is then to maximize the overall number of ones of to minimize the overall number of zeros.The first part of the thesis is a theoretical one. We study the complexity of the considered versions of the problem with regards to natural parameters such as m, n, p or the number of zeros per vector. We show that these problems can encode more classical problems such as Maximum Clique, Minimum Vertex Cover or k-Dimensional Matching. This leads to several negative results from computational complexity, approximability or even parameterized complexity point of view. We also provide several positive results for some specific cases of the problem.In a second part, we focus on the practical solving of the problem. We provide and compare several Integer Linear Programming formulations. We also focus on performances of some approximation algorithms that we detailed in the theoretical part
9
Efremov, Semen. "Croissance paramétrée et bruit procédural pour la conception de métamatériaux mécaniques." Electronic Thesis or Diss., Université de Lorraine, 2022. http://www.theses.fr/2022LORR0046.
Анотація:
Avec le développement constant des technologies, les capacités de calcul et de fabrication augmentent, les méthodes de production évoluent et de nouvelles techniques apparaissent. Par conséquent, le besoin de nouveaux matériaux aux propriétés adaptées et optimisées pour différentes applications se fait sentir. Les composites périodiques avec une topologie de microstructure adaptée, appelés métamatériaux cellulaires, sont largement étudiés dans ce contexte. Ces structures sont connues pour leurs propriétés mécaniques remarquables, notamment une résistance élevée, un poids réduit et une absorption d'énergie accrue. L'utilisation de ces matériaux permet d'obtenir des propriétés physiques améliorées ou des caractéristiques fonctionnelles spécifiques et apporte un gain économique et un bénéfice écologique. Cette thèse est consacrée au développement et à l'analyse de méthodes de conception assistée par ordinateur de matériaux aux propriétés mécaniques adaptées. Les métamatériaux mécaniques ont été étudiés à travers deux approches différentes : la modélisation de structures périodiques par un modèle de croissance paramétré et des fonctions de bruit procédurales. Pour relever le défi d'obtenir des microstructures quasi régulières avec des propriétés variant progressivement, j'ai proposé et étudié un matériau cellulaire engendré par un processus de croissance. La croissance est paramétrée par un ensemble d'étoiles 3D à chaque point du réseau, définissant la géométrie qui apparaîtra autour. Des tuiles individuelles peuvent être calculées et utilisées dans un treillis périodique, ou une structure globale peut être produite par gradation spatiale, en changeant l'ensemble paramétrique en forme d'étoile à chaque emplacement du treillis. Au-delà de la gradation spatiale libre, un avantage important de cette approche est que les symétries élastiques peuvent être intrinsèquement renforcées. Nous montrons dans ce travail comment les symétries partagées entre le réseau et l'ensemble étoilé se traduisent directement en symétries de la réponse élastique des structures périodiques. Ainsi, l'approche permet de restreindre la symétrie des réponses élastiques - monoclinique, orthorhombique, trigonale, etc. - tout en explorant librement un large espace de géométries et de topologies possibles. Je fournis une étude complète de l'espace de symétries et de larges combinaisons de paramètres de processus de croissance. De plus, je démontre par des résultats numériques et expérimentaux les réponses attendues déclenchées par les structures obtenues. La deuxième contribution de cette thèse est une nouvelle technique de synthèse procédurale de motifs. Cette approche présente des propriétés souhaitables pour la modélisation de motifs très contrastés, qui sont bien adaptés pour produire des détails de surface et de microstructure. Cette approche définit un champ de phase lisse stochastique - un bruit de phase - qui est ensuite introduit dans une fonction périodique (par exemple une onde sinusoïdale), produisant un champ oscillant avec des fréquences principales prescrites et des oscillations de contraste préservées. Je présente dans cette thèse un modèle mathématique qui repose sur une reformulation du bruit de Gabor en termes de champ phasor qui permet une séparation claire entre l'intensité locale et la phase. En particulier, j'étudie le comportement du bruit phasor en termes de spectre de puissance. Ainsi, une étude théorique comparative du bruit en phase est réalisée afin de comprendre les liens entre ses propriétés et ses paramètresWith constant development of technologies, computational and manufacturing capabilities increase, production methods evolve, and new techniques appear. As a result, the need for new materials with tailored, optimized properties for different applications arises. Periodic composites with tailored microstructure topology, called cellular metamaterials are extensively studied in this context. These structures are known for their remarkable mechanical properties, including high strength, lower weight, and increased energy absorption. The use of these materials allows to achieve improved physical properties or specific functional features and provides economical gain and ecological benefit.This thesis is dedicated to the development and analysis of methods for computer-aided design of materials with tailored mechanical properties. The mechanical metamaterials were studied through two different approaches: modelling periodic structures through a parameterized growth model and procedural noise functions. To tackle the challenge of obtaining near-regular microstructures with progressively varying properties, I proposed and studied a cellular material spawned by a growth process. The growth is parameterized by a 3D star-shaped set at each lattice point, defining the geometry that will appear around it. Individual tiles may be computed and used in a periodic lattice, or a global structure may be produced under spatial gradations, changing the parametric star-shaped set at each lattice location. Beyond free spatial gradation, an important advantage of this approach is that elastic symmetries can be intrinsically enforced. It is shown in this work how shared symmetries between the lattice and the star-shaped set directly translate into symmetries of the periodic structures' elastic response. Thus, the approach enables restricting the symmetry of the elastic responses -- monoclinic, orthorhombic, trigonal, and so on -- while freely exploring a wide space of possible geometries and topologies. I provide a comprehensive study of the space of symmetries and broad combinations of growth process parameters. Furthermore, I demonstrate through numerical and experimental results the expected responses triggered by the obtained structures.The second contribution of this thesis is a novel procedural pattern synthesis technique. This approach exhibits desirable properties for modeling highly contrasted patterns, that are well suited to produce surface and microstructure details. This approach defines a stochastic smooth phase field –- a phasor noise –- that is then fed into a periodic function (e.g. a sine wave), producing an oscillating field with prescribed main frequencies and preserved contrast oscillations. I present in this thesis a mathematical model, that builds upon a reformulation of Gabor noise in terms of a phasor field that affords for a clear separation between local intensity and phase. In particular, I study the behavior of phasor noise in terms of its power spectrum. Hence, a comparative theoretical study of phasor noise was performed in order to gain understanding of links between its properties and parameters
10
Andami, Ovono Armel. "Equations de diffusion paramétrée par la portée des interactions à longue distance." Phd thesis, Université de Poitiers, 2009. http://tel.archives-ouvertes.fr/tel-00365445.
Анотація:
Nous nous intéressons dans cette thèse à l'étude d'une équation parabolique quasilinéaire dans laquelle la diffusion est paramétrée par la longueur des différentes interactions non locales. Pour ce qui est du problème stationnaire associé, après avoir montré des résultats d'existence, d'unicité et de continuité. Nous présentons ensuite un critère général d'inversibilité dépendant du paramètre, ce critère très important va par la suite nous permettre en exemple d'application de retrouver des résultats d'inversibilités déjà connus lorsque le paramètre est égale au diamètre du domaine. Nous donnons ensuite un résultat de principe de comparaison de solutions symétriques radiales et une généralisation du compte du nombre de solutions. Enfin nous donnons quelques applications numériques utilisant une méthode de point fixe et de Newton pour illustrer ces résultats. Pour le problème d'évolution, après avoir montré l'existence d'un attracteur global associé à notre problème, nous démontrons une estimation $L^\infty$ de la solution en fonction d'estimations $L^q$, $q>1$ utilisant des itérations de type Moser.
11
Andami, Ovono Armel. "Équations de diffusion paramétrée par la portée des interactions à longue distance." Poitiers, 2009. http://theses.edel.univ-poitiers.fr/theses/2009/Andami-Ovono-Armel/2009-Andami-Ovono-Armel-These.pdf.
Анотація:
Nous nous intéressons dans cette thèse à l’étude d’une équation parabolique quasilinéaire dans laquelle la diffusion est paramétrée par la longueur des différentes interactions non locales. Pour ce qui est du problème stationnaire associé, après avoir montré des résultats d’existence, d’ unicité et de continuité. Nous présentons ensuite un critère général d’ inversibilité dépendant du paramètre, ce critère très important va par la suite nous permettre en exemple d’application, de retrouver des résultats d’inversibilité déjà connus lorsque le paramètre est égale au diamètre du domaine. Nous donnons ensuite un résultat de principe de comparaisons de solutions symétriques radiales et une généralisation du compte du nombre de solutions. Enfin nous donnons quelques applications numériques utilisant une méthode de point fixe et de Newton pour illustrer ces résultats. Pour le problème d’évolution, après avoir montré l’existence d’un attracteur global associé à notre problème, nous démontrons une estimation L∞ de la solution en fonction d’estimations Lq, q > 1 utilisant des itérations de type MoserThis thesis is devoted to a quasilinear parabolic equation in which the diffusion is defined by the length of different non local interactions. As regards stationary problem, having shown the results of existence, uniqueness and continuity. We introduce a general criterion of inversibility later depending on parameter, this very important criterion is going to allow us in example of application to find well known results when parameter will be equal to the diameter of domain. We give then a fundamental result of comparison of solutions in the case of radial symmetrical solutions and a general implementation of count of solutions. Finally we give some numerical applications using a method of fixed point and Newton’s method to illustrate these results. As regards parabolic problem having shown existence of global attractor associated to our problem, we show an estimate L∞ of solution according to estimate Lq, q >1 by using Moser’s iteration
12
Zimmermann, Jakub. "Détection d'intrusions paramétrée par la politique par contrôle de flux de références." Rennes 1, 2003. http://www.theses.fr/2003REN10155.
Анотація:
Nous proposons une approche de la d'tection d'intrusions orient'e politique bas'e sur un contr"le de flux d'informations. Nous construisons un modSle formel du systSme d'exploitation sous forme de canaux de flux d'informations et nous exprimons une politique de confidentialit' et d'int'grit' sous forme d'un ensemble de domaines, c'est. Dire de graphes de flux l'gaux. Nous en d'duisons alors un algorithme de d'tection des violations de cette politique. A titre exp'rimental, nous avons implant' cette approche sous Linux. Ce systSme se pr^te assez bien. La mod'lisation que nous utilisons et la politique de s'curit', mise en oeuvre par d'faut au moyen du contr"le d'accSs discr'tionnaire, peut ^tre traduite automatiquement sous forme de domaines dans notre modSle. Au cours de nos tests, cette approche s'est r'v'l'e fiable pour d'tecter des violations effectives de la politique de s'curit', y compris dans le cas d'attaques nouvelles ou inconnues. D'autre part, le taux de fausses alertes est faible.
13
Labbé, Sébastien. "Réduction paramétrée de spécifications formées d'automates communicants : algorithmes polynomiaux pour la réduction de modèles." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2007. http://tel.archives-ouvertes.fr/tel-00180174.
Анотація:
Les travaux décrits dans ce manuscrit de thèse s'inscrivent dans le cadre des méthodes formelles pour les langages de spécifications formées d'automates communicants. Ce type de langage est largement utilisé dans les industries de pointe où le niveau de fiabilité requis est élevé (e.g. aéronautique, transports), car ils permettent d'améliorer la précision des spécifications et d'exploiter des outils de simulation, de test ou de vérification qui contribuent à la validation des spécifications. Un frein au passage à l'échelle industrielle de ces méthodes formelles est connu sous le nom de l'explosion combinatoire, qui est due à la fois à la manipulation de larges domaines numériques, et au parallélisme intrinsèque aux spécifications.L'idée que nous proposons consiste à contourner ce phénomène en appliquant des techniques de réduction paramétrée, pouvant être désignées sous le terme anglo-saxon "slicing'', en amont d'une analyse complexe. Cette analyse peut ainsi être effectuée a posteriori sur une spécification réduite, donc potentiellement moins sujette à l'explosion combinatoire. Notre méthode de réduction paramétrée est basée sur des relations de dépendances dans la spécification sous analyse, et est fondée principalement sur les travaux effectués par les communautés de la compilation et du slicing de programmes. Dans cette thèse nous établissons un cadre théorique pour les analyses statiques de spécifications formées d'automates communicants, dans lequel nous définissons formellement les relations de dépendances mentionnées ci-dessus, ainsi que le concept de "tranche" de spécification par rapport à un "critère" de réduction. Ensuite, nous décrivons et démontrons les algorithmes efficaces que nous avons mis au point pour calculer les relations de dépendances et les tranches de spécifications, et enfin nous décrivons notre mise en oeuvre de ces algorithmes dans l'outil "Carver", pour la réduction paramétrée de spécifications formées d'automates communicants.
14
Watrigant, Rémi. "Approximation et complexité paramétrée de problèmes d’optimisation dans les graphes : partitions et sous-graphes." Thesis, Montpellier 2, 2014. http://www.theses.fr/2014MON20100/document.
Анотація:
La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retournant une solution optimale mais dont l'explosion combinatoire est capturée par un paramètre de l'entrée bien choisi. Cette thèse comporte deux objectifs. Dans un premier temps, nous proposons d'étudier et d'appliquer les méthodes classiques de ces deux domaines afin d'obtenir des résultats positifs et négatifs pour deux problèmes d'optimisation dans les graphes : un problème de partition appelé Sparsest k-Compaction, et un problème de recherche d'un sous-graphe avec une cardinalité fixée appelé Sparsest k-Subgraph. Dans un second temps, nous présentons comment les méthodes de ces deux domaines ont pu se combiner ces dernières années pour donner naissance au principe d'approximation paramétrée. En particulier, nous étudierons les liens entre approximation et algorithmes de noyauxThe theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms
15
Magos, Rivera Miguel. "Sur la modélisation des systèmes dynamiques à topologie variable : une formulation Hamiltonienne à ports paramétrée." Lyon 1, 2005. http://www.theses.fr/2005LYO10016.
Анотація:
Dans cette thèse, nous nous intéressons à la modélisation pour la commande des systèmes physiques à topologie variable. La modélisation du système physique non commandé, est effectuée par une formulation qui conserve explicitement la représentation de l’interconnexion et l’énergie, ce qui permettra l’étude des systèmes non-réguliers par une approche modulaire basée sur le concept de l’énergie. Le principal objectif est alors de représenter de manière structurée toutes les configurations du système, en terme de comportement physiquement possible. Les résultats présentés dans ce mémoire ont pour support un formalisme réseau dynamique pour lequel la théorie des graphes fournit plusieurs représentations mathématiques. Celles-ci permettent la formulation des structures d’interconnexion du système sous forme d’une famille paramétrée de Dirac. Une formulation Hamiltonienne à ports est donc établie à partir de cette expression pour les systèmes physiques à topologie variable incluant des sources d’énergie, des éléments en excès ou des éléments dissipatifs. Cette méthode de modélisation permet d’obtenir un modèle des dynamiques du système mais aussi de ces interconnexions. La représentation sous forme de graphes dynamiques facilite l’analyse des configurations admissibles et des configurations contraintes du système
16
Sebeloue, Martine. "Modélisation comportementale paramétrée de fonctions analogiques pour la simulation des systèmes de transmission, en technologie bipolaire." Toulouse, INPT, 2000. http://www.theses.fr/2000INPT014H.
Анотація:
Les concepteurs de circuits intégrés passent par des étapes de simulations qui leur permettent de réduire les coûts de fabrication. Cependant, dans le domaine analogique, l'intégration d'un grand nombre de fonctions rend souvent impossibles les simulations, à cause des problèmes de convergences et augmente considérablement les temps de simulations. Une solution consiste à remplacer lors des simulations, les blocs constitutifs de ces circuits par leurs modèles respectifs afin d'étudier le comportement des systèmes dans des temps très courts. L'objectif et l'originalité de ce travail de recherche consistent à réaliser des modèles d'ordre progressif de fonctions électroniques de base, très utilisées dans l'instrumentation et dans les télécommunications, tout en maintenant un compromis acceptable entre simplicité et précision. La technique de modélisation proposée consiste à créer des modèles simples, en ne considérant que les principaux paramètres intervenant dans la fonctionnalité de ces circuits. Nous présentons donc des macromodèles paramétrables de haut niveau d'un oscillateur contrôlé en tension et d'une boucle à verrouillage de phase. Partant de leur topologie en technologie bipolaire, nous réalisons des modèles d'ordre variable, valables quelle que soit la zone de fonctionnement qui prennent en compte les incertitudes des paramètres principaux des transistors (courant de saturation, gain direct en courant) et les variations en température. Les modèles réalisés sont utilisés dans le simulateur PSPICE, et sont validés par comparaisin de résultats de simulations avec les mesures effectuées avec IC-CAP. L'ensemble de l'étude montre que la technique de modélisation proposée permet de développer des modèles de haut niveau de fonctions électroniques complexes, qui ne consomment pas trop de temps de calcul tout en gardant une bonne précision.
17
Fournier, Paulin. "Parameterized verification of networks of many identical processesVérification paramétrée de réseaux composés d'une multitude de processus identiques." Thesis, Rennes 1, 2015. http://www.theses.fr/2015REN1S170/document.
Анотація:
Ce travail s'inscrit dans le cadre de la vérification formelle de programmes. La vérification de modèle permet de s'assurer qu'une propriété est vérifiée par le modèle du système. Cette thèse étudie la vérification paramétrée de réseaux composés d'un nombre non borné de processus identiques où le nombre de processus est considéré comme un paramètre. Concernant les réseaux de protocoles probabilistes temporisés nous montrons que les problèmes de l'accessibilité et de synchronisation sont indécidables pour des topologies de communication en cliques. Cependant, en considérant des pertes et créations probabiliste de processus ces problèmes deviennent décidables. Pour ce qui est des réseaux dans lequel les messages n'atteignent qu'une sous partie des composants choisie de manière non-déterministe, nous prouvons que le problème de l'accessibilité paramétrée est décidable grâce à une réduction à un nouveau modèle de jeux à deux joueurs distribué pour lequel nous montrons que l'on peut décider de l'existence d'une stratégie gagnante en coNP. Finalement, nous considérons des stratégies locales qui permettent d'assurer que les processus effectuent leurs choix non-déterministes uniquement par rapport a leur connaissance locale du système. Sous cette hypothèse de stratégies locales, nous prouvons que les problèmes de l'accessibilité et de synchronisation paramétrées sont NP-completThis thesis deals with formal verification of distributed systems. Model checking is a technique for verifying that the model of a system under study fulfills a given property. This PhD investigates the parameterized verification of networks composed of many identical processes for which the number of processes is the parameter. Considering networks of probabilistic timed protocols, we show that the parameterized reachability and synchronization problems are undecidable when the communication topology is a clique. However, assuming probabilistic creation and deletion of processes, the problems become decidable. Regarding selective networks, where the messages only reach a subset of the components, we show decidability of the parameterized reachability problem thanks to reduction to a new model of distributed two-player games for which we prove decidability in coNP of the game problem. Finally, we consider local strategies that enforce all processes to resolve the non-determinism only according to their own local knowledge. Under this assumption of local strategy, we were able to show that the parameterized reachability and synchronization problems are NP-complete
18
Potier, Jean-Claude. "Contribution à la notion de programmation par démonstration : conception sur exemple, mise au point et génération de programmes portables de géométrie paramétrée dans le système EBP." Poitiers, 1995. http://www.theses.fr/1995POIT2299.
19
Daligault, Jean. "Techniques combinatoires pour les algorithmes paramétrés et les noyaux, avec applications aux problèmes de multicoupe." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2011. http://tel.archives-ouvertes.fr/tel-00804206.
Анотація:
Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille k dans un graphe à n sommets peut être décidée en temps f(k) ∗ poly(n). Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en k. Nous donnons un algorithme en temps O∗(3.72k) pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que 2n). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les s−t numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées.
20
Toubiana, meyer Rivka. "Contribution à l’évaluation objective du confort en posture assise par le développement d’un modèle biomécanique paramétrable du tronc." Thesis, Paris, ENSAM, 2016. http://www.theses.fr/2016ENAM0016/document.
Анотація:
Le confort des véhicules automobiles est un élément stratégique et économique lors de leurs développements. L’un des enjeux de demain est la personnalisation du confort, qui ne pourra être atteinte qu'avec des modèles numériques originaux de pointe. En effet, il faudrait être capable de prendre en compte la diversité anthropométrique des occupants au niveau mondial. Dans ce contexte, Faurecia, équipementier de sièges d’automobile et leader dans ce domaine, souhaite optimiser son processus de conception, au moyen d’outils numériques permettant d’analyser le confort dès les premières étapes de la conception. Cependant, à l’heure actuelle, aucun outil numérique n’est disponible pour valider le confort du dossier. Le but de cette étude est donc de développer un outil numérique d’évaluation du confort du dos pour la conception des sièges en tenant compte des différences interindividuelles. Cet outil repose sur le développement d’un modèle biomécanique paramétré du tronc. Tout d’abord, une campagne d’essais a permis d'identifier la reproductibilité d’assise d’un volontaire dans une position standardisée (position, répartition de pression). Un modèle paramétré en éléments finis du tronc a été développé et permettra de simuler ces conditions expérimentales. Le modèle a été validé d’un point de vue géométrique et le maillage a été analysé. Pour valider complètement le modèle et pour permettre son utilisation par les équipementiers, des positions assises, dont la courbure du rachis est connue, devront être simulés. Puis, le modèle sera évalué pour l’analyse du confort par comparaison des cartographies de pression à l’interface homme/siègeThe comfort of motor vehicles is a strategic and economic element in their developments. One of the future challenges is the individual comfort, which can only be achieved with original digital models. Indeed, we should be able to take into account the diversity of anthropometric occupants in the worldwide. In this context, Faurecia, automotive seating manufacturer and leader in this field, wishes to optimize its design process through digital tools to analyze comfort in the early design steps. However, at present, no digital tool is available to validate the comfort of the backrest. The purpose of this study is to develop a numerical assessment tool for the comfort of the backrest design taking into account individual differences. This tool is based on the development of a biomechanical trunk model. Firstly, a test campaign allowed identifying the sitting reproducibility of a volunteer in a standardized position (position, pressure distribution). A parametric finite element model of the trunk was developed and will allow simulating these experimental conditions. The model was validated from a geometrical point of view and the mesh was analyzed. To fully validate the model and allow its use by OEMs, sitting positions which the spine curvature is known will be simulated. Then the model will be evaluated for the comfort analysis by comparison of the pressure maps to the human/seat interface
21
Garnero, Valentin. "(Méta)-noyaux constructifs et linéaires dans les graphes peu denses." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT328/document.
Анотація:
En algorithmique et en complexité, la plus grande part de la recherche se base sur l’hypothèse que P ≠ NP (Polynomial time et Non deterministic Polynomial time), c'est-à-dire qu'il existe des problèmes dont la solution peut être vérifiée mais non construite en temps polynomial. Si cette hypothèse est admise, de nombreux problèmes naturels ne sont pas dans P (c'est-à-dire, n'admettent pas d'algorithme efficace), ce qui a conduit au développement de nombreuses branches de l'algorithmique. L'une d'elles est la complexité paramétrée. Elle propose des algorithmes exacts, dont l'analyse est faite en fonction de la taille de l'instance et d'un paramètre. Ce paramètre permet une granularité plus fine dans l'analyse de la complexité.Un algorithme sera alors considéré comme efficace s'il est à paramètre fixé, c'est-à-dire, lorsque sa complexité est exponentielle en fonction du paramètre et polynomiale en fonction de la taille de l'instance. Ces algorithmes résolvent les problèmes de la classe FPT (Fixed Parameter Tractable).L'extraction de noyaux est une technique qui permet, entre autre, d’élaborer des algorithmes à paramètre fixé. Elle peut être vue comme un pré-calcul de l'instance, avec une garantie sur la compression des données. Plus formellement, une extraction de noyau est une réduction polynomiale depuis un problème vers lui même, avec la contrainte supplémentaire que la taille du noyau (l'instance réduite) est bornée en fonction du paramètre. Pour obtenir l’algorithme à paramètre fixé, il suffit de résoudre le problème dans le noyau, par exemple par une recherche exhaustive (de complexité exponentielle, en fonction du paramètre). L’existence d'un noyau implique donc l'existence d'un algorithme à paramètre fixé, la réciproque est également vraie. Cependant, l’existence d'un algorithme à paramètre fixé efficace ne garantit pas un petit noyau, c'est a dire un noyau dont la taille est linéaire ou polynomiale. Sous certaines hypothèses, il existe des problèmes n’admettant pas de noyau (c'est-à-dire hors de FPT) et il existe des problèmes de FPT n’admettant pas de noyaux polynomiaux.Un résultat majeur dans le domaine des noyaux est la construction d'un noyau linéaire pour le problème Domination dans les graphes planaires, par Alber, Fellows et Niedermeier.Tout d'abord, la méthode de décomposition en régions proposée par Alber, Fellows et Niedermeier, a permis de construire de nombreux noyaux pour des variantes de Domination dans les graphes planaires. Cependant cette méthode comportait un certain nombre d’imprécisions, ce qui rendait les preuves invalides. Dans la première partie de notre thèse, nous présentons cette méthode sous une forme plus rigoureuse et nous l’illustrons par deux problèmes : Domination Rouge Bleue et Domination Totale.Ensuite, la méthode a été généralisée, d'une part, sur des classes de graphes plus larges (de genre borné, sans-mineur, sans-mineur-topologique), d'autre part, pour une plus grande variété de problèmes. Ces méta-résultats prouvent l’existence de noyaux linéaires ou polynomiaux pour tout problème vérifiant certaines conditions génériques, sur une classe de graphes peu denses. Cependant, pour atteindre une telle généralité, il a fallu sacrifier la constructivité des preuves : les preuves ne fournissent pas d'algorithme d'extraction constructif et la borne sur le noyau n'est pas explicite. Dans la seconde partie de notre thèse nous effectuons un premier pas vers des méta-résultats constructifs ; nous proposons un cadre général pour construire des noyaux linéaires en nous inspirant des principes de la programmation dynamique et d'un méta-résultat de Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh et ThilikosIn the fields of Algorithmic and Complexity, a large area of research is based on the assumption that P ≠ NP(Polynomial time and Non deterministic Polynomial time), which means that there are problems for which a solution can be verified but not constructed in polynomial time. Many natural problems are not in P, which means, that they have no efficient algorithm. In order to tackle such problems, many different branches of Algorithmic have been developed. One of them is called Parametric Complexity. It consists in developing exact algorithms whose complexity is measured as a function of the size of the instance and of a parameter. Such a parameter allows a more precise analysis of the complexity. In this context, an algorithm will be considered to be efficient if it is fixed parameter tractable (fpt), that is, if it has a complexity which is exponential in the parameter and polynomial in the size of the instance. Problems that can be solved by such an algorithm form the FPT class.Kernelisation is a technical that produces fpt algorithms, among others. It can be viewed as a preprocessing of the instance, with a guarantee on the compression of the data. More formally, a kernelisation is a polynomial reduction from a problem to itself, with the additional constraint that the size of the kernel, the reduced instance, is bounded by a function of the parameter. In order to obtain an fpt algorithm, it is sufficient to solve the problem in the reduced instance, by brute-force for example (which has exponential complexity, in the parameter). Hence, the existence of a kernelisiation implies the existence of an fpt algorithm. It holds that the converse is true also. Nevertheless, the existence of an efficient fpt algorithm does not imply a small kernel, meaning a kernel with a linear or polynomial size. Under certain hypotheses, it can be proved that some problems can not have a kernel (that is, are not in FPT) and that some problems in FPT do not have a polynomial kernel.One of the main results in the field of Kernelisation is the construction of a linear kernel for the Dominating Set problem on planar graphs, by Alber, Fellows and Niedermeier.To begin with, the region decomposition method proposed by Alber, Fellows and Niedermeier has been reused many times to develop kernels for variants of Dominating Set on planar graphs. Nevertheless, this method had quite a few inaccuracies, which has invalidated the proofs. In the first part of our thesis, we present a more thorough version of this method and we illustrate it with two examples: Red Blue Dominating Set and Total Dominating Set.Next, the method has been generalised to larger classes of graphs (bounded genus, minor-free, topological-minor-free), and to larger families of problems. These meta-results prove the existence of a linear or polynomial kernel for all problems verifying some generic conditions, on a class of sparse graphs. As a price of generality, the proofs do not provide constructive algorithms and the bound on the size of the kernel is not explicit. In the second part of our thesis, we make a first step to constructive meta-results. We propose a framework to build linear kernels based on principles of dynamic programming and a meta-result of Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh and Thilikos
22
Ammour, Samir. "Support des patrons de conception dans les outils UML." Paris 6, 2006. http://www.theses.fr/2006PA066592.
Анотація:
Les outils UML intégrant le support de l’utilisation des patrons de conception doivent permettent une mise en œuvre correcte des solutions de patrons, sans remettre en cause la cohérence des modèles UML. Ils doivent permettre aussi de vérifier que les solutions des patrons appliqués résolvent réellement les problèmes de conception auxquels ces solutions sont destinées et que les contextes d’application ne contrarient pas les principes de conception que ces solutions utilisent pour résoudre les problèmes. Nous nous intéressons dans cette thèse aux aspects ‘‘solution’’ et ‘‘problème’’ des patrons de conception. Nous proposons un ensemble de contraintes et de transformations permettant : i) une intégration correcte et cohérente des solutions de patrons dans les modèles UML. Ii) spécifier la partie des problèmes de conception liés au couplage des patrons de conception GOF. Nous utilisons l’ensemble de contraintes et de transformations obtenues sous forme d’une extension au standard UML.
23
Hiet, Guillaume. "Détection d'intrusions paramétrée par la politique de sécurité grâce au contrôle collaboratif des flux d'informations au sein du système d'exploitation et des applications : mise en œuvre sous Linux pour les programmes Java". Phd thesis, Université Rennes 1, 2008. http://tel.archives-ouvertes.fr/tel-00355089.
Анотація:
La sécurité informatique est un enjeu crucial. Elle consiste en premier lieu à définir une politique de sécurité puis à mettre en œuvre cette politique. Les approches préventives comme le contrôle d'accès sont essentielles mais insuffisantes. Il est donc nécessaire de recourir à la détection d'intrusions. En particulier, l'approche de détection d'intrusions paramétrée par la politique de sécurité nous paraît prometteuse. Une telle approche s'appuie uniquement sur un modèle de l'évolution de l'état du système et sur un modèle de la politique de sécurité. Nous nous intéressons dans cette thèse aux politiques de flux d'informations permettant d'assurer la confidentialité et l'intégrité des données. Nous souhaitons utiliser une approche de détection d'intrusions paramétrée par la politique de sécurité pour surveiller un système comprenant un OS et des logiciels COTS comprenant des applications web. Nous proposons un modèle de détection permettant de suivre les flux d'informations entre les conteneurs d'informations. Nous définissons une architecture générique de système de détection d'intrusions (IDS) permettant d'implémenter le modèle proposé. Cette architecture repose sur la collaboration entre plusieurs IDS effectuant le suivi des flux d'informations à différents niveaux de granularité. Nous présentons une implémentation de cette architecture reposant sur Blare, un IDS existant permettant de gérer les conteneurs d'informations de l'OS, et JBlare, une implémentation que nous avons réalisée pour suivre les flux d'informations au niveau des applications Java. Nous présentons également les résultats des expérimentations que nous avons menées en instrumentant des applications Java « réalistes ».
24
Hiet, Guillaume. "Détection d'intrusions paramétrée par la politique de sécurité grâce au contrôle collaboratif des flux d'information au sein du système d'exploitation et des applications : mise en oeuvre sous Linux pour les programmes Java." Rennes 1, 2008. http://www.theses.fr/2008REN1S171.
Анотація:
La sécurité informatique est un enjeu crucial. Elle consiste en premier lieu à définir une politique de sécurité puis à mettre en œuvre cette politique. L’approche de détection d'intrusions paramétrée par la politique de sécurité nous paraît prometteuse. Une telle approche s'appuie uniquement sur un modèle de l'évolution de l'état du système et sur un modèle de la politique de sécurité. Nous souhaitons surveiller un système comprenant un OS et des logiciels COTS dont des applications web. Nous proposons un modèle de détection permettant de suivre les flux d'informations entre les conteneurs d'informations. Nous définissons une architecture générique de système de détection d'intrusions (IDS) permettant d'implémenter le modèle proposé. Cette architecture repose sur la collaboration entre plusieurs IDS effectuant le suivi des flux d'informations à différents niveaux de granularité. Nous présentons une implémentation de cette architecture ainsi que les résultats de nos expérimentationsComputer security is now a crucial issue. We are convinced that policy-based intrusion detection is a promising approach. This kind of detection is only based on both a model of the system state evolution and a model of the security policy. We aim at using policy-based intrusion detection systems (IDS) to monitor a system with OS running COTS software and web applications. We propose a detection model that can monitor information flow between information containers. We define a generic IDS architecture implementing the proposed model. This architecture is based on the collaboration between several IDS monitoring information flows at different granularity levels. We present an implementation of this architecture and the results of the experiments we realized on realistic Java applications
25
Watel, Dimitri. "Approximation de l'arborescence de Steiner." Thesis, Versailles-St Quentin en Yvelines, 2014. http://www.theses.fr/2014VERS0025/document.
Анотація:
Dans un graphe orienté contenant un nœud appelé racine, un sous ensemble de nœuds appelés terminaux et une pondération sur les arcs, le problème de l’arborescence de Steiner (DST) consiste en la recherche d’une arborescence de poids minimum contenant pour chaque terminal un chemin de la racine vers ce terminal. Ce problème est NP-Complet. Cette thèse se penche sur l’étude de l’approximabilité de ce problème. Sauf si P=NP, il n’existe pas pour ce problème d’approximation de rapport constant ou logarithmique en k, oú k est le nombre de terminaux. Le plus petit rapport d’approximation connu est O (k") où " est un réel strictement positif. Dans la première partie, nous donnons trois algorithmes d’approximation : un algorithme glouton efficace qui associe deux techniques d’approximations connues pour DST, un algorithme dans le cas des graphes structurés en paliers qui étudie l’approximabilité du problème quand les terminaux sont éloignés de la racine, et un algorithme exponentiel qui combine un algorithme d’approximation et un algorithme exact, dont le rapport d’approximation et la complexité temporelle sont paramétrés par le nombre de terminaux couverts par l’algorithme exact. Dans la seconde partie, nous étudions deux problèmes issus de DST auquel est ajoutée une contrainte sur les nœuds de branchement. Cette contrainte réduit le nombre de solutions réalisables et peut faciliter la recherche d’une solution optimale parmi ce sous-ensemble de solutions. En fonction de la contrainte, nous étudions la possibilité de la trouver en temps polynomial et quel est le rapport d’approximation entre cette solution et la solution du problème non contraintThe directed Steiner tree problem (DST) asks, considering a directed weighted graph, a node r called root and a set of nodes X called terminals, for a minimum cost directed tree rooted in r spanning X. DST is an NP-complete problem. We are interested in the search for polynomial approximations for DST. Unless P = NP, DST can not be approximated neither within a constant ratio nor a logarithmic ratio with respected to k, where k is the number of terminals. The smallest known approximation ratio is O(kԑ)$ where ԑ is a positive real.In the first part, we provide three new approximation algorithms : a practical greedy algorithm merging two of the main approximation techniques for DST, an algorithm for the case where the graph is layered and where the distance between the terminals and the root is high, and an exponential approximation algorithm combining an approximation algorithm and an exact algorithm, parameterized with the number of terminals the exact algorithm must cover.In the last part we study DST with two branching constraints. With this technique, we are able to reduce the number of feasible solutions, and possibly facilitate the search for an optimal solution of the constraint problem. We study how it is possible to build such a solution in polynomial time and if this solution is a good approximation of an optimal solution of the non-constraint problem
26
Chane-Yack-Fa, Raphaël. "Vérification formelle de systèmes d'information." Thèse, Université de Sherbrooke, 2018. http://hdl.handle.net/11143/11630.
Анотація:
Cette thèse s'intéresse à l'étude des méthodes formelles de spécification et de vérification dans le cadre des systèmes d'information. Les systèmes d'informations sont des systèmes dynamiques constitués d'entités et d'associations représentées par la composition en parallèle de processus répliqués issus de différentes classes. De plus, ces systèmes font partie de la classe des systèmes paramétrés. On propose un modèle de spécification de systèmes paramétrés, nommé PASTD, qui est adapté aux systèmes d'information et qui est basé sur la notation des diagrammes états-transitions algébriques (ASTD). Puis, on étudie le problème de sûreté pour les PASTD, à travers la méthode de vérification de couverture pour les systèmes de transitions bien structurés (WSTS). Cette méthode repose sur trois conditions principales : la monotonie, le beau préordre et la pred-base effective. Les PASTD sont montrés comme étant monotones et on définit une sous-classe vérifiant la propriété de beau préordre. Enfin, on décrit une nouvelle méthode, adaptée aux systèmes paramétrés, qui explicite un ensemble de conditions permettant de prouver la pred-base effective. Ces conditions définissent une nouvelle classe appelée RMTS (\emph{Ranked Monotone Transition Systems}). Cette méthode est appliquée aux PASTD.
27
Khosravian, Ghadikolaei Mehdi. "Extension of NP Optimization Problems." Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLED064.
Анотація:
Le problème de la détermination de la qualité d’une solution partielle se pose dans la majeure partie des approches algorithmiques cherchant à calculer progressivement une solution globale. L’élagage des arbres de recherche, la preuve de garanties d’approximation et l’efficacité des stratégies d’énumération sont des approches algorithmiques qui exigent souvent un moyen approprié de décider si une solution partielle donnée est un bon candidat pour l’étendre à une solution globale de bonne qualité. Dans cette thèse, nous étudions un type particulier de problèmes d’optimisation, appelés problèmes d’extension pour un grand nombre de problèmes basés sur des graphes. Contredisant peut-être l’intuition, ces problèmes ont tendance à être NP-difficile, même quand le problème d’optimisation sous-jacent peut être résolu en temps polynomial. Nous présentons de nombreux résultats positifs et négatifs de NP-difficulté et d’approximation pour différents scénarios d’entrée. De plus, nous étudions la complexité paramétrée des problèmes d’extension par rapport à la taille des pré-solutions, ainsi que l’optimalité de certains algorithmes exacts sous l’hypothèse du temps exponentielleThe problem of determining the quality of a partial solution occurs in almost every algorithmic approach that gradually computes a global solution. Pruning search trees, proving approximation guarantees, or the efficiency of enumeration strategies usually require a suitable way to decide if a given partial solution is a reasonable candidate to pursue for extension to a global one, of assured quality. In this thesis, we study a special type of optimization problems, called extension problems for a large number of optimization problems on graphs. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimization problem can be solved in polynomial time. We present many positive/negative hardness and approximation results for different input scenarios. Moreover, the parameterized complexity of extension problems with respect to size of partial solutions, as well as the optimality of some exact algorithms under the Exponential-Time Hypothesis (ETH) are studied
28
Laug, Patrick. "Contribution à la génération automatique de maillages de qualité pour la simulation numérique." Habilitation à diriger des recherches, Université Pierre et Marie Curie - Paris VI, 2006. http://tel.archives-ouvertes.fr/tel-00012000.
Анотація:
La simulation d'un phénomène physique par la méthode des éléments finis ou d'autres méthodes d'analyse numérique nécessite une décomposition spatiale, ou maillage, du domaine étudié. Pour que le processus de simulation converge rapidement et atteigne la précision voulue, la qualité en taille et en forme du maillage joue un rôle primordial.Ce mémoire constitue une synthèse de mes contributions concernant la génération automatique de maillages respectant le mieux possible ces critères de qualité. Ces différents travaux de recherche ont été réalisés au sein du projet Gamma de l'INRIA.
Dans ce document, les thèmes suivants sont abordés successivement :
- la discrétisation de courbes du plan ou de l'espace 3D,
- le maillage de domaines plans de contours fixes ou variables,
- le maillage de surfaces gauches paramétrées ou discrètes.
Au cours de ces opérations de discrétisation et de maillage, la taille et la forme des éléments sont contrôlées par un champ de métriques traduisant des contraintes géométriques et/ou physiques. Les méthodes présentées ont toutes été validées sur de nombreux exemples académiques ou industriels, notamment en mécanique des solides et en mécanique des fluides.
29
Sikora, Florian. "Aspects algorithmiques de la comparaison d'éléments biologiques." Phd thesis, Université Paris-Est, 2011. http://pastel.archives-ouvertes.fr/pastel-00667797.
Анотація:
Pour mieux saisir les liens complexes entre génotype et phénotype, une méthode utilisée consiste à étudier les relations entre différents éléments biologiques (entre les protéines, entre les métabolites...). Celles-ci forment ce qui est appelé un réseau biologique, que l'on représente algorithmiquement par un graphe. Nous nous intéressons principalement dans cette thèse au problème de la recherche d'un motif (multi-ensemble de couleurs) dans un graphe coloré, représentant un réseau biologique. De tels motifs correspondent généralement à un ensemble d'éléments conservés au cours de l'évolution et participant à une même fonction biologique. Nous continuons l'étude algorithmique de ce problème et de ses variantes (qui admettent plus de souplesse biologique), en distinguant les instances difficiles algorithmiquement et en étudiant différentes possibilités pour contourner cette difficulté (complexité paramétrée, réduction d'instance, approximation...). Nous proposons également un greffon intégré au logiciel Cytoscape pour résoudre efficacement ce problème, que nous testons sur des données réelles.Nous nous intéressons également à différents problèmes de génomique comparative. La démarche scientifique adoptée reste la même: depuis une formalisation d'un problème biologique, déterminer ses instances difficiles algorithmiquement et proposer des solutions pour contourner cette difficulté (ou prouver que de telles solutions sont impossibles à trouver sous des hypothèses fortes)
30
Charlet, Célina. "Raffiner pour vérifier des systèmes paramétrés." Besançon, 2003. http://www.theses.fr/2003BESA2054.
31
Sérée, Bastien. "Problèmes d'optimisation des les graphes paramétrés." Electronic Thesis or Diss., Ecole centrale de Nantes, 2022. http://www.theses.fr/2022ECDN0066.
Анотація:
Nous considérons des graphes orientés pondérés dont l’énergie est paramétrée. Nous proposons dans un premier temps un algorithme qui, étant donné un graphe et un de ses sommets, renvoie des arbres, chaque arbre représentant les plus courtschemins depuis la source vers tous les autres sommets du graphe pour une zone particulière de l’espace des paramètres. De plus l’union de ces zones couvre l’espace des paramètres. Nous considérons ensuite l’accessibilité dans les graphes à énergie multidimensionnelle, avec un type de contraintes plus absolues qui imposent que l’énergie reste entre des bornes. Nous montrons la décidabilité et la complexité du problème quel que soit le nombre de paramètres et de dimensions lorsque les paramètres prennent des valeurs entières. Nous montrons également l’indécidabilité de ce problème avec au moins un paramètre lorsque la dimension est supérieure ou égale à deux. Nous étudions enfin des jeux de parité à un et deux joueurs sur les graphes paramétrés dont l’objectif est la conjonction d’une condition qualitative sur la parité et d’une condition quantitative : l’énergiedoit rester positive. Nous montrons la décidabilité et prouvons des bornes de la complexité du problème de la recherche d’une stratégie gagnante dans les cas à un et à deux joueursWe are considering weighted oriented graphs with parametrized energy. Firstly we propose an algorithm that, given a graph and one of its vertices, returns trees, every tree representing shortest-paths from the source to every other vertex for a particular zone of the parameter space. Moreover, union of these zones is a covering of the parameter space. Then we consider reachability in graphs with multi-dimensional energy, with stricter constraints that enforce the energy to stay between bounds. We prove decidabilty and complexity of this problem regardless of the dimension and the number of parameters when parameters take integer values. We alsoprove the undecidability of this problem when there is at least one parameter and the dimension is at least two. Finally we study paritygames on parametrized graphs with one and two players whose objective is the conjunction of a qualitative condition on the parity andquantitative one : energy must stay positive. We show the decidability and prove bounds on the complexity of the problem of searchinga winning strategy in both cases with one and two players
32
Laville, Aurélien. "Modélisation géométrique et mécanique du complexe musculo-squelettique du rachis cervical sous facteur de charge." Phd thesis, Paris, ENSAM, 2010. http://pastel.archives-ouvertes.fr/pastel-00553250.
Анотація:
Les progrès technologiques considérables réalisés dans le secteur aéronautique militaire ont donné naissance à des avions atteignant des niveaux d'accélération importants (9 Gz sur le Rafale). Ces accélérations, à l'origine de lésions cervicales aigües et chroniques, placent plus que jamais les tolérances biomécaniques des pilotes de chasse au centre des préoccupations. Dans le contexte de protection des personnels navigants, l'Institut de Recherche Biomédicale des Armées (IRBA) coordonne, avec le soutien de la Délégation Générale à l'Armement (DGA), un programme de recherche visant entre autres à mieux comprendre les mécanismes lésionnels impliqués. Les modèles en éléments finis constituent des outils particulièrement propices à l'analyse des risques lésionnels dans la mesure où ils offrent une information quantitative des niveaux de sollicitation des tissus. Néanmoins, aucun modèle ne permet à l'heure actuelle de prendre en compte à la fois les variabilités morphologiques interindividuelles et les tissus musculaires. Le but de cette étude est par conséquent de contribuer à l'étude des mécanismes lésionnels en proposant une approche de modélisation géométrique paramétrée et personnalisée. La méthode consiste à générer automatiquement des maillages du complexe musculo-squelettique du rachis cervical à partir de données issues d'imagerie médicale. Enrichis par des lois de comportement mécanique, ces maillages sont utilisés pour la construction de modèles en éléments finis dont les mobilités segmentaires sont validées dans un premier temps. Une étude préliminaire vise ensuite à mettre en évidence les effets de la morphologie et des tissus musculaires dans le cas des sollicitations en compression axiale qui sont récurrentes sous facteur de charge.
33
Carbonnel, Clément. "Harnessing tractability in constraint satisfaction problems." Thesis, Toulouse, INPT, 2016. http://www.theses.fr/2016INPT0118/document.
Анотація:
Le problème de satisfaction de contraintes (CSP) est un problème NP-complet classique en intelligence artificielle qui a suscité un engouement important de la communauté scientifique grâce à la richesse de ses aspects pratiques et théoriques. Cependant, au fil des années un gouffre s'est creusé entre les praticiens, qui développent des méthodes exponentielles mais efficaces pour résoudre des instances industrielles, et les théoriciens qui conçoivent des algorithmes sophistiqués pour résoudre en temps polynomial certaines restrictions de CSP dont l'intérêt pratique n'est pas avéré. Dans cette thèse nous tentons de réconcilier les deux communautés en fournissant des méthodes polynomiales pour tester automatiquement l'appartenance d'une instance de CSP à une sélection de classes traitables majeures. Anticipant la possibilité que les instances réelles ne tombent que rarement dans ces classes traitables, nous analysons également de manière systématique la possibilité de décomposer efficacement une instance en sous-problèmes traitables en utilisant des méthodes de complexité paramétrée. Finalement, nous introduisons un cadre général pour exploiter dans les CSP les idées développées pour la kernelization, un concept fondamental de complexité paramétrée jusqu'ici peu utilisé en pratique. Ce dernier point est appuyé par des expérimentations prometteusesThe Constraint Satisfaction Problem (CSP) is a fundamental NP-complete problem with many applications in artificial intelligence. This problem has enjoyed considerable scientific attention in the past decades due to its practical usefulness and the deep theoretical questions it relates to. However, there is a wide gap between practitioners, who develop solving techniques that are efficient for industrial instances but exponential in the worst case, and theorists who design sophisticated polynomial-time algorithms for restrictions of CSP defined by certain algebraic properties. In this thesis we attempt to bridge this gap by providing polynomial-time algorithms to test for membership in a selection of major tractable classes. Even if the instance does not belong to one of these classes, we investigate the possibility of decomposing efficiently a CSP instance into tractable subproblems through the lens of parameterized complexity. Finally, we propose a general framework to adapt the concept of kernelization, central to parameterized complexity but hitherto rarely used in practice, to the context of constraint reasoning. Preliminary experiments on this last contribution show promising results
34
Pham, Thi Ngoc Diem. "Spécification et conception de services d'analyse de l'utilisation d'un environnement informatique pour l'apprentissage humain." Phd thesis, Université du Maine, 2011. http://tel.archives-ouvertes.fr/tel-00689025.
Анотація:
Notre travail de recherche s'inscrit dans le cadre du projet de recherche REDiM (Réingénierie des EIAH Dirigée par les Modèles) qui porte sur la réingénierie d'un scénario pédagogique. Il se focalise plus précisément sur l'analyse de traces collectées en session par un EIAH pour fournir à l'enseignant des indicateurs calculés.Dans notre contexte de travail, UTL (Usage Tracking Language) permet de définir des indicateurs sous une forme proche des patrons de conception. Il a été conçu pour répondre aux questions de capitalisation et de réutilisation. Par contre, UTL ne disposait initialement pas de moyens pour spécifier formellement la façon de calculer l'indicateur à partir des traces collectées. De plus, les approches par développement ad hoc d'indicateurs ne permettent pas de modéliser de façon formelle la méthode de calcul. En général, les patrons de conception se limitent à la description, ils ne peuvent donc pas être automatisés. Des descriptions textuelles dans UTL pour produire un indicateur à partir des traces ne permettent pas de générer automatiquement les valeurs d'un indicateur.Notre principal objectif de recherche a donc été de définir des modèles, des méthodes et des outils pour la formalisation et l'automatisation du calcul d'indicateurs. Pour cela, nous avons élaboré une nouvelle version d'UTL qui intègre un langage de combinaison de données nommé DCL4UTL, qui permet de modéliser des indicateurs sous une forme capitalisable, automatisable et réutilisable afin de fournir des indicateurs signifiants à l'enseignant/concepteur. Ces indicateurs peuvent être calculés en temps réel ou après une session, respectivement dans un contexte de tutorat ou de réingénierie du scénario pédagogique.L'originalité de notre approche réside dans le fait que cette version permet non seulement de capitaliser des savoir-faire sur les techniques d'analyse d'usage d'un EIAH, mais aussi, avec le langage DCL4UTL (1) de décrire formellement dans une forme générique des méthodes de modélisation et de calcul d'indicateurs à partir des traces collectées par un EIAH, (2) d'intégrer des fonctions externes (qui proviennent d'autres outils d'analyse), et (3) de créer des données intermédiaires paramétrées facilitant la modélisation et la réutilisation de la méthode de calcul d'indicateurs. Nous avons également développé un outil d'analyse pour calculer les indicateurs modélisés.Cette version est le résultat d'une étude théorique et d'une analyse de l'état de l'art, mais aussi de travaux exploratoires sur la modélisation d'indicateurs et l'analyse de traces. L'approche et le langage ont été validés par plusieurs expérimentations avec plusieurs EIAH existants.
35
Couchot, Jean-François. "Vérification d'invariants de systèmes paramétrés par superposition." Besançon, 2006. http://www.theses.fr/2006BESA2100.
36
Apprato, Dominique. "Approximation de surfaces paramétrées par éléments finis." Pau, 1987. http://www.theses.fr/1987PAUU3012.
Анотація:
On considère le problème suivant : comment obtenir un approximant de classe C**(k) d'une surface S paramétrée de r**(3) à partir d'un ensemble fini de points sur S. Une méthode d'interpolation utilisant des approximations des dérivées et une méthode d'ajustement liée a la théorie des fonctions splines sont déduites de la théorie des éléments finis. On établit des majorations de l'erreur d'interpolation et des résultats de convergence dans la méthode d'ajustement. On donne des exemples d'applications et des résultats graphiques.
37
Bennouna, Jaouad. "Approximation de courbes paramétrées par éléments finis." Pau, 1987. http://www.theses.fr/1987PAUU3009.
Анотація:
On cherche a approcher des courbes de r**(n) (n = 2,3) déterminées par une représentation paramétrique. On propose une méthode d'interpolation et une méthode d'ajustement. Les problèmes étudiés interviennent notamment en conception assistée par ordinateur. Les difficultés résident dans l'absence de paramétrage naturel des points de données et dans l'obtention d'approximants de classe c**(1) ou c**(2) a partir de données de Lagrange.
38
Ayad, Ali. "Complexité de résolution de systèmes algébriques paramétrés." Rennes 1, 2006. https://tel.archives-ouvertes.fr/tel-00127383.
Анотація:
On présente trois algorithmes dans cette thèse. Le premier algorithme résout des systèmes polynomiaux homogènes et paramétrés zéro-dimensionnels avec un temps simplement exponentiel en le nombre n des inconnus. Cet algorithme décompose l'espace des paramètres en un nombre fini d'ensembles constructibles et calcule le nombre fini de solutions par des représentations rationnelles paramétriques uniformes sur chaque ensemble constructible. Le deuxième algorithme factorise absolument des polynômes multivariés paramétrés avec un temps simplement exponentiel en n et en la borne supérieure d de degrés de polynômes à factoriser. Le troisième algorithme décompose les variétés algébriques définies par des systèmes algébriques paramétrés de dimensions positives en composantes absolument irréductibles d'une manière uniforme sur les valeurs des paramètres. La complexité de cet algorithme est doublement exponentielle en n. D'autre part, la borne inférieure du problème de résolution de systèmes algébriques paramétrés est doublement exponentielle en n.
39
Diallo, Madiagne. "Réseaux de flots : flots paramétrés et tarification." Versailles-St Quentin en Yvelines, 2003. http://www.theses.fr/2003VERS0030.
Анотація:
My thesis focusses on two applications of network flow problems. We emphasize on networks modelling energy or fluid distribution and telecommunication services. We study two differents aspects:The first aspect consists of the sensitivity analysis of flows in distribution networks. That is the analysis of the effects of one or more capacity variations on the all pairs maximum flow values. Moreover, we evaluate the importance of an edge in the network. Our contributions begin with a correction of the unique method in the literature that dealed with the case of a single capacity variation. We then propose simple and efficient algorithms to solve the same case, before proposing a generalization to the case of more than one capacity variation. Our algorithms and methods are based on Gomory-Hu cut trees. Given an undirected network in which capacities lambda_1, \lambda_2, \lambda_3, \ldots \lambda_k are varying. We show that ^k Gomory-Hu cut tree computations are sufficient in order to determine the all pairs maximum flow values. As far as link importance analysis is concerned, we show that two Gomory-Hu cut tree computations are sufficient to determine the set of all vertex pairs for which any maximum flow saturates the studied link. The second aspect concerns resource allocation in a telecommunicationnetwork with an objective of demands satisfaction. To do so, we study this problem using pricing in order to handle network congestion while taking into account users behaviour and the operator's profit maximization objective. We use a bi-level programming approach to solve the problem. With an Augmented Lagrangian method, we solve the resource allocation problem by associating the Lagrangian multipliers to the network link prices. We then use the Karush-Kuhn-Tucker optimality conditions to verify about the multipliers (prices) unicity. In case the multipliers are not unique, we show that a second optimization problem over the multipliers (prices) can be solved in order to improve the network revenuLa thèse se focalise sur des applications des problèmes de flots dans des réseaux modélisant, d'une part des réseaux de distribution de fluide ou d'énergie et d'autre part des réseaux de télécommunication. Nous nous sommes intéressés à deux aspects :Le premier aspect consiste en une analyse de sensibilité des flots sur les réseaux de distribution, c'est à dire, l'étude de l'impact de la variation de la capacité d'une ou de plusieurs arêtes sur l'ensemble des valeurs de flot maximum entre toutes les paires de sommets du réseau. En outre, nous nous sommes intéressés à la rentabilité d'une arête donnée dans un réseau. Nous avons d'abord apporté des corrections à l'unique méthode qui existait dans le cas d'une capacité d'arête qui varie et nous avons proposé des algorithmes simples et efficaces pour résoudre le cas de plusieurs capacités qui varient. Nos méthodes sont basées sur les arbres de coupes de Gomory et Hu. 'Etant donné un réseau non orienté ayant capacités qui peuvent varier avec des paramètres lambda_1,\lambda_2, \lambda_3, \ldots \lambda_k, nous avons montré que 2^k calculs d'un arbre de coupes de Gomory et Hu étaient suffisants pour déterminer les valeurs de flot maximum entre toutes les paires de sommets dans le réseau. En ce qui concerne le problème de la rentabilité d'un lien, nous avons montré que juste 2 calculs d'un arbre de coupes de Gomory et Hu suffisaient pour déterminer l'ensemble des paires de sommets pour lesquelles tout flot maximum sature le lien cible. Le second aspect concerne l'allocation de ressources dans un réseau de télécommunication pour la satisfaction de requêtes d'utilisateurs. Pour ce faire, nous avons étudié ce problème par le biais de la tarification pour gérer la congestion tout en tenant compte du comportement des utilisateurs et de la volonté de profit del'opérateur. Nous avons utilisé une approche bi-niveaux pour résoudre le problème. Avec la méthode du Lagragien augmenté, nous résolvons le problème d'allocation de ressources en associant les multiplicateurs de Lagrange aux prix sur les liens du réseaux. Nous utilisons ensuite les conditions d'optimalité de Karush-Kuhn-Tucker pour vérifier si les ultiplicateurs (prix) sont uniques ou pas. Au cas de non unicité nous montrons comment on peut résoudre un deuxième problème d'optimisation sur ces multiplicateurs (prix) afin d'améliorer le revenu sur le réseau
40
Bergé, Pierre. "Algorithmes pour voyager sur un graphe contenant des blocages." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS480.
Анотація:
Nous étudions des problèmes NP-difficiles portant sur les graphes contenant des blocages.Nous traitons les problèmes de coupes du point de vue de la complexité paramétrée. La taille p de la coupe est le paramètre. Étant donné un ensemble de sources {s1,...,sk} et une cible t, nous proposons un algorithme qui construit une coupe de taille au plus p séparant au moins r sources de t. Nous nommons ce problème NP-complet Partial One-Target Cut. Notre algorithme est FPT. Nous prouvons également que la variante de Partial One-Target Cut, où la coupe est composée de noeuds, est W[1]-difficile. Notre seconde contribution est la construction d'un algorithme qui compte les coupes minimums entre deux ensembles S et T en temps $2^{O(plog p)}n^{O(1)}$.Nous présentons ensuite plusieurs résultats sur le ratio de compétitivité des stratégies déterministes et randomisées pour le problème du voyageur canadien.Nous prouvons que les stratégies randomisées n'utilisant pas de mémoire ne peuvent pas améliorer le ratio 2k+1. Nous apportons également des éléments concernant les bornes inférieures de compétitivité de l'ensemble des stratégies randomisées. Puis, nous étudions la compétitivité en distance d'un groupe de voyageurs avec et sans communication. Enfin, nous nous penchons sur la compétitivité des stratégies déterministes pour certaines familles de graphes. Deux stratégies, avec un ratio inférieur à 2k+1 sont proposées: une pour les graphes cordaux avec poids uniformes et l'autre pour les graphes où la taille de la plus grande coupe minimale séparant s et t est au plus kWe study NP-hard problems on graphs with blockages seen as models of networks which are exposed to risk of failures.We treat cut problems via the parameterized complexity framework. The cutset size p is taken as a parameter. Given a set of sources {s1,...,sk} and a target $t, we propose an algorithm which builds a small edge cut of size p separating at least r sources from t. This NP-complete problem is called Partial One-Target Cut. It belongs to the family of multiterminal cut problems. Our algorithm is fixed-parameter tractable (FPT) as its execution takes $2^{O(p^2)}n^{O(1)}$. We prove that the vertex version of this problem, which imposes cuts to contain vertices instead of edges, is W[1]-hard. Then, we design an FPT algorithm which counts the minimum vertex (S,T)-cuts of an undirected graph in time $2^{O(plog p)}n^{O(1)}$.We provide numerous results on the competitive ratio of both deterministic and randomized strategies for the Canadian Traveller Problem. The optimal ratio obtained for the deterministic strategies on general graphs is 2k+1, where k is a given upper bound on the number of blockages. We show that randomized strategies which do not use memory cannot improve the bound 2k+1. In addition, we discuss the tightness of lower bounds on the competitiveness of randomized strategies. The distance competitive ratio for a group of travellers possibly equipped with telecommunication devices is studied. Eventually, a strategy dedicated to equal-weight chordal graphs is proposed while another one is built for graphs with small maximum (s,t)-cuts. Both strategies outperform the ratio 2k+1
41
Perez, Anthony. "Algorithmes de noyau pour des problèmes d'édition de graphes et autres structures." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2011. http://tel.archives-ouvertes.fr/tel-00660089.
Анотація:
Dans le cadre de cette thèse, nous considérons la complexité paramétrée de problèmes NP- complets. Plus précisément, nous nous intéressons à l'existence d'algorithmes de noyau polynomiaux pour des problèmes d'édition de graphes et de relations. Nous introduisons en particulier la notion de branches, qui permet d'obtenir des algorithmes polynomiaux pour des problèmes d'édition de graphes lorsque la classe de graphes cible respecte une décomposition d'adjacence. Cette technique nous permet ainsi d'élaborer les premiers algorithmes de noyaux polynomiaux pour les problèmes CLOSEST 3-LEAF POWER, COGRAPH EDITION et PROPER INTERVAL COMPLETION. Concernant les problèmes d'édition de relations, nous étendons la notion de Conflict Packing, qui a déjà été utilisée dans quelques problèmes paramétrés et permet d'élaborer des algorithmes de noyau linéaires pour différents problèmes. Nous présentons un noyau linéaire pour le problème FEEDBACK ARC SET IN TOURNAMENTS, et adaptons les techniques utilisées pour obtenir un noyau linéaire pour le problème DENSE ROOTED TRIPLET INCONSISTENCY. Dans les deux cas, nos résultats améliorent la meilleure borne connue, à savoir un noyau quadratique. Finalement, nous appliquons cette tech- nique sur les problèmes DENSE BETWEENNESS et DENSE CIRCULAR ORDERING, obtenant à nouveau des noyaux linéaires, qui constituent les premiers algorithmes de noyau polynomiaux connus pour ces problèmes.
42
Chapelle, Mathieu. "Décompositions de graphes : quelques limites et obstructions." Phd thesis, Université d'Orléans, 2011. http://tel.archives-ouvertes.fr/tel-00659666.
Анотація:
Les décompositions de graphes, lorsqu'elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d'obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d'obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O^{tw+4}. La seconde partie de notre travail porte sur l'étude du problème Ensemble [Sigma,Rho]-Dominant, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d'entiers Sigma et Rho. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas où le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l'est pas toujours, et que pour certains cas d'ensembles Sigma et Rho, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d'un nouveau problème de coloration appelé k-Coloration Additive, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k >= 4 fixé, tandis qu'il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé.
43
Vignola, Emanuele. "A Theoretical Perspective on Hydrogenation and Oligomerization of Acetylene over Pd Based Catalysts." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSEN054/document.
Анотація:
L’hydrogénation sélective de l’acétylène est un processus fondamental pour l’industrie pétrochimique qui permet la purification de l’éthylène utilisé dans les réactions de polymérisation. Ce processus est promu par des catalyseurs au palladium, qui présentent une bonne sélectivité en éthylène par rapport au produit d’hydrogénation totale, c’est-à-dire l’éthane. Les catalyseurs de palladium pur sont malheureusement désactivés par des oligomères qui se forment comme sous-produits de la réaction d’hydrogénation. Les catalyseurs d’usage industriel sont, pour cette raison, plutôt des alliages de palladium avec d’autres métaux, comme par exemple, l’argent. Ces alliages réduisent la production des oligomères, sans pour autant les supprimer complètement. Ce travail de thèse a été focalisé sur la compréhension à l’échelle moléculaire de la formation de ce mélange d’oligomères, souvent appelée « huile verte ». Pour commencer, une approche de champ moyen a été développée pour déterminer rapidement l’état de la surface catalytique de l’alliage Pd-Ag en condition de réaction. Ce modèle a montré que l’acétylène est capable de réorganiser la couche de la surface et de générer des îles de palladium. Pour confirmer cette prédiction, nous avons effectué des simulations Monte Carlo en utilisant un Hamiltonien modèle. Ces calculs ont produits des résultats similaires au modèle analytique simple. Ayant attribué la formation des oligomères aux domaines de palladium ainsi obtenus, les étapes de d’oligomérisation ont été étudies et comparés à celles qui décrivent l’hydrogénation de l’acétylène. Les calculs, réalisé avec l’approximation de la théorie de la fonctionnelle de la densité (DFT), ont montré que la formation des oligomères est compétitive avec l’hydrogénation. En plus, les oligomères sont plus faciles à hydrogéner que l’acétylene et pourraient, donc, impacter négativement sur l’hydrogénation sélective de l’acétylène. Le rôle exact des îles de palladium sous conditions réalistes est encore à clarifier, sachant que le palladium est recouvert d’une grande variété d’espèces chimiques. Les techniques d’intelligence artificielle peuvent aider à atteindre ce but : nous avons ainsi démontré qu’il est possible d’interpoler les résultats des calculs DFT d’une façon automatique et de décrire l’énergie du système en série de coefficients « cluster ». Ceci permet de prendre en compte les interactions latérales entre espèces chimiques à la surface du palladiumSelective hydrogenation of acetylene in ethylene-rich flows is a fundamental process in the petrochemical industry since it allows the purification of ethylene for polymer applications. The reaction is catalyzed by Pd, which features acceptable selectivity towards ethylene compared to the total hydrogenation product, ethane. Pure Pd is, however, deactivated by oligomeric byproducts, known as ”green oil” in the literature. Therefore, most industrial catalysts are Pd-Ag alloys, where Ag helps to suppress the secondary reactions. This work addresses the formation of initial oligomers on Pd and Ag-Pd catalysts. A mean field based theoretical model was built to efficiently screen the topology of the topper most layer of the alloy catalyst under relevant conditions. This model gave evidence for strongly favored Pd island formation. To confirm this result, the system was then re-investigated by means of Monte Carlo simulations including the effect of segregation. Emergence of large domains of Pd were confirmed over large ratios of Ag to Pd. Green oil is expected to form on these catalytically active islands. To obtain a detailed view on the oligomerization process, activation energies were computed both for hydrogenation and oligomerization steps by periodic density functional theory on Pd(111). Oligomerization was found to be competitive with hydrogenation, with the hydrogenation of the oligomers being among the fastest processes. The role of Pd domains to green oil formation is still to be clarified under realistic conditions, where the surface is covered by many different species. A step forward to this goal was taken by developing a machine-learning tool which automatically interpolates model Hamiltonians on graphical lattices based on DFT computations, accounting for lateral interactions and distorted adsorption modes on crowded surfaces
44
Muller, Alexis. "Construction de systèmes par application de modèles paramétrés." Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2006. http://tel.archives-ouvertes.fr/tel-00459025.
Анотація:
L'ingénierie logicielle vise à se rationaliser toujours plus et commence à atteindre des niveaux de productivité proches d'autres domaines, mécanique ou électronique par exemple. Notre approche vise la spécification de composants métiers réutilisables et composables dans des contextes (domaines) applicatifs différents. Nous proposons d'en faire des composants de modèles génériques paramétrés eux-mêmes par des ”modèles requis” et fournissant un modèle enrichi. On dépasse ainsi la notion de contrat d'assemblage de composants souvent réduite à une interface de services unitaires. La conception d'un système revient alors à assembler de tels composants par les modèles. Nous proposons pour cela un opérateur d'application de modèles paramétrés. Celui-ci permet de spécifier des assemblages à partir d'un ensemble de composants de modèles. Nous étudions des propriétés d'ordre permettant de garantir la cohérence des alternatives de composition. Ceci conduit à des règles et contraintes au niveau des modèles, afin d'assurer la cohérence de systèmes ainsi construits. Nous formulons une méta-modélisation de l'approche par extension du méta-modèle UML2 et un ensemble de contraintes. Nous proposons également différentes stratégies de mise en œuvre, sous la forme de patron de conception, permettant de préserver, jusqu'à l'exploitation, les qualités de structuration et de généricité obtenues au niveau modèle. Des projections ont été expérimentées sur différentes plates-formes à composants.
45
Netto, Mariana Schiavo. "La commande adaptative de systèmes non-linéairement paramétrés." Paris 11, 2001. http://www.theses.fr/2001PA112320.
Анотація:
Cette thèse s'articule autour de trois parties principales. Une première partie étudie un problème d'asservissement visuel d'un robot planaire à l'aide d'une caméra. Nous en proposons deux différentes solutions. La deuxième partie est consacrée à l'étude de l'usage de la propriété de convexité pour la commande adaptative des systèmes non-linéairement paramétrés. D'abord nous étudions une classe de systèmes présentés par Boskovic. Une reparamétrisation capable de rendre la non-linéarité convexe est proposée. Un contrôleur connu est alors appliqué au système paramétré de façon convexe. Une étude comparative est faite entre le contrôleur présenté dans cette thèse et celui proposé par Boskovic. Nous avons ensuite étendu cette démarche de reparamétrisation convexifiante à une classe plus générale de paramétrisations non-linéaires. Le nouveau résultat est alors appliqué pour la commande adaptative de processus de fermentation fed-batch. .The contents of the thesis are divided into three main parts as follows. The first part treats the visual servoing problem, consisting of the control of the motion of a two-links planar robot manipulator by a fixed TV camera. We propose two different solutions to solve the problem. The second main part is devoted to the study of the use of the convexity property in the adaptive control of nonlinearly parametrized plants. We first treat a class of plants considered by Boskovic. We propose a reparametrization that convexifies the nonlinearity. We then apply a known controller to the convexly-parametrized system. We provide then a comparison between the controller applied to the reparametrized plant and the controller by Boskovic. The next step was to extend this convexifying reparametrization to a more general class of nonlinear parametrizations. This new result is used for the adaptative control of fed-batch fermentation processes. .
46
Traonouez, Louis-Marie. "Vérification et dépliages de réseaux de Petri temporels paramétrés." Phd thesis, Université de Nantes, 2009. http://tel.archives-ouvertes.fr/tel-00466429.
Анотація:
Les travaux présentés portent sur l'étude de méthodes de vérification paramétrée des systèmes temps réels. La motivation pour ces recherches est de proposer des méthodes formelles à appliquer sur des systèmes dont les spécifications ne sont pas encore complètes. Des paramètres sont donc introduits dans les modèles utilisés afin de donner des degrés de liberté à la modélisation. Le but est alors de guider la conception du système en déterminant des valeurs satisfaisantes pour les paramètres.
Nous nous sommes focalisé sur les paramètres temporels qui sont en général parmi les plus complexes à définir. Nous avons ainsi défini le modèle des réseaux de Petri à chronomètres paramétrés.
Dans une première approche, nous étendons les méthodes d'analyse classiquement utilisées dans les réseaux de Petri temporels. L'espace d'états du modèle paramétré est ainsi représenté par le graphe des classes d'états paramétrées. Cela nous permet de proposer des semi-algorithmes de model-checking paramétré avec lesquels nous vérifions des formules de logique TCTL paramétrées.
Dans une seconde approche, nous étudions les méthodes qui préservent le parallélisme des réseaux de Petri. L'intérêt est de limiter l'explosion combinatoire qui apparaît lors de l'analyse de systèmes distribués, en particulier avec des modèles paramétrés. Nous proposons pour cela une méthode de dépliage temporel paramétré. Ce dépliage est a priori infini, mais nous proposons de l'utiliser pour résoudre un problème de supervision. La construction du dépliage est alors guidée par des observations finies, et nous extrayons les explications de ces observations, ainsi que les contraintes sur les paramètres qu'elles induisent.
47
Malaval, Jean-Louis. "Outils de CAO paramétrés pour la conduite de processus." Montpellier 2, 1987. http://www.theses.fr/1987MON20239.
Анотація:
Etude d'une chaine de tranduction de grafcet dans laquelle l'analyseur synthaxique est decrit par l'automate des diagrammes synthaxiques et autogenere par la chaine elle meme, en cas d'extension du langage
48
Mebsout, Alain. "Inférence d'invariants pour le model checking de systèmes paramétrés." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112188/document.
Анотація:
Cette thèse aborde le problème de la vérification automatique de systèmesparamétrés complexes. Cette approche est importante car elle permet de garantircertaines propriétés sans connaître a priori le nombre de composants dusystème. On s'intéresse en particulier à la sûreté de ces systèmes et on traitele côté paramétré du problème avec des méthodes symboliques. Ces travauxs'inscrivent dans le cadre théorique du model checking modulo théories et ontdonné lieu à un nouveau model checker : Cubicle.Une des contributions principale de cette thèse est une nouvelle technique pourinférer des invariants de manière automatique. Le processus de générationd'invariants est intégré à l'algorithme de model checking et permet de vérifieren pratique des systèmes hors de portée des approches symboliquestraditionnelles. Une des applications principales de cet algorithme estl’analyse de sûreté paramétrée de protocoles de cohérence de cache de tailleindustrielle.Enfin, pour répondre au problème de la confiance placée dans le model checker,on présente deux techniques de certification de notre outil Cubicle utilisantla plate-forme Why3. La première consiste à générer des certificats dont lavalidité est évaluée de manière indépendante tandis que la seconde est uneapproche par vérification déductive du cœur de CubicleThis thesis tackles the problem of automatically verifying complexparameterized systems. This approach is important because it can guarantee thatsome properties hold without knowing a priori the number of components in thesystem. We focus in particular on the safety of such systems and we handle theparameterized aspect with symbolic methods. This work is set in the theoreticalframework of the model checking modulo theories and resulted in a new modelchecker: Cubicle.One of the main contribution of this thesis is a novel technique forautomatically inferring invariants. The process of invariant generation isintegrated with the model checking algorithm and allows the verification inpractice of systems which are out of reach for traditional symbolicapproaches. One successful application of this algorithm is the safety analysisof industrial size parameterized cache coherence protocols.Finally, to address the problem of trusting the answer given by the modelchecker, we present two techniques for certifying our tool Cubicle based on theframework Why3. The first consists in producing certificates whose validity canbe assessed independently while the second is an approach by deductiveverification of the heart of Cubicle
49
Conversy, Stéphane. "Conception d'icones auditives paramétrées pour les interfaces homme-machine." Paris 11, 2000. http://www.theses.fr/2000PA112174.
Анотація:
Nos travaux concernent l'utilisation de sons non-parles dans les interfaces utilisateurs. Nous utilisons le fait que les sons peuvent apporter des informations par le biais de dimensions ecologiques, suivant en cela les preceptes de l'approche ecologique de la perception. Nous proposons que les sons construits a partir de sons elementaires possedent eux aussi des dimensions de haut-niveau pouvant etre vecteurs d'informations. Ils sont donc candidats a une utilisation dans l'interface. En stipulant que le spectre d'un son est moins important que les invariants qu'il contient, nous proposons d'utiliser une methode de synthese ad-hoc en temps reel pour creer des sons de vent, de vagues, de bouillonnement et d'ascenseur. La synthese ad-hoc, si elle ne genere pas des sons realistes, prend en compte les dimensions ecologiques de l'evenement sonore, et permet leur integration dans l'interface. De plus, les sons synthetises de cette maniere peuvent etre inclus dans un son plus complexe possedant ses propres invariants. Dans un son complexe, le realisme des sons simples n'est pas un facteur critique, et leur conception par synthese ad-hoc est adequate. Nous avons concu un outil, sofa, qui permet de creer ces sons en donnant notamment acces a un ordonnanceur et au reseau d'algorithmes composant le son. En utilisant des programmes de script, nous montrons comment reproduire des comportements complexes de sons de base comme le vent, ou des comportements de sons simples pour generer un son complexe comme le son de bouillonnement. Cet outil inclut un serveur d'icones auditives et propose un modele structure permettant le positionnement en deux dimensions et l'heritage d'attributs. Le serveur se sert des icones auditives concues avec sofa que le programmeur peut utiliser de facon intuitive. Nous donnons des exemples de suivi d'activites d'arriere-plan avec des icones auditives parametrees, pour lesquels l'usage de sons continus est approprie.
50
Du, Cauzé De Nazelle Paul. "Paramétrage de formes surfaciques pour l'optimisation." Thesis, Ecully, Ecole centrale de Lyon, 2013. http://www.theses.fr/2013ECDL0008/document.
Анотація:
Afin d’améliorer la qualité des solutions proposées par l’optimisation dans les processus de conception, il est important de se donner des outils permettant à l’optimiseur de parcourir l’espace de conception le plus largement possible. L’objet de cette Thèse est d’analyser différentes méthodes de paramétrage de formes surfaciques d’une automobile en vue de proposer à Renault un processus d’optimisation efficace. Trois méthodes sont analysées dans cette Thèse. Les deux premières sont issues de l’existant, et proposent de mélanger des formes, afin de créer de la diversité. Ainsi, on maximise l’exploration de l’espace de conception, tout en limitant l’effort de paramétrage des CAO. On montre qu’elles ont un fort potentiel, mais impliquent l’utilisation de méthodes d’optimisation difficiles à mettre en œuvre aujourd’hui. La troisième méthode étudiée consiste à exploiter la formulation de Koiter des équations de coques, qui intègre paramètres de forme et mécanique, et de l’utiliser pour faire de l’optimisation de forme sur critères mécaniques. Cette méthode a par ailleurs pour avantage de permettre le calcul des gradients. D’autre part, nous montrons qu’il est possible d’utiliser les points de contrôles de carreaux de Bézier comme paramètres d’optimisation, et ainsi, de limiter au strict nécessaire le nombre de variables du problème d’optimisation, tout en permettant une large exploration de l’espace de conception. Cependant, cette méthode est non-standard dans l’industrie et implique des développements spécifiques, qui ont été réalisés dans le cadre de cette Thèse. Enfin, nous mettons en place dans cette Thèse les éléments d’un processus d’optimisation de forme surfaciqueTo improve optimized solutions quality in the design process, it is important to provide the optimizer tools to navigate the design space as much as possible. The purpose of this thesis is to analyze different parametrization methods for automotive surface shapes, in order to offer Renault an efficient optimization process. Three methods are analyzed in this thesis. The first two are closed to the existing ones, and propose to blend shapes to create diversity. Thus, we are able to maximize the exploration of the design space, while minimizing the effort for CAD setting. We show their high potential, but they involve the use of optimization methods difficult to implement today. The third method is designed to exploit the formulation of Koiter shell equations, which integrates mechanical and shape parameters, and to use it to perform shape optimization with respect to different mechanical criteria. This method also has the advantage of allowing the gradients calculation. On the other hand, we show that it is possible to use the Bezier’s control points as optimization parameters, and thus control the minimum number of variables necessary for the optimization problem, while allowing a broad exploration of the design space. However, this method is non-standard in the industry and involves specific developments that have been made in the context of this thesis. Finally, we implement in this thesis essentials elements of an optimization process for surface shapes