To see the other types of publications on this topic, follow the link: Construction de graphes.
Dissertations / Theses on the topic 'Construction de graphes'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Construction de graphes.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Barakat-Barbieri, Bruno. "Vers une construction automatique de graphes de concepts." Châtenay-Malabry, Ecole centrale de Paris, 1992. http://www.theses.fr/1992ECAP0416.
Full textAbstract:
Ce travail propose une méthode de construction automatique de graphes de concepts à partir d'une base de données en texte intégral. La terminologie significative est extraite et normalisée à l'aide d'un traitement linguistique automatique. Le graphe de concepts ainsi construit est un arbre dont les nœuds sont les termes retenus. Les relations sont de nature générique-spécifique. Dans un premier temps, après une étude de la détermination de l'unité sémantique optimale, on introduit la notion de champ sémantique fondée sur la notion de concurrence de termes au sein de cette unité. Puis, après avoir mis en évidence les inconvénients de cette première approche, une nouvelle notion est présentée: les ensembles sémantiques. Ceux-ci sont moins dépendants de la répartition par thèmes des documents. L'étude du recouvrement de ces ensembles sémantiques nous permet de mettre en évidence les liens unissant les concepts entre eux. Une solution pour l'identification des polysèmes est également proposée. Enfin, l'auteur présente une discussion sur la qualité des résultats et les limites de cette approche
2
Bricage, Marie. "Modélisation et Algorithmique de graphes pour la construction de structures moléculaires." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLV031/document.
Full textAbstract:
Dans cette thèse, nous présentons une approche algorithmique permettant la génération de guides de construction de cages moléculaires organiques. Il s'agit d'architectures semi-moléculaires possédant un espace interne défini capable de piéger une molécule cible appelée substrat. De nombreuses œuvres proposent de générer des cages organiques moléculaires obtenues à partir de structures symétriques, qui ont une bonne complexité, mais elles ne sont pas spécifiques car elles ne prennent pas en compte des cibles précises. L'approche proposée permet de générer des guides de construction de cages moléculaires organiques spécifiques à un substrat donné. Afin de garantir la spécificité de la cage moléculaire pour le substrat cible, une structure intermédiaire, qui est une expansion de l'enveloppe du substrat cible, est utilisée. Cette structure définie la forme de l'espace dans lequel est piégé le substrat. Des petits ensembles d'atomes, appelés motifs moléculaires liants, sont ensuite intégrés à cette structure intermédiaire. Ces motifs moléculaires sont les ensembles d'atomes nécessaires aux cages moléculaires pour leur permettre d’interagir avec le substrat afin de le capturerIn this thesis, we present an algorithmic approach allowing the generation of construction guides of organic molecular cages. These semi-molecular architectures have a defined internal space capable of trapping a target molecule called substrate. Many works propose to generate molecular organic cages obtained from symmetrical structures, which have a good complexity, but they are not specific because they do not take into account precise targets. The proposed approach makes it possible to generate guides for the construction of organic molecular cages specific to a given substrate. In order to ensure the specificity of the molecular cage for the target substrate, an intermediate structure, which is an expansion of the envelope of the target substrate, is used. This structure defines the shape of the space in which the substrate is trapped. Small sets of atoms, called molecular binding patterns, are then integrated into this intermediate structure. These molecular patterns are the sets of atoms needed by molecular cages to allow them to interact with the substrate to capture it
3
Bloyet, Nicolas. "Caractérisation et plongement de sous-graphes colorés : application à la construction de modèles structures à activité (QSAR)." Thesis, Lorient, 2019. http://www.theses.fr/2019LORIS546.
Full textAbstract:
Dans le domaine de la chimie, il est intéressant de pouvoir estimer des propriétés physico- chimiques de molécules, notamment pour des applications industrielles. Celles-ci sont difficiles à estimer par simulations physique, présentant une complexité temporelle prohibitive. L'émergence des données (publiques ou privées) ouvre toutefois de nouvelles perspectives pour le traitement de ces problèmes par des méthodes statistiques et d'apprentissage automatique. La principale difficulté réside dans la caractérisation des molécules : celles-ci s'apparentent davantage à un réseau d'atomes (autrement dit un graphe coloré) qu'à un vecteur. Or, les méthodes de modélisation statistiques traitent usuellement avec des observations encodées comme telles, d'où la nécessité de méthodes spécifiques, nommées relations structures-activité, traitant des observations encodées sous forme de graphes. Le but de cette thèse est de tirer parti des corpus publics pour apprendre les meilleures représentations possibles de ces structures, et de transférer cette connaissance globale vers des jeux de données plus restreints. Nous nous inspirons pour ce faire de méthodes utilisées en traitement automatique des langages naturels. Pour les mettre en œuvre, des travaux d'ordre plus théorique ont été nécessaires, notamment sur le problème d'isomorphisme de graphes. Les résultats obtenus sur des tâches de classification/régression sont au moins compétitifs avec l'état de l'art, voire meilleurs, en particulier sur des jeux de données restreints, attestant des possibilités d'apprentissage par transfert sur ce domaineIn the field of chemistry, it is interesting to be able to estimate the physicochemical properties of molecules, especially for industrial applications. These are difficult to estimate by physical simulations, as their implementation often present prohibitive time complexity. However, the emergence of data (public or private) opens new perspectives for the treatment of these problems by statistical methods and machine learning. The main difficulty lies in the characterization of molecules: these are more like a network of atoms (in other words a colored graph) than a vector. Unfortunately, statistical modeling methods usually deal with observations encoded as such, hence the need for specific methods able to deal with graphs- encoded observations, called structure-activity relationships. The aim of this thesis is to take advantage of public corpora to learn the best possible representations of these structures, and to transfer this global knowledge to smaller datasets. We adapted methods used in automatic processing of natural languages to achieve this goal. To implement them, more theoretical work was needed, especially on the graph isomorphism problem. The results obtained on classification / regression tasks are at least competitive with the state of the art, and even sometimes better, in particular on restricted data sets, attesting some opportunities for transfer learning in this field
4
Said, Bilal. "Réécriture de graphes pour la construction de modèles en logique modale." Phd thesis, Université Paul Sabatier - Toulouse III, 2010. http://tel.archives-ouvertes.fr/tel-00466115.
Full textAbstract:
Pour modéliser le fonctionnement d'un système, décrire une situation ou représenter des idées, on se met intuitivement à dessiner des bulles et les lier par des flèches sous forme de graphes étiquetés. Les logiques modales constituent un cadre formel expressif et extensible qui permet de définir ces graphes sous forme de « modèles », et d'exprimer certaines propriétés de ces graphes sous forme de « formules » afin de pouvoir raisonner là-dessus: model checking, test de satisfiabilité ou de validité, etc. Pour des formules et modèles de tailles importantes, ces tâches deviennent compliquées. De ce fait, un outil permettant de les réaliser automatiquement s'avère nécessaire. LoTREC en est un exemple. Il permet à son utilisateur de créer sa propre méthode de preuve, grâce à un langage simple et de haut niveau, sans avoir besoin d'aucune expertise spécifique en programmation. Durant ma thèse, j'ai revu le travail qui était déjà accompli dans LoTREC et j'ai apporté de nouvelles extensions qui s'avéraient nécessaires pour pouvoir traiter de nouvelles logiques (K.alt1, universal modality, Hybrid Logic HL(@),Intuitionistic logic, Public Announcement Logic, ...) et offrir à l'utilisateur certaines nouvelles techniques. D'autre part, j'ai examiné les origines de LoTREC dans le monde de réécriture de graphes et j'ai spécifié la sémantique de son moteur de réécriture. Cela a permis d'éclaircir comment l'on peut hériter dans nos méthodes de preuve des résultats et des propriétés théoriques déjà bien établies dans le domaine de la réécriture de graphes.
5
Jin, Xiong. "Construction et analyse multifractale de fonctions aléatoires et de leurs graphes." Phd thesis, Université Paris Sud - Paris XI, 2010. http://tel.archives-ouvertes.fr/tel-00841501.
Full textAbstract:
Cette thèse est consacrée à la construction et l'analyse multifractale de fonctions aléatoires et de leurs graphes. La construction de ces objets se fait dans le cadre de la théorie des T-martingales de Kahane, et plus spécifiquement des [0, 1]-martingales. Cette théorie est fréquemment utilisée pour construire des martingales à valeurs dans les mesures de Borel positives dont la limite soit presque sûrement singulière par rapport à la mesure de Lebesgue. Ceci se fait en perturbant cette dernière à l'aide d'une suite de densités aléatoires qui sont des martingales positives d'espérance 1. Ici, nous autorisons ces martingales à prendre des valeurs complexes, et plutôt que des martingales à valeurs dans les mesures, nous considérons des martingales à valeurs dans les fonctions continues à valeurs complexes, puis la question de leur convergence uniforme presque sûre. Nous obtenons une condition suffisante de convergence pour les éléments d'une large classe de [0, 1]-martingales complexes. Les limites non dégénérées sont toutes candidates à être des fonctions multifractales. L'étude de leur nature multifractale révèle de nouvelles diffiultés. Nous la menons de façon complète dans le cas des "cascades b-adiques indépendantes" complexes. Ceci conduit à de nouveaux phénomènes. En particulier, nous construisons des fonctions continues statistiquement autosimilaires dont le spectre de singularité est croissant et entièrement supporté par l'intervalle [0;\infty]. Nous considérons également de nouveaux spectres de singularité associés au graphe, à l'image, ainsi qu'aux ensembles de niveau d'une fonction multifractale f donnée. Ces spectres s'obtiennent de la façon suivante. Soit Eh l'ensemble iso-Hölder de f associé à l'exposant h. Soit h le sous-ensemble du graphe de f obtenu en y relevant Eh. Pour tout h, on cherche la dimension de Hausdorff de h, celle de f(Eh), et celle des ensembles du type h \ Ly, où Ly est l'ensemble de niveau y de f. Pour les cascades b-adiques indépendantes non conservatives à valeurs réelles, nous obtenons presque sûrement les spectres associés au graphe et à l'image, et pour les spectres associés aux ensembles de niveau, nous obtenons un résultat en regardant des lignes de niveau dans "Lebesgue presque toute direction". Enfin, nous considérons les mêmes questions que précédemment pour une autre classe de foncions aléatoires multifractales obtenues comme séries d'ondelettes pondérées par des mesures de Gibbs. Nous obtenons presque sûrement les spectres associés au graphe et à l'image.
6
Andriyanova, Iryna. "Etude d'une certaine construction des codes definis par les graphes: codes TLDPC." Phd thesis, Télécom ParisTech, 2006. http://pastel.archives-ouvertes.fr/pastel-00002465.
Full textAbstract:
Ce travail est consacr'e `a l'analyse et la construction de codes d´efinis par des graphes dans le but d'obtenir des familles de codes ayant, pour une complexit´e de d´ecodage faible, de tr`es bonnes performances pour une large plage de rapports signal-`a-bruit. Nous nous int´eressons `a une famille de codes que nous appelons TLDPC (pour Tailbiting Trellis Low-Density Parity Check) qui contient, comme sous-familles, `a la fois les Turbo codes de Berrou et Glavieux et les codes de Gallager appel´es aussi codes LDPC. La premi`ere partie de cette th`ese est consacr´ee `a l'´etude des codes TLDPC binaires. Nous nous sommes int´eress´es au caract`ere asymptotiquement bon de ces codes et avons obtenus des conditions n´ecessaires ou suffisantes en ´etudiant les polyn
7
Loi, Michel. "Outils pour la construction de graphes de tâches acycliques à gros grain." Lyon 1, 1996. http://www.theses.fr/1996LYO10260.
Full textAbstract:
L'objet de cette these est de creer un lien entre les techniques d'ordonnancement basees sur les graphes de taches acycliques a gros grain, et celles utilisees en parallelisation automatique. Dans une premiere partie une etude des techniques existantes est proposee. La seconde partie presente differents algorithmes de generation de code et de comptage d'iteration. Une methode permettant de generer des bornes de boucles efficaces est proposee. La troisieme partie presente un modele de calcul parallele, le graphe de taches parametre, qui est une representation independante de la taille du probleme, de graphes de taches acycliques frequemment utilises. Differentes techniques qui permettent d'automatiser la construction du graphe de taches parametre : partir d'un programme sequentiel a controle de flot statique annote par l'utilisateur sont ensuite proposees. Nous montrons comment des informations necessaires a l'ordonnancement peuvent etre derivees. Une annexe presente pluspyr, un outil d'aide au developpement d'applications paralleles integrant les differentes techniques exposees dans cette these
8
Andriyanova, Iryna. "Etude d'une certaine construction des codes définis par les graphes : codes TLDPC." Paris, ENST, 2006. http://www.theses.fr/2006ENST0042.
Full textAbstract:
Ce travail est consacré à l’analyse et à la construction de codes définis par des graphes dans le but d’obtenir des familles de codes ayant, pour une complexité de décodage faible, de trés bonnes performances pour une large plage de rapports signal-à-bruit. Nous nous intéressons à une famille de codes TLDPC (Tail-biting Trellis Low-Density Parity Check) qui contient, comme sous-familles, à la fois les Turbo codes de Berrou et Glavieux et les codes de Gallager appelés aussi codes LDPC. La première partie de la thèse est consacrée à l'étude du caractère asymptotiquement bon des codes TLDPC binaires. Nous avons obtenu des conditions nécessaires et suffisantes sur ce caractère qui nous ont donné des bornes sur la proportion des noeuds de degré 2. Nous avons ensuite optimisé la distribution des noeuds des autres variables et nous obtenons de trés bonnes performances. Dans la deuxième partie, nous étudions certains codes LDPC et TLDPC non-binaires. Nous y présentons une famille de codes TLDPC non-binaires, avec une structure simple dont la pente des courbes de taux d'erreur dans la région de faible rapport signal-à-bruit est plus forte que pour les codes binaires correspondants. Notons qu’un code LDPC ayant au moins deux symboles de degré 2 par équation de parité peut être vu et décodé comme un code TLDPC avec des symboles de degré 1. Pour les codes de cycles d’un graphe, cette façon de faire nécessite beaucoup moins d'itérations de décodage. En introduisant dans la structure des codes de cycles d’un graphe des noeuds de degré 1, nous obtenons pour le canal à effacements en autorisant une petite fraction de symboles effacés aprés décodage, une famille de codes dont les performances se rapprochent encore des limites théoriques de ShannonThis study is dedicated to the analysis and the design of sparse-graph codes in order to construct codes having high performances both in waterfall and error-floor regions under an iterative decoding algorithm of low complexity. In particular, we explore a class of Tail-biting trellis LDPC (TLDPC) codes involving the class of turbo codes of Berrou and Glavieux as well as the class of codes of Gallager known as LDPC codes. In the first part of the thesis, binary TLDPC codes are investigated. We found sufficient and necessary conditions to ensure that they are asymptotically good by calculating their average weight enumerator and studying a certain graph in which the cycles correspond to potentially low weight codewords. These conditions give us an upper bound on the fraction of degree-2 nodes in the Tanner graph. By keeping the fraction of degree-2 nodes below the upper bound, we optimised the degree distribution of other variable nodes by EXIT chart techniques and thus we obtained good performances under standard iterative decoding algorithm (belief propagation). In the second part of the thesis, some non-binary TLDPC and LDPC codes are investigated. We propose a family of non-binary TLDPC codes with a very simple structure and a steep waterfall region. We also noticed that any LDPC code with at least two degree-2 symbols per parity-check equation can be represented as a TLDPC code with symbols in degree 1 in its structure. Thus, it can be decoded like a TLDPC code. In the case of cycle codes, such a decoding decreases significantly the number of iterations while the iterative decoding threshold does not seem to change. Moreover, by allowing a constant fraction of degree 1 symbols for this class of codes and a small fraction of erased bits after decoding over binary erasure channel, we obtained codes with improved iterative decoding performances
9
Andriyanova, Iryna. "Étude d'une certaine construction des codes définis par les graphes : codes TLDPC /." Paris : École nationale supérieure des télécommunications, 2007. http://catalogue.bnf.fr/ark:/12148/cb41087138x.
Full text
10
Vonseel, Audrey. "Hyperbolicité et bouts des graphes de Schreier." Thesis, Strasbourg, 2017. http://www.theses.fr/2017STRAD025/document.
Full textAbstract:
Cette thèse est consacrée à l'étude de la topologie à l'infini d'espaces généralisant les graphes de Schreier. Plus précisément, on considère le quotient X/H d'un espace métrique géodésique propre hyperbolique X par un groupe quasi-convexe-cocompact H d'isométries de X. On montre que ce quotient est un espace hyperbolique. Le résultat principal de cette thèse indique que le nombre de bouts de l'espace quotient X/H est déterminé par les classes d'équivalence sur une sphère de rayon explicitement calculable. Dans le cadre de la théorie des groupes, on montre que l'on peut construire explicitement des groupes et des sous-groupes pour lesquels il n'existe pas d'algorithme permettant de déterminer le nombre de bouts relatifs. Si le sous-groupe est quasi-convexe, on donne un algorithme permettant de calculer le nombre de bouts relatifsThis thesis is devoted to the study of the topology at infinity of spaces generalizing Schreier graphs. More precisely, we consider the quotient X/H of a geodesic proper hyperbolic metric space X by a quasiconvex-cocompact group H of isometries of X. We show that this quotient is a hyperbolic space. The main result of the thesis indicates that the number of ends of the quotient space X/H is determined by equivalence classes on a sphere of computable radius. In the context of group theory, we show that one can construct explicitly groups and subgroups for which there are no algorithm to determine the number of relative ends. If the subgroup is quasiconvex, we give an algorithm to compute the number of relative ends
11
Leclère, Michel. "Les connaissances du niveau terminologique du modèle des graphes conceptuels : construction et exploitation." Montpellier 2, 1995. http://www.theses.fr/1995MON20257.
Full textAbstract:
Le modele des graphes conceptuels permet la representation de connaissances par la description de concepts et de relations entre ces concepts. On peut distinguer plusieurs niveaux de connaissance: un niveau terminologique, un niveau assertionnel, un niveau regles cette these est consacree au niveau fondamental, le niveau terminologique. Nous exposons un ensemble de protocoles cooperatifs d'aide a la construction des taxinomies de types de concepts et de relations. Certains des types de ces taxinomies peuvent etre definis. Nous proposons d'utiliser le raisonnement par classification pour introduire ces types dans leur taxinomie. Un algorithme de projection, operation fondamentale du modele des graphes conceptuels, est presente. Cette operation permet la comparaison des types definis lors de la classification. Enfin, nous nous interessons a la possibilite d'introduire des types partiellement definis dans les taxinomies et a la prise en compte des types definis dans les raisonnements effectues au niveau assertionnel
12
Zablit, Patricia. "Construction de l'interprétation temporelle en langue naturelle : Un système fondé sur les graphes conceptuels." Paris 11, 1991. http://www.theses.fr/1991PA112380.
Full textAbstract:
Nous proposons un système pour l'interprétation temporelle des énoncés en langue naturelle. Nous supposons que cette interprétation se fait par le calcul de la référence temporelle, calcul qui implique la construction d'un modèle mental propre à la catégorie temps dans le discours. Le modèle mental que nous proposons est une structure discursive locale en ce sens que celui-ci représente l'interprétation d'un seul énoncé de la langue. La construction du modèle mental temporel se fait par composition de représentations lexicales des marqueurs temporels en langue tels que les temps grammaticaux, les syntagmes prépositionnels introduits par des prépositions temporelles, les adverbes de temps et des schémas temporels associes aux verbes. Les représentations lexicales introduisent des entités temporelles référentielles dans le modèle mental: des positions, avec deux sous-types, les points et les intervalles. Avant l'introduction de ces entités, le modèle mental contient déjà une entité qui est le moment de l'énoncé. Toutes ces représentations lexicales, ainsi que la représentation construite sont décrites selon un format uniforme. Il s'agit d'un format diagrammatique. L'uniformité du format et son caractère diagrammatique a un caractère heuristique en guidant le processus de composition et en facilitant la production d'un ensemble d'inférences pertinentes. Le choix du format diagrammatique du modèle mental, plus proche de la situation représentée, devrait rendre plus facile la tache d'un système muni de capacités perceptuelles pour déterminer la valeur de vérité d'un énoncé. Nous proposons une construction du modèle mental temporel en trois étapes: 1) la composition des représentations lexicales, intégrant sémantique et une forme limitée de pragmatique; 2) l'intégration de connaissances générales sur les situations; 3) la levée d'un certain type d'indétermination, a l'aide d'un principe de pertinence propre au domaine temporel. Nous distinguons la catégorie temps de la catégorie des situations, et cette distinction se reflète dans l'architecture de l'espace de travail qui se divise en deux sous-espaces: l'espace temps et l'espace des situations. L'espace temps comprend le modèle mental temporel et une pile de topicalisation (qui pourra être remplacée par une structure plus riche dans le cadre d'une théorie discursive plus globale). Le langage de représentation que nous adoptons est celui des graphes conceptuels, pour lequel nous proposons une réinterprétation selon qu'un graphe est une représentation lexicale ou discursive. Nous proposons également une version plus spécifique des opérations de joint et de projection
13
Lavergne, Julien. "Algorithme de fourmis artificielles pour la construction incrémentale et la visualisation interactive de grands graphes de voisinage." Thesis, Tours, 2008. http://www.theses.fr/2008TOUR4049.
Full textAbstract:
Nous nous intéressons dans cette thèse à la résolution d'un problème de classification non supervisée d'un grand volume de données (i.e. 1 million). Nous proposons une méthode de construction incrémentale de grands graphes de voisinage par des fourmis artificielles qui s'inspire du comportement d'auto-assemblage de fourmis réelles se fixant progressivement à un support puis successivement aux fourmis déjà fixées afin de créer une structure vivante. La connexion entre fourmis (données) se fait à partir d'une mesure de similarité entre les données. Nous permettons également l'exploration visuelle et interactive de nos graphes en réponse aux besoins d'extraction de connaissances de l'expert du domaine. Ce dernier peut visualiser la forme globale d'un graphe et explorer localement les relations de voisinage avec une navigation guidée par le contenu. Nos travaux s'inscrivent pleinement en classification interactive ainsi qu'en fouille de textes avec une immersion en réalité virtuelleWe present in this work a new incremental algorithm for building proximity graphs for large data sets in order to solve a clustering problem. It is inspired from the self-assembly behavior observed in real ants where ants progressively become attached to an existing support and then successively to other attached ants. Each artificial ant represents one data. The way ants move and build a graph depends on the similarity between the data. A graph, built with our method, is well suitable for visualization and interactively exploration depending on the needs of the domain expert. He can visualize the global shape of the graph and locally explore the neighborhood relations with a content-based navigation. Finally, we present different applications of our work as the interactive clustering, the automatic graph construction of documents and an immersion in a virtual reality environment for discovering knowledge in data
14
Nguyen, Viet Hang. "Constructive approaches to the rigidity of frameworks." Thesis, Grenoble, 2013. http://www.theses.fr/2013GRENM052/document.
Full textAbstract:
La théorie de la rigidité étudie l'unicité des réalisations des graphes, i.e., des charpentes. Initialement motivée par l'ingénierie des structures, la théorie de la rigidité trouve aujourd'hui des applications dans plusieurs domaines importants comme la prédiction de la flexibilité des protéines, la conception assistée par ordinateur, la localisation dans les réseaux des capteurs, etc. Cette thèse traite une grande variété de problèmes concernant différents types de rigidité, qui correspondent à différents niveaux d'unicité (locale/infinitésimale, globale et universelle) dans des modèles variés de charpentes. D'abord, nous développons des résultats sur la construction récursive et la décomposition des graphes avec des conditions mixtes de sparsité ainsi que des résultats sur le packing des arborescences avec des contraintes de matroïde. Ces résultats sont alors utilisés pour obtenir des caractérisations de la rigidité infinitésimale des charpentes avec des contraintes mixtes. Nous étudions aussi l'effet des opérations d'extension sur des charpentes et étendons un résultat connu sur la préservation de la rigidité globale d'$1$-extension dans les charpentes à direction et à longueur de la dimension deux aux dimensions supérieures. Pour la rigidité universelle, un sujet que l'on connait très peu, nous obtenons une caractérisation complète pour la classe des charpentes biparties complètes sur la ligne. Nous généralisons aussi une condition suffisante pour la rigidité universelle des charpentes en permettant des positions non généralesThe theory of rigidity studies the uniqueness of realizations of graphs, i.e., frameworks. Originally motivated by structural engineering, rigidity theory nowadays finds applications in many important problems such as predicting protein flexibility, Computer-Aided Design, sensor network localization, etc. The present thesis treats a wide range of problems concerning different kinds of rigidity, corresponding to different scopes of uniqueness (local/infinitesimal, global and universal), in various types of frameworks. First, we develop results in inductive construction and decomposition of graphs with mixed sparsity conditions as well as results on the packing of arborescences with matroidal constraints. These results are then used to obtain characterizations of infinitesimal rigidity in frameworks with mixed constraints. We also investigate the effect of extension operations on frameworks and extend a known result on the global rigidity preservation of $1$-extension on direction-length frameworks in dimension two to all dimensions. For universal rigidity, where little is known, we obtain a complete characterization for the class of complete bipartite frameworks on the line. We also generalize a sufficient condition for the universal rigidity of frameworks by allowing non-general positions
15
Sayadi, Mohamed Yosri. "Construction et analyse des algorithmes exacts et exponentiels : énumération input-sensitive." Electronic Thesis or Diss., Université de Lorraine, 2019. http://www.theses.fr/2019LORR0316.
Full textAbstract:
Moon et Moser ont prouvé que le nombre maximum des ensembles stables maximaux dans un graphe de n sommets est au plus 3^{n/3}. Cette borne, appelée borne supérieure, est stricte vu l’existence d’une famille des graphes avec un tel nombre appelée borne inférieure. Au contraire de l’énumération des ensembles stables maximaux, avoir deux bornes qui se qui se coïncident n’est pas évident du tout. Et c’est assez courant dans l’énumération « input-sensitive » d’avoir un grand écart. Ce problème concerne même les ensembles les plus classiques comme les ensembles dominants minimaux où le meilleur algorithme connu pour énumérer ces ensembles est en O(1.7159^n) et la meilleure borne inférieure connue est seulement 1.5704^n. Durant cette thèse, on a proposé un algorithme « Mesurer pour Conquérir » pour énumérer tous les ensembles dominants minimaux dans les graphes cordaux en O(1.5048^n). On a étudié aussi l’énumération des ensembles dominants connexes minimaux et les ensembles irredondants maximaux qui sont très proches des ensembles dominants minimaux. On a proposé un algorithme d’énumération des ensembles dominants connexes minimaux dans les graphes bipartis convexes en O(1.7254^n). On a conçu aussi des algorithmes d’énumération des ensembles irredondants maximaux dans les graphes cordaux, les graphes d’intervalles et les forêts en O(1.7549^n), O(1.6957^n ) et O(1.6181^n) respectivement au lieu de l’algorithme trivial en O*(2^n). On a proposé aussi comme une borne inférieure une famille de forêts avec Omega(1.5292^n) ensembles irredondants maximaux. Dans le cas des cographes, l'écart entre les deux bornes est réduit à néant en montrant que le nombre maximum de ces ensembles est Theta(15^{n/6}). Afin de varier, on a étudié un nouvel ensemble défini récemment : L’ensemble tropical connexe minimal. On a proposé une borne inférieure de 1.4961^n, mais sans réussir à améliorer la borne supérieure de 2^n. On a proposé des algorithmes d’énumération des ensembles tropicaux connexes minimaux dans les graphes cobipartis, les graphes d’intervalles et les graphes blocs en O*(3^{n/3}), O(1.8613^n) et O*(3^{n/3}) respectivement. On a établi une borne inférieure de 1.4766^n pour les graphes scindés et de 3^{n/3} pour les graphes cobipartis, les graphes d’intervalles et les graphes blocs. Finalement, comme perspective et pour attirer l’attention de la communauté sur l’énumération des ensembles dominants totaux minimaux, on a montré que le nombre maximum de ces ensembles est Ω(1.5848^n)Moon and Moser proved that the maximum number of maximal independent sets in a graph of n vertices is at most 3^{n/3}. This maximum number, called upper bound, is tight given the existence of a family of graphs with such a number called lower bound. Unlike the enumeration of maximal independent sets, having a tight bounds is not obvious at all. And it’s quite common in the “input-sensitive” enumeration to have a big gap. This problem concerns even the most studied sets as minimal dominating sets where the best known algorithm to enumerate those sets runs in time O(1.7159^n) and the best known lower bound is only 1.5704^n. During this thesis, we proposed a "Measure and Conquer" algorithm to enumerate all minimal dominating sets for chordal graphs in time O(1.5048^n). Minimal connected dominating sets and maximal irredundant sets, which are closely related to minimal dominating sets, were also studied. An enumeration algorithm of minimal connected dominating sets in convex bipartite graphs has been proposed with a running time in O(1.7254^n). Enumeration algorithms of maximal irredundant sets have also been given for chordal graphs, interval graphs, and forests in times O(1.7549^n), O(1.6957^n) and O(1.6181^n) respectively instead of the trivial algorithm in time O*(2^n). We complement these upper bounds by showing that there are forest graphs with Omega(1.5292^n) maximal irredundant sets. We proved also that every maximal irredundant set of a cograph is a minimal dominating set. This implies that the maximum number of those sets in cographs is Theta(15^{n/6}). Finally, to vary, we studied a new set has been defined recently: The minimal tropical connected set. A lower bound of 1.4961^n has been proposed but we failed to improve the upper bound of 2^n. Enumeration algorithms of minimal tropical connected sets have been given for cobipartite, interval and block graphs in times O*(3^{n/3}), O(1.8613^n) and O*(3^{n/3}) respectively. A lower bound of 1.4766^n for splits graphs and 3^{n/3} for cobipartite, interval graphs and block graphs have been provided. We proposed a new lower bound of 1.5848^n, as a perspective and in order to draw community attention to the maximum number of minimal total dominating sets
16
Eichler, Cédric. "Modélisation formelle de systèmes dynamiques autonomes : graphe, réécriture et grammaire." Thesis, Toulouse 3, 2015. http://www.theses.fr/2015TOU30057/document.
Full textAbstract:
Les systèmes distribués modernes à large-échelle évoluent dans des contextes variables soumis à de nombreux aléas auxquels ils doivent s'adapter dynamiquement. Dans ce cadre, l'informatique autonome se propose de réduire les interventions humaines lentes et coûteuses, en leur préférant l'auto-gestion. Elle repose avant tout sur une description adéquate de ses composants, de leurs interactions et des différents aspects ou topologies qu'il peut adopter. Diverses approches de modélisation ont étés proposées dans la littérature, se concentrant en général sur certains du système dynamique et ne permettent ainsi pas de répondre à chacune des problématiques inhérentes à l'auto-gestion. Cette thèse traite de la modélisation basée graphes des systèmes dynamiques et de son adéquation pour la mise en œuvre des quatre propriétés fondamentales de l'informatique. Elle propose quatre principales contributions théoriques et appliquées. La première est une méthodologie pour la construction et la caractérisation générative de transformations correctes par construction dont l'application préserve nécessairement la correction du système. La seconde contribution consiste en une extension des systèmes de réécriture de graphe permettant de représenter, mettre à jour, évaluer et paramétrer les caractéristiques d'un système aisément et efficacement. Une étude expérimentale extensive révèle un net gain d'efficacité vis à vis de méthodes classiques. Les deux dernières contributions s'articulent autour de l'élaboration de deux modules de gestions visant : (1) des requêtes de traitement d'événements complexes et (2) tout système Machine-à-Machine se conformant au standard ETSI M2MModern, large-scale systems are deployed in changing environments. They must dynamically adapt to context changes. In this scope, autonomic computing aims at reducing slow and costly human interventions, by building self-managed systems. Self-adaptability of a system is primarily based on a suitable description of its components, their interactions and the various states it can adopt. Various modeling approaches have been elaborated. They usually focus on some aspects or properties of dynamic systems and do not tackle each of self-management's requirements. This manuscript deals with graph-based representations of dynamic systems and their suitability for the implementation of autonomic computing's four fundamental properties : self-optimization, self-protection, self-healing and self-configuring. This thesis offers four principal theoretical and applied contributions. The first one is a methodology for the construction and generative characterization of transformations correct by construction whose application necessarily preserves a system's correctness. The second one consists in an extension of graph rewriting systems allowing to easily and efficiently represent, update, evaluate and configure a system's characteristics. An experimental study reveals a significant efficiency gain with regard to classical methods. The two lasts contribution are articulated around the design of two autonomic managers driving: (1) complex events processing requests and (2) any Machine-to-Machine system complying to the ETSI M2M2 standard
17
Navarro, Emmanuel. "Métrologie des graphes de terrain, application à la construction de ressources lexicales et à la recherche d'information." Phd thesis, Institut National Polytechnique de Toulouse - INPT, 2013. http://tel.archives-ouvertes.fr/tel-01020232.
Full textAbstract:
Cette thèse s'organise en deux parties : une première partie s'intéresse aux mesures de similarité (ou de proximité) définies entre les sommets d'un graphe, une seconde aux méthodes de clustering de graphe biparti. Une nouvelle mesure de similarité entre sommets basée sur des marches aléatoires en temps courts est introduite. Cette méthode a l'avantage, en particulier, d'être insensible à la densité du graphe. Il est ensuite proposé un large état de l'art des similarités entre sommets, ainsi qu'une comparaison expérimentale de ces différentes mesures. Cette première partie se poursuit par la proposition d'une méthode robuste de comparaison de graphes partageant le même ensemble de sommets. Cette méthode est mise en application pour comparer et fusionner des graphes de synonymie. Enfin une application d'aide à la construction de ressources lexicales est présentée. Elle consiste à proposer de nouvelles relations de synonymie à partir de l'ensemble des relations de synonymie déjà existantes. Dans une seconde partie, un parallèle entre l'analyse formelle de concepts et le clustering de graphe biparti est établi. Ce parallèle conduit à l'étude d'un cas particulier pour lequel une partition d'un des groupes de sommets d'un graphe biparti peut-être déterminée alors qu'il n'existe pas de partitionnement correspondant sur l'autre type de sommets. Une méthode simple qui répond à ce problème est proposée et évaluée. Enfin Kodex, un système de classification automatique des résultats d'une recherche d'information est présenté. Ce système est une application en RI des méthodes de clustering vues précédemment. Une évaluation sur une collection de deux millions de pages web montre les avantages de l'approche et permet en outre de mieux comprendre certaines différences entre méthodes de clustering.
18
Ayats, H. Ambre. "Construction de graphes de connaissances à partir de textes avec une intelligence artificielle explicable et centrée-utilisateur·ice." Electronic Thesis or Diss., Université de Rennes (2023-....), 2023. http://www.theses.fr/2023URENS095.
Full textAbstract:
Avec les progrès récents dans le domaine de l'intelligence artificielle, la question du contrôle humain est devenu centrale. Aujourd'hui, cela passe à la fois par des recherches en explicabilité et des systèmes centrés autour de l'interaction avec l'utilisateur·ice. De plus, avec l'expansion du web sémantique et des méthodes de traitement automatique du langage naturelle, la tâche de construction de graphes de connaissances à partir de textes est devenu un enjeu important. Cette thèse présente un système centré-utilisateur·ice pour la construction de graphes de connaissances à partir de textes. Cette thèse présente plusieurs contributions. Tout d'abord, nous introduisons un workflow centré-utilisateur·ice pour la tâche sus-citée, ayant la propriété d'automatiser progressivement les actions de l'utilisateur·ice tout en lui laissant un contrôle fin du résultat. Ensuite, nous présentons nos apports dans le domaine de l'analyse de concepts formels, utilisés afin de concevoir un module d'apprentissage fainéant et explicable pour la tâche de classification de relations. Enfin, nous présentons nos apports dans le domaine de l'extraction de relations, et comment ces apports s'inscrivent dans le workflow présenté précédemmentWith recent advances in artificial intelligence, the question of human control has become central. Today, this involves both research into explainability and designs centered around interaction with the user. What's more, with the expansion of the semantic web and automatic natural language processing methods, the task of constructing knowledge graphs from texts has become an important issue. This thesis presents a user-centered system for the construction of knowledge graphs from texts. This thesis presents several contributions. First, we introduce a user-centered workflow for the aforementioned task, having the property of progressively automating the user's actions while leaving them a fine-grained control over the outcome. Next, we present our contributions in the field of formal concept analysis, used to design an explainable instance-based learning module for relation classification. Finally, we present our contributions in the field of relation extraction, and how these fit into the presented workflow
19
Nel, François. "Suivi de mouvements informationnels : construction, modélisation et simulation de graphes de citations, application à la détection de buzz." Paris 6, 2011. http://www.theses.fr/2011PA066541.
Full textAbstract:
Cette thèse a pour contexte général l'étude des mouvements informationnels sur le Web. La démarche retenue se base sur l'étude du graphe des citations entre sites d'information sur le Web selon trois axes principaux : la construction, l'analyse et la génération d'un graphe de citations. Pour construire le graphe de citations, nous proposons une méthode de crawling adaptée à l'extraction de corpus de relations de citations entre sources Web. La stratégie choisie se base sur une extraction exhaustive des publications des sources et un nettoyage des pages afin d'en extraire les liens hypertextes utiles. L'analyse du graphe extrait consiste en une méthode de caractérisation des noeuds du graphe, considérés comme des sources d'information ayant des comportements de publication distincts et nous permet d'en identifier quatre. L'objectif de nos travaux sur la génération de graphes de citations est d'obtenir des graphes réalistes, c'est-à-dire capables de reproduire les comportements de publication identifiés sur les données réelles. Ainsi, nous proposons un modèle suffisamment flexible et adaptable en imitant au mieux le processus de publication réel d'un article sur un site et l'implémentons en un outil de simulation. Enfin, nous proposons une mise en application de nos travaux dans le cadre d'une étude sur la détection de buzz. Nous étudions le concept de buzz en proposant une définition sur laquelle nous basons plusieurs formalisations adaptées aux données disponibles. L'interprétation des expérimentations effectuées nous conduit à attribuer les méthodes de détection proposées à des cas d'application spécifiques selon la sémantique qui peut leur être attribuée.
20
Maturana, Miranda Francisco Ramón Javier. "Le système des villes moyennes du sud du Chili, vers la construction de nouveaux espaces de relations ?" Thesis, Paris 4, 2012. http://www.theses.fr/2012PA040082.
Full textAbstract:
La question des villes moyennes ou intermédiaires a été largement débattue, en raison de la difficulté à établir leur définition. Un système de villes moyennes particulier est situé au sud du Chili, constitué par les régions de La Araucanía, Los Ríos et Los Lagos. Ce système présente une configuration spatiale plutôt monocentrique, où les interactions entre villes sont développées à l'intérieur de chaque région et, par conséquence, les liens transfrontaliers sont faibles voire inexistants. Les centres urbains à l'intérieur de chaque région développent différents types de configuration spatiale, tant à un niveau régional et que local. Cette thèse a cherché à comprendre les concepts de ville intermédiaire ou moyenne et à les stabiliser, pour pouvoir mieux comprendre le système de villes moyennes du sud du Chili à partir d'une analyse de réseau et du degré de cohésion des différentes villes. Le réseau qui organise ce système est déterminé principalement par les relations hiérarchiques et de type vertical. Ainsi, il existe un élevé degré de dépendance à l'égard des capitales régionales, ce qui organise un réseau monocentrique à l'intérieur de chaque espace régional, où il serait encore possible de trouver des villes isolées. Le degré de polycentrisme pour l'ensemble du système a été estimé moyen à faible. Cette situation est encore plus dramatique au sein de chaque espace régional. Les relations spatiales entre centres urbains se réalisent à deux échelles. Dans la première, trois types d'organisation spatiale se mettent en place et dans la deuxième, trois types d'organisation spatiale ont lieu entre des paires de nœuds du réseauMedium-size cities have been the subject of profound debate given their complexity in order to define them. A particular system consisting of this type of cities is located in southern Chile, an area which comprises the regions of La Araucania, Los Ríos and Los Lagos. This system seems to have a monocentric configuration, where interactions between population centers would be arranged within each region and therefore trans-border links would be weak or not present. In addition to that, urban centers that compose the system would have differentiated spatial patterns, both at a regional and local scale. In this sense, this thesis tries to understand the concept of medium-size and intermediate cities and stabilize it, to understand the system of cities of southern Chile thanks to a network approach and the analysis of the cohesion degree in urban centers. The network that organizes this system is determined largely by relations of hierarchical and vertical type, having a high degree of dependency of small cities within a region to each of the regional capitals, which organizes a moncentric network within each regional area, including identifying isolated towns. The degree of polycentrism for the entire system is low and this situation is even deeper within each regional area. The spatial relationships between urban centers are in two scales, first to set up three types of spatial organization and second presents three types of spatial organization that develop between pairs of nodes in the network
21
Mohd, Salleh Mohd Najib. "Construction d'arbres de décision avec valeurs incomplètes pour la sélection de graines de palmier à huile." La Rochelle, 2008. http://www.theses.fr/2008LAROS240.
Full textAbstract:
Dans les cas de traitement d'information incomplète à l'aide d'arbres à décision, la qualité de l'affectation des valeurs dépend toujours du travail de classification. Dans certains cas, on ne pourra pas se contenter de méthodes générales qui tiennent peu compte de l'existant et il sera nécessaire d'affecter des valeurs vraisemblables. Afin de traiter ce problème d'affectation de valeurs manquantes à des attributs, nous proposons de généraliser les algorithmes de décision avec des modèles plus simples et plus compréhensibles, de manière à faciliter et optimiser le travail de l'expert humain. Notre proposition consiste à partitionner les données en nous basant sur l'information stockée et sur l'absence de certaines valeurs, mais également sur l'information globale afin d'améliorer aussi les performances de traitement. L'apport de ce travail consiste en de nouveaux algorihmes, ainsi que des analyses pour la classification de matériaux de plantation. Nous donnons des résultats d'expérimentation sur des données réelles, qui sont susceptibles d'améliorer de manière significative le travail de sélection des graines de palmier à huileA missing value in incomplete information always inherent the accuracy of classification tasks when a decision tree is used to classify unseen cases. There will be cases where plausible values are required to retain towards more principled and less intrusive. In order to handle the attribute with missing values, the researcher generalizes decision algorithms that provide simpler and more understandable models to optimally fulfill human expert requirement and constraint. Our objective is to partition data by taking full advantage of the information with the presence of missing values ; but with supporting global information to achieve better performance. The contributions of this study are newly developed algorithms and analyses for planting material classification. The researcher reports the empirical results that may provide high returnin planting material breeders in oil palm industry through effective policies design and decision making
22
Villard, Caroline. "Sélection dans l'espace des solutions engendrées par un plan de construction géométrique." Université Louis Pasteur (Strasbourg) (1971-2008), 2001. http://www.theses.fr/2001STR13182.
Full text
23
Costes, Benoît. "Vers la construction d'un référentiel géographique ancien : un modèle de graphe agrégé pour intégrer, qualifier et analyser des réseaux géohistoriques." Thesis, Paris Est, 2016. http://www.theses.fr/2016PESC1032/document.
Full textAbstract:
Les historiens et archéologues ont efficacement mis à profit les travaux réalisés dans le domaine des SIG pour répondre à leurs propres problématiques. Pour l'historien, un Système d’Information Géographique est avant tout un outil de compréhension des phénomènes sociaux.De nombreuses sources géohistoriques sont aujourd'hui mises à la disposition des chercheurs: plans anciens, bottins, etc. Le croisement de ces sources d'informations diverses et hétérogènes soulève de nombreuses questions autour des dynamiques urbaines.Mais les données géohistoriques sont par nature imparfaites, et pour pouvoir être exploitées, elles doivent être spatialisées et qualifiées.L'objectif de cette thèse est d'apporter une solution à ce verrou par la production de données anciennes de référence. En nous focalisant sur le réseau des rues de Paris entre la fin du XVIIIe et la fin du XIXe siècles, nous proposons plus précisément un modèle multi-représentations de données agrégées permettant, par confrontation d'observations homologues dans le temps, de créer de nouvelles connaissances sur les imperfections des données utilisées et de les corriger. Nous terminons par tester le rôle de référentiel géohistorique des données précédemment qualifiées et enrichies en spatialisant et intégrant dans le modèle de nouvelles données géohistoriques de types variés (sociales et spatiales), en proposant de nouvelles approches d'appariement et de géocodageThe increasing availability of geohistorical data, particularly through the development of collaborative projects is a first step towards the design of a representation of space and its changes over time in order to study its evolution, whether social, administrative or topographical.Geohistorical data extracted from various and heterogeneous sources are highly inaccurate, uncertain or inexact according to the existing terminology. Before being processed, such data should be qualified and spatialized.In this thesis, we propose a solution to this issue by producing reference data. In particular, we focus on Paris historical street networks and its evolution between the end of the XVIIIth and the end of the XIXth centuries.Our proposal is based on a merged structure of multiple representations of data capable of modelling spatial networks at different times, providing tools such as pattern detection in order to criticize, qualify and eventually correct data and sources without using ground truth data but the comparison of data with each other through the merging process.Then, we use the produced reference data to spatialize and integrate other geohistorical data such as social data, by proposing new approaches of data matching and geocoding
24
Rivals, Cécile. "La construction d'une ville de confluence : les dynamiques spatiales de Saint-Antonin-Noble-Val (82) du Moyen âge à la période pré-industrielle." Thesis, Toulouse 2, 2015. http://www.theses.fr/2015TOU20053/document.
Full textAbstract:
La compréhension des processus conduisant à la construction d’une ville nécessite une approche pluridisciplinaire, dont les prismes utilisés ici sont l’archéologie, l’histoire, les mathématiques, la géographie et la géomatique. Les sources doivent être multiples, archéologiques, écrites, fiscales, iconographiques, planimétriques et les échelles variées, de la maison au territoire. La ville de Saint-Antonin-Noble-Val, deuxième agglomération du Rouergue au bas Moyen Âge, dont le développement est étroitement lié à la gestion du réseau hydrographique, constitue l’espace-laboratoire de cette recherche. Ce bourg monastique représente un véritable creuset pour la mise en place d’une nouvelle méthodologie élaborée pour étudier le phénomène urbain médiéval. Les sources fiscales médiévales et modernes, traditionnellement utilisées pour l’étude des paysages, sont modélisées sous forme de graphes d’adjacence des parcelles afin de percevoir les dynamiques de l’espace urbain sur le temps long. La comparaison des parcellaires entre le bas Moyen Âge et le XIXe siècle, rendue possible par l’utilisation de la théorie des graphes et le croisement avec les données archéologiques, permet d’approcher les modalités d’aménagement d’un territoire urbainUnderstanding the process leading to the construction of a city requires a multidisciplinary approach. Herein are included disciplines such as archeology, history, mathematics, geography and geomatic. The sources should be diverse (archaeological, written, tax, iconographic, planimetric) and the scales varied, from the house to the territory. The city of Saint-Antonin-Noble-Val, whose development was closely related to the hydrographic network management, was the second largest city of Rouergue in the Late Middle Ages; it constitutes this research lab-area. With the example of this monastic town, a new methodology developed to study medieval urban phenomenon is provided. In order to perceive the dynamics of urban space over time, both medieval and modern tax sources, traditionally used for landscape study, are modeled as adjacency graphs of the plots. The comparison between the cadastral allotment of the Late Middle Ages and the XIXth century is achieved using the graph theory and its intersections with available archaeological data; it allows to approach the arrangement modalities of an urban area
25
Constant, Matthieu. "Grammaires locales pour l'analyse automatique de textes : méthodes de construction et outils de gestion." Phd thesis, Université Paris-Est, 2003. http://tel.archives-ouvertes.fr/tel-00626252.
Full textAbstract:
L'explosion du nombre de documents disponibles (notamment sur Internet) a rendu le domaine du Traitement Automatique des Langues (TAL) et ses outils incontournables. De nombreux chercheurs marquent l'importance de la linguistique dans ce domaine. Ils préconisent la construction de larges bases de descriptions linguistiques, composées de lexiques et de grammaires. Cette démarche a un gros inconvénient : elle nécessite un investissement lourd qui s'inscrit sur le long terme. Pour palier à ce problème, il est nécessaire de mettre au point des méthodes et des outils informatiques d'aide à la construction de composants linguistiques fins et directement applicables à des textes. Nous nous sommes penché sur le problème des grammaires locales qui décrivent des contraintes précises et locales sous la forme de graphes. Deux questions fondamentales se posent : - Comment construire efficacement des grammaires précises, complètes et applicables à des textes ? - Comment gérer leur nombre et leur éparpillement ? Comme solution au premier problème, nous avons proposé un ensemble de méthodes simples et empiriques. Nous avons exposé des processus d'analyse linguistique et de représentation à travers deux phénomènes : les expressions de mesure (un immeuble d'une hauteur de 20 mètres) et les adverbes de lieu contenant un nom propre locatif (à l'île de la Réunion), deux points critiques du TAL. Sur la base de M. Gross (1975), nous avons ramené chaque phénomène à une phrase élémentaire. Ceci nous a permis de classer sémantiquement certains phénomènes au moyen de critères formels. Nous avons systématiquement étudié le comportement de ces phrases selon les valeurs lexicales de ses éléments. Les faits observés ont ensuite été représentés formellement soit directement dans des graphes à l'aide d'un éditeur, soit par l'intermédiaire de tables syntaxiques ensuite converties semiautomatiquement en graphes. Au cours de notre travail, nous avons été confronté à des systèmes relationnels de tables syntaxiques pour lesquels la méthode standard de conversion due à E. Roche (1993) ne fonctionnait plus. Nous avons donc élaboré une nouvelle méthode adaptée avec des formalismes et des algorithmes permettant de gérer le cas où les informations sur les graphes à construire se trouvent dans plusieurs tables. En ce qui concerne le deuxième problème, nous avons proposé et implanté un prototype de système de gestion de grammaires locales : une bibliothèque en-ligne de graphes. Le but à terme est de centraliser et de diffuser les grammaires locales construites au sein du réseau RELEX. Nous avons conçu un ensemble d'outils permettant à la fois de stocker de nouveaux graphes et de rechercher des graphes suivant différents critères. L'implémentation d'un moteur de recherche de grammaires nous a également permis de nous pencher sur un nouveau champ d'investigation dans le domaine de la recherche d'information : la recherche d'informations linguistiques dans des grammaires locales.
26
Minescu, Bogdan. "Construction et stratégie d'exploitation des réseaux de confusion en lien avec le contexte applicatif de la compréhension de la parole." Phd thesis, Université d'Avignon, 2008. http://tel.archives-ouvertes.fr/tel-00629195.
Full textAbstract:
Cette thèse s'intéresse aux réseaux de confusion comme représentation compacte et structurée des hypothèses multiples produites par un moteur de reconnaissance de parole et transmises à un module de post-traitement applicatif. Les réseaux de confusion (CN pour Confusion Networks) sont générés à partir des graphes de mots et structurent l'information sous la forme d'une séquence de classes contenant des hypothèses de mots en concurrence. Le cas d'usage étudié dans ces travaux est celui des hypothèses de reconnaissance transmises à un module de compréhension de la parole dans le cadre d'une application de dialogue déployée par France Telecom. Deux problématiques inhérentes à ce contexte applicatif sont soulevées. De façon générale, un système de dialogue doit non seulement reconnaître un énoncé prononcé par un utilisateur, mais aussi l'interpréter afin de déduire sons sens. Du point de vue de l'utilisateur, les performances perçues sont plus proches de celles de la chaîne complète de compréhension que de celles de la reconnaissance vocale seule. Ce sont ces performances que nous cherchons à optimiser. Le cas plus particulier d'une application déployée implique de pouvoir traiter des données réelles et donc très variées. Un énoncé peut être plus ou moins bruité, dans le domaine ou hors-domaine, couvert par le modèle sémantique de l'application ou non, etc. Étant donnée cette grande variabilité, nous posons la question de savoir si le fait d'appliquer les mêmes traitements sur l'ensemble des données, comme c'est le cas dans les approches classiques, est une solution adaptée. Avec cette double perspective, cette thèse s'attache à la fois à enrichir l'algorithme de construction des CNs dans le but d'optimiser globalement le processus de compréhension et à proposer une stratégie adéquate d'utilisation des réseaux de confusion dans le contexte d'une application réelle. Après une analyse des propriétés de deux approches de construction des CNs sur un corpus de données réelles, l'algorithme retenu est celui du "pivot". Nous en proposons une version modifiée et adaptée au contexte applicatif en introduisant notamment un traitement différencié des mots du graphe qui privilégie les mots porteurs de sens. En réponse à la grande variabilité des énoncés à traiter dans une application déployée, nous proposons une stratégie de décision à plusieurs niveaux qui vise à mieux prendre en compte les spécificités des différents types d'énoncés. Nous montrons notamment qu'il est préférable de n'exploiter la richesse des sorties multiples que sur les énoncés réellement porteurs de sens. Cette stratégie permet à la fois d'optimiser les temps de calcul et d'améliorer globalement les performances du système
27
Le, goff Nicolas. "Construction of a conformal hexahedral mesh from volume fractions : theory and applications." Electronic Thesis or Diss., université Paris-Saclay, 2020. http://www.theses.fr/2020UPASG033.
Full textAbstract:
Ces travaux abordent le problème de la génération automatique de maillages hexaédriques pour des codes de simulation, à partir d'un maillage portant des fractions volumiques, c'est-à-dire dont les mailles peuvent contenir plusieurs matériaux. La solution proposée doit contruire un maillage hexaédrique dans lequel chaque maille correspond à un seul matériau, et dont les interfaces entre matériaux doivent former des surfaces lisses. D'un point de vue théorique, nous cherchons à adapter et étendre des solutions existantes, et à les appliquer sur une large variété d'exemples : certains issus de modèles de CAO (plaqués sur un maillage pour obtenir des fractions volumiques), d'autres générés procéduralement et enfin d'autres utilisés dans un rôle d'intercode, récupérés en sortie de codes de simulation. Nous définissons une métrique permettant d'évaluer notre (et d'autres) méthodes, ainsi qu'un post-processus pour améliorer ces résultats; nous introduisons également une méthode de reconstruction d'interfaces discrètes inspirés de méthodes issues du domaine de la visualisation scientifique, et nous proposons un algorithme appelé {sc ELG} avec garantie sur la qualité du maillage, faisant intervenir des modifications géométriques et topologiques sur ce maillageThis thesis addresses the problem of the automatic generation of purely hexahedral meshes for simulation codes when having a mesh carrying volume fraction data as an input, meaning that there can be several materials inside one cell. The proposed approach should create an hexahedral mesh where each cell corresponds to a single material, and where interfaces between materials form smooth surfaces. From a theoretical standpoint, we aim at adapting and extending state-of-the-art techniques and we apply them on examples, some classically issued from CAD models (and imprinted onto a mesh to obtain volume fractions), some procedurally generated cases and others in an intercode capacity where we take the results of a first simulation code to be our inputs. We first define a metric that allows the evaluation of our (or others') results and a method to improve those; we then introduce a discrete material interface reconstruction method inspired from the scientific visualization field and finally we present an algorithmic pipeline, called {sc ELG}, that offers a guarantee on the mesh quality by performing geometrical and topological mesh adaptation
28
François, Hélène. "Synthèse de la parole par concaténation d'unités acoustiques : construction et exploitation d'une base de parole continue." Rennes 1, 2002. http://www.theses.fr/2002REN10127.
Full textAbstract:
Ces travaux s'inscrivent dans le cadre de la synthèse de la parole par concaténation d'unités acoustiques de taille variable multi-représentées. Pour remédier à l'hétérogénéité de la qualité et de l'intelligibilité des voix synthétiques, nous utilisons une base de parole continue riche au niveau linguistique, ici un jeu de phrases naturelles. Sa construction est vue comme un problème NP-complet de recouvrement minimal d'ensemble. Les méthodes gloutonne, cracheuse et d'échange par paire condensent ainsi des corpus de 100000 à 5000 phrases. Ensuite nous cherchons dans un corpus spécifique l'ensemble des séquences d'unités acoustiques permettant la synthèse de 10 phrases tests. Pour chaque séquence trouvée ses unités sont concaténées, puis sa qualité est évaluée de façon objective en mesurant sa distance acoustique à une référence naturelle. Cela permet de spécifier et de caractériser des bases "génératives", de développer et d'évaluer de nouvelles méthodes de sélection d'unités.
29
Mazari, Ahmed. "Apprentissage profond pour la reconnaissance d’actions en vidéos." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS171.
Full textAbstract:
De nos jours, les contenus vidéos sont omniprésents grâce à Internet et les smartphones, ainsi que les médias sociaux. De nombreuses applications de la vie quotidienne, telles que la vidéo surveillance et la description de contenus vidéos, ainsi que la compréhension de scènes visuelles, nécessitent des technologies sophistiquées pour traiter les données vidéos. Il devient nécessaire de développer des moyens automatiques pour analyser et interpréter la grande quantité de données vidéo disponibles. Dans cette thèse, nous nous intéressons à la reconnaissance d'actions dans les vidéos, c.a.d au problème de l'attribution de catégories d'actions aux séquences vidéos. Cela peut être considéré comme un ingrédient clé pour construire la prochaine génération de systèmes visuels. Nous l'abordons avec des méthodes d'intelligence artificielle, sous le paradigme de l'apprentissage automatique et de l'apprentissage profond, notamment les réseaux de neurones convolutifs. Les réseaux de neurones convolutifs actuels sont de plus en plus profonds, plus gourmands en données et leur succès est donc tributaire de l'abondance de données d'entraînement étiquetées. Les réseaux de neurones convolutifs s'appuient également sur le pooling qui réduit la dimensionnalité des couches de sortie (et donc atténue leur sensibilité à la disponibilité de données étiquetées)Nowadays, video contents are ubiquitous through the popular use of internet and smartphones, as well as social media. Many daily life applications such as video surveillance and video captioning, as well as scene understanding require sophisticated technologies to process video data. It becomes of crucial importance to develop automatic means to analyze and to interpret the large amount of available video data. In this thesis, we are interested in video action recognition, i.e. the problem of assigning action categories to sequences of videos. This can be seen as a key ingredient to build the next generation of vision systems. It is tackled with AI frameworks, mainly with ML and Deep ConvNets. Current ConvNets are increasingly deeper, data-hungrier and this makes their success tributary of the abundance of labeled training data. ConvNets also rely on (max or average) pooling which reduces dimensionality of output layers (and hence attenuates their sensitivity to the availability of labeled data); however, this process may dilute the information of upstream convolutional layers and thereby affect the discrimination power of the trained video representations, especially when the learned action categories are fine-grained
30
Polette, Arnaud. "Analyse de maillages surfaciques par construction et comparaison de modèles moyens et par décomposition par graphes s'appuyant sur les courbures discrètes : application à l'étude de la cornée humaine." Thesis, Aix-Marseille, 2015. http://www.theses.fr/2015AIXM4084/document.
Full textAbstract:
Cette thèse se découpe en trois parties. Les deux premières portent sur le développement de méthodes pour la construction de modèles géométriques moyens et pour la comparaison de modèles. Plusieurs problématiques sont abordées, telles que la construction d'une cornée moyenne et la comparaison de cornées. Il existe à ce jour peu d'études ayant ces objectifs car la mise en correspondance de surfaces cornéennes est une problématique non triviale. En plus d'aider à développer la connaissance de l'anatomie cornéenne, la modélisation de la cornée normale permet de détecter tout écart significatif par rapport à la normale permettant un diagnostic précoce de pathologies. La seconde partie a pour objectif de développer une méthode pour reconnaître une surface parmi un groupe de surfaces à l’aide de leurs acquisitions pour une application de biométrie. L’idée est de quantifier la différence entre chaque surface et une surface donnée, et de déterminer un seuil permettant la reconnaissance. Deux méthodes sont proposées et une méthodologie en cascade utilisant ces deux méthodes afin de combiner les avantages de chacune est aussi proposée. La troisième et dernière partie porte sur une nouvelle méthode de décomposition en graphes de maillages 3D triangulés. Nous utilisons des cartes de courbures discrètes comme descripteur de forme afin de découper le maillage en différentes catégorie de carreaux. Ensuite un graphe d'adjacence est construit avec un nœud pour chaque carreau. Ces graphes sont utilisés pour extraire des caractéristiques géométriques décrites par des motifs (ou patterns), ce qui permet de détecter des régions spécifiques dans un modèle 3D, ou des motifs récurrentsThis thesis comprises three parts. The first two parts concern the development of methods for the construction of mean geometric models and for model comparison. Several issues are addressed, such as the construction of an average cornea and the comparison of corneas. Currently, there are few studies with these objectives because the matching of corneal surfaces is a non-trivial problem. In addition to help to develop a better understanding of the corneal anatomy, 3D models of normal corneas can be used to detect any significant deviation from the norm, thereby allowing for an early diagnosis of diseases or abnormalities using the shape of the cornea. The second part of this thesis aims to develop a method for recognizing a surface from a group of surfaces using their 3D acquisitions in a biometric application pertinent to the cornea. The concept behind this method is to quantify the difference between each surface and a given surface and to determine the threshold for recognition. Two complementary methods are proposed. A cascading methodology using both methods to combine the advantages of each method is also proposed. The third and final part of this thesis focuses on a new method for decomposing 3D triangulated meshes into graphs. We use discrete curvature maps as the shape descriptor to split the mesh in eight different categories. Next, an adjacency graph is built with a node for each patch. These graphs are used to extract geometric characteristics described by patterns that allow for the detection of specific regions in a 3D model or recurrent characteristics
31
Venant, Fabienne. "Représentation et calcul dynamique du sens : exploration du lexique adjectival du français." Phd thesis, Ecole des Hautes Etudes en Sciences Sociales (EHESS), 2006. http://tel.archives-ouvertes.fr/tel-00067902.
Full textAbstract:
Ce travail de thèse présente un modèle de construction du sens d'un genre nouveau, défini dans le cadre des mathématiques du continu. Le langage y est vu comme un système morphodynamique, obéissant aux principes de base de la Gestalttheorie. Les unités linguistiques découpent leur sens dans un espace sémantique possédant une structure de variété différentiable. Nous avons implémenté ce modèle et l'avons testé sur le lexique adjectival français. Une méthode de construction automatique des espaces sémantiques, reposant sur l'analyse d'un graphe de synonymie, permet d'explorer le lexique adjectival dans son ensemble, ou de construire des espaces locaux. Les espaces sémantiques locaux servent de base à une méthode dynamique de calcul du sens, permettant de prendre en compte les différents facteurs de polysémie adjectivale. L'utilisation des espaces sémantiques globaux ouvre de belles perspectives, tant dans le domaine du calcul du sens que celui de l'exploration de graphes petit monde.
32
Kamat, Vineet Rajendra. "Enabling 3D Visualization of Simulated Construction Operations." Thesis, Virginia Tech, 2000. http://hdl.handle.net/10919/35470.
Full textAbstract:
Simulation modeling and visualization can substantially help in designing complex
construction operations and in making optimal decisions where traditional methods prove
ineffective or are unfeasible. However, there has been limited use of simulation in
planning construction operations due to the unavailability of appropriate visual
communication tools that can provide users with a more realistic and comprehensible
feedback from simulation analyses. Visualizing simulated construction operations in 3D
can significantly help in establishing the credibility of simulation models. In addition, 3D
visualization can provide valuable insight into the subtleties of construction operations
that are otherwise non-quantifiable and presentable.
New software development technologies emerge at incredible rates that allow engineers
and scientists to create novel, domain-specific applications. This study capitalized on a
computer graphics technology based on the concept of the "Scene Graph" to design and
implement a general-purpose 3D Visualization System that is Simulation and CAD-software
independent. This system, the "Dynamic Construction Visualizer", enables
realistic visualization of modeled construction operations and the resulting products in
3D and can be used in conjunction with a wide variety of simulation tools. This thesis
describes the "Dynamic Construction Visualizer" as well as the "Scene Graph"
architecture and the Frame Updating algorithms used in its design.Master of Science
33
Rivierre, Yvan. "Algorithmes auto-stabilisants pour la construction de structures couvrantes réparties." Thesis, Grenoble, 2013. http://www.theses.fr/2013GRENM089/document.
Full textAbstract:
Cette thèse s'intéresse à la construction auto-stabilisante de structures couvrantes dans un système réparti. L'auto-stabilisation est un paradigme pour la tolérance aux fautes dans les algorithmes répartis. Plus précisément, elle garantit que le système retrouve un comportement correct en temps fini après avoir été perturbé par des fautes transitoires. Notre modèle de système réparti se base sur des mémoires localement partagées pour la communication, des identifiants uniques pour briser les symétries et un ordonnanceur inéquitable, c'est-à-dire le plus faible des ordonnanceurs. Dans la mesure du possible, nous nous imposons d'utiliser les plus faibles hypothèses, afin d'obtenir les constructions les plus générales de structures couvrantes réparties. Nous présentons quatre algorithmes auto-stabilisants originaux pour le k-partitionnement, la construction d'une (f,g)-alliance et l'indexation. Pour chacun de ces problèmes, nous prouvons la correction de nos solutions. De plus, nous analysons leur complexité en temps et en espace à l'aide de preuves formelles et de simulations. Enfin, pour le problème de (f,g)-alliance, nous prenons en compte la notion de convergence sûre qui vient s'ajouter à celle d'auto-stabilisation. Elle garantit d'abord que le comportement du système assure rapidement un minimum de conditions, puis qu'il continue de converger jusqu'à se conformer à une spécification plus exigeanteThis thesis deals with the self-stabilizing construction of spanning structures over a distributed system. Self-stabilization is a paradigm for fault-tolerance in distributed algorithms. It guarantees that the system eventually satisfies its specification after transient faults hit the system. Our model of distributed system assumes locally shared memories for communicating, unique identifiers for symmetry-breaking, and distributed daemon for execution scheduling, that is, the weakest proper daemon. More generally, we aim for the weakest possible assumptions, such as arbitrary topologies, in order to propose the most versatile constructions of distributed spanning structures. We present four original self-stabilizing algorithms achieving k-clustering, (f,g)-alliance construction, and ranking. For every of these problems, we prove the correctness of our solutions. Moreover, we analyze their time and space complexity using formal proofs and simulations. Finally, for the (f,g)-alliance problem, we consider the notion of safe convergence in addition to self-stabilization. It enforces the system to first quickly satisfy a specification that guarantees a minimum of conditions, and then to converge to a more stringent specification
34
Nickle, Elspeth J., and University of Lethbridge Faculty of Arts and Science. "Classes of arrangement graphs in three dimensions." Thesis, Lethbridge, Alta. : University of Lethbridge, Faculty of Arts and Science, 2005, 2005. http://hdl.handle.net/10133/632.
Full textAbstract:
A 3D arrangement graph G is the abstract graph induced by an arrangement of planes in general
position where the intersection of any two planes forms a line of intersection and an intersection
of three planes creates a point. The properties of three classes of arrangement graphs — four, five
and six planes — are investigated. For graphs induced from six planes, specialized methods were
developed to ensure all possible graphs were discovered. The main results are: the number of 3D
arrangement graphs induced by four, five and six planes are one, one and 43 respectively; the three
classes are Hamiltonian; and the 3D arrangement graphs created from four and five planes are planar
but none of the graphs created from six planes are planar.x, 89 leaves : ill. (some col.) ; 29 cm
35
Nguyen, Viet hang. "Approches constructives à la rigidité des charpentes." Phd thesis, Université de Grenoble, 2013. http://tel.archives-ouvertes.fr/tel-00992387.
Full textAbstract:
La théorie de la rigidité étudie l'unicité des réalisations des graphes, i.e., des charpentes. Initialement motivée par l'ingénierie des structures, la théorie de la rigidité trouve aujourd'hui des applications dans plusieurs domaines importants comme la prédiction de la flexibilité des protéines, la conception assistée par ordinateur, la localisation dans les réseaux des capteurs, etc. Cette thèse traite une grande variété de problèmes concernant différents types de rigidité, qui correspondent à différents niveaux d'unicité (locale/infinitésimale, globale et universelle) dans des modèles variés de charpentes. D'abord, nous développons des résultats sur la construction récursive et la décomposition des graphes avec des conditions mixtes de sparsité ainsi que des résultats sur le packing des arborescences avec des contraintes de matroïde. Ces résultats sont alors utilisés pour obtenir des caractérisations de la rigidité infinitésimale des charpentes avec des contraintes mixtes. Nous étudions aussi l'effet des opérations d'extension sur des charpentes et étendons un résultat connu sur la préservation de la rigidité globale d'$1$-extension dans les charpentes à direction et à longueur de la dimension deux aux dimensions supérieures. Pour la rigidité universelle, un sujet que l'on connait très peu, nous obtenons une caractérisation complète pour la classe des charpentes biparties complètes sur la ligne. Nous généralisons aussi une condition suffisante pour la rigidité universelle des charpentes en permettant des positions non générales.
36
Lountzi, Angeliki. "Expander Graphs and Explicit Constructions." Thesis, Uppsala universitet, Algebra och geometri, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-274643.
Full text
37
Small, Benjamin Luke. "On alpha-critical graphs and their construction." Thesis, Washington State University, 2015. http://pqdtopen.proquest.com/#viewpdf?dispub=3717480.
Full textAbstract:
A graph G is α-critical (or removal-critical) if α(G–e) = α(G)+1 for all edges ∈ 2 E(G), where α( G) is the vertex independence number of G. Similarly, a graph G is contraction-critical if α(G\e ) = α(G) – 1 for all edges e ∈ (G). This document discusses certain properties of removal-critical and contractioncritical graphs, and the enumeration of such graphs (up to 13 vertices and 17 vertices, respectively). It also discusses methods of constructing removal-critical graphs from smaller removal-critical graphs, including vertex duplication, splicing, buckling, and 1-joining. Finally, it discusses the number of removal-critical graphs that can or cannot be produced using these constructions.
38
Casamento, Katherine Imhoff. "Correct-by-Construction Typechecking with Scope Graphs." PDXScholar, 2019. https://pdxscholar.library.pdx.edu/open_access_etds/5272.
Full textAbstract:
Dependently-typed languages are well-known for the ability to enforce program invariants through type signatures, and previous work establishes the effectiveness of this style of program verification in the implementation of type-safe interpreters for a wide class of languages with a variety of interesting scoping semantics, offering an account of dynamic semantics. This thesis covers the complementary topic of static semantics, in the form of a pattern for constructing verified typechecking procedures in a dependently-typed setting. Implementations are given for simply-typed lambda calculus and a small procedural language as well as a module system with unrestricted cyclic module dependency semantics that are traditionally hard to formalize, parameterized over the choice of base language. A library of finite graphs and decision procedures for path search queries is presented and used in the construction of the example language implementations to resolve variable references. The resulting development is suitable as a static analysis phase ("middle end") in a hypothetical end-to-end verified interpreter developed in a dependently-typed setting.
39
Ridremont, Thomas. "Design of robust networks : application to the design of wind farm cabling networks." Electronic Thesis or Diss., Paris, CNAM, 2019. http://www.theses.fr/2019CNAM1228.
Full textAbstract:
Aujourd’hui, la conception de réseaux est une problématique cruciale qui se pose dans beaucoup de domaines tels que le transport ou l’énergie. En particulier, il est devenu nécessaire d’optimiser la façon dont sont conçus les réseaux permettant de produire de l’énergie. On se concentre ici sur la production électrique produite à travers des parcs éoliens. Cette énergie apparait plus que jamais comme une bonne alternative à la production d’électricité via des centrales thermiques ou nucléaires.Nous nous intéressons dans cette thèse à la conception du câblage collectant l’énergie dans les parcs éoliens. On connaît alors la position de l’ensemble des éoliennes appartenant au parc ainsi que celle du site central collecteur vers laquelle l’énergie doit être acheminée. On connaît également la position des câbles que l’on peut construire, leurs capacités, et la position des nœuds d’interconnexion possibles. Il s’agit de déterminer un câblage de coût minimal permettant de relier l’ensemble des éoliennes à la sous-station, tel que celui-ci soit résistant à un certain nombre de pannes sur le réseauNowadays, the design of networks has become a decisive problematic which appears in many fields such as transport or energy. In particular, it has become necessary and important to optimize the way in which networks used to produce, collect or transport energy are designed. We focus in this thesis on electricity produced through wind farms. The production of energy by wind turbines appears more than ever like a good alternative to the electrical production of thermal or nuclear power plants.We focus in this thesis on the design of the cabling network which allows to collect and route the energy from the wind turbines to a sub-station, linking the wind farm to the electrical network. In this problem, we know the location of each wind turbine of the farm and the one of the sub-station. We also know the location of possible inter-connection nodes which allow to connect different cables between them. Each wind turbine produces a known quantity of energy and with each cable are associated a cost and a capacity (the maximum amount of energy that can be routed through this cable). The optimizationproblem that we consider is to select a set of cables of minimum cost such that the energy produced from the wind turbines can be routed to the sub-station in the network induced by this set of cables, without exceeding the capacity of each cable. We focus on cabling networks resilient to breakdowns
40
Gasquoine, Sarah Louise. "Finite and infinite extensions of regular graphs." Thesis, Queen Mary, University of London, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.313750.
Full text
41
Hunt, D'Hania J. "Constructing higher-order de Bruijn graphs." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 2002. http://library.nps.navy.mil/uhtbin/hyperion-image/02Jun%5FHunt.pdf.
Full textAbstract:
Thesis (M.S. in Applied Mathematics)--Naval Postgraduate School, June 2002.Thesis advisor(s): Harold Fredricksen, Craig W. Rasmussen. Includes bibliographical references (p. 45-46). Also available online.
42
Buchele, Suzanne Fox. "Three-dimensional binary space partitioning tree and constructive solid geometry tree construction from algebraic boundary representations /." Digital version accessible at:, 1999. http://wwwlib.umi.com/cr/utexas/main.
Full text
43
Johansson, David. "Construction of Superimposed Codes Using Graphs and Galois Fields." Thesis, Karlstads universitet, Institutionen för matematik och datavetenskap (from 2013), 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kau:diva-62862.
Full textAbstract:
In this thesis some constructions of superimposed codes are presented. Many of the known nontrivial constructions arise from t−designs, and the constructions discussed in this thesis is also based on a block design idea. Superimposed codes are rather combinatorial in nature, so the connection to t−designs is not too surprising. What may be a little surprise, however, is the connection between superimposed codes and linear codes and Galois elds. Linear codes are quite intuitive and have nice properties, as is the case for Galois elds; combinatorial structures are quite often the contrary, not intuitive and quite dicult to understand. Because of this, it is interesting that a combinatorial structure like superimposed codes can be constructed from structures like linear codes and Galois elds. The main goal of this thesis is to present two possibly new approaches to construct superimposed codes. The constructions are described, but not proved to be correct. The rst construction presented is using graphs. In practice, this is not a good way to construct codes, since it requires the construction of a graph and nding certain cycles in the graph. It is still an interesting construction, however, since it provides a connection between constant weight codes and superimposed codes. Another construction is presented, one that seems much more useful when constructing codes. In [7] one particular superimposed code is constructed from a Galois eld. In this thesis we will see that this construction using Galois elds can be generalized.I denna uppsats presenteras några konstruktioner av överlagrade koder. Många av de redan kända konstruktionerna har sitt ursprung i t-designer, och även konstruktionerna som behandlas i denna uppsats är baserade på en blockdesignsidé. Överlagrade koder är tämligen kombinatoriska till sin natur, så kopplingen mellan överlagrade koder och t-designer är inte speciellt överraskande. Däremot kan kopplingen mellan överlagrade koder, linjära koder och Galoiskroppar vara överraskande. Linjära koder är ganska intuitiva och har trevliga egenskaper, likaså Galoiskroppar; kombinatoriska strukturer är ofta tvärt om, inte intuitiva och svåra att förstå. På grund av detta är det intressant att kombinatoriska strukturer som överlagrade koder kan konstrueras med hjälp av strukturer som linjära koder och Galoiskroppar. Det primära målet med denna uppsats är att presentera två möjligen nya konstruktioner av överlagrade koder. Konstruktionerna beskrivs men deras korrekthet bevisas inte. Den första konstruktionen som presenteras är baserad på grafer. I praktiken är denna konstruktionen inte bra för att skapa koder, eftersom den kräver konstruktion av en graf och sedan att hitta vissa cykler i grafen. Det är dock fortfarande en intressant konstruktion, eftersom den bidrar till en intressant koppling mellan konstantvikt koder och överlagrade koder. En annan konstruktion presenteras, och den är mycket mer praktiskt användbar. I [7] skapas en specik överlagrad kod med hjälp av en Galoiskropp. I denna uppsats ser vi hur denna konstruktion med Galoiskroppar kan generaliseras.
44
Garnero, Valentin. "(Méta)-noyaux constructifs et linéaires dans les graphes peu denses." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT328/document.
Full textAbstract:
En algorithmique et en complexité, la plus grande part de la recherche se base sur l’hypothèse que P ≠ NP (Polynomial time et Non deterministic Polynomial time), c'est-à-dire qu'il existe des problèmes dont la solution peut être vérifiée mais non construite en temps polynomial. Si cette hypothèse est admise, de nombreux problèmes naturels ne sont pas dans P (c'est-à-dire, n'admettent pas d'algorithme efficace), ce qui a conduit au développement de nombreuses branches de l'algorithmique. L'une d'elles est la complexité paramétrée. Elle propose des algorithmes exacts, dont l'analyse est faite en fonction de la taille de l'instance et d'un paramètre. Ce paramètre permet une granularité plus fine dans l'analyse de la complexité.Un algorithme sera alors considéré comme efficace s'il est à paramètre fixé, c'est-à-dire, lorsque sa complexité est exponentielle en fonction du paramètre et polynomiale en fonction de la taille de l'instance. Ces algorithmes résolvent les problèmes de la classe FPT (Fixed Parameter Tractable).L'extraction de noyaux est une technique qui permet, entre autre, d’élaborer des algorithmes à paramètre fixé. Elle peut être vue comme un pré-calcul de l'instance, avec une garantie sur la compression des données. Plus formellement, une extraction de noyau est une réduction polynomiale depuis un problème vers lui même, avec la contrainte supplémentaire que la taille du noyau (l'instance réduite) est bornée en fonction du paramètre. Pour obtenir l’algorithme à paramètre fixé, il suffit de résoudre le problème dans le noyau, par exemple par une recherche exhaustive (de complexité exponentielle, en fonction du paramètre). L’existence d'un noyau implique donc l'existence d'un algorithme à paramètre fixé, la réciproque est également vraie. Cependant, l’existence d'un algorithme à paramètre fixé efficace ne garantit pas un petit noyau, c'est a dire un noyau dont la taille est linéaire ou polynomiale. Sous certaines hypothèses, il existe des problèmes n’admettant pas de noyau (c'est-à-dire hors de FPT) et il existe des problèmes de FPT n’admettant pas de noyaux polynomiaux.Un résultat majeur dans le domaine des noyaux est la construction d'un noyau linéaire pour le problème Domination dans les graphes planaires, par Alber, Fellows et Niedermeier.Tout d'abord, la méthode de décomposition en régions proposée par Alber, Fellows et Niedermeier, a permis de construire de nombreux noyaux pour des variantes de Domination dans les graphes planaires. Cependant cette méthode comportait un certain nombre d’imprécisions, ce qui rendait les preuves invalides. Dans la première partie de notre thèse, nous présentons cette méthode sous une forme plus rigoureuse et nous l’illustrons par deux problèmes : Domination Rouge Bleue et Domination Totale.Ensuite, la méthode a été généralisée, d'une part, sur des classes de graphes plus larges (de genre borné, sans-mineur, sans-mineur-topologique), d'autre part, pour une plus grande variété de problèmes. Ces méta-résultats prouvent l’existence de noyaux linéaires ou polynomiaux pour tout problème vérifiant certaines conditions génériques, sur une classe de graphes peu denses. Cependant, pour atteindre une telle généralité, il a fallu sacrifier la constructivité des preuves : les preuves ne fournissent pas d'algorithme d'extraction constructif et la borne sur le noyau n'est pas explicite. Dans la seconde partie de notre thèse nous effectuons un premier pas vers des méta-résultats constructifs ; nous proposons un cadre général pour construire des noyaux linéaires en nous inspirant des principes de la programmation dynamique et d'un méta-résultat de Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh et ThilikosIn the fields of Algorithmic and Complexity, a large area of research is based on the assumption that P ≠ NP(Polynomial time and Non deterministic Polynomial time), which means that there are problems for which a solution can be verified but not constructed in polynomial time. Many natural problems are not in P, which means, that they have no efficient algorithm. In order to tackle such problems, many different branches of Algorithmic have been developed. One of them is called Parametric Complexity. It consists in developing exact algorithms whose complexity is measured as a function of the size of the instance and of a parameter. Such a parameter allows a more precise analysis of the complexity. In this context, an algorithm will be considered to be efficient if it is fixed parameter tractable (fpt), that is, if it has a complexity which is exponential in the parameter and polynomial in the size of the instance. Problems that can be solved by such an algorithm form the FPT class.Kernelisation is a technical that produces fpt algorithms, among others. It can be viewed as a preprocessing of the instance, with a guarantee on the compression of the data. More formally, a kernelisation is a polynomial reduction from a problem to itself, with the additional constraint that the size of the kernel, the reduced instance, is bounded by a function of the parameter. In order to obtain an fpt algorithm, it is sufficient to solve the problem in the reduced instance, by brute-force for example (which has exponential complexity, in the parameter). Hence, the existence of a kernelisiation implies the existence of an fpt algorithm. It holds that the converse is true also. Nevertheless, the existence of an efficient fpt algorithm does not imply a small kernel, meaning a kernel with a linear or polynomial size. Under certain hypotheses, it can be proved that some problems can not have a kernel (that is, are not in FPT) and that some problems in FPT do not have a polynomial kernel.One of the main results in the field of Kernelisation is the construction of a linear kernel for the Dominating Set problem on planar graphs, by Alber, Fellows and Niedermeier.To begin with, the region decomposition method proposed by Alber, Fellows and Niedermeier has been reused many times to develop kernels for variants of Dominating Set on planar graphs. Nevertheless, this method had quite a few inaccuracies, which has invalidated the proofs. In the first part of our thesis, we present a more thorough version of this method and we illustrate it with two examples: Red Blue Dominating Set and Total Dominating Set.Next, the method has been generalised to larger classes of graphs (bounded genus, minor-free, topological-minor-free), and to larger families of problems. These meta-results prove the existence of a linear or polynomial kernel for all problems verifying some generic conditions, on a class of sparse graphs. As a price of generality, the proofs do not provide constructive algorithms and the bound on the size of the kernel is not explicit. In the second part of our thesis, we make a first step to constructive meta-results. We propose a framework to build linear kernels based on principles of dynamic programming and a meta-result of Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh and Thilikos
45
Wauquier, Pauline. "Task driven representation learning." Thesis, Lille 3, 2017. http://www.theses.fr/2017LIL30005/document.
Full textAbstract:
De nombreux algorithmes d'Apprentissage automatique ont été proposés afin de résoudre les différentes tâches pouvant être extraites des problèmes de prédiction issus d'un contexte réel. Pour résoudre les différentes tâches pouvant être extraites, la plupart des algorithmes d'Apprentissage automatique se basent d'une manière ou d'une autre sur des relations liant les instances. Les relations entre paires d'instances peuvent être définies en calculant une distance entre les représentations vectorielles des instances. En se basant sur la représentation vectorielle des données, aucune des distances parmi celles communément utilisées n'est assurée d'être représentative de la tâche à résoudre. Dans ce document, nous étudions l'intérêt d'adapter la représentation vectorielle des données à la distance utilisée pour une meilleure résolution de la tâche. Nous nous concentrons plus précisément sur l'algorithme existant résolvant une tâche de classification en se basant sur un graphe. Nous décrivons d'abord un algorithme apprenant une projection des données dans un espace de représentation permettant une résolution, basée sur un graphe, optimale de la classification. En projetant les données dans un espace de représentation dans lequel une distance préalablement définie est représentative de la tâche, nous pouvons surpasser la représentation vectorielle des données lors de la résolution de la tâche. Une analyse théorique de l'algorithme décrit est développée afin de définir les conditions assurant une classification optimale. Un ensemble d'expériences nous permet finalement d'évaluer l'intérêt de l'approche introduite et de nuancer l'analyse théoriqueMachine learning proposes numerous algorithms to solve the different tasks that can be extracted from real world prediction problems. To solve the different concerned tasks, most Machine learning algorithms somehow rely on relationships between instances. Pairwise instances relationships can be obtained by computing a distance between the vectorial representations of the instances. Considering the available vectorial representation of the data, none of the commonly used distances is ensured to be representative of the task that aims at being solved. In this work, we investigate the gain of tuning the vectorial representation of the data to the distance to more optimally solve the task. We more particularly focus on an existing graph-based algorithm for classification task. An algorithm to learn a mapping of the data in a representation space which allows an optimal graph-based classification is first introduced. By projecting the data in a representation space in which the predefined distance is representative of the task, we aim at outperforming the initial vectorial representation of the data when solving the task. A theoretical analysis of the introduced algorithm is performed to define the conditions ensuring an optimal classification. A set of empirical experiments allows us to evaluate the gain of the introduced approach and to temper the theoretical analysis
46
Mosbah, Mohamed. "Constructions d'algorithmes pour les graphes structurés par des méthodes algébriques et logiques." Bordeaux 1, 1992. http://www.theses.fr/1992BOR10511.
Full textAbstract:
Ce travail definit, au moyen de la logique monadique du second-ordre et d'homomorphismes de semi-anneaux, des fonctions calculables efficacement, sur les graphes structures en arbres, de largeur arborescente bornee. Nous obtenons, ainsi, des algorithmes polynomiaux et meme lineaires pour plusieurs problemes, dont beaucoup sont np-complets, lorsqu'ils sont restreints aux graphes structures en arbres, de largeur bornee. Cette approche est etendue a d'autres fonctions telles que le diametre, et est appliquee aux grammaires de graphes probabilistes. Nous presentons, en particulier, des methodes pour calculer la valeur moyenne d'une fonction, de la classe consideree, sur une grammaire de graphes probabiliste
47
Pinto, Guilherme Vituri Fernandes. "Motivic constructions on graphs and networks with stability results /." São José do Rio Preto, 2020. http://hdl.handle.net/11449/192494.
Full textAbstract:
Orientador: Thiago de MeloResumo: Neste trabalho estudamos certos funtores sobre grafos, chamados de representáveis ou motívicos. Esses funtores não mudam os vértices de um grafo, mas apenas suas setas (as arestas direcionadas). Quaisquer tais funtores podem ser estendidos para networks (uma generalização de espaços métricos). Funtores de clustering sobre grafos dão origem a funtores de hierarchical clustering sobre networks. Mais ainda, podemos modificar a definição de funtor representável para criar filtrações de complexos simpliciais, que tem como caso particular os complexos de Vietoris-Rips e Cech. Isso faz com que possamos aplicar o funtor de homologia ˇ simplicial e obter um diagrama de persistência, como usual em Análise Topológica de Dados. Obtivemos resultados de estabilidade com respeito à distância bottleneck e à distância network, quando uma certa condição é imposta nos motivos de um funtor representável. Algumas operações sobre grafos (e.g., produtos e suspensão) também podem ser estendidas para networks, e três fórmulas de Künneth foram obtidas. Finalmente, alguns algoritmos e códigos para casos especiais são fornecidos com exemplos.
Doutor
48
POLVERINO, SALVATORE. "Graphene-based construction materials: experimentation and application development." Doctoral thesis, Università degli studi di Genova, 2021. http://hdl.handle.net/11567/1058131.
Full textAbstract:
The construction sector is entering the new era of production, construction and management of Industry 4.0. The development of smart and resilient technologies focused on the user and the environment has significant potential to improve the ways of experiencing indoor and outdoor spaces. This scenario generates new opportunities to exploit innovation to create the conditions for human well-being and to contribute to the future of the Earth.
The construction sector is in a period of transition. On the one hand, there is a demand for construction with high technological content, capable of incorporating innovations at low cost, low environmental impact, low energy consumption, safe and resilient, adaptable, convertible, transformable over time and personalised; on the other hand, there is a continued reliance on traditional building approaches/solutions that only partially meet the new requirements.
In this context, the research into new materials to produce innovative construction components capable of contributing to the achievement of the above-mentioned objectives is one of the areas of contemporary development. Among them are included two-dimensional materials that owe their name to their particular structure, consisting of a single atomic layer.
The event that enabled such a reduction in the size scale was the isolation of graphene, a material with unique properties and numerous possible applications. Its potential uses are currently being studied and tested, as demonstrated by the numerous research programmes on the subject, aimed at transferring technology from research laboratories to industry.
This PhD research aims to investigate the potential applications of graphene in the field of cementitious composites and polymer-based coatings. The activities carried out included: a critical analysis of the state of the art of the most recent applications in the field of construction; the consequent choice of possible composite materials graphene and graphene-related materials based; the design and development of an experimental campaign; the proposal and final verification of the applications in the construction sector. The activities were carried out in collaboration with the Graphene Labs of the Italian Institute of Technology (IIT).
49
Behnen, Severin Hilar Behnen Severin Hilar Behnen Severin Hilar Behnen Severin Hilar Behnen Severin Hilar Behnen Severin Hilar Behnen Severin Hilar Behnen Severin Hilar. "Volume I. The construction of motion graphics scores Volume II. Seven motion graphics scores /." Diss., Restricted to subscribing institutions, 2008. http://proquest.umi.com/pqdweb?did=1581435611&sid=1&Fmt=2&clientId=1564&RQT=309&VName=PQD.
Full textAbstract:
Thesis (Ph. D.)--University of California, Los Angeles, 2008.CD-ROM entitled "The motion graphics scores of Severin Behnen" includes the animated scores. Includes bibliographical references (v. 1, leaves 138-142).
50
Werner, Rose-Line. "Concrete constructions of unbalanced bipartite expander graphs and generalized conductors." Zürich : ETH, Eidgenössische Technische Hochschule Zürich, Departement Informatik, Institut für Informationssysteme, 2008. http://e-collection.ethbib.ethz.ch/show?type=dipl&nr=389.
Full text