To see the other types of publications on this topic, follow the link: Graphs Construction.
Dissertations / Theses on the topic 'Graphs Construction'
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 'Graphs Construction.'
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
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.
2
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.
3
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
4
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.
5
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
6
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
7
Pereira, Gabriel Maier Fernandes Vidueiro. "Test-case-based call graph construction in dynamically typed programming languages." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2015. http://hdl.handle.net/10183/134355.
Full textAbstract:
Evolução de software é uma das atividades mais desafiadoras do processo de desenvolvimento de software. Uma importante questão associada à essa atividade é a correta compreensão do código fonte e outros artefatos que necessitam ser mantidos e evoluídos. Visando auxiliar desenvolvedores na manutenção de código, Integrated Development Environments (IDE’s) proporcionam ferramentas que informam desenvolvedores sobre as dependências e as particularidades do código a ser modificado. No entanto, linguagens dinamicamente tipadas não definem tipos explicitamente no código fonte, o que dificulta a análise estática do código e consequentemente a contrução dessas ferramentas. Como exemplo, a construção de call graphs (grafos de chamadas), utilizados pelas IDE’s para criar ferramentas de navegação de código, é prejudicada pela ausência da definição de tipos. Para abordar o problema da criação de call graphs para linguagens dinamicamente tipadas, propomos uma técnica dividida em passos para a construção de um call graph baseado em informações extraídas da execução de testes. A técnica é dividida em 3 passos, o Passo #1 cria um call graph conservativo e estático que resolve chamadas de métodos baseado apenas em nomes dos métodos, ainda no primeiro passo, testes são executados e seu traço de execução é armazenado para posterior análise. O Passo #2 combina a informação armazenada da execução dos testes e o call graph construído no primeiro passo, o Passo #2 também é responsável pela criação de um conjunto de regras de associação que servirão para guiar desenvolvedores durante a criação de novas partes do código. Nossa avaliação em uma aplicação real de porte grande mostrou que a técnica melhora a precisão do call graph criado removendo arestas desnecessárias (70%), e mostrou-se apta a auxiliar desenvolvedores definindo pontos de navegação no código baseada na análise de regras de associação extraídas do test-case-based call graph.Evolving enterprise software systems is one of the most challenging activities of the software development process. An important issue associated with this activity is to properly comprehend the source code and other software assets that must be evolved. To assist developers on these evolution tasks, Integrated Development Environments (IDEs) build tools that provides information about the source code and its dependencies. However, dynamically typed languages do not define types explicitly in the source code, which difficult source code analysis and therefore the construction of these tools. As an example, the call graph construction, used by IDE’s to build source code navigation tools, is hampered by the absence of type definition. To address the problem of constructing call graphs for dynamic languages, we propose a technique based on steps to build a call graph based on test runtime information, called test-case-based call graph. The technique is divided in three steps; Step #1 creates a conservative and static call graph that decides target nodes based on method names, and the first step also run tests profiling its execution; Step #2 combines the test runtime information and the conservative call graph built in the first step to create the test-case-based call graph, it also creates a set of association rules to guide developers in the maintenance while creating new pieces of code; Finally, Step #3 uses the test-case-based call graph and the association rules to assist developers in source code navigation tasks. Our evaluation on a large-size real-world software shows that the technique increases call graph precision removing several unnecessary conservative edges ( %70), and assist developers filtering target nodes of method calls based on association rules extracted from the call graph.
8
PORRINI, RICCARDO. "Construction and Maintenance of Domain Specific Knowledge Graphs for Web Data Integration." Doctoral thesis, Università degli Studi di Milano-Bicocca, 2016. http://hdl.handle.net/10281/126789.
Full textAbstract:
A Knowledge Graph (KG) is a semantically organized, machine readable collection of types, entities, and relations holding between them. A KG helps in mitigating semantic heterogeneity in scenarios that require the integration of data from independent sources into a so called dataspace, realized through the establishment of mappings between the sources and the KG. Applications built on top of a dataspace provide advanced data access features to end-users based on the representation provided by the KG, obtained through the enrichment of the KG with domain specific facets. A facet is a specialized type of relation that models a salient characteristic of entities of particular domains (e.g., the vintage of wines) from an end-user perspective.
In order to enrich a KG with a salient and meaningful representation of data, domain experts in charge of maintaining the dataspace must be in possess of extensive knowledge about disparate domains (e.g., from wines to football players). From an end-user perspective, the difficulties in the definition of domain specific facets for dataspaces significantly reduce the user-experience of data access features and thus the ability to fulfill the information needs of end-users. Remarkably, this problem has not been adequately studied in the literature, which mostly focuses on the enrichment of the KG with a generalist, coverage oriented, and not domain specific representation of data occurring in the dataspace.
Motivated by this challenge, this dissertation introduces automatic techniques to support domain experts in the enrichment of a KG with facets that provide a domain specific representation of data. Since facets are a specialized type of relations, the techniques proposed in this dissertation aim at extracting salient domain specific relations. The fundamental components of a dataspace, namely the KG and the mappings between sources and KG elements, are leveraged to elicitate such domain specific representation from specialized data sources of the dataspace, and to support domain experts with valuable information for the supervision of the process. Facets are extracted by leveraging already established mappings between specialized sources and the KG. After extraction, a domain specific interpretation of facets is provided by re-using relations already defined in the KG, to ensure tight integration of data. This dissertation introduces also a framework to profile the status of the KG, to support the supervision of domain experts in the above tasks.
Altogether, the contributions presented in this dissertation provide a set of automatic techniques to support domain experts in the evolution of the KG of a dataspace towards a domain specific, end-user oriented representation. Such techniques analyze and exploit the fundamental components of a dataspace (KG, mappings, and source data) with an effectiveness not achievable with state-of-the-art approaches, as shown by extensive evaluations conducted in both synthetic and real world scenarios.
9
Balamohan, Balasingham. "Efficient Mechanisms for Exploration of Dangerous Graphs and for Inter-agent Communication." Thèse, Université d'Ottawa / University of Ottawa, 2013. http://hdl.handle.net/10393/26002.
Full textAbstract:
This thesis deals with the problems of exploration and map construction of a dangerous network by mobile agents, and it introduces new general mechanisms for inter-agent communication, which could be applied
to other mobile agents' problems.
A dangerous network contains a harmful process called Black Hole that destroys all agents entering the node where it resides, without leaving any observable trace.
The task for the agents, which are moving asynchronously, is to construct a map of the network with edges incident on the black hole unambiguously identified.
Two types of communication mechanisms are considered:
whiteboards and tokens.
In the whiteboard model every node provides a shared memory on which agents can read and write.
When communication occurs through tokens, instead, the agents have some pebbles that
can be placed on and picked up from the nodes.
Four different costs for comparing the efficiency of the protocols are taken into account: the number of agents required,
the number of moves performed, the size of the whiteboard (or the token capacity at a node), and time.
The black hole search problem is considered first in ring networks with whiteboards, and optimal exact time and move complexities
are established improving all existing results.
The same problem is then studied in arbitrary unknown graphs and it is solved in the token model by using a constant number of tokens in total.
The protocol improves on existing results and is based on a novel technique for communicating using tokens.
Finally, the new method of communicating using tokens described in the context of black hole search is generalized to propose a novel communication mechanism among the agents that could possibly be employed for any distributed algorithm by mobile agents.
10
Eshghi, Kourosh. "The existence and construction of Ã-valuations of 2-regular graphs with three components." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp02/NQ27919.pdf.
Full text
11
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
12
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
13
Bohren, Janet Linderoth. "A nine month study of graph construction skills and reasoning strategies used by ninth grade students to construct graphs of science data by hand and with computer graphing software /." The Ohio State University, 1988. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487588249823852.
Full text
14
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
15
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
16
Berton, Lilian. "Construção de redes baseadas em vizinhança para o aprendizado semissupervisionado." Universidade de São Paulo, 2016. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-29072016-100548/.
Full textAbstract:
Com o aumento da capacidade de armazenamento, as bases de dados são cada vez maiores e, em muitas situações, apenas um pequeno subconjunto de itens de dados pode ser rotulado. Isto acontece devido ao processo de rotulagem ser frequentemente caro, demorado e necessitar do envolvimento de especialistas humanos. Com isso, diversos algoritmos semissupervisionados foram propostos, mostrando que é possível obter bons resultados empregando conhecimento prévio, relativo à pequena fração de dados rotulados. Dentre esses algoritmos, os que têm ganhado bastante destaque na área têm sido aqueles baseados em redes. Tal interesse, justifica-se pelas vantagens oferecidas pela representação via redes, tais como, a possibilidade de capturar a estrutura topológica dos dados, representar estruturas hierárquicas, bem como modelar manifolds no espaço multi-dimensional. No entanto, existe uma grande quantidade de dados representados em tabelas atributo-valor, nos quais não se poderia aplicar os algoritmos baseados em redes sem antes construir uma rede a partir desses dados. Como a geração das redes, assim como sua relação com o desempenho dos algoritmos têm sido pouco estudadas, esta tese investigou esses aspectos e propôs novos métodos para construção de redes, considerando características ainda não exploradas na literatura. Foram propostos três métodos para construção de redes com diferentes topologias: 1) S-kNN (Sequential k Nearest Neighbors), que gera redes regulares; 2) GBILI (Graph Based on the Informativeness of Labeled Instances) e RGCLI (Robust Graph that Considers Labeled Instances), que exploram os rótulos disponíveis gerando redes com distribuição de grau lei de potência; 3) GBLP (Graph Based on Link Prediction), que se baseia em medidas de predição de links gerando redes com propriedades mundo-pequeno. As estratégias de construção de redes propostas foram analisadas por meio de medidas de teoria dos grafos e redes complexas e validadas por meio da classificação semissupervisionada. Os métodos foram aplicados em benchmarks da área e também na classificação de gêneros musicais e segmentação de imagens. Os resultados mostram que a topologia da rede influencia diretamente os algoritmos de classificação e as estratégias propostas alcançam boa acurácia.With the increase capacity of storage, databases are getting larger and, in many situations, only a small subset of data items can be labeled. This happens because the labeling process is often expensive, time consuming and requires the involvement of human experts. Hence, several semi-supervised algorithms have been proposed, showing that it is possible to achieve good results by using prior knowledge. Among these algorithms, those based on graphs have gained prominence in the area. Such interest is justified by the benefits provided by the representation via graphs, such as the ability to capture the topological structure of the data, represent hierarchical structures, as well as model manifold in high dimensional spaces. Nevertheless, most of available data is represented by attribute-value tables, making necessary the study of graph construction techniques in order to convert these tabular data into graphs for applying such algorithms. As the generation of the weight matrix and the sparse graph, and their relation to the performance of the algorithms have been little studied, this thesis investigated these aspects and proposed new methods for graph construction with characteristics litle explored in the literature yet. We have proposed three methods for graph construction with different topologies: 1) S-kNN (Sequential k Nearest Neighbors) that generates regular graphs; 2) GBILI (Graph Based on the informativeness of Labeled Instances) and RGCLI (Robust Graph that Considers Labeled Instances), which exploit the labels available generating power-law graphs; 3) GBLP (Graph Based on Link Prediction), which are based on link prediction measures and generates small-world graphs. The strategies proposed were analyzed by graph theory and complex networks measures and validated in semi-supervised classification tasks. The methods were applied in benchmarks of the area and also in the music genre classification and image segmentation. The results show that the topology of the graph directly affects the classification algorithms and the proposed strategies achieve good accuracy.
17
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
18
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
19
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
20
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
21
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.
22
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
23
Honar, Elnaz, and Jahromi Seyed AmirHossein Mortazavi. "A Framework for Call Graph Construction." Thesis, Linnaeus University, School of Computer Science, Physics and Mathematics, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-6629.
Full textAbstract:
In object oriented programming, a Call Graph represents the calling relationships between the program’s methods. To be more precise, a Call Graph is a rooted directed graph where each node of the graph represents a method and each edge (u, v) represents a method call from method u to method v.
Focus of this thesis is on building a framework for Call Graph construction algorithms which can be used in program analysis. Our framework is able to be initialized by different front-ends and constructs various Call Graph algorithms. Here, we instantiate framework with two bytecode readers (ASM and Soot) as front-ends and implement three Call Graph construction algorithms (CHA, RTA and CTA).
At first, we used two above mentioned bytecode readers to read the bytecode of a specific Java program, then we found reachable methods for each invoked method; meanwhile we kept obtained details on our own data structures. Creating data structures for storing required information about Classes, Methods, Fields and Statements, gives us a great opportunity to implement an independent framework for applying well known Call Graph algorithms. As a result of these data structures, Call Graph construction will not depend on bytecode readers; since, whenever we read the bytecode of a program, we accumulate all necessary points in pre-defined data structures and implement our Call Graphs based on this accumulated data.
Finally, the result is a framework for different Call Graph construction algorithms which is the goal of this thesis. We tested and evaluated the algorithms with a variety of programs as the benchmark and compared the bytecode readers besides the three Call Graph algorithms in different aspects.
24
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
25
Löfstedt, Tommy. "Fractal Geometry, Graph and Tree Constructions." Thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-51347.
Full textAbstract:
In the 18th and 19th centuries the branch of mathematics that would later be known as fractal geometry was developed. It was the ideas of Benoˆıt Mandelbrot that made the area expand so rapidly as it has done recently, and since the publication of his works there have for fractals, and most commonly the estimation of the fractal dimension, been found uses in the most diverse applications. Fractal geometry has been used in information theory, economics, flow dynamics and image analysis, among many different areas. This thesis covers the foundations of fractal geometry, and gives most of the fun- damental definitions and theorems that are needed to understand the area. Concepts such as measure and dimension are explained thoroughly, especially for the Hausdorff di- mension and the Box-counting dimension. An account of the graph-theoretic approach, which is a more general way to describe self-similar sets is given, as well as a tree- construction method that is shown to be equivalent to the graph-theoretic approach.
26
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
27
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
28
Schmidt, Jens M. [Verfasser]. "Structure and constructions of 3-connected graphs / Jens M. Schmidt." Berlin : Freie Universität Berlin, 2011. http://d-nb.info/1025489926/34.
Full text
29
Sulong, Ghazali bin. "Algorithms for timetable construction." Thesis, Cardiff University, 1989. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.253664.
Full text
30
Keenan, David Wayne 1955. "BLOCK PLAN CONSTRUCTION FROM A DELTAHEDRON-BASED ADJACENCY GRAPH." Thesis, The University of Arizona, 1986. http://hdl.handle.net/10150/292025.
Full text
31
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
32
Wang, C. Y. "The construction of general graph editors using object-oriented programming." Thesis, Swansea University, 1994. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.639337.
Full textAbstract:
Diagrams are used extensively to model real world systems and problems, and as such, application-specific diagram editors are needed in computer application systems. However, the development of a diagram editor from scratch is time consuming and needs specialized expertise. This thesis describes the implementation of DECADE, a software development environment for constructing application-specific diagram editors. It provides users with an application framework, a specification editing tool, and an application construction tool to reduce this development effort. Object-oriented technology, which is discussed in the thesis, was employed in the design and implementation of DECADE. An analysis of diagrams and editors is included which leads to a model of diagrams and an abstraction of diagram editors. Diagram editors are abstracted into four parts: the diagram, representation, manipulation and the editor user interface. A diagram object defines a type of diagram with special elements, the representation objects manage a given diagram and generate specific application data. The manipulation abstraction models editing activities, and the user interface objects support the interaction with users. Based on these abstractions, an application framework was developed which provides substantial software reusability, and the possibility to automate diagram editor construction from the software components that are derived from the framework. The construction tool selects and specializes the components according to a specification, which is generated by the specification editing tool, and then integrates them together into a diagram editor. An object-oriented specification method and a frame-based construction mechanism for software automation are presented and used in the implementation. A few experimental applications are also given and analyzed in the thesis.
33
Albishry, Nabeel Hamad Hamdan. "Graph construction approach for social networks analysis : Twitter case studies." Thesis, University of Bristol, 2018. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.761234.
Full text
34
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
35
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.
36
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.
37
Weninger, Timothy Edwards. "Link discovery in very large graphs by constructive induction using genetic programming." Thesis, Manhattan, Kan. : Kansas State University, 2008. http://hdl.handle.net/2097/1087.
Full text
38
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
39
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
40
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
41
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
42
Przytycka, Teresa Maria. "Parallel techniques for construction of trees and related problems." Thesis, University of British Columbia, 1990. http://hdl.handle.net/2429/30640.
Full textAbstract:
The concept of a tree has been used in various areas of mathematics for over a century. In particular, trees appear to be one of the most fundamental notions in computer science. Sequential algorithms for trees are generally well studied. Unfortunately many of these sequential algorithms use methods which seem to be inherently sequential. One of the contributions of this thesis is the introduction of several parallel techniques for the construction of various types of trees and the presentation of new parallel tree construction algorithms using these methods. Along with the parallel tree construction techniques presented here, we develop techniques which have broader applications.
We use the Parallel Random Access Machine as our model of computation. We consider two basic methods of constructing trees:tree expansion and tree synthesis.
In the tree expansion method, we start with a single vertex and construct a tree by adding nodes of degree one and/or by subdividing edges. We use the parallel tree expansion technique to construct the tree representation for graphs in the family of graphs known as cographs.
In the tree synthesis method, we start with a forest of single node subtrees and construct a tree by adding edges or (for rooted trees) by creating parent nodes for some roots of the trees in the forest. We present a family of parallel and sequential algorithms to construct various approximations to the Huffman tree. All these algorithms apply the tree synthesis method by constructing a tree in a level-by-level fashion. To support one of the algorithms in the family we develop a technique which we call the cascading sampling technique.
One might suspect that the parallel tree synthesis method can be applied only to trees of polylogarithmic height, but this is not the case.We present a technique which we call the valley filling technique and develop its accelerated version called the accelerated valley filling technique. We present an application of this technique to an optimal parallel algorithm for construction of minimax trees.Science, Faculty of
Computer Science, Department of
Graduate
43
Russold, Michael Friedrich. "Surgical construction, conditioning and activation of functional muscle grafts." Thesis, University of Liverpool, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.419009.
Full text
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
Yang, Fang. "Construction and application of hierarchical matrix preconditioners." Diss., University of Iowa, 2008. https://ir.uiowa.edu/etd/196.
Full textAbstract:
H-matrix techniques use a data-sparse tree structure to represent a dense or a sparse matrix. The leaves of the tree store matrix sub-blocks that are represented in full-matrix format or Rk-matrix (low rank matrix) format. H-matrix arithmetic is defined over the H-matrix representation, which includes operations such as addition, multiplication, inversion, and LU factorization. These H-matrix operations approximate results with almost optimal computational complexity. Based on the properties of H-matrices, the H-matrix preconditioner technique has been introduced. It uses H-matrix operations to construct preconditioners, which are used in iterative methods to speed up the solution of large systems of linear equations (Ax = b). To apply the H-matrix preconditioner technique, the first step is to represent a problem in H-matrix format. The approaches to construct an H-matrix can be divided into two categories: geometric approaches and algebraic approaches.
In this thesis, we present our contributions to algebraic H-matrix construction approaches and H-matrix preconditioner technique. We have developed a new algebraic H-matrix construction approach based on matrix graphs and multilevel graph clustering approaches. Based on the new construction approach, we have also developed a scheme to build algebraic H-matrix preconditioners for systems of saddle point type. To verify the effectiveness of our new construction approach and H-matrix preconditioner scheme, we have applied them to solve various systems of linear equations arising from finite element methods and meshfree methods. The experimental results show that our preconditioners are competitive to other H-matrix preconditioners based on domain decomposition and existing preconditioners such as JOR and AMG preconditioners. Our H-matrix construction approach and preconditioner technique provide an alternative effective way to solve large systems of linear equations.
46
Van, Straten Celene Debra. "The construction of plant expression vectors for the introduction of leafroll disease resistance in grapevine." Thesis, Stellenbosch : Stellenbosch University, 2000. http://hdl.handle.net/10019.1/51950.
Full textAbstract:
Thesis (MSc)--University of Stellenbosch, 2000.ENGLISH ABSTRACT: Grapevine leafroll is one of the most damaging viral diseases that affect many viticultural regions of the world. Numerous reports over the last few years have associated closterovirus-like particles with leafroll disease. To date, eight serologically distinct closteroviruses have been isolated from leafroll infected vines, of which grapevine leafroll associated closterovirus-3 (GLRaV-3) is the best characterized. Virus resistance in transgenic plants based on the expression of a virusderived gene is known as pathogen-derived resistance. The viral coat protein (CP) gene, which expresses a structural protein responsible for coating the virus particles, was used in the first demonstration of virus-derived resistance. Coat protein-mediated resistance is currently the most feasible and most widely used method to obtain virus resistance in crop plants. The CP gene of a South African isolate of GLRaV-3 infected grapevine was isolated, cloned and sequenced. Double stranded RNA (dsRNA) was extracted from GLRaV-3 infected material and a high molecular weight band, of -18 kb was identified from infected vines. The dsRNA was used as a template in a reverse transcription PCR together with GLRaV-3 CP gene specific primers for the amplification of the GLRaV-3 CP gene (975 bp). The GLRaV-3 CP gene was cloned into the pGem®-T Easy vector. Clones hosting the CP gene in the sense (pLR3CP+) and antisense (pLR3CP-) orientations respectively were obtained. The sequence obtained from these two clones showed 99.26 % similarity to the only other GLRaV-3 CP nucleotide sequence available. The GLRaV-3 CP gene was excised from pLR3CP+ and pLR3CP- and subcloned into a plant expression vector, pCAMBIA 3301 in the sense (pCamBLR3CP+) and antisense (pCamBLR3CP-) orientations respectively, therefore enabling sense and antisense gene expression in transgenic plants. The GLRaV-3 CP gene was also subcloned from pCamBLR3CP+ into another plant expression vector, pCAMBIA 2301 in the sense orientation and designated as pCVSLR3CP+. These three constructs were given to Dr. M. Vivier (Institute for Wine Biotechnology, Stellenbosch) for grapevine transformation experiments. Two of these constructs, pCamBLR3CP+ and pCamBLR3CP- as well as pCAMBIA 3301 were used to transform Nicotiana tabacum by Agrobacterium tumefaciens-mediated transformation. Plants were selected for their ability to withstand the herbicide, Basta. This resistance is due to the presence of a plant selectable marker gene on each of these constructs, known as the bar gene. PCR with GLRaV-3 CP gene specific primers showed no amplification of the GLRaV-3 CP gene in the plants transformed with pCamBLR3CP+ and pCamBLR3CP-. Southern blot analysis with the GLRaV-3 CP gene as hybridization probe showed no signal for these plants, thus confirming the PCR results. PCR with bar gene specific primers showed no amplification of the bar gene in the plants infected with pCAMBIA 3301. The plants transformed with pCamBLR3CP+ and pCamBLR3CP- were also screened for the presence of the bar gene. Three of the eight plants tested showed amplification of the -560 bp bar gene. This result suggests that these plants were transformed with pCAMBIA 3301 (vector without the ligated GLRaV-3 CP gene) and not pCamBLR3CP+ or pCamBLR3CP- as had been expected. This project provides preliminary work for the subsequent transformation of grapevine with the GLRaV-3 CP gene, in an attempt to impart virus resistance.
AFRIKAANSE OPSOMMING: Wingerd rolblaar is een van die mees beskadigende virale siektes wat baie wingerd areas in die wêreld aantas. In Aantal verslae oor die afgelope jare het closterovirus partikels met wingerd rolblaar geassosieer. Tot hede, is agt serologiese onderskeibare closterovirusse geïsoleer vanuit geaffekteerde wingerde, waarvan wingerd rolblaar geassosieerde closterovirus-3 (GLRaV-3) die beste gekarakteriseerd is. Virus bestandheid in transgeniese plante gebaseer op die uitdrukking van gene afkomstig vanaf virusse, staan bekend as patogeen-afgeleide weerstand. Die virale kapsule protein (CP) geen vervaardig In strukturele protein wat verantwoordelik is vir die bedekking van die virus partikel. Dié geen was gebruik in die eerste demonstrasie van patogeen-afgeleide weerstand. Kapsuul protein-bemiddelde weerstand is tans die mees praktiese en algemene gebruikte metode om virus weerstand in plant gewasse te verkry. Die CP geen van In Suid Afrikaanse isolaat van GLRaV-3 geïnfekteerde wingerde is geïsoleer, gekloneer en die volgorde is bepaal. Dubbelstring RNA (dsRNA) was uit GLRaV-3 geïnfekteerde materiaal geëkstraheer en In hoë molekulêre gewig band van -18 kb is geïdentifiseer. Die dsRNA is gebruik as In templaat vir In omgekeerde transkripsie PKR saam met GLRaV-3 CP geen spesifieke inleiers vir die amplifikasie van die GLRaV-3 CP geen (975 bp). Die GLRaV-3 CP geen is gekloneer in die pGem®-T Easy vektor. Klone met die CP geen in die sin (pLR3CP+) en teensin (pLR3CP-) oriëntasies respektiewelik is verkry. Die volgorde wat verkry is vanuit hierdie twee klone dui op In 99.26 % ooreenstemming met die enigste ander GLRaV-3 CP geen volgorde wat beskikbaar is. Die GLRaV-3 CP geen is uit pLR3CP+ en pLR3CP- gesny en is gesubkloneer in In plant ekspressie vektor, pCAMBIA 3301 in die sin (pCamBLR3CP+) en teensin (pCamBLR3CP-) oriëntasies respektiewelik, wat die sin en teensin geen ekspressie in transgeniese plante in staat stel. Die GLRaV-3 CP geen was ook gesubkloneer vanaf pCamBLR3CP+ in In ander plant ekspressie vektor, pCAMBIA 2301 in die sin orientasie en is as pCVSLR3CP+ benoem. Hierdie drie konstruksies is aan Dr. M. Vivier (Instituut vir Wyn Biotegnologie, Stellenbosch) gegee vir wingerd transformasie eksperimente. Twee van hierdie konstruksies, pCamBLR3CP+ en pCamBLR3CP- asook pCAMBIA 3301 is gebruik om Nicotiana tabacum deur middel van Agrobacterium tumefaciens-bemiddelde transformasie te transformeer. Plante is geselekteer vir hul vermoë om die onkruiddoder, Basta, te weerstaan. Die teenwoordigheid van die plant selekteerbare merker geen, bar, op elke konstruksie lui tot dié weerstand. Die plante wat getransformeer is met pCamBLR3CP+ en pCamBLR3CP- is deur PKR saam met die GLRaV-3 CP geen spesifieke inleiers getoets, en geen amplifikasie van die GLRaV-3 CP geen is getoon nie. Southern blot analise met die GLRaV-3 CP geen as hibridisasie peiler het geen sein gewys vir hierdie plante nie, wat die PKR resultate bevestig. Die plante wat getransformeer is met pCAMBIA 3301 is deur PKR saam met die bar geen spesifieke inleiers getoets, en geen amplifikasie van die bar geen is getoon nie. Die plante wat getransformeer is met pCamBLR3CP+ en pCamBLR3CP- is ook getoets vir die teenwoordigheid vir die bar geen. Drie van die agt plante wat getoets is, het amplifikasie van die -560 bp bar geen getoon. Hierdie onverwagte resultate stel voor dat dié plante met pCAMBIA 3301 (vektor sonder die geligeerde GLRaV-3 CP geen) en nie met pCamBLR3CP+ en pCamBLR3CPgetransformeer is nie. Hierdie projek verskaf voorlopige werk vir die daaropvolgende transformasie van wingerd met die GLRaV-3 CP geen in 'n poging om virus bestandheid te verskaf.
47
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
48
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
49
Holm, Kora. "Construction of a cDNA library for the vine mealybug, Planococcus ficus (Signoret) /." Link to the online version, 2008. http://hdl.handle.net/10019/1884.
Full text
50
Pagan, Maria Adriana. "A interdisciplinaridade como proposta pedagógica para o ensino de estatística na educação básica." Pontifícia Universidade Católica de São Paulo, 2010. https://tede2.pucsp.br/handle/handle/11439.
Full textAbstract:
Made available in DSpace on 2016-04-27T16:59:02Z (GMT). No. of bitstreams: 1
Maria Adriana Pagan.pdf: 4063282 bytes, checksum: 2ef49261c808fd4633561d7044023c48 (MD5)
Previous issue date: 2010-02-03Secretaria da Educação do Estado de São Paulo
The objective of this study was to compare the learning gains of three different student groups in first year high school who had contact with elementary concepts of statistics from Mathematics lessons (GM), Geography (GG) and Mathematics lessons applied interdisciplinary (statistics taught from Geography, Biology, Physics and Chemistry contents) (GI). To achieve this aim a study was done on a quasi-experimental basis which consisted of three groups of 35 students each at a public school in the state of São Paulo. It was applied two diagnostic tests (pre and post-test) at the study and the intervention was performed in each group by different teachers composing GM, GG and GI groups. The theoretical framework of this study included the theory of semiotics Records Offices of Raymond Duval (1995) about the change in registration; studies by Curcio (1989) and Wainer (1992) regarding to the levels of reading and interpreting data in graphs and tables respectively and the Literacy, Reasoning and Statistical Thinking with several authors as Cazorla (2002, 2005), Gal (2002), Lopes (2004), Morais (2006), Silva (2007) and Campos (2007). The interdisciplinary aspects were based on Fazenda (1994), Klein (2007) and Lenoir (2007) and the arithmetics in Novaes and Coutinho (2008). The study aimed to answer the following question: "What are the contributions that an educational intervention based on the principles of interdisciplinarity bring to the learning of statistics?" To answer this question the study was based on quantitative analysis of the results obtained in the tests applied to the three groups and a qualitative analysis of results presented by the students in the GI. The analysis showed a gain with the use of educational intervention at the three groups GM, GG and GI on the statistical study (construction, interpretation and arithmetic), but one significant performance was presented by students of the interdisciplinary group after educational intervention. This result allowed inferring that the teaching of Statistics based on an interdisciplinary approach proved its effectiveness as the interest of students in dealing with issues as well as their knowledge were reinforced by their understanding of statistical elements
O objetivo deste estudo foi comparar os ganhos de aprendizagem de três grupos de alunos da 1ª série do Ensino Médio que tiveram contato com conceitos elementares da Estatística a partir das aulas de Matemática (GM), de Geografia (GG) e de aulas de Matemática aplicadas de forma interdisciplinar (Estatística a partir de conteúdos de Geografia, Biologia, Física e Química) (GI). Para atingir este objetivo, foi feito um estudo de caráter do tipo quase-experimental que contou com três grupos compostos de 35 alunos de uma escola da rede pública estadual da cidade de São Paulo. No estudo foram aplicados dois testes diagnósticos (pré e pós-teste) e uma intervenção de ensino ocorrida em cada grupo, realizada por professores distintos que compunham os grupos GM, GG e GI. O quadro teórico do estudo contou com a teoria dos Registros de Representações Semiótica de Raymond Duval (1995) quanto à mudança de registro. Os estudos realizados por Curcio (1989) e Wainer (1992), quanto aos níveis de leitura e interpretação de dados em gráficos e tabelas, respectivamente; o Letramento, Raciocínio e Pensamento Estatístico com diversos autores como Cazorla (2002, 2005), Gal (2002), Lopes (2004), Morais (2006), Silva (2007) e Campos (2007). Quanto a interdisciplinaridade contou com Fazenda (1994), Klein (2007) e Lenoir (2007) e para a média aritmética com Novaes e Coutinho (2008). O estudo propôs-se a responder à seguinte questão: Quais as contribuições que uma intervenção de ensino pautada nos princípios da interdisciplinaridade traz para a aprendizagem da Estatística? Para responder à questão de pesquisa, tomou-se por base as análises quantitativas dos resultados obtidos nos testes aplicados nos três grupos e uma análise qualitativa dos resultados apresentados pelos alunos do grupo GI. As análises mostraram um ganho com a intervenção de ensino nos três grupos GM, GG e GI no que diz respeito aos elementos estatísticos estudados (construção, interpretação e média aritmética), porém um desempenho significativo foi apresentado pelos alunos do grupo da Interdisciplinaridade após a intervenção de ensino. O resultado permitiu inferir que o ensino de Estatística, pautado nos moldes da interdisciplinaridade mostrou-se eficaz quanto ao interesse por parte dos alunos em tratar de assuntos e, também, quanto ao ganho adquirido no que diz respeito ao conhecimento dos elementos estatísticos estudados