Spelling suggestions: "subject:"élagage"" "subject:"elagage""
1 |
Elagage d'un arbre de Lévy - Diffusion aléatoire en milieu LévyVoisin, Guillaume 02 December 2009 (has links) (PDF)
Se donnant un mécanisme de branchement critique ou sous-critique, on définit une procédure d'élagage de l'arbre aléatoire continu de Lévy associé. Cette procédure d'élagage est définie en plaçant des marques sur l'arbre grâce à des techniques de serpent de Lévy. On démontre alors que le sous-arbre obtenu après élagage est encore un arbre aléatoire continu de Lévy. Ce résultat est démontré en utilisant une propriété de Markov spéciale et un problème de martingale pour les processus d'exploration. On construit ensuite, par couplage, une autre procédure d'élagage qui définit un processus de fragmentation sur l'arbre. On calcule la famille de mesures de dislocation associée à cette fragmentation. Dans un deuxième travail, on considère une diffusion aléatoire dans un milieu Lévy stable. On montre que le processus des temps locaux renormalisé et recentré au minimum de la vallée standard de hauteur log t, converge en loi vers une fonctionnelle de deux processus de Lévy conditionnés à rester positifs indépendants. Pour démontrer ce résultat, on montre que la loi de la vallée standard est proche de celle de deux processus de Lévy conditionnés à rester positifs concaténés en 0. On obtient également la loi limite du supremum du temps local renormalisé.
|
2 |
Branchement et Elagage sur Grilles Pair-à-Pair à Grande-EchelleDi Costanzo, Alexandre 12 October 2007 (has links) (PDF)
Cette thèse a pour objectif de faciliter le déploiement d'applications distribuées sur des grilles de calcul à grande échelle, en utilisant une infrastructure pair-à-pair (P2P) pour les grilles. De plus, cette thèse propose aussi une bibliothèque basée sur la technique << Elagage et Branchement >> (de l'anglais, Branch-and-Bound -- B&B) pour résoudre les problèmes d'optimisation combinatoire.<br /><br />Les modèles et infrastructures pour le P2P existant sont plutôt décevants : seulement des tâches indépendantes généralement sans communication entre les tâches, et des API de bas niveau. Cette thèse propose une infrastructure P2P qui partage des noeuds de calcul, afin de fournir des grilles à grande échelle. L'infrastructure est un réseau P2P non-structuré, auto-organisé, configurable et qui permet le déploiement d'applications communicantes.<br /><br />Les environnements P2P semblent être bien adaptés aux applications avec un faible ratio communication/computation, comme les algorithmes de recherche parallèle et plus particulièrement les algorithmes de B&B. En plus d'une infrastructure P2P, cette thèse propose une bibliothèque de B&B parallèle pour la grille. Cette bibliothèque aide les utilisateurs, en masquant toutes les difficultés liées à la distribution, à paralléliser leurs problèmes sur des grilles. La bibliothèque repose sur un modèle maître-travailleur hiérarchique et offre un système transparent de communication afin d'améliorer la vitesse de résolution.<br /><br />Nous avons tout d'abord implémenté notre infrastructure P2P au-dessus de l'intergicielle Java pour la grille, ProActive. Cette infrastructure P2P a été déployée comme grille de bureau de manière permanente, avec laquelle nous avons pu réaliser un record mondial de calcul en résolvant le problème des n-reines avec 25 reines. Ensuite, nous avons aussi implémenté avec ProActive notre bibliothèque pour le B&B. Nous montrons le passage à l'échelle et l'efficacité de la bibliothèque en déployant sur une grille de taille nationale (Grid'5000) une application qui résout le problème du << flow-shop >>. Pour finir, nous avons mixé Grid'5000 et notre grille de bureau pour expérimenter le déploiement à grande échelle des n-reines et du flow-shop.
|
3 |
Approche de recherche intelligente fondée sur le modèle des Topic Maps : application au domaine de la construction durableEllouze, Nebrasse 03 December 2010 (has links) (PDF)
Cette thèse aborde les problématiques liées à la construction de Topic Maps et à leur utilisation pour la recherche d'information dans le cadre défini par le Web sémantique (WS). Le WS a pour objectif de structurer les informations disponibles sur le Web. Pour cela, les ressources doivent être sémantiquement étiquetées par des métadonnées afin de permettre d'optimiser l'accès à ces ressources. Ces métadonnées sont actuellement spécifiées à l'aide des deux standards qui utilisent le langage XML : RDF et les Topic Maps. Un contenu à organiser étant très souvent volumineux et sujet à enrichissement perpétuel, il est pratiquement impossible d'envisager une création et gestion d'une Topic Map, le décrivant, de façon manuelle. Plusieurs travaux de recherche ont concerné la construction de Topic Maps à partir de documents textuels [Ellouze et al. 2008a]. Cependant, aucune d'elles ne permet de traiter un contenu multilingue. De plus, bien que les Topic Maps soient, par définition, orientées utilisation (recherche d'information), peu d'entre elles prennent en compte les requêtes des utilisateurs.Dans le cadre de cette thèse, nous avons donc conçu une approche que nous avons nommée ACTOM pour " Approche de Construction d'une TOpic Map Multilingue ". Cette dernière sert à organiser un contenu multilingue composé de documents textuels. Elle a pour avantage de faciliter la recherche d'information dans ce contenu. Notre approche est incrémentale et évolutive, elle est basée sur un processus automatisé, qui prend en compte des documents multilingues et l'évolution de la Topic Map selon le changement du contenu en entrée et l'usage de la Topic Map. Elle prend comme entrée un référentiel de documents que nous construisons suite à la segmentation thématique et à l'indexation sémantique de ces documents et un thésaurus du domaine pour l'ajout de liens ontologiques. Pour enrichir la Topic Map, nous nous basons sur deux ontologies générales et nous explorons toutes les questions potentielles relatives aux documents sources. Dans ACTOM, en plus des liens d'occurrences reliant un Topic à ses ressources, nous catégorisons les liens en deux catégories: (a) les liens ontologiques et (b) les liens d'usage. Nous proposons également d'étendre le modèle des Topic Maps défini par l'ISO en rajoutant aux caractéristiques d'un Topic des méta-propriétés servant à mesurer la pertinence des Topics plus précisément pour l'évaluation de la qualité et l'élagage dynamique de la Topic Map.
|
4 |
Approche de recherche intelligente fondée sur le modèle des Topic Maps : application au domaine de la construction durable / An Intelligent Research Approach based on Topic Map ModelEllouze, Nebrasse 03 December 2010 (has links)
Cette thèse aborde les problématiques liées à la construction de Topic Maps et à leur utilisation pour la recherche d’information dans le cadre défini par le Web sémantique (WS). Le WS a pour objectif de structurer les informations disponibles sur le Web. Pour cela, les ressources doivent être sémantiquement étiquetées par des métadonnées afin de permettre d'optimiser l'accès à ces ressources. Ces métadonnées sont actuellement spécifiées à l'aide des deux standards qui utilisent le langage XML : RDF et les Topic Maps. Un contenu à organiser étant très souvent volumineux et sujet à enrichissement perpétuel, il est pratiquement impossible d’envisager une création et gestion d’une Topic Map, le décrivant, de façon manuelle. Plusieurs travaux de recherche ont concerné la construction de Topic Maps à partir de documents textuels [Ellouze et al. 2008a]. Cependant, aucune d’elles ne permet de traiter un contenu multilingue. De plus, bien que les Topic Maps soient, par définition, orientées utilisation (recherche d’information), peu d’entre elles prennent en compte les requêtes des utilisateurs.Dans le cadre de cette thèse, nous avons donc conçu une approche que nous avons nommée ACTOM pour « Approche de Construction d’une TOpic Map Multilingue ». Cette dernière sert à organiser un contenu multilingue composé de documents textuels. Elle a pour avantage de faciliter la recherche d’information dans ce contenu. Notre approche est incrémentale et évolutive, elle est basée sur un processus automatisé, qui prend en compte des documents multilingues et l’évolution de la Topic Map selon le changement du contenu en entrée et l’usage de la Topic Map. Elle prend comme entrée un référentiel de documents que nous construisons suite à la segmentation thématique et à l’indexation sémantique de ces documents et un thésaurus du domaine pour l’ajout de liens ontologiques. Pour enrichir la Topic Map, nous nous basons sur deux ontologies générales et nous explorons toutes les questions potentielles relatives aux documents sources. Dans ACTOM, en plus des liens d’occurrences reliant un Topic à ses ressources, nous catégorisons les liens en deux catégories: (a) les liens ontologiques et (b) les liens d’usage. Nous proposons également d’étendre le modèle des Topic Maps défini par l’ISO en rajoutant aux caractéristiques d’un Topic des méta-propriétés servant à mesurer la pertinence des Topics plus précisément pour l’évaluation de la qualité et l’élagage dynamique de la Topic Map. / The research work in this thesis is related to Topic Map construction and their use in semantic annotation of web resources in order to help users find relevant information in these resources. The amount of information sources available today is very huge and continuously increasing, for that, it is impossible to create and maintain manually a Topic Map to represent and organize all these information. Many Topic Maps building approaches can be found in the literature [Ellouze et al. 2008a]. However, none of these approaches takes as input multilingual document content. In addition, although Topic Maps are basically dedicated to users navigation and information search, no one approach takes into consideration users requests in the Topic Map building process. In this context, we have proposed ACTOM, a Topic Map building approach based on an automated process taking into account multilingual documents and Topic Map evolution according to content and usage changes. To enrich the Topic Map, we are based on a domain thesaurus and we propose also to explore all potential questions related to source documents in order to represent usage in the Topic Map. In our approach, we extend the Topic Map model that already exists by defining the usage links and a list of meta-properties associated to each Topic, these meta-properties are used in the Topic Map pruning process. In our approach ACTOM, we propose also to precise and enrich semantics of Topic Map links so, except occurrences links between Topics and resources, we classify Topic Map links in two different classes, those that we have called “ontological links” and those that we have named “usage links”.
|
5 |
Solving Games and All That / Résoudre les jeux et le resteSaffidine, Abdallah 08 July 2013 (has links)
Il existe des algorithmes en meilleur d'abord efficace pour la résolution des jeux déterministes à deux joueurs et à deux issues.Nous proposons un cadre formel pour la représentation de tels algorithmes en meilleur d'abord.Le cadre est suffisamment général pour exprimer des algorithmes populaires tels Proof Number Search, Monte Carlo Tree Search, ainsi que l'algorithme Product Propagation.Nous montrons par ailleurs comment adapter ce cadre à deux situations plus générales: les jeux à deux-joueurs à plusieurs issues, et le problème de model checking en logique modale K.Cela donne lieu √† de nouveau algorithmes pour ces situations inspirés des méthodes Proof Number et Monte Carlo.La technique de l'élagage alpha-beta est cruciale dans les jeux à actions séquentielles.Nous proposons une extension de cette techniques aux stacked-matrix games, une généralisation des jeux à deux joueurs, à information parfaite et somme nulle qui permet des actions simultanées. / Efficient best-first search algorithms have been developed for deterministic two-player games with two-outcome.We present a formal framework to represent such best-first search algorithms.The framework is general enough to express popular algorithms such as Proof Number Search, Monte Carlo Tree Search, and the Product Propagation algorithm.We then show how a similar framework can be devised for two more general settings: two-player games with multiple outcomes, and the model checking problem in modal logic K.This gives rise to new Proof Number and Monte Carlo inspired search algorithms for these settings.Similarly, the alpha-beta pruning technique is known to be very important in games with sequential actions.We propose an extension of this technique for stacked-matrix games, a generalization of zero-sum perfect information two-player games that allows simultaneous moves.
|
Page generated in 0.0327 seconds