Teses / dissertações sobre o tema "Statistiques combinatoires"
Siga este link para ver outros tipos de publicações sobre o tema: Statistiques combinatoires.
Crie uma referência precisa em APA, MLA, Chicago, Harvard, e outros estilos
Veja os 50 melhores trabalhos (teses / dissertações) para estudos sobre o assunto "Statistiques combinatoires".
Ao lado de cada fonte na lista de referências, há um botão "Adicionar à bibliografia". Clique e geraremos automaticamente a citação bibliográfica do trabalho escolhido no estilo de citação de que você precisa: APA, MLA, Harvard, Chicago, Vancouver, etc.
Você também pode baixar o texto completo da publicação científica em formato .pdf e ler o resumo do trabalho online se estiver presente nos metadados.
Veja as teses / dissertações das mais diversas áreas científicas e compile uma bibliografia correta.
1
Kasraoui, Anisse. "Études combinatoires sur les permutations et partitions d'ensemble". Phd thesis, Université Claude Bernard - Lyon I, 2009. http://tel.archives-ouvertes.fr/tel-00393631.
Texto completo da fonteResumo:
Cette thèse regroupe plusieurs travaux de combinatoire énumérative sur les permutations et permutations d'ensemble. Elle comporte 4 parties.Dans la première partie, nous répondons aux conjectures de Steingrimsson sur les partitions ordonnées d'ensemble. Plus précisément, nous montrons que les statistiques de Steingrimsson sur les partitions ordonnées d'ensemble ont la distribution euler-mahonienne. Dans la deuxième partie, nous introduisons et étudions une nouvelle classe de statistiques sur les mots : les statistiques "maj-inv". Ces dernières sont des interpolations graphiques des célèbres statistiques "indice majeur" et "nombre d'inversions". Dans la troisième partie, nous montrons que la distribution conjointe des statistiques"nombre de croisements" et "nombre d'imbrications" sur les partitions d'ensemble est symétrique. Nous étendrons aussi ce dernier résultat dans le cadre beaucoup plus large des 01-remplissages de "polyominoes lunaires".La quatrième et dernière partie est consacrée à l'étude combinatoire des q-polynômes de Laguerre d'Al-Salam-Chihara. Nous donnerons une interprétation combinatoire de la suite de moments et des coefficients de linéarisations de ces polynômes.
2
Manouvrier, Jean-François. "Méthode de décomposition pour résoudre des problèmes combinatoires sur les graphes". Compiègne, 1998. http://www.theses.fr/1998COMP1152.
Texto completo da fonteResumo:
Les travaux de cette thèse utilisent une méthode de décomposition pour résoudre des problèmes combinatoires NP-difficiles énoncés sous la forme de problèmes de graphes. Parmi les méthodes exactes existantes, les méthodes utilisant une décomposition-arbre du graphe permettent de résoudre certains problèmes NP-difficiles en temps polynomial pour un graphe de largeur-arbre inferieur à K. K est une constante fixée en fonction du problème et des capacités de la machine utilisée. Nous nommons ces méthodes de programmation dynamique : méthodes de décomposition. Dans cette thèse, nous utilisons une décomposition-chemin du graphe, basée sur une numérotation linéaire des sommets du graphe, pour résoudre certains problèmes NP-difficiles. Les problèmes que nous avons ainsi traites sont les problèmes de la fiabilité des réseaux (fiabilité tous-terminaux et fiabilité 2-arête-connexe tous-terminaux), le problème du voyageur de commerce et le problème de l'arbre de Steiner minimal. Pour chacun de ces problèmes, nous étudions les autres méthodes existantes, nous démontrons que la méthode de décomposition peut être appliquée, en modélisant des classes d'équivalences regroupant des solutions partielles, et nous analysons l'implémentation de ces méthodes. Une des difficultés essentielles de l'implémentation des programmes de décomposition consiste à gérer efficacement en mémoire les classes. Pour la fiabilité 2-arête-connexe tous-terminaux, la structure des classes nous a contraints à introduire un concept de forêts fictives et à développer un algorithme énumérant ces forêts. Nous obtenons ainsi des algorithmes de décomposition résolvant ces problèmes, dont les complexités en temps sont linéaires en fonction de la taille du graphe pour des graphes de largeur-chemin bornée.
3
Briend, Simon. "Inference of the past of random structures and other random problems". Electronic Thesis or Diss., université Paris-Saclay, 2024. http://www.theses.fr/2024UPASM013.
Texto completo da fonteResumo:
Cette thèse est décomposée en trois parties disjointes. Les deux premières parties se concentrent sur des modèles de graphes aléatoires croissants de manière dynamique. Dans la première partie, nous inférons des informations sur le passé d'un graphe à partir d'une unique observation dudit graphe. Nous commençons par le problème de la recherche de racine, où l'objectif est de trouver un ensemble de confiance pour la racine. Nous proposons une méthode pour les L-dags uniformes et analysons ses performances. À notre connaissance, il s'agit de la première méthode réalisant une archéologie du graphe dans des graphes généraux. Nous étendons ensuite naturellement la question de la recherche de racine à celle de la sériation. Étant donné un instantané d'un graphe, est-il possible de récupérer son ordre complet ? Nous présentons une méthode et une garantie statistique sur sa qualité dans le cas des arbres récursifs uniformes et des arbres d'attachement préférentiel linéaire. Pour conclure la section sur l'archéologie de graphe, nous étudions un problème de broadcasting, où l'on ne tente pas de retrouver la racine du graphe mais son état. Dans de tels problèmes, la racine se voit attribuer un bit, qui est ensuite propagé de manière bruité lors de la croissance du réseau. Dans les L-dags, nous étudions un vote par majorité pour estimer le bit de la racine et identifions trois régimes, dépendants du niveau de bruit. Dans la deuxième partie, nous étudions l'arbre d'amitié aléatoire, qui est un modèle d'arbre récursif aléatoire avec redirection complète. Dans ce modèle apparaît un phénomène de rich-get-richer, mais à la différence du modèle d'attachement préférentiel celui ci découle d'un processus d'attachement local. Nous prouvons des conjectures sur la distribution des degrés, le diamètre et la structure locale. Enfin, nous plongeons dans le monde de l'apprentissage automatique théorique et de l'analyse de données. Nous étudions une approximation aléatoire de la profondeur de Tukey. La profondeur de Tukey est un outil puissant pour la visualisation des données et peut être considérée comme une extension des quantiles en dimension plus élevée (ils coïncident en dimension 1). Son calcul exact est NP-difficile, et nous étudions les performances d'une approximation aléatoire dans le cas de données échantillonnées à partir d'une distribution log-concaveThis thesis is decomposed in three disjoint parts. The first two parts delve into dynamically growing networks. In the first part, we infer information about the past from a snapshot of the graph. We start by the problem of root finding, where the goal is to find confidence set for the root. We propose a method for uniform L-dags and analyse its performance. It is, to the best of our knowledge, the first method achieving network archaeology in general graphs. Then, we naturally extend the question of root finding to the one of seriation. Given a snapshot of a graph, is it possible to retrieve its whole ordering? We present a method and statistical guarantee of its quality in the case of uniform random recursive trees and linear preferential attachment tree. To conclude the network archaeology section, we study the root bit finding problem, where one does not try to infer the position of the root but its state. In such problems, the root is assigned a bit and is then propagated through a noisy channel during network growth. In the L-dag, we study majority voting to infer the bit of the root and we identify three different regimes depending on the noise level. In the second part of this thesis, we study the so called friendship tree, which is a random recursive tree model with complete redirection. This model display emerging properties, but unlike in the preferential attachment model they stem from a local attachment rule. We prove conjectures about degree distribution, diameter and local structure. Finally, we delve into the world of theoretical machine learning and data analysis. We study a random approximation of the Tukey depth. The Tukey depth is a powerful tool for data visualization and can be thought of as an extension of quantiles in higher dimension (they coincide in dimension 1). Its exact computation is NP-hard, and we study the performances of a classical random approximation in the case of data sets sampled from log-concave distribution
4
Gouraud, Sandrine-Dominique. "Utilisation des Structures Combinatoires pour le Test Statistique". Phd thesis, Université Paris Sud - Paris XI, 2004. http://tel.archives-ouvertes.fr/tel-00011191.
Texto completo da fonteResumo:
Cette thèse propose une nouvelle approche pour le test statistique delogiciel à partir d'une description graphique des comportements du
système à tester (graphe de contrôle, statecharts). Son originalité
repose sur la combinaison de résultats et d'outils de combinatoire
(génération aléatoire de structures combinatoires) et d'un solveur de
contraintes, pour obtenir une méthode de test complètement automatisée.
Contrairement aux approches classiques qui tirent des entrées, la
génération aléatoire uniforme est utilisée pour tirer des chemins parmi
un ensemble de chemins d'exécution ou de traces du système à tester.
Puis, une étape de résolution de contraintes est utilisée pour
déterminer les entrées qui permettront d'exécuter ces chemins.
De plus, nous montrons comment les techniques de programmation
linéaire peuvent améliorer la qualité d'un ensemble de tests.
Une première application a été effectuée pour le test statistique
structurel défini par Thévenod-Fosse et Waeselynck (LAAS) et un
prototype a été développé.
Des expériences (plus de 10000 réalisées sur quatre fonctions issues
d'un logiciel industriel) ont été effectuées pour évaluer notre approche
et sa stabilité.
Ces expériences montrent que notre approche est comparable à celle
du LAAS, est stable et a l'avantage d'être complètement automatisée.
Ces premières expériences nous permettent également d'envisager un
passage à l'échelle de notre approche. Plus généralement, ces travaux
pourraient servir de base pour une nouvelle classe d'outils dans le
domaine du test de logiciel, combinant génération aléatoire de
structures combinatoires, techniques de programmation linéaire et
résolution de contraintes.
5
Oudinet, Johan. "Approches combinatoires pour le test statistique à grande échelle". Paris 11, 2010. http://www.theses.fr/2010PA112347.
Texto completo da fonteResumo:
Cette thèse porte sur le développement de méthodes combinatoires pour le test et la vérification formelle. En particulier, sur des approches probabilistes lorsque la vérification exhaustive n'est plus envisageable. Dans le cadre du test (basé sur un modèle), je cherche à guider l'exploration aléatoire du modèle afin de garantir une bonne satisfaction du critère de couverture attendu, quelle que soit la topologie sous-jacente du modèle exploré. Dans le cadre du model-checking, je montre comment générer aléatoirement un nombre fini de chemins pour savoir si une propriété est satisfaite avec une certaine probabilité. Dans une première partie, je compare différents algorithmes pour générer uniformément des chemins dans un automate. Puis je propose un nouvel algorithme qui offre un bon compromis avec une complexité en espace sous-linéaire en la longueur des chemins et une complexité quasi-linéaire en temps. Cet algorithme permet l'exploration d'un modèle de plusieurs dizaines de millions d'états en y générant des chemins de plusieurs centaines de milliers de transitions. Dans une seconde partie, je présente une manière de combiner réduction par ordres partiels et génération à la volée pour explorer des systèmes concurrents sans construire le modèle global, mais en s'appuyant uniquement sur les modèles des composants. Enfin, je montre comment biaiser les algorithmes précédents pour satisfaire d'autres critères de couverture. Lorsque ces critères ne sont pas basés sur des chemins, mais un ensemble d'états ou de transitions, nous utilisons une solution mixte pour assurer à la fois un ensemble varié de moyens d'atteindre ces états ou transitions et la satisfaction du critère avec une bonne probabilitéThis thesis focuses on the development of combinatorial methods for testing and formal verification. Particularly on probabilistic approaches because exhaustive verification is often not tractable for complex systems. For model-based testing, I guide the random exploration of the model to ensure a satisfaction with desired probability of the expected coverage criterion, regardless of the underlying topology of the explored model. Regarding model-checking, I show how to generate a random number of finite paths to check if a property is satisfied with a certain probability. In the first part, I compare different algorithms for generating uniformly at random paths in an automaton. Then I propose a new algorithm that offers a good compromise with a sub-linear space complexity in the path length and a almost-linear time complexity. This algorithm allows the exploration of large models (tens of millions of states) by generating long paths (hundreds of thousands of transitions). In a second part, I present a way to combine partial order reduction and on-the-fly generation techniques to explore concurrent systems without constructing the global model, but relying on models of the components only. Finally, I show how to bias the previous algorithms to satisfy other coverage criteria. When a criterion is not based on paths, but on a set of states or transitions, we use a mixed solution to ensure both various ways of exploring those states or transitions and the criterion satisfaction with a desired probability
6
Huynh, Cong Bang. "Une promenade aléatoire entre combinatoire et mécanique statistique". Thesis, Université Grenoble Alpes (ComUE), 2019. http://www.theses.fr/2019GREAM026/document.
Texto completo da fonteResumo:
Cette thèse se situe à l'interface entre combinatoire et probabilités,et contribue à l'étude de différents modèles issus de la mécanique statistique : polymères, marches aléatoires inter-agissantes ou en milieu aléatoire, cartes aléatoires. Le premier modèle que nous étudions est une famille de mesures de probabilités sur les chemins auto-évitants de longueur infinie sur un réseau régulier, construites à partir de marches aléatoires biaisées sur l'arbre des chemins auto-évitants finis. Ces mesures, introduites par Beretti et Sokal, existent pour tout biais strictement supérieur à l'inverse de la constante de connectivité, et leur limite en ce biais critique serait l'un des définitions naturelles de la marche aléatoire uniforme en longueur infinie. Le but de ce travail, en collaboration avec Vincent Beffara, est de comprendre le lien entre cette limite, si elle existe, et d'autres chemins aléatoires notamment la mesure de Kesten (qui est la limite faible de la marche auto-évitante uniforme dans le demi-plan) et les interfaces de percolation de Bernoulli critique; d'une certaine façon le modèle constitue une interpolation entre les deux. Dans une deuxième partie, nous considérons des marches aléatoires en conductances aléatoires sur un arbre quelconque, dans le cas où la loi des conductances est à queue lourde. L’objectif de notre travail, en collaboration avec Andrea Collevecchio et Daniel Kious, est de montrer une transition de phase par rapport au paramètre de la queue; on exprime le paramètre critique comme une fonction explicite de l'arbre sous-jacent. Parallèlement, nous étudions des modèles de marches aléatoires excitées sur des arbres et leurs transitions de phase. En particulier, nous étendons une conjecture de Volkov et généralisons des résultats de Bas devant et Singh. Enfin, une troisième partie en collaboration avec Vincent Beffara et Benjamin Lévêque porte sur les cartes aléatoires en genre supérieur : nous montrons l'existence de limites d'échelle, le long de sous-suites, pour les triangulations simples uniformes sur le tore, étendant à ce cas les résultats d'Adario-Berri et Albenque (sur les triangulations simples de la sphère) et de Bettinelli (sur les quadrangulations du tore). La question de l'unicité de la limite et de son universalité restent ouvertes, mais nous obtenons des résultats partiels dans ce sensThis thesis is at the interface between combinatorics and probability,and contributes to the study of a few models stemming from statisticalmechanics: polymers, self-interacting random walks and random walks inrandom environment, random maps.bigskipThe first model that we investigate is a one-parameter family ofprobability measures on self-avoiding paths of infinite length on aregular lattice, constructed from biased random walks on the tree offinite self-avoiding paths. These measures, initially introduced byBeretti and Sokal, exist for every bias larger than the inverseconnectivity constant, and their limit at the critical bias would beaamong the natural definitions of the uniform self-avoiding walk ofinfinite length. The aim of our work, in collaboration with VincentBeffara, is to understand the link between this limit, if it indeedexists, and other random infinite paths such as Kesten's measure(which is the weak limit of uniformly random finite self-avoidingwalks in the half-plane) and critical Bernoulli percolationinterfaces; the model can be seen as an interpolation between thesetwo.In a second part, we consider random walks with random conductances ona tree, in the case when the law of the conductances has heavy tail.Our aim, in collabration with Andrea Collevecchio and Daniel Kious, isto show a phase transition in the tail parameter; we express thecritical point as an explicit function of the underlying tree.In parallel, we study excited random walks on trees and their phasetransitions: we extend a conjecture of Volkov's and generalize resultsby Basdevant and Singh.Finally, a third part in collaboration with Vincent Beffara andBenjamin Lévêque contributes to the study of random maps of highergenus: we show the existence of subsequential scaling limits foruniformly random simple triangulations of the torus, extending to thatsetup fromer results by Adario-Berri and Albenque (on simpletriangulations of the sphere) and by Bettinelli (on quadrangulationsof the torus). The question of uniqueness and universality of thelimit remain open, but we obtain partial results in that direction
7
Krauth, Werner. "Physique statistique des réseaux de neurones et de l'optimisation combinatoire". Phd thesis, Université Paris Sud - Paris XI, 1989. http://tel.archives-ouvertes.fr/tel-00011866.
Texto completo da fonteResumo:
Dans la première partie nous étudions l'apprentissage et le rappel dans des réseaux de neurones à une couche (modèle de Hopfield). Nous proposons un algorithme d'apprentissage qui est capable d'optimiser la 'stabilité', un paramètre qui décrit la qualité de la représentation d'un pattern dans le réseau. Pour des patterns aléatoires, cet algorithme permet d'atteindre la borne théorique de Gardner. Nous étudions ensuite l'importance dynamique de la stabilité et d'un paramètre concernant la symétrie de la matrice de couplages. Puis, nous traitons le cas où les couplages ne peuvent prendre que deux valeurs (inhibiteur, excitateur). Pour ce modèle nous établissons les limites supérieures de la capacité par un calcul numérique, et nous proposons une solution analytique. La deuxième partie de la thèse est consacrée à une étude détaillée - du point de vue de la physique statistique - du problème du voyageur de commerce. Nous étudions le cas spécial d'une matrice aléatoire de connexions. Nous exposons la théorie de ce problème (suivant la méthode des répliques) et la comparons aux résultats d'une étude numérique approfondie.
8
Cabon, Bertrand. "Problèmes d'optimisation combinatoire : évaluation de méthodes de la physique statistique". Toulouse, ENSAE, 1996. http://www.theses.fr/1996ESAE0024.
Texto completo da fonteResumo:
Nous abordons dans cette thèse trois approches pour la résolution de problèmes combinatoires difficiles. Nous montrons comment les méthodes du Recuit Simulé et de l'Approximation de Champ Moyen, issues de la Physique Statistique, peuvent être utilisées pour résoudre des problèmes d'optimisation discrète. Nous présentons également, dans le cadre CSP (Constraint Satisfaction Problems), des méthodes exactes de résolution sur le principe du "Branch and Bound". Les comportements de ces approches sont comparés sur différents problèmes combinatoires difficiles tels que le recalage d'images satellites, le problème d'allocation de f'équences radio, ou des problèmes CSP aléatoires. Enfin, nous montrons comment la méthode du Champ Moyen peut accélérer une méthode de type Branch and Bound en lui fournissant une bonne affectation initiale et deux heuristiques d'ordonnancement des variables et des valeurs. Nous présentons des résultats expérimentaux sur des problèmes CSP générés aléatoirement.
9
Bouttier, Jérémie. "Physique statistique des surfaces aléatoires et combinatoire bijective des cartes planaires". Phd thesis, Université Pierre et Marie Curie - Paris VI, 2005. http://tel.archives-ouvertes.fr/tel-00010651.
Texto completo da fonteResumo:
Les cartes sont des objets combinatoires apparaissant en physique comme discrétisation naturelle des surfaces aléatoires employées pour la gravité quantique bidimensionnelle ou la théorie des cordes, ainsi que dans les modèles de matrices. Après rappel de ces relations, nous établissons des correspondances entre diverses classes de cartes et d'arbres, autres objets combinatoires de structure simple. Un premier intérêt mathématique de ces constructions est de donner des preuves bijectives, élémentaires et rigoureuses, de plusieurs résultats d'énumération de cartes. Par ailleurs, nous accédons ainsi à une information fine sur la géométrie intrinsèque des cartes, conduisant à des résultats analytiques exacts grâce à une propriété inattendue d'intégrabilité. Nous abordons enfin la question de l'existence d'une limite continue universelle.
10
Dasse-Hartaut, Sandrine. "Combinatoire des tableaux escalier". Paris 7, 2014. http://www.theses.fr/2014PA077070.
Texto completo da fonteResumo:
Les tableaux escalier sont des objets combinatoires définis par S. Corteel et L. Williams, qui généralisent les tableaux de permutations et les tableaux alternatifs. Ils ont été utilisés pour donner une formule combinatoire pour les moments des polynômes d'Askey-Wilson. Les tableaux escalier sont également liés au processus d'exclusion asymétrique sur un réseau unidimensionnel avec bords ouverts, l'ASEP, un modèle de physique statistique important et sujet de nombreuses études, et ont permis de donner une formule combinatoire pour en exprimer la probabilité stationnaire. On montre ici différentes approches des tableaux escalier : une approche probabiliste permet d'en déduire des propriétés exactes et asymptotiques, une approche bijective permet de découvrir des propriétés de sous-ensembles de ces tableaux, via les tree-like tableaux ou des tables d'inversion. Enfin, une chaîne de Marov sur un sous-ensemble des tableaux escalier confirme intuitivement les formules obtenues par le calcul de la probabilité stationnaire du PASEPA relatively new combinatorial structure, called staircase tableaux, was introduced in recent work of S. Corteel and L. Williams. Staircase tableaux are a generalisation of permutation tableaux and alternative tableaux. Their study gave a combinatorial formula for the moments of Askey-Wilson polynomials. Staircase tableaux are also related to the asymmetric exclusion process on a one-dimensional lattice with open boundaries (ASEP), an important and heavily studied particle model in statistical mechanics. The study of the generating function of the staircase tableau has given a combinatorial formula for the steady state probability of the ASEP. We use differents approaches to study the staircase tableaux : with a probabilistic approach, we prove the asymptotic normality of some parameters of the staircase tableaux ; with bijective combinatorics, we get the properties of some subsets of staircase tableaux, using for example tree-like tableaux or permutations. Finally, a Markov chain on a subset of staircase tableaux confirms intuitively the formula for the steady state probability without using the matrix ansatz
11
Berry, Vincent. "Méthodes et algorithmes pour reconstruire les arbres de l'Evolution". Montpellier 2, 1997. http://www.theses.fr/1997MON20246.
Texto completo da fonteResumo:
Nous proposons des methodes pour retrouver l'histoire evolutive des especes. Cette histoire est representee sous la forme d'un arbre dont les differentes aretes (branches) designent les differents groupes d'especes. Nous nous attachons plus particulierement ici a proposer une estimation robuste de cet arbre, i. E. , a ne proposer que des aretes fiables, quitte a ne retrouver qu'une partie de l'histoire des especes. Les methodes que nous proposons se divisent en deux categories : les methodes descendantes partent d'une topologie complete de laquelle elles enlevent les aretes non sures ; les methodes ascendantes inferent d'emblee une phylogenie ne contenant que des aretes jugees fiables. Les methodes descendantes que nous proposons reposent sur la technique du bootstrap (un procede de reechantillonnage). Les methodes ascendantes que nous proposons reposent sur un principe d'optimisation combinatoire lie aux quadruplets d'especes : on infere d'abord des phylogenies sur quatre especes, qu'on cherche ensuite a combiner en une phylogenie sur l'ensemble des especes, de facon a optimiser un certain critere. Diverses simulations montrent que les methodes ascendantes et descendantes que nous proposons obtiennent de meilleurs resultats que les methodes habituellement utilisees pour reconstruire l'arbre d'evolution des especes.
12
Herrbach, Claire. "Etude algorithmique et statistique de la comparaison des structures secondaires d'ARN". Bordeaux 1, 2007. http://www.theses.fr/2007BOR13432.
Texto completo da fonteResumo:
Notre travail s'inscrit dans la problématique de la comparaison de structures d'ARN. Nous étudions en particulier le cas des structures secondaires sans pseudo-noeud, qu'il est possible de modéliser par des arbres ordonnés étiquetés. Il existe des algorithmes polynomiaux d'édition et d'alignement d'arbres. Cependant, les opérations d'édition utilisées par ces algorithmes ne sont pas adaptées pour l'ARN. D'un autre côté, il a été montré que si l'on utilise un jeu d'opérations réalistes d'un point de vue biologique, le problème de l'édition de structures secondaires sans pseudo-noeud est NP-complet. Dans cette thèse, nous étudions le problème de l'alignement, avec ce même jeu d'opérations réaliste, de structures secondaires d'ARN sans pseudo-noeud. Nous proposons un algorithme polynomial d'alignement global et ses variantes d'alignement local et de recherche d'un motif structurel. Puis nous montrons que cet algorithme, et par le même coup l'algorithme classique d'alignement d'arbres ordonnés, a une complexité moyenne en O(n2). Nous avons implanté notre algorithme d'alignement ainsi que ses variantes afin de comparer notre approche aux outils déjà existants, et nous présentons quelques résultats. Nous présentons ensuite un travail préliminaire sur la construction de matrices de scores pour chaque opération d'édition réaliste pour l'ARN. Enfin, nous étudions le problème de sous-structures secondaires communes à un ensemble de structures tertiaires d'ARN, de façon à maximiser le nombre d'empilements. Nous montrons que dans le cas général, ce problème est NP-complet. Cependant, nous donnons un algorithme polynomial dans le cas où le nombre de structures en entrée est fixé.
13
Rouat, Valérie. "Validité de l'approche classification dans la réduction statistique de la complexité de #SAT". Rennes 1, 1999. http://www.theses.fr/1999REN10021.
Texto completo da fonteResumo:
Le problème abordé dans cette thèse est celui du dénombrement des solutions du problème de la satisfiabilité d'une formule booléenne sous forme normale conjonctive (problème #SAT). Ce problème est #P-complet et les résultats actuels montrent que la résolution de #SAT, même approchée, est, dans le pire des cas, exponentielle en temps. Notre approche utilise une algorithmique issue de l'analyse combinatoire des données et s'appuie sur une représentation ensembliste, géométrique et logique des clauses définies par une bijection entre clauses et sous-ensemble de l'ensemble des interprétations. Une telle représentation permet une vision synthétique du problème #SAT et la prise en compte de caractéristiques statistiques globales de l'instance. En appliquant le principe général "diviser pour résoudre", la méthode de résolution approchée de #SAT que nous proposons permet de réduire de facon considérable la complexité algorithmique du problème. Elle est basée sur la segmentation d'une sériation établie sur la table d'incidence associée à la formule. Nous montrons, dans le cas difficile des instances SAT aléatoires, l'intérêt de la sériation et de sa meilleure coupure en deux parties connexes et de tailles comparables. De plus, nous définissons la notion d'indépendance en probabilité entre clauses et entre ensembles de clauses. La méthode proposée est validée à la fois théoriquement et par une vaste expérimentation. Par ailleurs, nous nous intéressons à la distribution de probabilité du nombre de solutions d'une instance kSAT aléatoire. L'espérance et la variance du nombre de solutions sont connues, nous montrons en utilisant des tests statistiques que la distribution suit une loi log-normale.
14
Zdeborova, Lenka. "Physique statistique des problèmes d'optimisation". Phd thesis, Université Paris Sud - Paris XI, 2008. http://tel.archives-ouvertes.fr/tel-00294232.
Texto completo da fonteResumo:
L'optimisation est un concept fondamental dans beaucoup de domaines scientifiques comme l'informatique, la théorie de l'information, les sciences de l'ingénieur et la physique statistique, ainsi que pour la biologie et les sciences sociales. Un problème d'optimisation met typiquement en jeu un nombre important de variables et une fonction de coût qui dépend de ces variables. La classe des problèmes NP-complets est particulièrement difficile, et il est communément admis que, dans le pire des cas, un nombre d'opérations exponentiel dans la taille du problème est nécessaire pour minimiser la fonction de coût. Cependant, même ces problèmes peuveut être faciles à résoudre en pratique. La question principale considérée dans cette thèse est comment reconnaître si un problème de satisfaction de contraintes NP-complet est "typiquement" difficile et quelles sont les raisons pour cela ? Nous suivons une approche inspirée par la physique statistique des systèmes désordonnés, en particulier la méthode de la cavité développée originalement pour les systèmes vitreux. Nous décrivons les propriétés de l'espace des solutions dans deux des problèmes de satisfaction les plus étudiés : la satisfiabilité et le coloriage aléatoire. Nous suggérons une relation entre l'existence de variables dites "gelées" et la difficulté algorithmique d'un problème donné. Nous introduisons aussi une nouvelle classe de problèmes, que nous appelons "problèmes verrouillés", qui présentent l'avantage d'être à la fois facilement résoluble analytiquement, du point de vue du comportement moyen, mais également extrêmement difficiles du point de vue de la recherche de solutions dans un cas donné.
15
Ickowicz, Adrien. "Méthodes d'estimation statistique pour le suivi de cibles à l'aide d'un réseau de capteurs". Phd thesis, Université Rennes 1, 2010. http://tel.archives-ouvertes.fr/tel-00482418.
Texto completo da fonteResumo:
Cette thèse s'intéresse à l'estimation des paramètres du mouvement d'une ou plusieurs cibles évoluant au sein d'une zone surveillée par un réseau de capteurs. Dans une première partie nous proposons de déterminer de façon exacte l'influence de paramètres d'influence du pistage à l'aide de la détermination d'une expression explicite d'une probabilité de bonne association. Nous parvenons à extraire l'influence de ces variables à l'aide de l'utilisation de méthodes numériques. Dans un deuxième temps nous nous intéressons à un type de capteurs bien particuliers. Nous supposons en effet que nous disposons de l'instant de plus grande proximité entre la cible et chaque capteur du réseau. A partir de ces données partielles, nous nous proposons de reconstruire la trajectoire de la cible. Après avoir montré que nous ne pouvions estimer conjointement la position et la vitesse de la cible, nous proposons des méthodes d'estimation du vecteur vitesse dans divers cas de trajectoire envisagés. Enfin, nous étudions dans la troisième partie de ce document le cas d'un réseau de capteurs binaires directionnels. Après une étude rapide sur l'estimation du vecteur vitesse dans le cas d'un mouvement rectiligne uniforme, nous étendons notre approche au cas ou le mouvement de la cible suivrait une marche aléatoire gaussienne, et nous proposons un nouvel algorithme permettant d'estimer conjointement les vecteurs vitesse et position. Nous proposons enfin une solution d'extension de notre algorithme au suivi multicible. Nous présentons dans chacun des scénarios des résultats de simulation illustrant les performances des méthodes proposées.
16
Deremble, Cyril. "Modélisation et étude statistique de la spécificité des interactions protéine-ADN". Paris 6, 2006. http://www.theses.fr/2006PA066525.
Texto completo da fonte
17
Bonomi, Ernesto. "Simulation numérique et mécanique statistique : extension et étude de quelques problèmes d'ingénierie". Paris 11, 1985. http://www.theses.fr/1985PA112322.
Texto completo da fonteResumo:
Le contenu de ce travail, rassemblé en une série d’articles –publiés, ou en cours de publication- touche aussi bien à la physique, aux télécommunications qu’à l’optimisation combinatoire. Les idées utilisées s’articulent autour de deux disciplines : la simulation numérique et la mécanique statistique des systèmes, aussi bien physiques que d’ingénierie. Nous entendons par système, un ensemble d’éléments en interaction entre eux et avec l’environnement qui les entoure. Le point de vue adopté est celui du modèle om le problème est ramené à un niveau tel, qu’une analyse mathématique puisse être envisagée, ou tout au moins formulée. Il s’est agi pour nous d’analyser l’ordre statistique qui prend place dans un espace des configurations dans lequel les interactions font évoluer les différents éléments. Le cadre de départ a été microscopique et l’utilisation d’une description complète, imposée jusque dans les plus petits détails du système, nous a amenés tout naturellement à définir des procédures opératoires dans le but de générer, à travers un code de simulation, toutes les configurations admissibles du système étudié. Il faut signaler que les contraintes de temps et de mémoire du calculateur nous ont forcés à chercher les représentations les plus adaptées. Cette analyse poussée du comportement du système et de sa meilleure représentation dans les organes du calculateur a souvent débouché sur des résultats analytiques nouveaux.
18
Lutton, Jean-Luc. "Mécanique statistique et théorie des systèmes : utilisation de méthodes de mécanique statistique pour étudier des systèmes de télécommunication et traiter des problèmes de recherche opérationnelle". Paris 11, 1985. http://www.theses.fr/1985PA112172.
Texto completo da fonteResumo:
L'objectif de ce travail est d'utiliser les concepts issus de la mécanique statistique pour étudier les problèmes d'ingénierie. Dans une première partie, nous analysons les performances de réseaux de connexion: réseaux de CLOS à 2k+1 étages. Nous montrons que ces réseaux, comme les systèmes physiques admettent une limite thermodynamique. Nous en déduisons alors, analytiquement, les valeurs de certaines grandeurs macroscopiques décrivant leurs divers modes de fonctionnement (systèmes avec perte des appels bloqués, avec réarrangement ou mise en attente de ces derniers) en fonction de la charge. Nous estimons en particulier certaines lois de distribution de probabilité d'événement (loi du nombre de réarrangements, loi des temps d'attente) grâce au principe du maximum d'entropie. Tous ces résultats analytiques sont comparés avec succès à des résultats de simulation numérique. Dans une deuxième partie, nous appliquons la procédure dite d· recuit simulé à des problèmes d'optimisation combinatoire (voyageur de commerce, couplage parfait de points de poids minimum, affectation à coût quadratique minimum). En fait nous utilisons l'algorithme de Metropolis pour déterminer la solution "optimale" des problèmes considérés. Nous obtenons ainsi une heuristique dont les performances sont favorablement comparées à celles d'autres méthodes classiques. Nous en profitons pour traiter des problèmes de grande taille (voyageur de commerce avec 10000 villes). De plus utilisant le formalisme des ensembles statistiques, nous estimons le comportement asymptotique des solutions optimales des problèmes étudiésThe aim of this work is to use· statistical mechanics ideas for studying engineering problems. First we analyze the performance of a class of connecting networks: Clos connecting Networks with 2 k + 1 stages. We show that these networks, like physical systems, exhibit the thermodynamical limit property. We deduce analytical expressions which give values of macroscopic system performance parameters (system with loss, system with rearrangement or system with queueing) in terms of the offered traffic. In particular, we estimate probability distribution of the number of rearrangements and the waiting time distribution using the maximum entropy principle. All these analytical results give good agreements with numerical simulations. We then apply the simulated annealing procedure to some combinatorial optimization problems (travelling salesman problem, minimum weighted matching problem, quadratic sum assignment problem). In fact, we use the Metropolis algorithm to determine a quasi-optimal solution to the problem we consider. We deduce a good heuristic with better performances than other classical methods, especially for large problems. For example we obtain a "good" solution for a 10000-city travelling salesman problem. Using statistical mechanics formalism, we also estimate the asymptotic behaviour of the optimal solution
19
Gelineau, Yoann. "Études combinatoires des nombres de Jacobi-Stirling et d’Entringer". Thesis, Lyon 1, 2010. http://www.theses.fr/2010LYO10156/document.
Texto completo da fonteResumo:
Cette thèse se divise en 2 grandes parties indépendantes ; la première traitant des nombres de Jacobi-Stirling, la seconde abordant les nombres d’Entringer. La première partie introduit les nombres de Jacobi-Stirling de seconde et de première espèce comme coefficients algébriques dans des relations polynomiales. Nous donnons des interprétations combinatoires de ces nombres, en termes de partitions d’ensembles et de quasi-permutations pour les nombres de seconde espèce, et en termes de permutations pour les nombres de première espèce. Nous étudions également les fonctions génératrices diagonales de ces familles de nombres, ainsi qu’une de leur généralisation sur le modèle des r-nombres de Stirling. La seconde partie introduit les nombres d’Entringer à l’aide de leur interprétation en termes de permutations alternantes. Nous étudions les différentes formules de récurrence vérifiées par ces nombres et généralisons ces résultats à l’aide d’un q-analogue utilisant la statistique d’inversion. Nous verrons également que ces résultats peuvent être étendus à des permutations de forme donnée quelconque. Enfin, nous définissons la notion de famille d’Entringer, et établissons des bijections entre certaines de ces familles. En particulier, nous établissons une bijection reliant les permutations alternantes de premier terme fixé, aux arbres binaires croissants dont l’extrémité du chemin minimal est fixéeThis thesis is constructed in two main independant parts ; the first one dealing with the numbers of Jacobi-Stirling, the second one tackling the numbers of Entringer. The first part introduces the numbers of Jacobi-Stirling of the second kind and of the first kind, as algebraic coefficients in some polynomial relations. We give some combinatorial interpretations of these numbers, in terms of set partitions and quasi-permutations for the numbers of the second kind, and in terms of permutations for the numbers of the first kind. We also study the diagonal generating functions of these sequences of numbers, and one of their generalization based on the model of r-Stirling numbers. The second part introduces the numbers of Entringer with their interpretation in terms of alternating permutations. We study the different recurrences formulas satisfied by these numbers, and refine these results with a q-analogue using the inversion statistic. We also note that these results can be extend to permutations with any fixed shape. Finally, we define the notion of Entringer family, and provide bijections between some of these families. In particular, we establish a bijection between the alternating permutations with fixed given value, and the binary increasing trees such that the end-point of the minimal path is fixed
20
Julis, Guenaëlle de. "Analyse d'accumulateurs d'entropie pour les générateurs aléatoires cryptographiques". Thesis, Grenoble, 2014. http://www.theses.fr/2014GRENM075.
Texto completo da fonteResumo:
En cryptographie, l'utilisation de nombres aléatoires est fréquente (graine, token, ...) et une mauvaise génération d'aléa peut compromettre toute la sécurité d'un protocole, comme en témoigne régulièrement l'actualité. Les générateurs de nombres aléatoires à usage cryptographique sont des composants formés de trois modules : la source brute qui produit de l'aléa (un algorithme ou un phénomène physique), un retraitement pour corriger les défauts de la source, et un retraitement cryptographique pour obtenir l'aléa final. Cette thèse se focalise sur l'analyse des générateurs issus d'une source physique, en vue de dégager des retraitements adaptés à leurs propriétés et résistants à des perturbations de leur environnement d'utilisation. La complexité des dispositifs entravant souvent la formulation explicite d'un modèle stochastique prouvé, leur évaluation repose principalement sur une analyse statistique. Or, les tests statistiques, principale méthode recommandée par les institutions gouvernementales (ANSSI, BSI, NIST) pour certifier ces composants, peuvent détecter des anomalies mais ne permettent pas de les identifier, et de les caractériser. Les travaux de cette thèse structurent la modélisation d'une source d'aléa, vue comme une suite de variables aléatoires, affinent les tests statistiques, et ajoutent une analyse temporelle pour détecter et expliciter ses anomalies au niveau global ou local. Les résultats ont été implantés dans une librairie composée d'un simulateur de perturbations, des outils statistiques et temporels obtenus, des batteries de tests recommandées (FIPS, AIS31, Test U01, SP800), et de retraitements appropriés à certaines anomalies. La structure mise en place a permis d'extraire des familles d'anomalies de motifs dont les propriétés rendent certains tests incapables de distinguer la source anormale d'une source idéalement aléatoire. L'analyse des faiblesses inhérentes aux méthodes statistiques a montré que l'interprétation d'un test par intervalle de rejet ou taux de réussite n'est pas adapté à la détection de certaines fautes de transition. Elle a aussi permis d'étudier les méthodes d'estimations d'entropie, notamment les estimateurs proposés dans la norme SP800-90. Par ailleurs, les paramètres de spécifications de certains générateurs, dont un déduit du standard de chiffrement AES, se sont avérés distinguables grâce aux statistiques de test. Les outils temporels développés évaluent la structure des anomalies, leur évolution au cours du temps et analysent les motifs déviants au voisinage d'un motif donné. Cela a permis d'une part d'appliquer les tests statistiques avec des paramètres pertinents, et d'autre part de présenter des retaitements dont la validité repose sur la structure des anomalies et non sur leur amplitudeWhile random numbers are frequently used in cryptography (seed, token, ...), news regurlarly prove how bad randomness generation can compromise the wole security of a protocol. Random number generators for crypthography are components with three steps : a source (an algorithm or physical phenomenon) produces raw numbers which are two times postprocessed to fix anomalies. This thesis focuses on the analysis of physical random bit generators in order to extract postprocessing which will be adapted to the anomalies of the source. As the design of a physical random bit generator is complex, its evaluation is mainly a statistical analysis with hypothesis testing. However, the current standards (AIS31, FIPS140-2, Test U01, SP800) can not provide informations to characterize anomalies. Thus, this thesis adjust several tests and add a time analysis to identify and to make global and local anomalies explicit. A C library was developped, providing anomalies simulator and tools to apply statistical and time analysis results on random bit generators
21
De, Tilière Béatrice. "Modèles exactement solubles de mécanique statistique en dimension deux : modèle d'Ising, dimères et arbres couvrants". Habilitation à diriger des recherches, Université Pierre et Marie Curie - Paris VI, 2013. http://tel.archives-ouvertes.fr/tel-00909569.
Texto completo da fonteResumo:
Ce mémoire donne un aperçu de mes travaux de recherche depuis la thèse. La thématique générale est la mécanique statistique, qui a pour but de comprendre le comportement macroscopique d'un système physique dont les interactions sont décrites au niveau microscopique. De nombreux modèles appartiennent à la mécanique statistique; nos résultats se concentrent sur le modèle d'Ising, le modèle de dimères et les arbres couvrants en dimension deux. Ces trois modèles ont la particularité d'être exactement solubles, c'est-à-dire qu'il existe une expression exacte et explicite pour la fonction de partition. Ce mémoire décrit et met en perspective les résultats de mes publications, et donne les étapes principales des démonstrations.
22
Hamon, Julie. "Optimisation combinatoire pour la sélection de variables en régression en grande dimension : Application en génétique animale". Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2013. http://tel.archives-ouvertes.fr/tel-00920205.
Texto completo da fonteResumo:
Le développement des technologies de séquençage et de génotypage haut-débit permet de mesurer, pour un individu, une grande quantité d'information génomique. L'objectif de ce travail est, dans le cadre de la sélection génomique animale, de sélectionner un sous-ensemble de marqueurs génétiques pertinents permettant de prédire un caractère quantitatif, dans un contexte où le nombre d'animaux génotypés est largement inférieur au nombre de marqueurs étudiées. Ce manuscrit présente un état de l'art des méthodes actuelles permettant de répondre à la problématique. Nous proposons ensuite de répondre à notre problématique de sélection de variables en régression en grande dimension en combinant approches d'optimisation combinatoire et modèles statistiques. Nous commençons par paramétrer expérimentalement deux méthodes d'optimisation combinatoire, la recherche locale itérée et l'algorithme génétique, combinées avec une régression li- néaire multiple et nous évaluons leur pertinence. Dans le contexte de la génomique animale les relations familiales entre animaux sont connues et peuvent constituer une information importante. Notre approche étant flexible, nous proposons une adapta- tion permettant de prendre en considération ces relations familiales via l'utilisation d'un modèle mixte. Le problème du sur-apprentissage étant particulièrement présent sur nos données dû au déséquilibre important entre le nombre de variables étudiées et le nombre d'animaux disponibles, nous proposons également une amélioration de notre approche permettant de diminuer ce sur-apprentissage. Les différentes approches proposées sont validées sur des données de la littérature ainsi que sur des données réelles de Gènes Diffusion.
23
Ratiéville, Matthieu. "Prévisions de champ moyen détaillées sur des systèmes désordonnés". Paris 6, 2003. http://www.theses.fr/2003PA066280.
Texto completo da fonte
24
Semerjian, Guilhem. "Modeles dilues en physique statistique : Dynamiques hors d'equilibre et algorithmes d'optimisation". Phd thesis, Université Pierre et Marie Curie - Paris VI, 2004. http://tel.archives-ouvertes.fr/tel-00006329.
Texto completo da fonteResumo:
Cette these est consacree a l'etude des proprietes dynamiques des modeles dilues. Ces derniers sont des systemes de physique statistique de type champ moyen, mais dont la connectivite locale est finie. Leur etude est notamment motivee par l'etroite analogie qui les relient aux problemes d'optimisation combinatoire, la K-satisfiabilite aleatoire par exemple. On expose plusieurs approches analytiques visant a decrire le regime hors d'equilibre de ces systemes, qu'il soit du a une divergence des temps de relaxation dans une phase vitreuse, a l'absence de condition de balance detaillee pour un algorithme d'optimisation, ou a une preparation initiale dans une configuration loin de l'equilibre pour un ferromagnetique. Au cours de ces etudes on rencontrera egalement un probleme de matrices aleatoires, et une generalisation du theoreme de fluctuation-dissipation aux fonctions a n temps.
25
Krzakala, Florent. "Aspects géométriques et paysages d'énergies des verres de spins : étude d'un système désordonné et frustré en dimension finie". Paris 6, 2002. https://tel.archives-ouvertes.fr/tel-00002232.
Texto completo da fonte
26
Deroulers, Christophe. "Application de la mécanique statistique à trois problèmes hors d'équilibre : algorithmes, épidémies, milieux granulaires". Phd thesis, Université Pierre et Marie Curie - Paris VI, 2006. http://tel.archives-ouvertes.fr/tel-00102083.
Texto completo da fonteResumo:
Cette thèse de doctorat étudie trois problèmes à l'aide des outils de la mécanique statistique. Nous montrons l'existence du phénomène d'universalité critique pour la transition de phases dynamique de certains algorithmes de recherche combinatoire. Nous donnons les valeurs exactes des exposants critiques et une formule analytique pour une fonction d'échelle. Nous développons un formalisme qui nous permet de calculer un développement perturbatif systématique, en grandes dimensions d'espace, de la fonction de grandes déviations de l'état métastable du processus de contact. Il peut resservir entre autres pour d'autres modèles de biologie des populations. Nous introduisons enfin deux modèles bidimensionnels exactement solubles pour la statique des milieux granulaires. Ils reproduisent la transition de jamming et permettent de discuter les différentes échelles de longueurs de ces milieux et de mettre en défaut l'hypothèse d'Edwards dans un cas réaliste.
27
Hites, Romina. "Robustness and preferences in combinatorial optimization". Doctoral thesis, Universite Libre de Bruxelles, 2005. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210905.
Texto completo da fonteResumo:
In this thesis, we study robust combinatorial problems with interval data. We introduce several new measures of robustness in response to the drawbacks of existing measures of robustness. The idea of these new measures is to ensure that the solutions are satisfactory for the decision maker in all scenarios, including the worst case scenario. Therefore, we have introduced a threshold over the worst case costs, in which above this threshold, solutions are no longer satisfactory for the decision maker. It is, however, important to consider other criteria than just the worst case.Therefore, in each of these new measures, a second criteria is used to evaluate the performance of the solution in other scenarios such as the best case one.
We also study the robust deviation p-elements problem. In fact, we study when this solution is equal to the optimal solution in the scenario where the cost of each element is the midpoint of its corresponding interval.
Then, we finally formulate the robust combinatorial problem with interval data as a bicriteria problem. We also integrate the decision maker's preferences over certain types of solutions into the model. We propose a method that uses these preferences to find the set of solutions that are never preferred by any other solution. We call this set the final set.
We study the properties of the final sets from a coherence point of view and from a robust point of view. From a coherence point of view, we study necessary and sufficient conditions for the final set to be monotonic, for the corresponding preferences to be without cycles, and for the set to be stable.
Those that do not satisfy these properties are eliminated since we believe these properties to be essential. We also study other properties such as the transitivity of the preference and indifference relations and more. We note that many of our final sets are included in one another and some are even intersections of other final sets. From a robust point of view, we compare our final sets with different measures of robustness and with the first- and second-degree stochastic dominance. We show which sets contain all of these solutions and which only contain these types of solutions. Therefore, when the decision maker chooses his preferences to find the final set, he knows what types of solutions may or may not be in the set.
Lastly, we implement this method and apply it to the Robust Shortest Path Problem. We look at how this method performs using different types of randomly generated instances.
Doctorat en sciences, Orientation recherche opérationnelle
info:eu-repo/semantics/nonPublished
28
Bourdache, Nadjet. "Élicitation incrémentale des préférences pour l’optimisation multi-objectifs : modèles non-linéaires, domaines combinatoires et approches tolérantes aux erreurs". Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS255.
Texto completo da fonteResumo:
Les travaux effectués durant cette thèse s'inscrivent dans le cadre de la théorie de la décision algorithmique, domaine au carrefour de la théorie de la décision, de la recherche opérationnelle et de l'intelligence artificielle. Cette thèse vise à concevoir des méthodes d'optimisation interactive fondées sur l'élicitation incrémentale des préférences pour la prise de décision multicritère, multi-agents ou dans le risque. Nous nous intéressons plus précisément à l'élicitation incrémentale des paramètres de fonctions d'agrégation qui consiste à alterner questions préférentielles permettant de réduire l'incertitude concernant la valeur des paramètres modélisant les préférences particulières du décideur, et exploration de l'espace des solutions, jusqu'à pouvoir déterminer une recommandation de bonne qualité. L'intérêt d'alterner phases de questions et phases d'exploration est double: d'une part, les informations préférentielles récoltées durant une phase d'élicitation permettent de mieux focaliser la phase d'exploration suivante sur les solutions les plus intéressantes pour le décideur; d'autre part, l'exploration de l'espace des solutions permet de guider le choix des questions de manière à ce qu'elles soient les plus informatives possible. Nous introduisons dans cette thèse des méthodes d'élicitation dans différents contextes. Dans un premier temps, nous nous intéressons à des fonctions d'agrégation non-linéaires pour modéliser les préférences du décideur sur un ensemble combinatoire d'alternatives. Nous nous intéressons ensuite à la conception de méthodes d'élicitation prenant en compte la possibilité de la présence d'incohérences dans les réponses du décideur, d'abord sur domaine explicite, puis sur domaine combinatoire. Les algorithmes introduits sont génériques et peuvent s'appliquer à différents problèmes de choix multi-objectifsThis thesis work falls within the area of algorithmic decision theory, a research domain at the crossroad of decision theory, operations research and artificial intelligence. The aim is to produce interactive optimization methods based on incremental preference elicitation in decision problems involving several criteria, opinions of agents or scenarios. Preferences are represented by general decision models whose parameters must be adapted to each decision problem and each decision maker. Our methods interleave the elicitation of parameters and the exploration of the solution space in order to determine the optimal choice for the decision maker. The idea behind this is to use information provided by the elicitation to guide the exploration of the solution space and vice versa. In this thesis, we introduce new incremental elicitation methods for decision making in different contexts : first for decision making in combinatorial domains when the decision models are non-linear, and then in a setting where one takes into account the possibility of inconsistencies in the answers of te decision maker. All the algorithms that we introduce are general and can be applied to a wide range of multiobjective decision problems
29
Jourdan, Laetitia Talbi El-Ghazali Dhaenens Clarisse. "Métaheuristiques pour l'extraction de connaissances application à la génomique /". [S.l.] : [s.n.], 2003. http://www.univ-lille1.fr/bustl-grisemine/pdf/extheses/50376-2003-239-240.pdf.
Texto completo da fonte
30
Kammoun, Mohamed Slim. "Universalité pour les permutations aléatoires". Thesis, Lille 1, 2020. http://www.theses.fr/2020LIL1I032.
Texto completo da fonteResumo:
On présente dans cette thèse des techniques de preuve d'universalité pour les permutations aléatoires. La principale méthode utilise une marche aléatoire sur le groupe symétrique. Cette technique nous permet de généraliser plusieurs résultats de convergence connus pour le cas uniforme, entre autres, le résultat de Baik, Deift et Johansson sur les fluctuations de la longueur de la plus longue sous-suite croissante. Cette technique n'est pas spécifique aux permutations aléatoires. On présente ainsi une généralisation à d'autres groupes. Une deuxième partie de la thèse est consacrée à l'utilisation de la méthode des moments ; on étudie la structure en cycle de produits de permutations indépendantes ayant une loi stable sous conjugaison. On montre qu'un simple contrôle des points fixes et des cycles de longueur 2 garantit une universalité pour les lois jointes des petits cycles du produitWe present, in this work, universality techniques for random permutations. The main method uses a random walk on the symmetric group. This technique allows us to generalize several results of known convergences for the uniform case. We generalize for example the result of Baik, Deift and Johansson on the fluctuations of the length of the longest increasing subsequence. This technique is not specific to random permutations. We present then a generalization to other groups.Using the method of moments, we study the cycle structure of the product of two independent conjugation invariant random permutations. We show that a simple control of fixed points and cycles of length 2 guarantees universality for the joint distribution of the small cycles of the product of the two permutations
31
Krzakala, Florent. "Aspects géométriques et paysage d'énergie des verres de spins: étude d'un système désordonné et frustré en dimension finie". Phd thesis, Université Pierre et Marie Curie - Paris VI, 2002. http://tel.archives-ouvertes.fr/tel-00002232.
Texto completo da fonteResumo:
Les systèmes vitreux sont caracterisés par un grand nombre d'états métastables. Cette thèse présente une étude de ces états dans les verres de spins en dimension finie - l'un des paradigmes de la physique statistique des systèmes désordonnés - à l'aide de modèles simples, d'approches phénoménologiques et de calculs numériques utilisant l'optimisation combinatoire. Nous nous interressons particulièrement à la structure du paysage d'énergie, à la nature du diagramme des phases ainsi qu'à l'éventuelle présence de chaos en température. Nos résultats indiquent que la structure du paysage d'énergie est complexe et qu'il existe des excitations macroscopiques d'énergie O(1) comme prévu par la théorie champ moyen, correspondant à des amas spongieux dont la topologie est non-triviale. Le diagramme des phases semble par contre être trivial, contrairement à ces prédictions: l'éventuelle phase verre de spins sous champ magnétique ainsi que la phase mixte où coexistent ordre ferromagnétique et ordre verre de spins semblent être absentes. Un scenario nommé TNT, pour Trivial - Non Trivial, pour lequel ces propriétés sont attendues, est présenté et est compatible avec l'ensemble des résultats connus. La présence de chaos en température est mise en évidence dans deux modèles : un verre de spins sous l'approximation champ moyen de Curie-Weiss et un modèle avec énergies et entropies aléatoires soluble analytiquement. Enfin, des propriétés générales des fondamentaux de systèmes désordonnés ont été étudiées numériquement et analytiquement. Les excitations et leur nature, les effets de tailles finies, les fluctuations d'échantillon à échantillon, l'unversalité par rapport à la réalisation du désordre, la dimension critique inférieure ainsi que la nature des statistiques extrêmes ont ainsi été abordés.
32
Fonseca, Tiago. "Matrices à signes alternants, boucles denses et partitions planes". Phd thesis, Université Pierre et Marie Curie - Paris VI, 2010. http://tel.archives-ouvertes.fr/tel-00521884.
Texto completo da fonteResumo:
Cette thèse est consacrée à l'étude d'identités qu'on observe à l'interface entre le domaine des modèles intégrables en physique statistique et la combinatoire. L'histoire a commencé quand Mills, Robbins et Rumsey étudiaient des Matrices à Signes Alternants (ASM). En 1982, ils proposèrent une formule d'énumération. Pendant qu'ils cherchaient une preuve de cette formule ils découvrirent l'existence d'autres objets comptés par la même formule : les Partitions Planes Totalement Symétriques Auto-Complémentaires (TSSCPP). C'est seulement quelques années plus tard que Zeilberger fut capable de prouver cette égalité, prouvant que les deux objets sont comptés par la même formule. La même année, Kuperberg utilise l'intégrabilité quantique (notion venue de la physique statistique) pour donner une preuve plus simple. En 2001, Razumov et Stroganov conjecturèrent une intrigante relation entre les ASM et l'état fondamental du modèle de spins XXZ (pour Delta=-1/2), lui aussi intégrable. Cette conjecture a été démontrée en 2010 par Cantini et Sportiello. L'objectif principal de ce manuscrit est de comprendre le rôle de l'intégrabilité dans cette histoire, notamment le rôle joué par l'équation de Knizhnik-Zamolodchikov quantique. Grâce à cette équation nous avons été capables de démontrer plusieurs conjectures combinatoires, dont une version raffinée de l'équalité entre le nombre des TSSCPP et des ASM proposée en 1986 par Mills, Robbins et Rumsey et certains propriétés des composantes du vecteur fondamental du modèle XXZ. Est présentée aussi une série de nouvelles conjectures concernant l'état fondamental.
33
Rouvière, Laurent. "Estimation de densité en dimension élevée et classification de courbes". Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2005. http://tel.archives-ouvertes.fr/tel-00011624.
Texto completo da fonteResumo:
L'objectif de cette thèse consiste étudier et approfondir des techniques d'estimation de la densité et de classification dans des espaces de dimension élevée. Nous avons choisi de structurer notre travail en trois parties.La première partie, intitulée compléments sur les histogrammes modifiés, est composée de deux chapitres consacrés l'étude d'une famille d'estimateurs non paramétriques de la densité, les histogrammes modifiés, connus pour posséder de bonnes propriétés de convergence au sens des critères de la théorie de l'information. Dans le premier chapitre, ces estimateurs sont envisagés comme des systèmes dynamiques espace d'états de dimension infinie. Le second chapitre est consacré l'étude de ces estimateurs pour des dimensions suprieures un.
La deuxième partie de la thèse, intituleé méthodes combinatoires en estimation de la densité, se divise en deux chapitres. Nous nous intéressons dans cette partie aux performances distance finie d'estimateurs de la densité sélectionnés à l'intérieur d'une famille d'estimateurs candidats, dont le cardinal n'est pas nécessairement fini. Dans le premier chapitre, nous étudions les performances de ces méthodes dans le cadre de la sélection des différents paramètres des histogrammes modifiés. Nous poursuivons, dans le deuxième chapitre, par la sélection d'estimateurs à noyau dont le paramètre de lissage s'adapte localement au point d'estimation et aux données.
Enfin, la troisième et dernière partie, plus appliquée et indépendante des précédentes, présente une nouvelle méthode permettant de classer des courbes partir d'une décomposition des observations dans des bases d'ondelettes.
34
Rivoire, Olivier. "Phases vitreuses, optimisation et grandes déviations". Phd thesis, Université Paris Sud - Paris XI, 2005. http://tel.archives-ouvertes.fr/tel-00009956.
Texto completo da fonteResumo:
Les problèmes d'optimisation combinatoires définis sur graphes aléatoires sont au coeur de la théorie de la complexité algorithmique. Ils sont également étroitement liés à une formulation champ moyen, dite approximation de Bethe, de modèles sur réseau de verres de spins et verres structuraux. Cette thèse s'appuie sur ce parallèle pour appliquer à des problèmes d'optimisation une approche issue de la physique statistique des systèmes désordonnés, la méthode de la cavité. Etant donné un ensemble d'entrées (instances) d'un problème d'optimisation, cette méthode permet de déterminer les propriétés des solutions des instances typiques, ainsi que celles des instances atypiques, dont les probabilités sont exponentiellement petites (grandes déviations sur la structure externe). Pour une instance donnée, la méthode de la cavité donne également accès à la thermodynamique des différentes solutions admissibles (grandes déviations sur la structure interne). D'un point de vue physique, de nombreux problèmes algorithmiquement difficiles se révèlent ainsi posséder une phase de type verre. Cette thèse est composée de trois parties destinées à exposer les principes, applications et limitations de la méthode de la cavité. La première partie rappelle, dans la perspective des grandes déviations, les liens entre physique statistique et optimisation combinatoire. La deuxième partie aborde les modèles définis sur graphes aléatoires et, pour différents ensembles de graphes, analyse les propriétés typiques et atypiques de ces modèles. La troisième partie est consacrée aux grandes déviations sur le "désordre interne", constitué par les solutions et quasi-solutions d'une instance donnée. Une attention particulière est dévolue au traitement des phases vitreuses où l'ensemble des solutions est fragmenté en un nombre exponentiel d'amas disjoints (structure dite à un pas de brisure de symétrie des répliques); il est montré comment la méthode de la cavité fournit dans de tels cas une description fine des propriétés géométriques de l'espace des solutions.
35
Bourien, Jérôme. "Analyse de distributions spatio-temporelles de transitoires dans des signaux vectoriels. Application à la détection classificationd'activités paroxystiques intercritiques dans des observations EEG". Rennes 1, 2003. https://tel.archives-ouvertes.fr/tel-00007178.
Texto completo da fonteResumo:
Les signaux électroencéphalographiques (EEG) enregistrés chez des patients épileptiques reflètent, en dehors des périodes correspondant aux crises, de nombreux signaux transitoires appelés "événements paroxystiques intercritiques" (EPIC) dont l'analyse peut contribuer à l'étude des épilepsies partielles pharmacorésistantes. Une méthode de caractérisation de la distribution spatio-temporelle des EPIC à partir des enregistrements EEG de profondeur est présentée. Les EPIC sont détectés puis analysés afin d'extraire des ensembles de sites distribués dans les structures cérébrales, conjointement et significativement impliqués. Cette méthode est appliquée à des signaux de longue durée enregistrés chez 8 sujets comptant chacun plusieurs milliers d'EPIC. Les résultats montrent une reproductibilité élevée des distributions spatio-temporelles des EPIC. La méthode constitue un premier pas vers une mise en correspondance objective de l'organisation des EPIC avec celle des crises.
36
Bienaise, Solène. "Tests combinatoires en analyse géométrique des données - Etude de l'absentéisme dans les industries électriques et gazières de 1995 à 2011 à travers des données de cohorte". Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00941220.
Texto completo da fonteResumo:
La première partie de la thèse traite d'inférence combinatoire en Analyse Géométrique des Données (AGD). Nous proposons des tests multidimensionnels sans hypothèse sur le processus d'obtention des données ou les distributions. Nous nous intéressons ici aux problèmes de typicalité (comparaison d'un point moyen à un point de référence ou d'un groupe d'observations à une population de référence) et d'homogénéité (comparaison de plusieurs groupes). Nous utilisons des procédures combinatoires pour construire un ensemble de référence par rapport auquel nous situons les données. Les statistiques de test choisies mènent à des prolongements originaux : interprétation géométrique du seuil observé et construction d'une zone de compatibilité.La seconde partie présente l'étude de l'absentéisme dans les Industries Electriques et Gazières de 1995 à 2011 (avec construction d'une cohorte épidémiologique). Des méthodes d'AGD sont utilisées afin d'identifier des pathologies émergentes et des groupes d'agents sensibles.
37
Maes, Francis. "Learning in Markov decision processes for structured prediction : applications to sequence labeling, tree transformation and learning for search". Paris 6, 2009. http://www.theses.fr/2009PA066500.
Texto completo da fonteResumo:
De nombreux problèmes d'apprentissage supervisé font intervenir des sorties complexes : séquences, arbres ou graphes. La prédiction de sorties structurées pose d'importants défis, liés à la nature combinatoire du problème. Dans cette thèse, je propose une nouvelle formulation basée sur le cadre des processus de décision Markoviens. Cette formulation permet d'utiliser des algorithmes d'apprentissage par renforcement pour traiter des problèmes particulièrement complexes qu'aucun algorithme n'était en mesure de résoudre jusqu'alors. La validation est effectuée sur deux tâches: l'étiquetage de séquences et la transformation d'arbres. Les résultats obtenus sur les séquences sont compétitifs avec l'état de l'art et pour certains significativement meilleurs. La transformation d'arbres est un des problèmes d'apprentissage statistique les plus complexes abordés à ce jour. Je démontre l'efficacité de l'apprentissage par renforcement pour ce problème sur cinq jeux de données de large échelle.
38
Lhoussaine, Cédric. "Réceptivité, mobilité et π-Calcul". Aix-Marseille 1, 2002. http://www.theses.fr/2002AIX11046.
Texto completo da fonteResumo:
Cette thèse est une contribution au développement de modèles formels décrivant la migration de code. Plus particulièrement, nous y développons un calcul distribué fondé sur un fragment du π-calcul asynchrone dont la syntaxe est enrichie d'une distribution explicite des processus dans des localités et d'un opérateur de migration de processus entre différentes localités. Dans ce modèle, nous prouvons qu'une forme d'absence d'interblocage peut être garantie grâce à un système d'analyse statique simple combiné avec un système de types. Les canaux de communication ont une propriété dite de "réceptivité", et plus généralement nous démontrons la "livrabilité des messages" qui établit que tous les messages émis auront la possibilité d'être reçus, même éventuellement après migration. Une série d'exemples illustrant le "style de programmation réceptif", nous porte à croire que ce calcul distribué reste suffisamment expressif. La réceptivité peut également être exprimée dans le π-calcul asynchrone sans répartition. On démontre dans ce cas que la réceptivité n'est pas obtenue au détriment de son expressivité par un codage "fully-abstract" du π-calcul à récepteurs uniques dans le π-calcul réceptif. Pour cela, nous sommes amenés à développer des techniques de preuves de bisimulations asynchrones "up-to". Enfin, dans la dernière partie de cette thèse nous nous intéressons au problème de l'inférence de types pour le π-calcul réparti. Nous montrons que la présence de types dépendants complique ce problème et nécessite le développement de nouvelles techniques. Nous donnons un algorithme, qui, étant donné un terme du langage retourne les types les plus généraux. Nous montrons que cet algorithme est correct et complet.
39
Jourdan, Laetitia. "Métaheuristiques pour l'extraction de connaissances : application à la génomique". Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2003. http://tel.archives-ouvertes.fr/tel-00007983.
Texto completo da fonteResumo:
Le travail présenté dans cette thèse traite de l'extraction de connaissances à l'aide de métaheuristiques et de ses applications à des problématiques en génomique. Dans un premier temps, nous donnons un état de l'art des métaheuristiques utilisées pour l'extraction de connaissances et plus particulièrement de l'utilisation des algorithmes génétiques en orientant notre présentation sur trois aspects fondamentaux des métaheuristiques : la représentation d'une solution, la fonction d'évaluation et le choix des opérateurs. Nous présentons ensuite deux problématiques issues d'une collaboration avec l'Institut de Biologie de Lille autour de la recherche de facteurs génétiques de prédisposition à certaines maladies multifactorielles (diabète de type II, obésité). Nous proposons une modélisation de ces problèmes en problèmes d'extraction de connaissances. Nous traitons ensuite les différentes taches d'extraction de connaissances identifiées comme des problèmes d'optimisation et proposons un schéma d'algorithme génétique possédant des mécanismes avancés d'intensification et de diversification pour les résoudre. Les apports de ces mécanismes sont testés modulairement afin de montrer leurs performances. Nous intégrons également des connaissances du domaine biologique afin de répondre aux problématiques posées. Cette intégration s'effectue aussi bien au niveau des fonctions d'évaluation proposées qu'au niveau de certains mécanismes utilisés. Enfin, différents modèles de parallélisme sont utilisés.
40
Ducamp, Gaspard. "PROCOP : probabilistic rules compilation and optimisation". Electronic Thesis or Diss., Sorbonne université, 2021. http://www.theses.fr/2021SORUS090.
Texto completo da fonteResumo:
Adoptées depuis plus de 20 ans par le monde de l’industrie, les règles métiers (business rules) offrent la possibilité à des utilisateurs non-informaticiens de définir des politiques de prise de décision de manière simple et intuitive. Pour faciliter leurs utilisations, des systèmes à base de règles, dits « systèmes de gestion des règles métier », ont été développés, séparant la logique métier de l’application informatique. S’ils sont adaptés pour traiter des données structurées et complètes, ils ne permettent pas aisément de travailler sur des données probabilistes. PROCOP (Probabilistic Rules Optimized and COmPilation) est une thèse proposant une nouvelle approche pour l’intégration de raisonnement probabiliste dans IBM Operational Decision Manager (ODM), le système de gestion des règles métier développé par IBM, notamment via l’introduction d’une notion de risque global sur l'évaluation des conditions d'exécution d'une action, complexifiant la phase de compilation du système mais augmentant l’expressivité des règles métiers. Diverses méthodes sont explorées, implémentées et comparées afin de permettre l'utilisation d'une telle capacité de raisonnement à large échelle, notamment afin de répondre aux problématiques liées à l'utilisation de modèles graphiques probabilistes dans des réseaux complexesWidely adopted for more than 20 years in industrial fields, business rules offer the opportunity to non-IT users to define decision-making policies in a simple and intuitive way. To facilitate their use, rule-based systems, known as business rule management systems, have been developed, separating the business logic from the computer application. While they are suitable for processing structured and complete data, they do not easily allow working with probabilistic data. PROCOP (Probabilistic Rules Optimized and COmPilation) is a thesis proposing a new approach for the integration of probabilistic reasoning in IBM Operational Decision Manager (ODM), IBM's business rules management system, in particular through the introduction of a concept of global risk on the evaluation of the execution conditions of an action, complicating the compilation phase of the system but increasing the expressiveness of the business rules. Various methods are explored, implemented and compared in order to allow the use of such a powerful reasoning capacity on a large scale, in particular in order to answer the problems linked to the use of probabilistic graphical models in complex networks
41
Fléchon, Elsa. "Définition d'un modèle unifié pour la simulation physique adaptative avec changements topologiques". Thesis, Lyon 1, 2014. http://www.theses.fr/2014LYO10284/document.
Texto completo da fonteResumo:
Les travaux réalisés pendant mon doctorat répondent à la problématique de la simulation physique, en temps interactif, du comportement d'objets déformables soumis à des changements topologiques. Mes travaux ont abouti à la définition d'un nouveau modèle unifié couplant un modèle topologique complet et un modèle physique, pour la simulation physique d'objets déformables décomposés en éléments surfaciques comme volumiques, tout en réalisant pendant cette simulation des changements topologiques comme la découpe ou la subdivision locale d'un élément du maillage. Cette dernière opération a permis de proposer une méthode adaptative où les éléments du maillage sont raffinés selon un critère géométrique au cours de la simulation. Nous avons fait le choix des cartes combinatoires et plus particulièrement celui des complexes cellulaires linéaires, comme modèle topologique de notre modèle unifié. Ils ont l'avantage d'être génériques par rapport à la dimension de l'objet représenté mais également par rapport à la topologie des cellules en lesquelles l'objet est décomposé. Le système masses-ressort a, quant à lui, été choisi comme modèle physique de notre modèle unifié. L'avantage de ce dernier réside dans la simplicité de ses équations, son implémentation intuitive, son interactivité et sa facilité à gérer les changements topologiques. Enfin, la définition d'un modèle unifié nous a permis de proposer un modèle évitant la redondance d'informations et facilitant la mise à jour de ces dernières suite à des changements topologiquesThe work made during my PhD, respond to the problematic of physical simulation of the behavior of deformable objects subject to topological changes in interactive time. My work resulted in the definition of a new unified model coupling a complete topological model and a physical model for physical simulation of deformable objects decomposed in surface as volume elements, while performing during this simulation topological changes such as cutting or subdivision local of a mesh element. This operation allowed us to propose an adaptive method where mesh elements are refined during the simulation according to a geometric criterion. For the topological model of our unified model, we made the choice of combinatorial maps and more particularly linear cellular complexes. Their main advantage of the latter is the simplicity of its equations, its intuitive implementation, its interactivity and its ease to handle topological changes. Finally, the definition of a unified model allowed us to propose a model avoiding duplication of information and facilitate the update after topological changes
42
Semerjian, Guilhem. "Mean-field disordered systems : glasses and optimization problems, classical and quantum". Habilitation à diriger des recherches, Ecole Normale Supérieure de Paris - ENS Paris, 2013. http://tel.archives-ouvertes.fr/tel-00785924.
Texto completo da fonteResumo:
Ce mémoire présente mes activités de recherche dans le domaine de la mécanique statistique des systèmes désordonnés, en particulier sur les modèles de champ moyen à connectivité finie. Ces modèles présentent de nombreuses transitions de phase dans la limite thermodynamique, avec des applications tant pour la physique des verres que pour leurs liens avec des problèmes d'optimisation de l'informatique théorique. Leur comportement sous l'effet de fluctuations quantiques est aussi discuté, en lien avec des perspectives de calcul quantique.
43
Liu, Yu. "Étude et calcul de la fiabilité des réseaux de télécommunication". Compiègne, 1993. http://www.theses.fr/1993COMPD651.
Texto completo da fonteResumo:
L'évolution technologique (fibres optiques + nouvelles générations de matériels de brassage) dans les réseaux de télécommunication fait que les problèmes de fiabilité sont très stratégiques lors de la conception et de la planification d'un réseau de télécommunication. L'objectif de ce travail est donc de définir des mesures pertinentes de fiabilité pour des réseaux de télécommunication situés dans le contexte ci-dessus, et de développer des outils performants pour évaluer ces mesures. De plus, les réseaux de grande taille doivent pouvoir être traités. On a proposé d'évaluer la disponibilité et l'espérance mathématique du trafic perdu. Une démarche en deux étapes a été choisie : évaluation des conséquences d'une panne ou de plusieurs pannes par simulation du reroutage, et calcul probabiliste pour évaluer la disponibilité et le trafic perdu moyen. Nous avons proposé une heuristique efficiente de reroutage basée sur les plus courts chemins. Pour le calcul probabiliste, nous avons développé trois méthodes complémentaires. Une première méthode est basée sur l'agrégation d'états d'une chaîne de Markov. La deuxième méthode est fondée sur l'énumération complète des états les plus probables. Ces deux méthodes permettent de borner inférieurement et supérieurement les grandeurs que nous calculons, mais elles ne sont applicables que pour des réseaux de taille petite ou moyenne. La troisième méthode dite d'échantillonnage stratifié fournit des intervalles de confiance. Elle est fondée sur la théorie des sondages. Mais, d'une part ces intervalles sont très précis, d'autre part elle permet de traiter des réseaux de très grande taille.
44
Parashar, Karthick Nagarat. "System-level approaches for fixed-point refinement of signal processing algorithms". Rennes 1, 2012. http://www.theses.fr/2012REN1E015.
Texto completo da fonteResumo:
Le problème de l'optimisation des systèmes utilisant l'arithmétique virgule fixe est un problème d'optimisation combinatoire de complexité NP-difficile. Savoir analyser et optimiser des applications complexes et de taille réelle est le thème central de cette thèse. Une technique de type diviser-pour-régner, où un système donné est décomposé en plusieurs petits sous-systèmes organisés selon une hiérarchie est au cœur de cette approche. Cette décomposition ouvre la voie à l'évaluation rapide de la précision et au problème d'optimisation hiérarchique de la largeur des données et des opérations du système. En raison de la réduction du nombre de variables, la convergence du problème d'optimisation hiérarchique vers une solution est beaucoup plus rapide que dans le cas classique. Le modèle "Single Noise Source" (SNS) est proposé pour étudier les statistiques des erreurs de quantification. Au lieu de simplement se concentrer sur la moyenne et la variance du bruit des erreurs dues à la quantification, il fournit également des formules analytiques pour dériver les paramètres statistiques des processus aléatoires produisant les erreurs de quantification équivalentes à une simulation en virgule fixe. En présence des opérations " non-lisses " (un- smooth) telles que la décision dans les modulations QAM, les fonctions Min() ou Max(), etc. , il est pour l'instant inévitable d'utiliser la simulation en virgule fixe. Une technique pour l'évaluation analytique des statistiques des erreurs de quantification en présence d'opérateurs non-lisses dans les graphes ne contenant pas de rebouclage est également proposée. Afin de tenir compte également des systèmes ayant des rebouclages, une technique hybride qui utilise le modèle SNS pour accélérer les simulations en virgule fixe est de plus proposée. Un cadre d'utilisation de l'optimisation convexe est proposé comme heuristique pour résoudre le problème d'optimisation des largeurs. Cette nouvelle technique améliore non seulement la qualité de la solution, mais permet de résoudre le problème plus rapidement que les approches itératives classiques. L'application des techniques proposées permet non seulement de réduire les coûts du système mais aussi une réduction de plusieurs ordres de grandeur dans le temps nécessaire pour optimiser les systèmes utilisant l'arithmétique virgule fixeThe fixed-point refinement problem is a combinatorial optimization problem whose search space grows exponentially. It is known to be NP-hard in complexity. Scalability issues involved in performing fixed-point refinement are the central theme of this thesis. A divide-and-conquer technique, where a given system is decimated to smaller sub-systems organized in a hierarchy is at the heart of this approach. This paves way for fast accuracy evaluation and the proposed hierarchical word-length optimization problem. Due to the reduction in number of variables, the convergence of hierarchical optimization problem to a solution is much faster than in the classical case. The single noise source (SNS) model has been proposed to study the quantization error statistics. Instead of just focusing on the average noise-power and mean of the errors due to quantization, it also provides analytical formulae for deriving statistical parameters of the random process generating quantization errors due to fixed-point simulation. In the presence of un-smooth operations such as QAM-slicing, Min() or Max() etc. , it is inevitable to use fixed-point simulation. A technique for analytical evaluation of quantization error statistics in the presence of un-smooth quantizers applicable for feed-forward networks is also proposed. In order to address systems with feedback involving un-smooth operations, a hybrid technique that makes use of the SNS model to accelerate fixed-point simulation is proposed. A convex-optimization framework is proposed as an improved heuristic to solve the word-length optimization problem. This not only improves the quality of the solution but also solves the problem much faster than classical iterative approaches. Application of the proposed techniques has resulted in improved reduction in system costs even and a reduction of several orders of magnitude in the over all time required for fixed-point refinement
45
Mansouri, Majdi. "Traitement du signal collaboratif dans les réseaux de capteurs sans fils". Phd thesis, Université de Technologie de Troyes, 2011. http://tel.archives-ouvertes.fr/tel-00675803.
Texto completo da fonteResumo:
L'objectif principal de la thèse est d'étudier le problème d'inférence bayésienne dans les réseaux de capteurs distribués avec un accent particulier sur le compromis entre la précision de l'estimation et la consommation de l'énergie. Nous avons proposé des algorithmes de traitement distribué du signal avec des mesures de capteurs quantifiées. En particulier, cette thèse porte sur l'application des méthodes variationnelles pour résoudre les problèmes de suivi de cibles sous les contraintes d'énergie dans les RCSFs. Le travail a abouti à la résolution de trois problèmes en RCSFs: la quantification intelligente des données des capteurs, la gestion des clusters et l'application de l'optimisation multi-objectifs pour s'accommoder des contraintes énergétiques d'un réseau de capteurs. Les contributions de cette thèse concernent les points suivant: -Estimation des positions de cibles basée sur des mesures quantifiées utilisant des méthodes variationnelles. -Estimation de canal entre les capteurs candidats et le chef de cluster. -Un régime de quantification adaptative sous contraintes de puissance de transmission constante et variable. -Sélection de meilleurs capteurs qui peuvent participer à la collecte de données. -Agrégation sécurisée de données dans le RCSF. -Sélection de chemins de communication optimaux entre les capteurs. -Méthode d'optimisation multi-objectifs dans le RCSF. -Application de la méthode d'agrégation multicritères des données basée sur le systéme multi-agents pour la gestion de crise dans le RCSF.
46
Mustafa, Nabil. "Approximations of Points: Combinatorics and Algorithms". Habilitation à diriger des recherches, Université Paris-Est, 2013. http://tel.archives-ouvertes.fr/tel-01062825.
Texto completo da fonteResumo:
At the core of successful manipulation and computation over large geometric data is the notion of approximation, both structural and computational. The focus of this thesis will be on the combinatorial and algorithmic aspects of approximations of point-set data P in d-dimensional Euclidean space. It starts with a study of geometric data depth where the goal is to compute a point which is the 'combinatorial center' of P. Over the past 50 years several such measures of combinatorial centers have been proposed, and we will re-examine several of them: Tukey depth, Simplicial depth, Oja depth and Ray-Shooting depth. This can be generalized to approximations with a subset, leading to the notion of epsilon-nets. There we will study the problem of approximations with respect to convexity. Along the way, this requires re-visiting and generalizing some basic theorems of convex geometry, such as the Caratheodory's theorem. Finally we will turn to the algorithmic aspects of these problems. We present a polynomial-time approximation scheme for computing hitting-sets for disks in the plane. Of separate interest is the technique, an analysis of local-search via locality graphs. A further application of this technique is then presented in computing independent sets in intersection graphs of rectangles in the plane.
47
Tahay, Pierre-Adrien. "Colonnes dans les automates cellulaires et suites généralisées de Rudin-Shapiro". Electronic Thesis or Diss., Université de Lorraine, 2020. http://www.theses.fr/2020LORR0198.
Texto completo da fonteResumo:
Cette thèse se situe à la frontière entre mathématiques et informatique théorique. Nous nous intéressons dans un premier temps aux automates finis et aux automates cellulaires. Bien qu’ils s’agissent de deux objets mathématiques assez différents, il est possible de les relier par des constructions explicites, en regardant la réalisation des suites automatiques dans les diagrammes espace-temps des automates cellulaires. Dans un second temps, nous étudions les corrélations discrètes de certaines suites automatiques, appelées suites généralisées de Rudin–Shapiro, qui se comportent comme des suites aléatoires pour la corrélation discrète d’ordre 2, bien qu’elles soient déterministes. Après une introduction des objets d’étude, que nous illustrons par plusieurs exemples, nous rappelons le résultat de Rowland et Yassawi, qui ont montré en 2015 qu’il était possible de construire de manière explicite toute suite p-automatique, dans le cas où p est un nombre premier, en colonne d’un automate cellulaire linéaire, à partir d’une configuration initiale finie. En utilisant leur méthode, nous obtenons différentes constructions de suites automatiques de référence, puis nous établissons un moyen explicite de construire toute une famille de suites p-automatiques, appelées suites généralisées de Rudin–Shapiro, que nous étudions dans la deuxième partie de la thèse, dans un cadre plus général. Nous nous intéressons également au cas de certaines suites non-automatiques, telles que l’indicatrice des polynômes et le mot de Fibonacci, que nous réussissons à construire en colonne d’automates cellulaires non-linéaires. Puis nous obtenons des résultats sur des recodages binaires, permettant de réduire le nombre de symboles dans les automates cellulaires. Grâce à un recodage binaire, nous avons également construit explicitement une suite 3-automatique sur un alphabet binaire, en colonne d’un automate cellulaire à 2 états, non-périodique à partir d’un certain rang, ce qui répond à une question posée par Rowland et Yassawi. Dans la deuxième partie de cette thèse, nous reprenons les travaux de Grant, Shallit et Stoll, qui ont établi en 2009 des résultats sur les corrélations discrètes de suites infinies sur des alphabets finis. En exploitant les propriétés de récursivité de la suite classique de Rudin–Shapiro, ils construisent une famille de suites déterministes sur des alphabets plus grands, pour lesquelles ils montrent que dans le cas où la taille de l’alphabet est sans facteur carré, la moyenne empirique des coefficients de corrélation d’ordre 2 a la même limite que dans le cas de suites où les lettres sont tirées aléatoirement, de manière uniforme et indépendamment. De plus, ils arrivent à quantifier explicitement le terme d’erreur. En généralisant leur construction à l’aide de la théorie des matrices de différence, nous arrivons à établir un résultat similaire pour des alphabets de taille quelconque ainsi qu’une amélioration du terme d’erreur dans certains cas. Tout comme Grant et al., nous nous servons de la théorie des sommes d’exponentielles pour démontrer notre résultat sur les corrélations discrètes d’ordre 2 de nos suites généralisées de Rudin–Shapiro. Dans la troisième partie, nous terminons par une approche combinatoire de ces questions, qui nous a permis d’obtenir une amélioration du terme d’erreur dans le cas où la taille de l’alphabet est un produit d’au moins deux nombres premiers distincts, et de généraliser certains de nos résultatsThis thesis is at the interface between mathematics and theoretical computer science. In the first part, our main objects are finite automata and cellular automata. While relatively different in nature, it is possible to link both by explicit constructions. More specifically, it is possible to realise automatic sequences in the space-time diagrams of cellular automata. In the second part, we study discrete correlation properties of so-called generalised Rudin–Shapiro sequences. These are automatic sequences, hence deterministic, but show similar properties as random sequences with respect to their discrete correlation of order 2. After introducing the objects of study, illustrated by several examples, we first recall the result of Rowland and Yassawi. They showed in 2015 via an algebraic approach that it is possible to construct explicitly any p-automatic sequence (p is a prime number) as a column of a linear cellular automaton with a finite initial configuration. By using their method, we obtain several constructions of classical automatic sequences, and an explicit way to build a family of p-automatic sequences that we study in a more general context in the second part of the thesis. We also investigate several non-automatic sequences, such as the characteristic sequence of integer-valued polynomials and the Fibonacci word, which both can be realised as columns of non-linear cellular automata. We end this part by some results about binary recodings in order to reduce the number of symbols in the cellular automata. Under a binary recoding, we give explicitly a 3-automatic sequence on a binary alphabet, as a column of a cellular automaton with 2 states, that is not eventually periodic. This answers a question asked by Rowland et Yassawi. In the second part of the thesis, we take up research from 2009 of Grant, Shallit, and Stoll about discrete correlations of infinite sequences over finite alphabets. By using the recursivity properties of the classical Rudin–Shapiro sequence, they built a family of deterministic sequences over larger alpha- bets, called generalised Rudin–Shapiro sequences, for which they showed that when the size of the alphabet is squarefree, the empirical means of the discrete correlation coefficients of order 2 have the same limit as in the case of random sequences where each letter is independently and uniformly chosen. Moreover, they gave explicit error terms. We extend their construction by means of difference matrices and establish a similar result on alphabets of arbitrary size. On our way, we obtain an improvement of the error term in some cases. The methods stem, as those used by Grant et al., from the theory of exponential sums. In the third part, we use a more direct combinatorial approach to study correlations. This allows for an improvement of the error term when the size of the alphabet is a product of at least two distinct primes, and allows to generalise some of our results of the second part
48
Chen, Linxiao. "Cartes planaires aléatoires couplées aux systèmes de spins". Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS096/document.
Texto completo da fonteResumo:
Cette thèse vise à améliorer notre compréhension des cartes planaires aléatoires décorées par les modèles de physique statistique. On examine trois modèles particuliers à l'aide des outils provenant de l'analyse, de la combinatoire et des probabilités. Dans une perspective géométrique, on se concentre sur les propriétés des interfaces et les limites locales des cartes aléatoires décorées. Le premier modèle consiste en une famille de quadrangulations aléatoires du disque décorées par un modèle de boucles O(n). Après avoir complété la preuve de son diagramme de phase initiée par [BBG12c] (chap. II), on étudie les longueurs et la structure d'imbrication des boucles dans la phase critique non-générique (chap. III). On montre que ces statistiques, décrites par un arbre étiqueté, convergent en loi vers une cascade multiplicative explicite lorsque le périmètre du disque tend vers l'infini. Le deuxième modèle (chap. IV) consiste en une carte planaire aléatoire décorée par la percolation de Fortuin-Kasteleyn. On complète la preuve de la convergence du modèle esquissée dans [She16b] et établit un certain nombre de propriétés de la limite. Le troisième modèle (chap. V) est celui des triangulations aléatoires du disque décorées par le modèle d'Ising. Il est étroitement lié au modèle des quadrangulations décorées par un modèle O(n) quand n=1. On calcule explicitement la fonction de partition du modèle muni des conditions au bord de Dobrushin au point critique, sous une forme exploitable pour les asymptotiques. À l'aide de ces asymptotiques, on étudie le processus d'épluchage le long de l'interface d'Ising dans la limite où le périmètre du disque tend vers l'infini. Mots clés. Carte planaire aléatoire, modèle de boucles O(n), percolation de Fortuin-Kasteleyn, modèle d'Ising, limite locale, géométrie d'interfacesThe aim of this thesis is to improve our understanding of random planar maps decorated by statistical physics models. We examine three particular models using tools coming from analysis, combinatorics and probability. From a geometric perspective, we focus on the interface properties and the local limits of the decorated random maps. The first model defines a family of random quadrangulations of the disk decorated by an O(n)-loop model. After completing the proof of its phase diagram initiated in [BBG12c] (Chap. II), we look into the lengths and the nesting structure of the loops in the non-generic critical phase (Chap. III). We show that these statistics, described as a labeled tree, converge in distribution to an explicit multiplicative cascade when the perimeter of the disk tends to infinity. The second model (Chap. IV) consists of random planar maps decorated by the Fortuin-Kasteleyn percolation. We complete the proof of its local convergence sketched in [She16b] and establish a number of properties of the limit. The third model (Chap. V) is that of random triangulations of the disk decorated by the Ising model. It is closely related to the O(n)-decorated quadrangulation when n=1. We compute explicitly the partition function of the model with Dobrushin boundary conditions at its critical point, in a form ameneable to asymptotics. Using these asymptotics, we study the peeling process along the Ising interface in the limit where the perimeter of the disk tends to infinity.Key words. Random planar map, O(n) loop model, Fortuin-Kasteleyn percolation, Ising model, local limit, interface geometry
49
Gaudier, Fabrice. "Modélisation par réseaux de neurones : application à la gestion du combustible dans un réacteur". Cachan, Ecole normale supérieure, 1999. http://www.theses.fr/1999DENS0009.
Texto completo da fonteResumo:
Tous les ans, un quart du combustible nucléaire d'un cœur de réacteur est remplace par du combustible neuf. Du fait de leur historique. Les autres combustibles ont des propriétés physiques très différentes. Se pose alors le problème de la répartition du combustible au sein du cœur tout en veillant à ce que le plan de chargement proposé vérifie des contraintes de sureté : c'est le problème du repositionnement de combustible. Si une recherche exhaustive est illusoire, elle nécessite le calcul des caractéristiques neutroniques, notamment le pic de puissance, pour des milliers de plans de chargements. Dans un code d'optimisation automatique comme Formosa, le calcul de ces caractéristiques représente 90% de la dizaine d'heures nécessaire à l'optimisation. Afin de réduire ce temps de calcul, nous proposons une architecture neuronale originale adaptée au phénomène physique à modéliser. Une analyse de données a permis de caractériser plus finement le combustible nucléaire. L'introduction d'une connaissance a priori portant sur les phénomènes neutroniques a permis de réduire le nombre de paramètres libres du modèle. Nous avons ensuite implémenté ce modèle neuronal dans Formosa, et nous avons montre sur des problèmes réels d'EDF un gain de temps considérable. Enfin, nous proposons également une méthode hybride alliant le meilleur parti de l'approximateur linéaire local GPT (generalized perturbation theory) et les réseaux de neurones.
50
Coron, Jean-Luc. "Quelques exemples de jeux à champ moyen". Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLED032/document.
Texto completo da fonteResumo:
La théorie des jeux à champ moyen fut introduite en 2006 par Jean-Michel Lasry et Pierre-Louis Lions. Elle permet l'étude de la théorie des jeux dans certaines configurations où le nombre de joueurs est trop grand pour espérer une résolution pratique. Nous étudions la théorie des jeux à champ moyen sur les graphes en nous appuyant sur les travaux d'Olivier Guéant que nous étendrons à des formes plus générales d'Hilbertien. Nous étudierons aussi les liens qui existent entres les K-moyennes et les jeux à champ moyen ce qui permettra en principe de proposer de nouveaux algorithmes pour les K-moyennes grâce aux techniques de résolution numérique propres aux jeux à champ moyen. Enfin nous étudierons un jeu à champ moyen à savoir le problème "d'heure de début d'une réunion" en l'étendant à des situations où les agents peuvent choisir entre deux réunions. Nous étudierons de manière analytique et numérique l'existence et la multiplicité des solutions de ce problèmeThe mean field game theory was introduced in 2006 by Jean-Michel Lasry and Pierre-Louis Lions. It allows us to study the game theory in some situations where the number of players is too high to be able to be solved in practice. We will study the mean field game theory on graphs by learning from the studies of Oliver Guéant which we will extend to more generalized forms of Hilbertian. We will also study the links between the K-means and the mean field game theory. In principle, this will offer us new algorithms for solving the K-means thanks to the techniques of numerical resolutions of the mean field games. Findly, we will study a mean field game called the "starting time of a meeting". We will extend it to situations where the players can choose between two meetings. We will study analytically and numerically the existence and multiplicity of the solutions to this problem