To see the other types of publications on this topic, follow the link: Graphes de propriétés.
Dissertations / Theses on the topic 'Graphes de propriétés'
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 'Graphes de propriétés.'
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
Ducoffe, Guillaume. "Propriétés métriques des grands graphes." Thesis, Université Côte d'Azur (ComUE), 2016. http://www.theses.fr/2016AZUR4134/document.
Full textAbstract:
Les grands réseaux de communication sont partout, des centres de données avec des millions de serveurs jusqu’aux réseaux sociaux avec plusieurs milliards d’utilisateurs.Cette thèse est dédiée à l’étude fine de la complexité de différents problèmes combinatoires sur ces réseaux. Dans la première partie, nous nous intéressons aux propriétés des plongements des réseaux de communication dans les arbres. Ces propriétés aident à mieux comprendre divers aspects du trafic dans les réseaux (tels que la congestion). Plus précisément, nous étudions la complexité du calcul de l’hyperbolicité au sens de Gromov et de paramètres des décompositions arborescentes dans les graphes. Ces paramètres incluent la longueur arborescente (treelength) et l’épaisseur arborescente (treebreadth). Au passage, nous démontrons de nouvelles bornes sur ces paramètres dans de nombreuses classes de graphes, certaines d’entre elles ayant été utilisées dans la conception de réseaux d’interconnexion des centres de données. Le résultat principal dans cette partie est une relation entre longueur et largeur arborescentes (treewidth), qui est un autre paramètre très étudié des graphes. De ce résultat, nous obtenons une vision unifiée de la ressemblance des graphes avec un arbre, ainsi que différentes applications algorithmiques. Nous utilisons dans cette partie divers outils de la théorie des graphes et des techniques récentes de la théorie de la complexité<br>Large scale communication networks are everywhere, ranging from data centers withmillions of servers to social networks with billions of users. This thesis is devoted tothe fine-grained complexity analysis of combinatorial problems on these networks.In the first part, we focus on the embeddability of communication networks totree topologies. This property has been shown to be crucial in the understandingof some aspects of network traffic (such as congestion). More precisely, we studythe computational complexity of Gromov hyperbolicity and of tree decompositionparameters in graphs – including treelength and treebreadth. On the way, we givenew bounds on these parameters in several graph classes of interest, some of thembeing used in the design of data center interconnection networks. The main resultin this part is a relationship between treelength and treewidth: another well-studiedgraph parameter, that gives a unifying view of treelikeness in graphs and has algorithmicapplications. This part borrows from graph theory and recent techniques incomplexity theory. The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analysing information flows in these networks,represented as dynamical processes on graphs. First, a coloring game on graphs isstudied as a solution concept for the dynamic of online communities. We give afine-grained complexity analysis for computing Nash and strong Nash equilibria inthis game, thereby answering open questions from the literature. On the way, wepropose new directions in algorithmic game theory and parallel complexity, usingcoloring games as a case example
2
Ravaux, Romain. "Graphes arbitrairement partitionnables : propriétés structurelles et algorithmiques." Versailles-St Quentin en Yvelines, 2009. http://www.theses.fr/2009VERS0017.
Full textAbstract:
Les problèmes de décomposition de graphes sont au coeur de la théorie des graphes. Dans cette thèse nous étudions le problème Graphe_Partition qui, étant donné un graphe d'ordre n et une partition de n (séquence d'entiers positifs dont la somme est égale à n), consiste à déterminer s'il existe une partition des sommets du graphe telle que chaque ensemble de cette partition induit un sous-graphe connexe et la séquence des ordres de ces sous-graphes est une permutation de la partition de n. Si une telle partition des sommets existe, nous dirons que le graphe est décomposable pour cette partition de n. Un graphe arbitrairement décomposable est un graphe décomposable pour toutes les partitions de n. Le problème_Partition a déjà été l'objet de plusieurs études. Il a notamment été montré que celui-ci est NP-complet même restreint à la classe des arbres et que les arbres arbitrairement décomposables sont principalement de degré inférieur ou égale à 3. Dans cette thèsenous avons dans un premier temps approfondie l'étude structurelle des arbres arbitrairement décomposables et commencé l'étude structurelle des graphes décomposables. Nous avons pu montrer que les graphes décomposables de longueur arbitrairement grande étaient exactement l'ensemble des peignes. Nous avons donné une construction par récurrence qui permet de construire des peignes arbitrairement décomposables contenant un nombre de sommets de degré 3 et de longueurs arbitrairement grands. Nous avons apporté également une première contribution concernant l'étude structurelle des graphes arbitrairement décomposables minimaux (quelle que soit l'arrête que l'on retire, le graphe restant n'est plus décomposable). Puis dans un deuxième temps, nous nous sommes intéressés à l'aspect algorithmique. Nous avons notamment montré que pour des partitions de n contenant peu d'entiers, il était possible de déterminer assez rapidement si un graphe était décomposable pour cette partition. Nous avons étendu ce résultat aux graphes contenant un petit nombre de sommets de degré 3. Enfin, nous avons montré qu'il était possible de déterminer assez rapidement si un arbre de large diamètre est arbitrairement décomposable<br>Graphes decomposition problems are in the heart of graphes theory. In this thesis we study the problem Graph_Partition wich in defined as follow. Being done a n-vertex graph ans a partition of n (a sequence of positives integers whose sum is equal to n), does it exists a partition of the vertex set such that every set of the partition induce a connected sub-graph, and the sequence of vertices numbers of these sub-graphes is a permutation of the partition of n. If a such partition of the vertex set exists, we say that the graph is decomposable for this partition of n. The problem Graph_Partition has already been the target of several studies. It has been shown that this problem is NP-Complet even restreint to the set of trees, and arbitrarily decomposable trees are principaly of degree 3. In this thesis we have in a first time continued structural study on arbitrarily decomposable and we have started structural studies on arbitrarily decomposable graphs. We have shown that arbitrarily decomposable trees with length arbitrarily haigh are exactly the set of combs. We gave an introduction building wich allow to construct arbitrarily decomposable combs with a number of degree 3 vertices and a length arbitrarily high. We have also given a first contribution concerning structural study of arbitrarily decomposable minimal graphs (whatever the edge you remove from the graph, the remaining graph is not arbitrarily decomposable). In a second time we study algorithmic aspect. We have shown that if we consider partition of n containing few integers, it is possible to determine enough quickly if a graph in decomposable for this partition of n. We have extended this result over the graphs containing few degree 3 vertices. Finally we have shown that it is possible to decide enough quickly if a tree with large diameter in arbitrarily decomposable
3
Zuk, Andrzej. "Sur certaines propriétés spectrales du Laplacien sur les graphes." Toulouse 3, 1996. http://www.theses.fr/1996TOU30272.
Full textAbstract:
Dans cette these on s'interesse a la propriete (t) pour les groupes discrets et aux spectres des operateurs associes aux marches aleatoires sur ces groupes. On etudie aussi le rayon spectral de ces operateurs sur certains graphes
4
Mostefaoui, Mustapha. "Analyse des propriétés temporelles des graphes d'événements valués continus." Nantes, 2001. http://www.theses.fr/2001NANT2100.
Full textAbstract:
Les réseaux de Petri (RdP) sont un formalisme puissant de modélisation et d'évaluation des systèmes dynamiques complexes. Une classe particulière des RdP, que sont les graphes d'événements valués (GdEV) fortement connexes, permet plus particulièrement d'analyser les systèmes cycliques sans conflit structurel. Lorsque la notion de flux apparaît (système fluide, structure à haut débit, etc. ) il est possible d'utiliser un modèle GdEV continu (GdEVC). Le plus souvent, les méthodes d'analyse des propriétés temporelles des RdP continus se basent sur le développement du graphe d'évolution qui représente la dynamique du système. . .
5
Colcombet, Thomas. "Représentations et propriétés de structures infinies." Rennes 1, 2004. http://www.theses.fr/2004REN10094.
Full textAbstract:
This work is dedicated to the study of infinite structures (or graphs) which admit a finite presentation. To the equivalences between those presentations and to the geometrical and decidability properties concerning them. The study starts with stack based structures,mainly the prefix recognizable ones. We establish various presentations for those structures, as solutions of equational systems,by transformation of the infinite complete binary tree and by word rewriting. We then study the term-automatic structures and give them,in particular, a new characterization by mean of equational systems. We finally study the families of graphs defined by ground term rewriting. We introduce a new family of graphs of this kind defined as solutions of equational systems. We then study the logics decidable over those graphs and establish some of their geometrical properties.
6
Birmelé, Étienne. "Largeur d'arborescence quasi-clique-mineurs et propriétés d'erdos-posa." Lyon 1, 2003. http://www.theses.fr/2003LYO10259.
Full textAbstract:
La largeur d'arborescence est une notion intéressante d'un point de vue théorique mais également algorithmique puisque beaucoup de problèmes NP-difficiles deviennent polynomiaux quand on se restreint aux graphes de largeur d'arborescence bornée. Elle est étroitement liée à la notion de q-clique-mineur qui lui est duale et à une propriété des familles de graphes dite propriété d'Erdos-Posa. De plus, le caractère borné de la largeur d'arborescence est lié à l'interdiction de graphes planaires en tant que mineurs. Cette thèse est une étude plus précise de ces notions dans le cas de l'interdiction de trois familles, à savoir les circuits de différents types, les prismes et les petites grilles. Nous en déduisons d'une part des bornes polynomiales pour la largeur d'arborescence de certaines familles de graphes et certaines propriétés d'Erdos-Posa et d'autre part de nouveaux algorithmes polynomiaux
7
Delhommé, Christian. "Propriétés de projection." Lyon 1, 1995. http://www.theses.fr/1995LYO10159.
Full textAbstract:
La propriete de projection a ete introduite par ernest corominas pour les ensembles ordonnes : un ensemble ordonne est 2-projectif si les projections sont ses seules operations binaires, croissantes et identiques sur la diagonale. L'objet de cette these est l'etude d'extensions de cette notion, a des operations d'arite superieure (projectivite de hamming finie et projectivite cartesienne infinie) et a des structures plus generales. Notre etude des proprietes de projection de hamming (relatives a des operations regulieres par rapport a chaque argument) est fondee sur des idees de topologie algebrique de base. Nous introduisons divers complexes de chaines, dont les proprietes nous fournissent des criteres de projectivite. Ainsi, nous etablissons par exemple, qu'un graphe fini, connexe, sans sommet pendant, est hamming 2-projectif des qu'il n'a ni triangle ni carre, et plus generalement pour n>2, qu'il est hamming n-projectif, quand il n'a pas cycle de longueur inferieure ou egale a n + 1 et qu'il n'est pas lui-meme un cycle. En particulier, cela fournit les premiers exemples de graphes verifiant la propriete de 3-projection de hamming. Notre point de vue va egalement nous permettre d'introduire les proprietes de n-projection simple et double. Notre approche des proprietes de projection infinies (relatives a des operations infinitaires) est de nature plus ensembliste. Nous montrons en particulier, qu'un graphe projectif de diametre fini est denombrablement projectif, des qu'il n'est pas compact pour les systemes atomiques a un nombre fini d'inconnues. Cette these est partagee en sept chapitres regroupes en trois parties. La premiere est consacree a l'expose de generalites. Nous y etablissons egalement la projectivite de certaines structures homogenes, qui nous permettront d'illustrer la suite de notre propos. Dans une seconde partie, nous mettons en place un cadre algebrique pour l'etude des proprietes de projection de hamming. Dans la troisieme, nous etudions des proprietes de projection infinie, que nous illustrons notamment par les exemples des shift-graphs et des structures homogenes.
8
Barbar, Kablan. "Grammaires d'arbres attribuées : méthodes de vérification des propriétés de graphes engendrés." Bordeaux 1, 1988. http://www.theses.fr/1988BOR10595.
Full textAbstract:
Presentation d'une methode de recherche d'algorithmes de test des proprietes de graphes d'attributs engendres. Sont decrits, sous forme de point fixe d'un systeme regulier, des algorithmes iteratifs pour les tests de non-circularite, d'existence d'attributs inutiles et d'existence de chemins hamiltoniens dans les graphes engendres
9
Chepoi, Victor. "Métriques et convexité dans les graphes et espaces discrèts : propriétés et algorithmes." Aix-Marseille 2, 1997. http://www.theses.fr/1997AIX22124.
Full text
10
Soto, Gomez Mauricio Abel. "Quelques propriétés topologiques des graphes et applications à internet et aux réseaux." Paris 7, 2011. http://www.theses.fr/2011PA077228.
Full textAbstract:
Ce travail étudie des propriétés topologiques des graphes et leurs applications aux réseaux de communications, notamment aux graphes représentant structure d'Internet. Dans un premier temps, on s'intéresse à l'arborescence des graphes par l'étude de deux paramètres : l'hyperbolicité et la largeur arborescente (treewidth). Pour l' hyperbolicité, on analyse sa relation avec d'autres paramètres de graphes et on montre que certaines décompositions de graphes en permettent un calcul efficace. On calcule ces deux paramètres dans des instantanés d'Internet pour différents niveaux hiérarchiques et différentes périodes de temps. On y apporte des interprétations structurelles et algorithmiques pour les valeurs obtenues. On aborde ensuite le problème de partitionnement de graphes (clustering) sous l'angle de la modularité, paramètre qui mesure la qualité d'un partitionnement, largement utilisé dans la littérature. On analyse la modularité du point de vue théorique et son comportement asymptotique pour certaines familles de graphes. Enfin, on s'intéresse à une approche comminatoire de la théorie des files d'attente où les injections de paquets sont effectuées par un adversaire. On propose une généralisation de ce modèle par l'introduction de différentes classes de requêtes<br>This thesis focuses on topological properties of graphs and their application on communication networks, specifically on graphs reflecting Internet structure. We first look how far from a tree a graph may be by the study of two parameters: hyperbolicity and treewidth. For hyperbolicity, we analyse the relation with others graph parameters, we also show that some graph decompositions allow its efficient computation. We compute both parameters o Internet snapshots at different levels of granularity and time periods. We propose some structural and algorithmic consequences of obtained values. Then, we study the graph clustering problem from the perspective of modularity, which measures a clustering quality and is largely studied in the literature. We analyse modularity from a theoretical point of view and [describe] its asymptotic behaviour for some graph families. Finally, we deal with adversarial queueing theory, a combinatorial framework derived from classic queueing theory where injection process is und the control of an adversary. We propose a new model generalisation by considering request of distinct types
11
Ayadi, Hèla. "Opérateur de Gauss-Bonnet semi-Fredholm et propriétés spectrales sur les graphes infinis." Nantes, 2015. http://archive.bu.univ-nantes.fr/pollux/show.action?id=4e93e5ba-424b-4597-b472-15f4526b70c2.
Full textAbstract:
Dans le contexte des graphes infinis, localement finis et pondérés, nous nous intéressons à l’étude des propriétés de l’opérateur discret de Gauss-Bonnet qui est un opérateur de type Dirac (son carré est l’opérateur Laplacien). Plus précisément, nous donnons une version discrète de la notion importante de non-parabolicité à l’infini introduite par Gilles Carron pour les variétés Riemanniennes non-compactes. De plus, grâce à cette condition notre opérateur est Semi-Fredholm ce qui est utile dans la décomposition de Hodge pour résoudre des problèmes tel que le problème de Kirchhoff. Une autre partie de cette thèse consiste à étudier les propriétés spectrales de l’opérateur Laplacien. En fait, nous distinguons deux types d’opérateurs Laplaciens le premier défini sur l’espace des fonctions sur les sommets et le deuxième défini sur l’espace des fonctions sur les arêtes. C’est une question naturelle de voir le lien entre leur spectres respectifs. En utilisant, le critère de Weyl, nous montrons que le spectre de ces deux Laplaciens coïncident en dehors de la valeur 0. De plus, nous étendons le résultat de John Lott qui affirme que la valeur spectrale 0 est dans le spectre de l’un de ces deux Laplacien<br>In the context of an infinite locally finite weighted graph, we are interested in the study of discrete Gauss-Bonnet operator which is a Dirac type operator ( its square is the Laplacian operator ). In particular, we are focused on the conditions to have semi-Fredholmness operator needed to approach the Hodge decomposition theorem, which is important for solving problems such that Kirchhoff’s problem. In fact, we present a discrete version of the work of Gilles Carron which defines a new concept non-parabolicity at infinity to have the Gauss-Bonnet operator with closed range. Another part of this thesis consist to study the spectral properties of the Laplacian operator. We define two Laplacians one as an operator acting on functions on vertices and the other one acting on functions on edges. So, it is a natural question to characterize the relation between their spectrum in terms of a certain geometric property of the graph and properties of the operators. In fact, we show that the nonzero spectrum of the two laplacians are the same, by using Weyl criterion. In addition, we give an extension of the work of John Lott such that with suitable weight conditions, we prove that the spectral value 0 in the spectrum of one of these two Laplacians
12
Gaüzère, Benoit. "Application des méthodes à noyaux sur graphes pour la prédiction des propriétés des molécules." Phd thesis, Université de Caen, 2013. http://tel.archives-ouvertes.fr/tel-00933187.
Full textAbstract:
Cette thèse s'intéresse à l'application des méthodes à noyaux sur graphes pour la prédiction de propriétés moléculaires. Dans ce manuscrit, nous présentons un état de l'art des méthodes à noyaux sur graphes définies dans le cadre de la chémoinformatique et plus particulièrement les noyaux sur graphes basés sur les sacs de motifs. Dans ce cadre, nous proposons un nouveau noyau sur graphes basé sur un ensemble explicite de sous-arbres, appelés treelets, permettant d'encoder une grande partie de l'information structurelle acyclique des graphes moléculaires. Nous proposons également de combiner ce noyau avec des méthodes d'apprentissage à noyaux multiples afin d'extraire un ensemble de motifs pertinents. Cette contribution est ensuite étendue en incluant l'information cyclique encodée par deux représentations moléculaires définies par le graphe de cycles pertinents et l'hypergraphe de cycles pertinents. Le graphe des cycles pertinents permet d'encoder le système cyclique d'une molécule. L'hypergraphe de cycles pertinents correspond à une nouvelle représentation moléculaire permettant d'encoder à la fois le système cyclique d'une molécule ainsi que les relations d'adjacence entre les cycles et les parties acycliques. Nous proposons également deux noyaux sur graphes utilisant ces représentations. Enfin, la dernière partie vise à définir des noyaux sur graphes pour la chémoinformatique basés sur la distance d'édition. Un premier noyau est basé sur un opérateur de régularisation utilisant la distance d'édition entre graphes moléculaires. Le second noyau introduit la comparaison de treelets dissimilaires basée sur un algorithme de calcul de la distance d'édition entre treelets.
13
Gaüzère, Benoît. "Application des méthodes à noyaux sur graphes pour la prédiction des propriétés des molécules." Caen, 2013. http://www.theses.fr/2013CAEN2043.
Full textAbstract:
Cette thèse s'intéresse à l'application des méthodes à noyaux sur graphes pour la prédiction de propriétés moléculaires. Dans ce manuscrit, nous présentons un état de l'art des méthodes à noyaux sur graphes définies dans le cadre de la chémoinformatique et plus particulièrement les noyaux sur graphes basés sur les sacs de motifs. Dans ce cadre, nous proposons un nouveau noyau sur graphes basé sur un ensemble explicite de sous-arbres, appelés treelets, permettant d'encoder une grande partie de l'information structurelle acyclique des graphes moléculaires. Nous proposons également de combiner ce noyau avec des méthodes d'apprentissage à noyaux multiples afin d'extraire un ensemble de motifs pertinents. Cette contribution est ensuite étendue en incluant l'information cyclique encodée par deux représentations moléculaires définies par le graphe de cycles pertinents et l'hypergraphe de cycles pertinents. Le graphe des cycles pertinents permet d'encoder le système cyclique d'une molécule. L'hypergraphe de cycles pertinents correspond à une nouvelle représentation moléculaire permettant d'encoder à la fois le système cyclique d'une molécule ainsi que les relations d'adjacence entre les cycles et les parties acycliques. Nous proposons également deux noyaux sur graphes utilisant ces représentations. Enfin, la dernière partie vise à définir des noyaux sur graphes pour la chémoinformatique basés sur la distance d'édition. Un premier noyau est basé sur un opérateur de régularisation utilisant la distance d'édition entre graphes moléculaires. Le second noyau introduit la comparaison de treelets dissimilaires basée sur un algorithme de calcul de la distance d'édition entre treelets<br>This work deals with the application of graph kernel methods to the prediction of molecular properties. In this document, we first present a state of the art of graph kernels used in chemoinformatics and particurlarly those which are based on bags of patterns. Within this framework, we introduce the treelet kernel based on a set of trees which allows to encode most of the structural information encoded in molecular graphs. We also propose a combination of this kernel with multiple kernel learning methods in order to extract a subset of relevant patterns. This kernel is then extended by including cyclic information using two molecular representations defined by the relevant cycle graph and the relevant cycle hypergraph. Relevant cycle graph allows to encode the cyclic system of a molecule
14
Piau, Didier. "Quelques propriétés isopérimétriques du mouvement brownien et des marches au hasard sur les graphes." Lyon 1, 1994. http://www.theses.fr/1994LYO10018.
Full textAbstract:
Dans une premiere partie, on etudie une conjecture due a m. Sakai en 1987 et qui concerne le plus petit majorant harmonique de la fonction sous-harmonique x#p sur un domaine de l'espace euclidien. Nous donnons une interpretation brownienne du probleme, qui nous conduit a etudier des fonctionnelles polynomiales du mouvement brownien relatives au temps et au lieu de sortie de ses trajectoires hors du domaine. Cette approche permet d'obtenir de nouvelles estimations, de repondre completement a la question dans certains cas particuliers et elle conduit naturellement a construire de nouvelles extensions. Dans une deuxieme partie, on etudie des proprietes d'isoperimetrie analogues pour les arbres, en relation avec les marches au hasard associees. Nous montrons que le marcheur revient moins souvent a son point de depart sur un arbre donne que sur un arbre qui lui est subordonne. Nous retrouvons de maniere elementaire l'invariance du type des graphes par une quasi-isometrie demontree par m. Kanai en 1986. Finalement, nous obtenons une loi forte des grands nombres pour le rang d'une marche au hasard sur les arbres aleatoires de galton-watson supercritiques et un theoreme central limite pour les arbres homogenes
15
Sartor, del Giudice Pablo Enrique. "Propriétés et méthodes de calcul de la fiabilité diamètre-bornée des réseaux." Phd thesis, Université Rennes 1, 2013. http://tel.archives-ouvertes.fr/tel-00945265.
Full textAbstract:
Soit un réseau comprenant des lignes de communication qui échouent indépendamment, dans lequel tous ou certains sites, appelés terminaux, doivent être capables de communiquer entre eux. Dans le modèle stochastique statique classique le réseau est représenté par un graphe probabiliste dont les arêtes sont présentes selon des probabilités connues. La mesure de fiabilité classique (CLR) est la probabilité que les terminaux appartiennent à la même composante connexe. Dans plusieurs contextes il est utile d'imposer la condition plus forte que la distance entre deux terminaux quelconques soit bornée supérieurement par un paramètre d. La probabilité que ça se produise est connue comme la fiabilité diamètre-bornée (DCR). Il s'agit d'une extension de la CLR. Les deux problèmes appartiennent à la classe NP-difficile de complexité; le calcul exact n'est possible que pour les instances de taille limitée ou topologies spécifiques. Dans cette thèse, nous contribuons des résultats concernant le problème du calcul et l'estimation de la DCR. Nous étudions la complexité de calcul de cas particuliers, paramétré par le nombre de terminaux, nœuds et le paramètre d. Nous passons en revue des méthodes pour le calcul exact et étudions des topologies particulières pour lesquelles le calcul de la DCR a une complexité polynomiale. Nous introduisons des résultats de base sur le comportement asymptotique de la DCR lorsque le réseau se développe comme un graphe aléatoire. Nous discutons sur l'impact de la contrainte de diamètre dans l'utilisation des techniques de Monte Carlo, et adaptons et testons une famille de méthodes basées sur le conditionnement de l'espace d'échantillonnage en utilisant des structures nommées d-pathsets et d-cutsets. Nous définissons une famille de mesures de performabilité qui généralise la DCR, développons une méthode de Monte Carlo pour l'estimer, et présentons des résultats expérimentaux sur la performance de ces techniques Monte Carlo par rapport é l'approche naïve. Finalement, nous proposons une nouvelle technique qui combine la simulation Monte Carlo et l'interpolation polynomiale pour les mesures de fiabilité.
16
Benchetrit, Yohann. "Propriétés géométriques du nombre chromatique : polyèdres, structures et algorithmes." Thesis, Université Grenoble Alpes (ComUE), 2015. http://www.theses.fr/2015GREAM049/document.
Full textAbstract:
Le calcul du nombre chromatique et la détermination d'une colo- ration optimale des sommets d'un graphe sont des problèmes NP- difficiles en général. Ils peuvent cependant être résolus en temps po- lynomial dans les graphes parfaits. Par ailleurs, la perfection d'un graphe peut être décidée efficacement. Les graphes parfaits sont caractérisés par la structure de leur poly- tope des stables : les facettes non-triviales sont définies exclusivement par des inégalités de cliques. Réciproquement, une structure similaire des facettes du polytope des stables détermine-t-elle des propriétés combinatoires et algorithmiques intéressantes? Un graphe est h-parfait si les facettes non-triviales de son polytope des stables sont définies par des inégalités de cliques et de circuits impairs. On ne connaît que peu de résultats analogues au cas des graphes parfaits pour la h-perfection, et on ne sait pas si les problèmes sont NP-difficiles. Par exemple, les complexités algorithmiques de la re- connaissance des graphes h-parfaits et du calcul de leur nombre chro- matique sont toujours ouvertes. Par ailleurs, on ne dispose pas de borne sur la différence entre le nombre chromatique et la taille maxi- mum d'une clique d'un graphe h-parfait. Dans cette thèse, nous montrons tout d'abord que les opérations de t-mineurs conservent la h-perfection (ce qui fournit une extension non triviale d'un résultat de Gerards et Shepherd pour la t-perfection). De plus, nous prouvons qu'elles préservent la propriété de décompo- sition entière du polytope des stables. Nous utilisons ce résultat pour répondre négativement à une question de Shepherd sur les graphes h-parfaits 3-colorables. L'étude des graphes minimalement h-imparfaits (relativement aux t-mineurs) est liée à la recherche d'une caractérisation co-NP com- binatoire de la h-perfection. Nous faisons l'inventaire des exemples connus de tels graphes, donnons une description de leur polytope des stables et énonçons plusieurs conjectures à leur propos. D'autre part, nous montrons que le nombre chromatique (pondéré) de certains graphes h-parfaits peut être obtenu efficacement en ar- rondissant sa relaxation fractionnaire à l'entier supérieur. Ce résultat implique notamment un nouveau cas d'une conjecture de Goldberg et Seymour sur la coloration d'arêtes. Enfin, nous présentons un nouveau paramètre de graphe associé aux facettes du polytope des couplages et l'utilisons pour donner un algorithme simple et efficace de reconnaissance des graphes h- parfaits dans la classe des graphes adjoints<br>Computing the chromatic number and finding an optimal coloring of a perfect graph can be done efficiently, whereas it is an NP-hard problem in general. Furthermore, testing perfection can be carried- out in polynomial-time. Perfect graphs are characterized by a minimal structure of their sta- ble set polytope: the non-trivial facets are defined by clique-inequalities only. Conversely, does a similar facet-structure for the stable set polytope imply nice combinatorial and algorithmic properties of the graph ? A graph is h-perfect if its stable set polytope is completely de- scribed by non-negativity, clique and odd-circuit inequalities. Statements analogous to the results on perfection are far from being understood for h-perfection, and negative results are missing. For ex- ample, testing h-perfection and determining the chromatic number of an h-perfect graph are unsolved. Besides, no upper bound is known on the gap between the chromatic and clique numbers of an h-perfect graph. Our first main result states that the operations of t-minors keep h- perfection (this is a non-trivial extension of a result of Gerards and Shepherd on t-perfect graphs). We show that it also keeps the Integer Decomposition Property of the stable set polytope, and use this to answer a question of Shepherd on 3-colorable h-perfect graphs in the negative. The study of minimally h-imperfect graphs with respect to t-minors may yield a combinatorial co-NP characterization of h-perfection. We review the currently known examples of such graphs, study their stable set polytope and state several conjectures on their structure. On the other hand, we show that the (weighted) chromatic number of certain h-perfect graphs can be obtained efficiently by rounding-up its fractional relaxation. This is related to conjectures of Goldberg and Seymour on edge-colorings. Finally, we introduce a new parameter on the complexity of the matching polytope and use it to give an efficient and elementary al- gorithm for testing h-perfection in line-graphs
17
Sandouk, Mohamed Zouheir. "Méthodes et algorithmes pour l'infographie : exploitation des propriétés topologiques et géométriques de la scène." Toulouse 3, 1990. http://www.theses.fr/1990TOU30156.
Full textAbstract:
L'objectif de ces travaux est d'ameliorer des outils de l'infographie et d'accelerer des algorithmes de visualisation et en particulier le lancer de rayons. Par une exploitation de la coherence topologique et spatiale, nous proposons des techniques appliquees a des differentes modelisations: 1) modelisation csg: il s'agit d'utiliser le maximum d'informations que peut contenir l'arbre csg. Ces informations, obtenues dans une etape de pre-traitement, servent a reduire le nombre total d'intersection rayon-primitives. Cette reduction s'effectue grace a deux phases d'optimisation: la premiere phase est l'optimisation par les englobants relatifs. La seconde est l'utilisation du graphe de connexion et la normalisation de l'arbre csg; 2) modelisation quelconque: il s'agit d'utiliser au maximum les proprietes contenues dans la geometrie de la scene en proposant une generalisation du lemme euclidien: par deux points passe une droite et une seule. Ces informations, obtenues dans une etape de pre-traitement, servent a reduire le nombre total d'intersection rayon-primitives. Cette idee de generalisation du lemme euclidien peut etre utilisee pour traiter d'autres problemes dans l'infographie. Nous avons envisage son utilisation, pour le choix d'une bonne vue. Nous presentons a la fin une approche analytique pour l'evaluation de l'efficacite des optimisations proposees
18
Bernardinello, Luca. "Propriétés algébriques et combinatoires des régions dans les graphes et leur application a la synthèse de réseaux." Rennes 1, 1998. http://www.theses.fr/1998REN1S018.
Full textAbstract:
Une region d'un systeme de transitions est une application de l'ensemble des etats du systeme dans un espace d'evaluation, telle que les variations des valeurs aux extremites de transitions correspondant a la meme action soient uniformes. On etudie en detail le cas ou l'espace d'evaluation est un groupe. Toute region sur un groupe est associee a une application des actions dans le meme groupe, application qu'on appelle contrainte. Les regions et les contraintes d'un systeme de transitions sur un groupe forment deux groupes qui, sous certaines conditions, sont libres et finiment engendres. On montre une caracterisation des contraintes d'ou on derive un algorithme efficace pour le calcul d'une base du groupe des contraintes. L'etude des conditions sous lesquelles un ensemble des regions sur un groupe donne une representation fidele d'un systeme de transitions (c'est-a-dire suffisant a reconstruire le systeme) conduit au probleme de la synthese : decider si un systeme de transitions admet une representation <<<> structurelle <>>> (par opposition a l'aspect <<<> operationnel <>>> du systeme de transition) dans une classe de modeles fixee. On traite ici le probleme pour certaines classes de reseaux de petri, et on montre que dans le cas des reseaux elementaires le probleme est np-complet, tandis que pour les reseaux de places et transitions, finis et bornes, on decrit un algorithme de complexite polynomiale en la taille du systeme de transitions.
19
Martinez-Martinez, Sinuhé. "Analyse des propriétés structurelles d'observabilité de l'état et de l'entrée inconnue des systèmes linéaires par approche graphique." Phd thesis, Université Henri Poincaré - Nancy I, 2008. http://tel.archives-ouvertes.fr/tel-00324534.
Full textAbstract:
Le travail de thèse présenté dans ce document traite de l'analyse de différentes propriétés liées à l'observabilité des systèmes à entrée inconnue par approche graphique. La simplicité de mise en œuvre de l'approche graphique permet de se défaire des difficultés numériques inhérentes aux approches géométrique et algébrique. Ce constat a conduit ces dernières décennies, à une série d'études structurelles basées sur l'approche graphique. <br />Parmi les propriétés encore non abordées graphiquement, l'observabilité forte traduit l'observabilité des variables d'état d'un système pour toute valeur d'entrée ainsi que l'observabilité conjointe de l'état et de l'entrée. Ces propriétés plus fortes que l'observabilité simple et le diagnostic nous ont paru utiles et pertinentes à étudier. En effet, les outils d'analyse développés peuvent s'avérer importants dans le cadre de la synthèse d'observateurs ou d'estimateurs d'entrées utile à la synthèse de lois de commandes tolérantes aux défauts ou robustes aux perturbations, ou encore quand il s'agit de vérifier si la propriété d'observabilité d'un système n'est pas altérée lorsqu'il est soumis à des perturbations, voire à des défauts d'amplitude trop importante pour être négligés. <br />Le manuscrit est structuré en trois parties. Dans la première, nous avons abordé l'analyse de différentes propriétés d'observabilité. Plus précisément, nous avons tout d'abord donné des conditions nécessaires et suffisantes d'observabilité de l'entrée et de l'état d'un système. Des conditions nécessaires et suffisantes pour l'observabilité forte d'une partie donnée des composantes de l'entrée et de l'état ont ensuite été établies. Le dernier résultat de cette partie concerne l'observabilité forte de tout l'état d'un système à entrée inconnue. Des conditions nécessaires et suffisantes ont été démontrées. <br />La seconde partie de cette thèse a consisté à étudier le problème du placement des capteurs afin de recouvrer des propriétés d'observabilité forte lorsque les conditions de la première partie ne sont pas vérifiées. Deux cas ont été traités. Le premier concerne la propriété d'observabilité forte d'une partie donnée de l'état. La stratégie de placement de capteurs consiste alors en une condition nécessaire permettant d'imposer qu'au moins une sortie du système soit sensible à chacune des composantes de l'état devant être fortement observables, puis en un système de relations graphiques, utilisé comme condition suffisante à ce qu'une configuration de capteurs assure l'observabilité forte des composantes de l'état choisies. Le second problème de placement de capteurs a pour objectif de rendre observables toutes les composantes de l'état. Le problème a été traité en trois étapes. Pour chacune d'elles, des conditions nécessaires et suffisantes sur le placement de capteurs ont été trouvées. Le nombre minimal de capteurs nécessaire et suffisant a aussi été déterminé. Les conditions trouvées sont fondées essentiellement sur des algorithmes classiques de la théorie des graphes.<br />La troisième partie traite de l'implémentation des résultats établis dans une boîte à outils dédiée à l'analyse structurelle (lisa) des systèmes linéaires et bilinéaires structurés. En premier lieu, les motivations qui ont conduit à la conception de cette boîte à outils sont exposées. La structure de lisa est ensuite présentée. Elle repose entièrement sur des algorithmes de base tels que la détermination des ensembles de successeurs et de prédécesseurs, le calcul des tailles de lien et de couplages maximaux entre deux ensembles de sommets et la caractérisation des ensembles de sommets essentiels dans des liens de taille maximale ou encore des séparateurs d'entrée et de sortie. Tous ces algorithmes ont des ordres de complexité polynomiaux. Nous avons montré comment en associant certains algorithmes de base, nous sommes arrivés à analyser l'observabilité de l'état et de l'entrée et à établir des conditions de détection et de localisation de défauts. Enfin, il est présenté des fonctions pouvant être rajoutées à lisa concernant différentes propriétés structurelles pour en faire un outil d'analyse plus complet.
20
Dakil, Manal. "Développement d'une méthodologie conjointe d'analyse structurelle et de sûreté de fonctionnement des propriétés d'un système complexe." Thesis, Université de Lorraine, 2014. http://www.theses.fr/2014LORR0133/document.
Full textAbstract:
Ce sujet de thèse concerne le développement d’analyse des propriétés structurelles en interaction avec des indicateurs de fiabilité. Notre étude porte sur des systèmes structurés (linéaire, bilinéaire ou linéaire à commutations), ces derniers doivent vérifier quelques propriétés importantes pour l’accomplissement de leur mission. Ces propriétés dépendent de la structure du système, d’où l’appellation "propriétés structurelles". La structure du système peut être représentée par un graphe composé de sommets et d’arcs. La vérification des propriétés structurelles dépend principalement de 4 conditions élémentaires de connectivité, de lien, de distance et de couplage complet. Nous avons développé des algorithmes permettant de les exprimer sous forme d’expressions booléennes basées sur les arcs du graphe représentant le système. Nous considérons que chaque arc est lié aux composants du système. Une défaillance au niveau des composants peut provoquer la modification de la structure du système, et donc peut rendre une propriété structurelle insatisfaite. Ainsi, les propriétés structurelles sont écrites sous forme d’expressions booléennes basées sur l’état de fonctionnement des composants. En utilisant les expressions booléennes associées aux propriétés structurelles, leur fiabilité et/ou disponibilité peut être calculée sachant les caractéristiques de sûreté de fonctionnement des composants du système. À travers cette étude, nous pouvons vérifier si, pendant le temps de mission du système, une propriété structurelle restera satisfaite et/ou respectera un niveau de performance exigé par un cahier des charges<br>This thesis concerns the development of analysis of structural properties in interaction with indicators of reliability. Our study focuses on (linear, bilinear or switching) structured systems, they must verify some important properties for the accomplishment of their mission. Properties depend on the structure of the system, hence the term "structural properties". The structure of the system can be represented by a graph consisting of vertices and edges. Verification of structural properties depends mainly on four basic conditions of connectivity, link distance and complete linkage. We have developed algorithms to express the form of Boolean expressions based on the edges of the graph representing the system. We consider that each edge is linked to the system components. A failure at the component level can cause changes in the structure of the system, and therefore can make a structural property unsatisfied. Thus, the structural properties are written as boolean expressions based on the operating state of the components. Using boolean expressions associated to the structural properties, reliability and / or availability can be calculated knowing the characteristics of the system components. Through this study, we can check if during the mission time of the system, a structural property remain satisfied and / or comply with a level of performance required by the specifications
21
Martinet, Lucie. "Réseaux dynamiques de terrain : caractérisation et propriétés de diffusion en milieu hospitalier." Thesis, Lyon, École normale supérieure, 2015. http://www.theses.fr/2015ENSL1010/document.
Full textAbstract:
Durant cette thèse, nous nous sommes intéressés aux outils permettant d'extraire les propriétés structurelles et temporelles de réseaux dynamiques ainsi que les caractéristiques de certains scénarios de diffusion pouvant s'opérer sur ces réseaux. Nous avons travaillé sur un jeu de données spécifiques, issu du projet MOSAR, qui comporte entre autre le réseau de proximité des personnes au cours du temps durant 6 mois à l'hôpital de Berk-sur-mer. Ce réseau est particulier dans le sens où il est constitué de trois dimensions: temporelle, structurelle par la répartition des personnes en services et fonctionnelle car chaque personne appartient à une catégorie socio-professionnelle. Pour chacune des dimensions, nous avons utilisé des outils existants en physique statistique ainsi qu'en théorie des graphes pour extraire des informations permettant de décrire certaines propriétés du réseau. Cela nous a permis de souligner le caractère très structuré de la répartition des contacts qui suit la répartition en services et mis en évidence les accointances entre certaines catégories professionnelles. Concernant la partie temporelle, nous avons mis en avant l'évolution périodique circadienne et hebdomadaire ainsi que les différences fondamentales entre l'évolution des interactions des patients et celle des personnels. Nous avons aussi présenté des outils permettant de comparer l'activité entre deux périodes données et de quantifier la similarité de ces périodes. Nous avons ensuite utilisé la technique de simulation pour extraire des propriétés de diffusion de ce réseau afin de donner quelques indices pour établir une politique de prévention<br>In this thesis, we focus on tools whose aim is to extract structural and temporal properties of dynamic networks as well as diffusion characteristics which can occur on these networks. We work on specific data, from the European MOSAR project, including the network of individuals proximity from time to time during 6 months at the Brek-sur-Mer Hospital. The studied network is notable because of its three dimensions constitution : the structural one induced by the distribution of individuals into distinct services, the functional dimension due to the partition of individual into groups of socio-professional categories and the temporal dimension.For each dimension, we used tools well known from the areas of statistical physics as well as graphs theory in order to extract information which enable to describe the network properties. These methods underline the specific structure of the contacts distribution which follows the individuals distribution into services. We also highlight strong links within specific socio-professional categories. Regarding the temporal part, we extract circadian and weekly patterns and quantify the similarities of these activities. We also notice distinct behaviour within patients and staff evolution. In addition, we present tools to compare the network activity within two given periods. To finish, we use simulations techniques to extract diffusion properties of the network to find some clues in order to establish a prevention policy
22
Andaloussi, Chafik. "Propriétés structurelles des systèmes linéaires à paramètres variant dans le temps : approche bond-graph." Ecole Centrale de Lille, 2007. http://www.theses.fr/2007ECLI0004.
Full textAbstract:
Cette thèse étudie des propriétés structurelles sur les modèles bond graphs. La motivation principale est de contribuer à la résolution des problèmes liés à l’étude des propriétés structurelles et au calcul du système inverse d’un système LTV à l’aide de l’utilisation des propriétés et des avantages offerts par une représentation graphique telle que le bond graph. Cette problématique est abordée dans le cas de modèles bond graphs linéaires à paramètres variant dans le temps et des outils adéquats ont été proposés. De nouveaux concepts ont été introduits : en définissant la notion d’anneau bond graph non commutatif, une nouvelle règle de gain ou "règle de Riegle" est introduite en bond graph. Grâce à l’introduction de la notion de l’algèbre différentielle et à l’aide des opérateurs (delta et sigma), il est possible de calculer graphiquement les termes des matrices de commandabilité/observabilité en utilisant des règles adéquates basées sur le calcul de la longueur des chemins causaux entrées-états/états-sorties. Il est aussi montré que les règles graphiques de l’étude de la structure à l’infini restent applicables dans un anneau bond-graph. Pour aller plus loin dans l’introduction de l’outil d’algèbre différentielle aux bond graphs, l’étude des propriétés d’inversibilité d’un modèle anneau bond-graph a été abordée. Dans ce contexte et grâce à la notion des chemins causaux entrées-sorties disjoints, il est possible de faire une analyse de l’inversibilité directement à partir de son modèle BG. Il est également montré que la notion de bicausalité et l’obtention graphique de la paramétrisation différentielle en utilisant la règle de Riegle est rendue possible<br>This thesis aims at the study of the structural properties on the bond-graph models. The principal motivation is to contribute to the resolution of the problems related on the study of the structural properties and calculation of the inverse system of a LTV system using of the properties and the advantages offered by a graphical representation such as the bond-graph. These problems are approached in the case of linear bond-graphs models with time varying parameters and the adequate tools were proposed. To achieve these goals, new concepts and tools were introduced. In particular, defining the concept of noncommutative bond-graph ring, a new gain rule known under the name of “Riegle rule” is introduced in bond-graph. In addition, thanks to the introduction of the notion of the differential algebra and using of the operators (delta and sigma), it became possible to graphically calculate the terms of the matrices of commandability/observability by using appropriate rules based on calculation length of the causal paths inputs-states/states-outputs. It is also shown that the graphic rules of the study of the infinite structure remain applicable in a bond-graph ring. Finally, to go further in the introduction of the algebra tool and modules to the bond-graphs, the study of the properties of inversibility of a bond-graph ring model was approached. In this context and basing on the disjoint input-output causal paths notion, it is possible to make an analysis of the inversibility directly from its BG model. It is also shown that the bicausality concept and graphic determination of the differential parameterization by using the rule of Riegle are made possible
23
Sartor, Pablo. "Propriétés et méthodes de calcul de la fiabilité diamètre-bornée des réseaux." Phd thesis, Université Rennes 1, 2013. http://tel.archives-ouvertes.fr/tel-00939946.
Full textAbstract:
Soit un réseau comprenant des lignes de communication qui échouent indépendamment, dans lequel tous ou certains sites, appelés terminaux, doivent être capables de communiquer entre eux. Dans le modèle stochastique statique classique le réseau est représenté par un graphe probabiliste dont les arêtes sont présentes selon des probabilités connues. La mesure de fiabilité classique (CLR) est la probabilité que les terminaux appartiennent à la même composante connexe. Dans plusieurs contextes il est utile d'imposer la condition plus forte que la distance entre deux terminaux quelconques soit bornée supérieurement par un paramètre d. La probabilité que ça se produise est connue comme la fiabilité diamètre-bornée (DCR). Il s'agit d'une extension de la CLR. Les deux problèmes appartiennent à la clase NP-difficile de complexité ; le calcul exact n'est possible que pour les instances de taille limitée ou topologies spécifiques. Dans cette thèse, nous contribuons des résultats concernant le problème du calcul et l'estimation de la DCR. Nous étudions la complexité de calcul de cas particuliers, paramétré par le nombre de terminaux, noeuds et le paramètre d. Nous passons en revue des méthodes pour le calcul exact et étudions des topologies particulières pour lesquelles le calcul de la DCR a une complexité polynomiale. Nous présentons des résultats de base sur le comportement asymptotique de la DCR lorsque le réseau se développe comme un graphe aléatoire. Nous discutons sur l'impact de la contrainte de diamètre dans l'utilisation des techniques de Monte Carlo, et adaptons et testons une famille de méthodes basées sur le conditionnement de l'espace d'échantillonnage en utilisant des structures nommées d-pathsets et d-cutsets. Nous définissons une famille de mesures de performabilité qui généralise la DCR, développons une méthode de Monte Carlo pour l'estimer, et présentons des résultats expérimentaux sur la performance de ces techniques Monte Carlo par rapport à l'approche naïve. Finalement, nous proposons une nouvelle technique qui combine la simulation Monte Carlo et l'interpolation polynomiale pour les mesures de fiabilité.
24
Kozhevnikov, Artem. "Propriétés métriques des ensembles de niveau des applications différentiables sur les groupes de Carnot." Thesis, Paris 11, 2015. http://www.theses.fr/2015PA112073/document.
Full textAbstract:
Nous étudions les propriétés métriques locales des ensembles de niveau des applicationshorizontalement différentiables entre des groupes de Carnot, c'est-à-dire différentiable par rapport à la structure sous-riemannienne intrinsèque.Nous considérons des applications dont la différentielle horizontale est surjective,et notre étude peut être vue comme une généralisation du théorème des fonctions implicites pour les groupes de Carnot.Tout d'abord, nous présentons deux notions de tangence dans les groupes de Carnot:la première basée sur la condition de platitude au sens de Reifenberg et la deuxième issue de l'analyse convexe classique.Nous montrons que dans les deux cas, l'espace tangent à un ensemble de niveau coïncide avec le noyau de la différentielle horizontale.Nous montrons que cette condition de tangence caractérise en fait les ensembles de niveaudits ‘co-abéliens', c'est-à-dire ceux pour lesquels l'espace d'arrivée est abélien, et qu'une telle caractérisation n'est pas vraie en général.Ce résultat sur les espaces tangents a plusieurs conséquences remarquables.La plus importante est que la dimension de Hausdorff des ensembles de niveau est celle à laquelle l'on s'attend.Nous montrons également la connectivité locale des ensembles de niveau, et le fait que les ensembles de niveau de dimension 1 sont topologiquement des arcs simples.Pour les ensembles de niveau de dimension 1 nous trouvons une formule de l'aire qui permet d'exprimer la mesure de Hausdorff en termes d'intégrales de Stieltjes généralisées.Ensuite, nous menons une étude approfondie du cas particulier des ensembles de niveau dans les groupes d'Heisenberg.Nous montrons que les ensembles de niveau sont topologiquement équivalents à leurs espaces tangents.Il s'avère que la mesure de Hausdorff des ensembles de niveau de codimension élevée est souvent irrégulière, étant, par exemple, localement nulle ou infinie.Nous présentons une condition simple de régularité supplémentaire pour une application pour assurer la régularité au sens d'Ahlfors des ses ensembles de niveau.Parmi d'autres résultats, nous obtenons une nouvelle caractérisation généraledes graphes Lipschitziens associés à une décomposition en produit semi-direct d'un groupe de Carnot.Nous traitons, en particulier, le cas des groupes de Carnot dont le nombre de stratesest plus grand que $2$.Cette caractérisation nous permet de déduire une nouvelle caractérisation des ensemblesde niveau co-abéliens qui admettent une représentation en tant que graphe<br>Metric properties of level sets of differentiable maps on Carnot groupsAbstract.We investigate the local metric properties of level sets of mappings defined between Carnot groups that are horizontally differentiable, i.e.with respect to the intrinsic sub-Riemannian structure. We focus on level sets of mapping having a surjective differential,thus, our study can be seen as an extension of implicit function theorem for Carnot groups.First, we present two notions of tangency in Carnot groups: one based on Reifenberg's flatness condition and another coming from classical convex analysis.We show that for both notions, the tangents to level sets coincide with the kernels of horizontal differentials.Furthermore, we show that this kind of tangency characterizes the level sets called ``co-abelian'', i.e.for which the target space is abelian andthat such a characterization may fail in general.This tangency result has several remarkable consequences.The most important one is that the Hausdorff dimension of the level sets is the expected one. We also show the local connectivity of level sets and, the fact that level sets of dimension one are topologically simple arcs.Again for dimension one level set, we find an area formula that enables us to compute the Hausdorff measurein terms of generalized Stieltjes integrals.Next, we study deeply a particular case of level sets in Heisenberg groups. We show that the level sets in this case are topologically equivalent to their tangents.It turns out that the Hausdorff measure of high-codimensional level sets behaves wildly, for instance, it may be zero or infinite.We provide a simple sufficient extra regularity condition on mappings that insures Ahlfors regularity of level sets.Among other results, we obtain a new general characterization of Lipschitz graphs associated witha semi-direct splitting of a Carnot group of arbitrary step.We use this characterization to derive a new characterization of co-ablian level sets that can be represented as graphs
25
Vergara, Soto Ignacio. "Multipliers and approximation properties of groups." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSEN042/document.
Full textAbstract:
Cette thèse porte sur des propriétés d'approximation généralisant la moyennabilité pour les groupes localement compacts. Ces propriétés sont définies à partir des multiplicateurs de certaines algèbres associés aux groupes. La première partie est consacrée à l'étude de la propriété p-AP, qui est une extension de la AP de Haagerup et Kraus au cadre des opérateurs sur les espaces Lp. Le résultat principal dit que les groupes de Lie simples de rang supérieur et de centre fini ne satisfont p-AP pour aucun p entre 1 et l'infini. La deuxième partie se concentre sur les multiplicateurs de Schur radiaux sur les graphes. L'étude de ces objets est motivée par les liens avec les actions de groupes discrets et la moyennabilité faible. Les trois résultats principaux donnent des conditions nécessaires et suffisantes pour qu'une fonction sur les nombres naturels définisse un multiplicateur radial sur des différentes classes de graphes généralisant les arbres. Plus précisément, les classes de graphes étudiées sont les produits d'arbres, les produits de graphes hyperboliques et les complexes cubiques CAT(0) de dimension finie<br>This thesis focusses on some approximation properties which generalise amenability for locally compact groups. These properties are defined by means of multipliers of certain algebras associated to the groups. The first part is devoted to the study of the p-AP, which is an extension of the AP of Haagerup and Kraus to the context of operators on Lp spaces. The main result asserts that simple Lie groups of higher rank and finite centre do not satisfy p-AP for any p between 1 and infinity. The second part concentrates on radial Schur multipliers on graphs. The study of these objects is motivated by some connections with actions of discrete groups and weak amenability. The three main results give necessary and sufficient conditions for a function of the natural numbers to define a radial multiplier on different classes of graphs generalising trees. More precisely, the classes of graphs considered here are products of trees, products hyperbolic graphs and finite dimensional CAT(0) cube complexes
26
De, Joannis de Verclos Rémi. "Applications des limites de structures combinatoires en géométrie et en théorie des graphes." Thesis, Université Grenoble Alpes (ComUE), 2018. http://www.theses.fr/2018GREAM037/document.
Full textAbstract:
Cette thèse traite de problèmes liés à la théorie des limitesd'objets combinatoires, une récente théorie qui a permis de tisserdes liens entre différents domaines tels que la combinatoire,l'analyse, la géométrie ou la théorie de la probabilité.Cette thèse applique des méthode venant de cette théorie à des problèmesde combinatoire extrémale.Dans un premier chapitre, je développe une théorie des limites d'objetsappelés emph{types d'ordre}, un objets qui encode des configurationsd'ensembles de points du plan. Le type d'ordre d'un ensemble de pointssuffit à caractériser de nombreuses propriétés essentielles de cet ensemblede point comme, par exemple, son enveloppe convexe.Je montre qu'une limite de type d'ordre peut être représentée par un objetanalogue à un graphon à valeurs O ou 1.Je fais ensuite le lien entre limites de type d'ordre et la distributionnaturelle de limite de type d'ordre obtenue par l’échantillonnage de pointsdu plan suivant une certaine probabilité.De cette manière, toute probabilité sur le plan engendre une limite de typed'ordre. Je montre d'une part que cette correspondance n'est pas surjective-c'est à dire qu'il existe des limites de type d'ordre ne venant pas de probabilitédu plan- et j'étudie d'autre part son injectivité.Je montre que si le support d'une mesure de probabilité est assez gros, par exemple siil contient une boule ouvert, alors la limite que cette mesure engendre suffit à caractériser cette mesure à une transformation projective près.Un second chapitre traite de test de propriété.Un testeur de propriété est un algorithme aléatoire permettant de séparerles objets ayant une certaine propriété des objet à distance au moins εde l'avoir, au sens de la distance d'édition.Ce domaine donne des algorithmes extrêmement rapides, et en particulierdes algorithmes dont la complexité ne dépends pas de la taille de l'entréemais seulement du paramètre de précision ε.Un résultat fondamental de cet domaine pour les graphes montré par Alonet Shapira est le suivant : toute classe de graphe héréditaire possède un teltesteur.Cette thèse contribue à la question suivante :Quelles classes de graphes possède un testeur dont la complexité est unpolynôme en 1/ε ?Je montre qu'en particulier la classe des graphes d'intervales possède un teltesteur.La théorie des algèbres de drapeaux est un outil étroitement lié aux limites degraphes denses qui donne une méthode pour démontrer des bornes sur certainsparamètres combinatoires à l'aide d'un ordinateur.Dans un troisième chapitre, je présente un programme écrit durant ma thèsequi implémente cette méthode.Ce programme fonctionne comme une bibliothèque pour calculer dans les algèbresde drapeaux, manipuler des inégalités sur les drapeaux ou encoder des problèmesd'optimisations par une instance de programme semi-défini positif qui peutensuite être résolu par un solveur externe.Ce programme est en particulier utilisé pour obtenir un nouvelle borne pour le cas triangulaire de la conjecture de Caccetta-Häggkvist<br>This thesis is focused on problems related to the theory of combinatorial limits.This theory opened links between different fields such asanalysis, combinatorics, geometry and probability theory.In this thesis, we apply ideas coming from this framework toproblems in extremal combinatorics.In a first chapter we develop a theory of limits for emph{order types},a geometrical object that encodes configuration of a set of points in theplane by the mean of the orientations of their triangles.The order type of a point set suffices to determine many of its properties,such as for instance the boundary of its convex hull.We show that the limit of a converging sequence of order typescan be represented by random-free object analogous to a graphon.Further, we link this notion to the natural distributions of order typesarising from the sampling of random points from some probability measureof the plane.We observe that in this mean, every probability measure gives rise to a limitof order types.We show that this map from probability measure on the plane to limit oforder type is not surjective.Concerning its injectivity,we prove that if a measure has large enough support, for instance if its supportcontains an open ball, the limit of order types the measure generatessuffices to essentially determine this measure.A second chapter is focused on property testing.A tester is a randomized algorithm for distinguishing between objects satisfyinga property from those that are at some distance at least εfrom having itby means of the edition distance.This gives very efficient algorithms, and in particular algorithms whosecomplexity does not depend on the size of the input but only on the parameter ε.For graphs, it has been shown by Alon and Shapira that every hereditary propertyhas such a tester.We contribute to the following question :which classes of graphs have a one-sided property tester with a number of queries that is a polynomial in 1/ε ?We give a proof that the class of interval graphs has such a tester.The theory of flag algebras is a framework introduced by Razborovclosely related to dense limit of graphs, that gives a way to systematicallyderive bounds for parameters in extremal combinatorics.In a third chapter we present a program developed during my Phd.that implements this method.This program works as a library that can compute flag algebras,manipulate inequalities on densities and encode the optimization of some parameterin a semi-definite positive instance that can be given to a dedicated solverto obtain a bound on this parameter.This program is in particular used to obtain a new bound forthe triangle case of the Caccetta-Häggkvist conjecture
27
Lissy, Alexandre. "Utilisation de méthodes formelles pour garantir des propriétés de logiciels au sein d'une distribution : exemple du noyau Linux." Thesis, Tours, 2014. http://www.theses.fr/2014TOUR4019/document.
Full textAbstract:
Dans cette thèse nous nous intéressons à intégrer dans la distribution Linux produite par Mandriva une assurance qualité permettant de proposer des garanties de propriétés sur le code exécuté. Le processus de création d’une distribution implique l’utilisation de logiciels de provenances diverses pour proposer un assemblage cohérent et présentant une valeur ajoutée pour l’utilisateur. Ceci engendre une moindre maîtrise potentielle sur le code. Un audit manuel permet de s’assurer que celui-Ci présente de bonnes propriétés, par exemple, en matière de sécurité. Le nombre croissant de composants à intégrer, et la croissance de la quantité de code de chacun amènent à avoir besoin d’outils pour permettre une assurance qualité. Après une étude de la distribution nous choisissons de nous concentrer sur un paquet critique, le noyau Linux : nous proposons un état de l’art des méthodes de vérifications appliquées à ce contexte particulier, et identifions le besoin d’améliorer la compréhension de la structure du code source, la question de l’explosion combinatoire et le manque d’intégration des outils d’analyse de l’état de l’art. Pour répondre à ces besoins nous proposons une représentation du code source sous la forme d’un graphe, et l’utilisons pour aider à la documentation et à la compréhension de l’architecture du code. Des méthodes de détection de communautés sont évaluées sur ce cas pour répondre au besoin de l’explosion combinatoire. Enfin nous proposons une architecture intégrée dans le système de construction de la distribution permettant d’intégrer des outils d’analyse et de vérification de code<br>In this thesis we are interested in integrating to the Linux distribution produced by Mandriva quality assurance level that allows ensuring user-Defined properties on the source code used. The core work of a distribution and its producer is to create a meaningful aggregate from software available. Those softwares are free and open source, hence it is possible to adapt it to improve end user’s experience. Hence, there is less control over the source code. Manual audit can of course be used to make sure it has good properties. Examples of such properties are often referring to security, but one could think of others. However, more and more software are getting integrated into distributions and each is showing an increase in source code volume: tools are needed to make quality assurance achievable. We start by providing a study of the distribution itself to document the current status. We use it to select some packages that we consider critical, and for which we can improve things with the condition that packages which are similar enough to the rest of the distribution will be considered first. This leads us to concentrating on the Linux kernel: we provide a state of the art overview of code verification applied to this piece of the distribution. We identify a need for a better understanding of the structure of the source code. To address those needs we propose to use a graph as a representation of the source code and use it to help document and understand its structure. Specifically we study applying some state of the art community detection algorithm to help handle the combinatory explosion. We also propose a distribution’s build system-Integrated architecture for executing, collecting and handling the analysis of data produced by verifications tools
28
Cassé, Clement. "Prévision des performances des services Web en environnement Cloud." Electronic Thesis or Diss., Toulouse 3, 2023. http://www.theses.fr/2023TOU30268.
Full textAbstract:
Le Cloud Computing a bouleversé la façon dont sont développés et déployées les logiciels. De nos jours, les applications Cloud sont conçues comme des systèmes distribués, en constante évolution, hébergés dans des data~center gérés par des tiers, et potentiellement même dispersés dans le monde entier. Ce changement de paradigme a également eu un impact considérable sur la façon dont les logiciels sont monitorés : les applications cloud se sont développées pour atteindre l'ordre de centaines de services, et les outils de monitoring ont rapidement rencontré des problèmes de mise à l'échelle. De plus, ces outils de monitoring doivent désormais également traiter les défaillances et les pannes inhérentes aux systèmes distribués, comme par exemple, les pannes partielles, les configurations incohérentes, les goulots d'étranglement ou même la vampirisation de ressources. Dans cette thèse, nous présentons une approche basée sur une nouvelle source de télémétrie qui s'est développée dans le domaine du monitoring des applications Cloud. En effet, en nous appuyant sur le récent standard OpenTelemetry, nous présentons un système qui convertit les données de "traces distribuées" en un graphe de propriétés hiérarchique. Grâce un tel modèle, il devient possible de mettre en évidence la topologie des applications, y compris la répartition sur les différentes machines des programmes, y compris sur plusieurs data-centers. L'objectif de ce modèle est donc d'exposer le comportement des fournisseurs de service Cloud aux développeurs qui maintiennent et optimisent leur application. Ensuite, nous présentons l'utilisation de ce modèle pour résoudre certains des défis majeurs des systèmes distribués~: la détection des communications inefficaces entre les services et l'anticipation des goulots d'étranglement. Nous abordons ces deux problèmes avec une approche basée sur la théorie des graphes. La composition inefficace des services est détectée avec le calcul de l'indice de hiérarchie de flux. Une plateforme Proof-of-Concept représentant un cluster Kubernetes zonal pourvu d'une instrumentation OpenTelemetry est utilisée pour créer et détecter les compositions de services inefficaces. Dans une dernière partie, nous abordons la problématique de la détection des goulots d'étranglement dans un réseau de services au travers de l'analyse de centralité du graphe hiérarchique précédent. Ce travail s'appuie sur un programme de simulation qui a aussi été instrumenté avec OpenTelemetry afin d'émettre des données de traçage. Ces traces ont été converties en un graphe de propriétés hiérarchique et une étude sur les algorithmes de centralité a permis d'identifier les points d'étranglement. Les deux approches présentées dans cette thèse utilisent et exploitent l'état de l'art en matière de monitoring des applications Cloud. Elles proposent une nouvelle utilisation des données de "distributed tracing" pas uniquement pour l'investigation et le débogage, mais pour la détection et la réaction automatiques sur un système réel<br>Cloud Computing has changed how software is now developed and deployed. Nowadays, Cloud applications are designed as rapidly evolving distributed systems that are hosted in third-party data centre and potentially scattered around the globe. This shift of paradigms also had a considerable impact on how software is monitored: Cloud application have been growing to reach the scale of hundreds of services, and state-of-the-art monitoring quickly faced scaling issues. In addition, monitoring tools also now have to address distributed systems failures, like partial failures, configuration inconsistencies, networking bottlenecks or even noisy neighbours. In this thesis we present an approach based on a new source of telemetry that has been growing in the realm of Cloud application monitoring. Indeed, by leveraging the recent OpenTelemetry standard, we present a system that converts "distributed tracing" data in a hierarchical property graph. With such a model, it becomes possible to highlight the actual topology of Cloud applications like the physical distribution of its workloads in multiple data centres. The goal of this model is to exhibit the behaviour of Cloud Providers to the developers maintaining and optimizing their application. Then, we present how this model can be used to solve some prominent distributed systems challenges: the detection of inefficient communications and the anticipation of hot points in a network of services. We tackle both of these problems with a graph-theory approach. Inefficient composition of services is detected with the computation of the Flow Hierarchy index. A Proof of Concept is presented based on a real OpenTelemetry instrumentation of a Zonal Kubernetes Cluster. In, a last part we address the concern of hot point detection in a network of services through the perspective of graph centrality analysis. This work is supported by a simulation program that has been instrumented with OpenTelemetry in order to emit tracing data. These traces have been converted in a hierarchical property graph and a study on the centrality algorithms allowed to identify choke points. Both of the approaches presented in this thesis comply with state-of-the-art Cloud application monitoring. They propose a new usage of Distributed Tracing not only for investigation and debugging but for automatic detection and reaction on a full system
29
Ferrah, Djawhar. "Etude des propriétés physico-chimiques d'interfaces par photoémission." Thesis, Ecully, Ecole centrale de Lyon, 2013. http://www.theses.fr/2013ECDL0048/document.
Full textAbstract:
L'objectif de cette thèse est d'étudier les propriétés physico-chimiques des surfaces et des interfaces des couches minces par spectroscopie de photoémission (XPS), diffraction des photoélectrons (XPD), et la photoémission résolue en temps (PTR). Les expériences sont réalisées en utilisant une source standard des rayons X AlKa à l'INL ou les rayons X mous auprès du synchrotron Soleil. La première étude sur le système Pt/ Gd203/ Si(111) a montré que le transfert de charge entre le Pt et 0 à l'interface Pt/Gd203 implique un déplacement chimique de niveau Pt4f sans modification des caractéristiques de la composante métallique des spectres XPS. L'étude XPD montre que Pt se cristallise partiellement en deux domaines : [110] Pt(111) // [110] Gd203 (111) et [101] Pt(111) / / [110] Gd203 (111). De plus, une autre phase ordonnée d'oxyde de platine Pt02 à l'interface a été observée. A travers la caractérisation de la morphologie déterminée par la technique AFM et XPD, nous avons discuté l'adhésion aux interfaces métal/oxyde. La deuxième étude traite l'évolution d'interface d'un système modèle : métal non réactive/ semi-conducteur, dépendent fortement des conditions thermodynamiques. Nous avons étudié la couche mince d'Au déposée sur le substrat Si(001) par photoémission résolue en temps (TEMPO- synchrotron Soleil). L'étude XPS, montre avant le recuit la formation de l'oxyde native Si02 sur l'heterostructure à température ambiante. La désorption de cet oxyde se produit à faible température et induit une décroissance de l'intensité des photoélectrons durant le temps de recuit. La désorption de l'oxyde Si02 et la formation de l'alliage AuSi sont responsables de la gravure et la formation des puits de forme cubique à la surface de Si due à l'activité catalytique de l'Au. La troisième étude concerne la croissance du graphène à partir de cristal de SiC(0001)- face Si par décomposition thermique. Le niveau de coeur C1s résolu en trois composantes principales sont associées au carbone de 6H-SiC, de graphène, et l'interface graphène/ 6H-SiC (0001). L'intensité de chaque composante est rapportée en fonction de l'angle polaire (azimutale) pour différents angles azimutales (polaire). Les mesures XPD fournissent des informations cristallographiques qui indiquent clairement que les feuillets de graphène sont organisés en structure graphite sur le substrat 6H-SiC (0001). Cette organisation résulte de l’effondrement de la maille de substrat. Enfin, le découplage à l'interface graphène/ 6H-SiC (0001) par l'oxygène a été étudié par XPS. La dernière étude concerne la croissance du film mince d'InP par MBE sur le substrat SrTi03 (001). L'intégration des semi-conducteurs III-V sur le Si, en utilisant la couche tampon d'oxyde SrTi03 est l'objet des intenses recherches, en raison des applications prometteuses dans le domaine de nano-optoélectronique. Les niveaux de coeur O1s, Sr3d, Ti2p, In3d, P2p ont été analysés et rapportés en fonction de l'angle azimutale à différents angles polaires. La comparaison des courbes XPD azimutales de Sr3d et In3d montre que les ilots InP sont orientées (001) avec la relation d'épitaxie; [110]InP(001 )/ / [100]! SrTi03 (001). La caractérisation morphologique par AFM montre des ilots InP facettés régulièrement dispersée à la surface<br>The main objective of this thesis is to study the chemical and physical properties at the surface or at the interface between thin layers by photoemission spectroscopy (XPS), photoelectron diffraction (XPD), and time resolved photoemission (PTR) . The experiments were conducted using an Alka source at INL or soft -X ray synchrotron radiation at Soleil, the French national Synchrotron facility. The first photoemission study has been performed on platinum deposited on thin Gd2(h layers grown by Molecular Bearn Epitaxy (MBE) on Si (111) substrate. The charge transfer between Pt and 0 at the interface causes a chemical shift to higher binding energies without changing the characteristic shape of the metal XPS peak. The XPD study shows that Pt is partially crystallized into two (111)-oriented do mains on Gd20 3 (111) with the in-plane epitaxial relationships [11 0] Pt (111) / / [11 0] Gd203 (111) and [101] Pt(111)/ / [11 0] Gd20 3 (111). In addition to bi-domains formation of platinum Pt (111) on Gd20 3 (111), a new ordered phase of platinum oxide Pt02 at the Pt/ Gd203 interface have been observed. The study of the background of the polar curves depending of the morphology has shown, that the film of Pt does not wet on the oxide, due to the low energy of interaction at the interface compared to the Pt thin layer. The second study has been interested to the photoemission time-resolved study of non-reactive metal / semiconductor model system. We have studied the thin layer gold (Au) growth on silicon (Si) substrate before and during annealing in TEMPO beam line (synchrotron Soleil).The XPS study, shows before annealing the formation of silicon native oxide on heterostructure at ambient temperature. The desorption of silicon oxide during annealing at low temperature induce photoemission intensity decreases with time. The desorption of oxide and alloy formation (AuSi) induce distribution of pits with cubic form at silicon surface due to gold etching activity. The third photoemission study has concerned thin films of a few layers of graphene obtained by solid-state graphitization from 6H-SiC (0001) substrates have been studied by X-ray photoelectron spectroscopy (XPS) and X-ray photoelectron diffraction (XPD). The Cls core-level has been resolved into components, which have been associated with carbon from bulk SiC, carbon from graphene and carbon at the interface graphene/ 6H-SiC (0001). Then, the intensity of each of these components has been recorded as a function of polar (azimuth) angle for several azimuth (polar) angles. These XPD measurements provide crystallographic information which clearly indicates that the graphene sheets are organized in graphite-like structure on 6H-SiC(0001), an organization that results of the shrinking of the 6H-SiC (0001) lattice after Si depletion. Finally the decoupling of graphene from 6H-SiC (0001) substrate by oxygen intercalation has been studied from the XPS point of view. Finally, photoemission study has concerned thin film of InP (phosphor indium ) islands grown by Molecular Bearn Epitaxy (MBE) on SrTi03 (001) bulk substrate have been investigated by X-ray photoelectron spectroscopy and diffraction (XPS/ XPD).Integration of III-V semi-conductor on silicon wafer, via SrTi03 buffer is currently the subject of intense research because of its potentially interesting applications in future nano-optoelectronics. The Ols, Sr3d, Ti2p, In3d, and P 2p core level area have been studied as function of azimuth angle for different polar angles. Comparison of the XPD azimuth curves of Sr3d and In3d shows that islands InP are oriented (001) with an in-plane epitaxial relationship [110] InP(001 ) // [100] SrTi03 (001). AFM images shows that InP islands are regularly dispersed on the surface. Their shape is a regularly facetted half-sphere
30
Hujsa, Thomas. "Contribution à l'étude des réseaux de Petri généralisés." Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066342/document.
Full textAbstract:
De nombreux systèmes réels et applications, tels que les ateliers flexibles et systèmes embarqués, sont formés de tâches communicantes et sont modélisables par des réseaux de Petri pondérés. Le comportement de ces systèmes peut être vérifié sur leur modèle dès la phase de conception afin d'éviter les simulations post-conception coûteuses. Ces systèmes doivent satisfaire trois propriétés : vivacité, capacité bornée et réversibilité. La vivacité préserve la possibilité d'exécuter chaque tâche. La capacité bornée assure une quantité limitée de ressources. La réversibilité évite une initialisation coûteuse et permet de réinitialiser le système. Les méthodes d'analyse de ces propriétés ont généralement une complexité exponentielle. Dans cette thèse, nous étudions plusieurs sous-classes expressives des réseaux de Petri pondérés, soient les classes Fork-Attribution, Choice-Free, Join-Free et Equal-Conflict, pour lesquelles nous développons les premiers algorithmes polynomiaux garantissant vivacité, capacité bornée et réversibilité. Premièrement, nous apportons des transformations polynomiales qui préservent de nombreuses propriétés des réseaux de Petri pondérés et facilitent l'étude de leur comportement. Deuxièmement, nous utilisons ces transformations pour obtenir plusieurs conditions polynomiales suffisantes de vivacité pour les sous-classes considérées. Enfin, ces transformations simplifient l'étude de la réversibilité sous hypothèse de vivacité. Nous donnons plusieurs caractérisations et conditions polynomiales suffisantes de réversibilité pour les sous-classes étudiées. Nos conditions passent à l'échelle et sont aisément implémentables dans les systèmes réels<br>Many real systems and applications, including flexible manufacturing systems and embedded systems, are composed of communicating tasks and may be modeled by weighted Petri nets. The behavior of these systems can be checked on their model early on at the design phase, thus avoiding costly simulations on the designed systems. Usually, the models should exhibit three basic properties: liveness, boundedness and reversibility.Liveness preserves the possibility of executing every task, while boundedness ensures that the operations can be performed with a bounded amount ofresources. Reversibility avoids a costly initialization phase and allows resets of the system.Most existing methods to analyse these properties have exponential time complexity.By focusing on several expressive subclasses of weighted Petri nets, namely Fork-Attribution, Choice-Free, Join-Free and Equal-Conflict nets,the first polynomial algorithms that ensure liveness, boundednessand reversibility for these classes have been developed in this thesis.First, we provide several polynomial time transformations that preserve structural andbehavioral properties of weighted Petri nets, while simplifying the study of their behavior.Second, we use these transformations to obtain several polynomial sufficient conditions of livenessfor the subclasses considered. Finally, the transformations also prove useful for the study of the reversibility propertyunder the liveness assumption. We provide several characterizations and polynomial sufficient conditionsof reversibility for the same subclasses. All our conditions are scalable and can be easily implemented in real systems
31
Faik, Taoufik. "La b-continuite des b-colorations : complexité, propriétés structurelles et algorithmes." Paris 11, 2005. http://www.theses.fr/2005PA112047.
Full textAbstract:
LA B-COLORATION D'UN GRAPHE G EST UNE COLORATION TELLE QUE POUR CHAQUE COULEUR c, IL EXISTE AU MOINS UN SOMMET v COLORE c DONT LE VOISINAGE EST COLORE PAR TOUTES LES AUTRES COULEURS. LE SOMMET v EST DIT UN SOMMET B-CHROMATIQUE. UNE F-COLORATION EST UNE B-COLORATION OU TOUS LES SOMMETS SONT B-CHROMATIQUEUNE COLORATION AVEC LE NOMBRE CHROMATIQUE EST UNE B-COLORATION, EN REVANCHE IL EXITE DES GRAPHES QUI N'ADMETTES AUCUNE F-COLORATIONS. CONTRAIREMENT A TOUTES LES AUTRES COLORATIONS, IL PEUT EXISTER UNE B-COLORATION D'UN GRAPHE AVEC p COULEURS ET UNE AUTRE AVEC q COULEURS (p<br>THE B-COLORING OF A GRAPH G IS A COLORING SUCH OF G SUCH THAT FOR EACH COLOR c, THERE EXISTS AT LEAST A VERTEX v (CALLED COLORFUL VERTEX) COLORED c HAVING EACH OTHER COLOR ON ITS NEIGHBORHOOD. AN F-COLORING IS A B-COLORING WHERE ALL THE VERTICES ARE COLORFUL. IT IS CLEAR THAT ANY COLORING WITH THE CHROMATIC NUMBER OF COLORS IS A B-COLORING. WHOEVER, THE F-COLORING DO NOT EXIST IN ANY GRAPH. ^ONE PECULIAR CHARACTERISTIC OF B-COLORINGS (RESP; F-COLORINGS) IS THAT FOR SOME GRAPHS, THERE EXISTS A p AND A q B-COLORING (RESP. F-COLORING) WITH p
32
Bader, El Dine Kamil. "Uterine synchronization analysis during pregnancy and labor using graph theory, classification based on machine learning." Thesis, Compiègne, 2022. http://www.theses.fr/2022COMP2680.
Full textAbstract:
L'objectif global de cette thèse est d'étudier le phénomène de la propagation de l'activité électrique utérine par une approche basée sur la théorie de graphe. La première étape dans cette thèse est de trouver de nouveaux paramètres extraits des graphes qui conviennent pour représenter les évolutions physio-pathologiques de l'utérus. Ces paramètres seront testés directement sur les signaux EHG enregistrés au niveau de l'abdomen puis au niveau des sources identifiées à partir des EHG. Cette analyse sera appliquée sur le signal EHG i) globalement (en utilisant toute la contraction) et ii) dynamiquement (en utilisant des fenêtres temporelles dans la contraction pour caractériser à chaque fois le graphe correspondant). La deuxième étape sera de développer une nouvelle méthode basée sur les réseaux de neurones et de l'appliquer sur tous les paramètres déjà utilisés afin de sélectionner les meilleurs paramètres qui peuvent différencier les contractions de grossesse et de travail. Les résultats attendus seront utilisés à la fois pour enrichir les connaissances scientifiques dans ce domaine et pour essayer d'améliorer les performances de la prédiction de la prématurité chez les femmes<br>The overall objective of this thesis is to study the phenomenon of the propagation of uterine electrical activity by a approach based on graph theory. The first step in this thesis is to find new parameters extracted from the graphs which are suitable to represent the physio-pathological evolutions of the uterus. These parameters will be tested directly on th EHG signals recorded at the level of the abdomen then at the level of the sources identified from the EHGs. This analysis will be applied to the EHG signal i) globally (using the entire contraction) and ii) dynamically (using time windows in the contraction to characterize each time the corresponding graph). The second step will be to develop a new method based on neural networks and apply it on all the parameters already used in order to select the best parameters that can differentiate pregnancy and labor contractions. The expected results will be used both to enrich scientific knowledge in this field and to try to improve the performance of the prediction of prematurity in women
33
Caniou, Yann. "Analyse de sensibilité globale pour les modèles de simulation imbriqués et multiéchelles." Phd thesis, Université Blaise Pascal - Clermont-Ferrand II, 2012. http://tel.archives-ouvertes.fr/tel-00864175.
Full textAbstract:
Cette thèse est une contribution à la modélisation imbriquée de systèmes complexes. Elle propose une méthodologie globale pour quantifier les incertitudes et leurs origines dans une chaîne de calcul formée par plusieurs modèles pouvant être reliés les uns aux autres de façon complexe. Ce travail est organisé selon trois axes. D'abord, la structure dedépendance des paramètres du modèle, induite par la modélisation imbriquée, est modélisée de façon rigoureuse grâce à la théorie des copules. Puis, deux méthodes d'analyse de sensibilité adaptées aux modèles à paramètres d'entrée corrélés sont présentées : l'une est basée sur l'analyse de la distribution de la réponse du modèle, l'autre sur la décomposition de la covariance. Enfin, un cadre de travail inspiré de la théorie des graphes est proposé pour la description de l'imbrication des modèles. La méthodologie proposée est appliquée à des exemples industriels d'envergure : un modèle multiéchelles de calcul des propriétés mécaniques du béton par une méthode d'homogénéisation et un modèle multiphysique de calcul de dommage sur la culasse d'un moteur diesel. Les résultats obtenus fournissent des indications importantes pour une amélioration significative de la performance d'une structure.
34
Zhao, Mali. "Electronic Properties of Graphene Functionalized with 2D Molecular Assemblies." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS013.
Full textAbstract:
Le graphène a des propriétés électroniques et mécaniques extraordinaires en raison de sa structure de bande linéaire. Toutefois, l'absence d’une bande interdite limite l’utilisation du graphène dans les dispositifs électroniques. Ajuster la bande interdite de graphène permettrait un contrôle précis des porteurs de charge. Une solution prometteuse consiste à modifier le graphène par des briques élémentaires de molécules organiques. Les molécules organiques avec un ion métallique (métal-porphyrine et métal-phtalocyanine) sont des candidats potentiels en raison de leur structure robuste et de leurs propriétés de charge et de spin qui peuvent être modulées. Dans cette thèse, le graphène a été préparé par la sublimation d’atomes de Si sur les faces de Si et de C- du substrat SiC. Trois molécules qui transportent l'information de spin différents ont été étudiés avec le STM. A travers des collaborateurs les calculs DFT, nous apporte des informations complémentaires. La première molécule utilisée dans notre expérience est la phtalocyanine de Ni (NiPc). L'ion Ni²⁺ a une configuration d'électrons 3d⁸ avec au état de spin de 0. La seconde molécule est la tétraphénylporphyrine de Pt (PtTPP (CO₂Me)₄). L'ion Pt²⁺ montre également une configuration d'électrons 3d8 à un état de spin de zéro. Cependant, l'atome Pt est plus lourd que celui du Ni. Promettant des effets spin orbite plus importants. La troisième molécule est tétraphénylporphyrine de fer (III) chlorure (FeTPPCl). Le Fe³⁺ est dans l'état haut spin (S = 5/2). Chacune de ces trois molécules forment un réseau moléculaire carré bien ordonné sur le graphène. Les directions de réseau moléculaires sont dominées par la symétrie du graphène, tandis que les orientations moléculaires dépendent des interactions inter moléculaires. Les couplages électroniques entre chaque molécule et le graphène sont transmis par la force de Van der Waals, qui donne lieu à des interfaces capacitifs entre la couche de graphène et les molécules. Les interactions électroniques entre les molécules FeTPP et graphène sont plus fortes que celles entre NiPc ou PtTPP et le graphène. Les études des molécules organiques avec adsorbées sur le graphène des spins différents a le potentiel d’ouvrir la voie à l'application de l'interface organométallique molécules/ graphène dans les dispositifs de spintronique<br>Graphene has extraordinary properties because of its linear band structure and zero band gap. However, the lack of a band gap hinders the implementation of graphene in electronics; tuning the band gap of graphene would enable a precise control of the charge carriers. One of the promising solutions is to modify graphene with organic molecular building blocks. Organic molecules with a metal ion (metal- porphyrin, metal- phthalocyanine) are potential candidates, because of their robust structure and the fact that their charge and spin properties can be tuned. In this thesis, graphene was prepared by sublimating Si atoms from both Si and C- terminated SiC substrates. Three molecules which carry different spin information were studied by STM experiments. Through collaborations, DFT calculations were used to improve our understanding of the molecule- graphene interaction.The first molecule used in our experiment is Ni- phthalocyanine (NiPc). The Ni²⁺ ion has a 3d⁸ electron configuration, giving a spin- state of 0. The second molecule is Pt- tetraphenylporphyrin (PtTPP(CO₂Me)₄). The Pt²⁺ ion also shows a d8 electron configuration with a spin state of zero. However, the Pt atom is heavier than Ni, which should increase the spin- orbit effects. The third molecule is tetraphenylporphyrin iron(III) chloride (Fe(TPP)Cl). The Fe³⁺ in Fe(TPP)Cl is stable in the high spin state (S=5/2). These three molecules each form well- ordered nearly square lattice molecular networks on graphene. The molecular lattice directions are dominated by the graphene symmetry, while the molecular orientations depend on the molecule- molecule interactions. The electronic couplings between each of three molecules and graphene are via the Van der Waals forces, which gives rise to the capacitive molecular- layer/ graphene interfaces. The electronic interactions between FeTPP molecules and graphene are stronger than those between NiPc or PtTPP molecules and graphene. The studies of the organic molecules with different spin information on the graphene has the potential to pave the way for the application of organometallic molecules/graphene interface in spintronic devices
35
Zhao, Shen. "Propriétés optiques de nanorubans et boites quantiques de graphène." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLN032/document.
Full textAbstract:
Ce manuscrit présente une étude expérimentale sur les propriétés optiques des nanorubans de graphène (acronyme anglais : GNRs) et des boites quantiques de graphène (acronyme anglais : GQDs) synthétisés par la chimie ascendante.Pour la partie sur les GNRs, les spectres d'absorption et de photoluminescence ainsi que les mesures de la durée de vie sur la dispersion impliquent la formation d'états excimères résultant de l'agrégation des GNRs. Au moyen de la microscopie confocale et de la microscopie à force atomique, nous observons l'émission de petits agrégats de GNRs confirmant leur capacité à émettre de la lumière à l'état solide. D'autre part, les caractérisations optiques des GNRs synthétisés sur une surface d’or présentent des caractéristiques de Raman remarquables, impliquant les propriétés vibrationnelles spécifiques des GNRs par rapport au graphène et aux nanotubes de carbone. La PL observée est spectralement large avec une énergie plus élevée que celle de la bande interdite des GNRs. Cela pourrait être lié aux défauts créés lors de la préparation de l'échantillon.Pour la partie sur les GQDs, les résultats de spectroscopie optique indiquent que les GQDs sont individualisées en dispersion plutôt que sous la forme d’agrégats. Ensuite, grâce à la microphotoluminescence, nous abordons directement les propriétés intrinsèques des GQDs uniques. Des mesures de corrélation de photons de second ordre révèlent que les GQDs présentent une émission de photons uniques avec une grande pureté. De plus, l'émission de GQD présente une bonne photo-stabilité avec une brillance élevée. Comme premier exemple de l'accordabilité optique des GQDs via le contrôle de la structure, nous observons que l'émission de GQDs fonctionalisés avec des atomes de chlore est décalée de près de 100 nm tout en maintenant une émission de photons uniques<br>This manuscript presents an experimental study on the optical properties of graphene nanoribbons (GNRs) and graphene quantum dots (GQDs) synthesized by bottom-up chemistry.For the part on GNRs, the optical absorption and photoluminescence spectra as well as the life-time measurements on the dispersion of solution-mediated synthesized GNRs implies the formation of excimer states as a result of aggregation of GNRs. By means of confocal fluorescence microscopy and atomic force microscopy, we observe the emission of small GNR aggregates confirming the ability of GNRs to emit light in the solid state. On the other hand, the optical characterizations of on-surface synthesized GNRs shows remarkable Raman features, implying the distinct vibrational properties of GNRs compared to graphene and carbon nanotubes. The observed PL is spectrally broad with higher energy instead of a bright bandgap emission, which might be related to the defects created during the sample preparation.For the part on GQDs, the optical spectroscopy results indicate that GQDs are individualized in dispersions rather than in the form of aggregates. Then by means of microphotoluminescence, we directly address the intrinsic properties of single GQDs. Second-order photon correlation measurements reveal that GQDs exhibit single-photon emission with a high purity. Notably, the emission of GQDs has good photo-stability with high brightness. As a first example of the optical tunability of GQDs through the control of their structure, we observe that the emission of single edge-chlorinated GQDs is redshifted by almost 100 nm while maintaining the single-photon emission
36
Schwarz, Cornelia. "Propriétés optomécaniques, vibrationelles et thermiques de membranes de graphène suspendues." Thesis, Université Grenoble Alpes (ComUE), 2016. http://www.theses.fr/2016GREAY024/document.
Full textAbstract:
Le but de la Nano- Opto- Mécanique et Electronic à base de graphène est d'utiliser des membranes de graphène en suspension comme blocs de construction pour aborder le couplage entre l'optique, la mécanique et l'électronique dans ce nouveau matériau. Avec un module d'Young similaire à celui du diamant (1 TPA), le graphène est une membrane extrêmement rigide, légère et mince (epaaisseur de seulement un atome) qui peut supporter son propre poids sans effondrement ou la rupture lorsqu'il est suspendu. Ces membranes, intégrées dans des dispositifs mécaniques, peuvent être actionnés à partir de DC jusqu'à des fréquences de vibration mécaniques très élevées (GHz). En outre, le graphène est un gaz d'électrons 2D exposé pour lequel une porte électrostatique tunes considérablement la densité de porteurs de charge et ses propriétés optiques. Last but not least, il offre une architecture unique pour effectuer la fonctionnalisation physico-chimiques et obtenir des matériaux hybrides combinant les propriétés particulières des espèces chimisorbées avec ceux du graphène<br>The aim of the Graphene Nano- Opto- Mechanics and Electronics is to use suspended graphene membranes as building blocks to address the coupling of optics, mechanics and electronics in this novel material. With a Young modulus similar to that of diamond (1 TPa), graphene is an extremely stiff, light and atomically thin membrane that can withstand its own weight without collapsing or breaking when suspended. Such membranes, integrated as mechanical devices, can be actuated from DC up to very high mechanical vibration frequencies (GHz). Moreover, graphene is an exposed 2D electron gas for which an electrostatic gate dramatically tunes the charge carrier density and its optical properties. Last but not least, it provides a unique architecture to perform physico-chemical functionalization and obtain hybrid materials combining the peculiar properties of adsorbed and chemisorbed species with the graphene ones
37
Arezki, Hakim. "Ingénierie des propriétés optoélectroniques du graphène." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLS095/document.
Full textAbstract:
Ce travail s’est articulé autour de la modulation des propriétés électroniques du graphène. Un des objectifs visés étant la conception d’électrodes transparentes pour des applications photovoltaïques. Différentes techniques de dopage ont été utilisées pour la modulation du travail de sortie (WF) et de la mobilité électronique comme l’incorporation d’azote in-situ lors de la croissance, l’incorporation d’azote ex-situ par acide nitrique et acide aurique. Diverses techniques de caractérisation ont été employées notamment la microscopie à force atomique AFM/CPAFM, la spectroscopie Raman, la spectroscopie photoélectronique (XPS et UPS), les mesures de transport électrique par effet Hall et effet de champ. Ces techniques nous ont permis de déterminer l’homogénéité, la qualité cristalline, la variation de densité de charges électronique, la résistance électrique et la mobilité électronique des différents matériaux intrinsèques et dopés. Par ailleurs, nous avons montré qu’il était possible de moduler le travail de sortie du graphène CVD en déposant par PECVD du silicium amorphe dopé N ou P sans endommager le graphène. Cette approche présente un intérêt particulier pour la substitution de l’ITO par le graphène en tant qu’électrode transparente. Les mesures de transport électronique ont mis en évidence un transfert de charges à l’interface de l’hétérojonction graphène/silicium amorphe. Cette variation dépend non seulement du type du dopage du silicium amorphe mais aussi de la cristallinité de ce dernier, ainsi peut-on espérer réduire la résistivité d’une électrode pour cellule photovoltaïque<br>This work was structured around the modulation of the electronic properties of graphene obtained via the CVD growth on copper substrate and/or the graphitization of the carbon atoms in the SiC substrate. One of the objectives was the design of electrodes (front or rear) for photovoltaic cells, among other applications. Different doping techniques have been implemented for modulating the work function (WF) and the electron mobility i.e. the incorporation of nitrogen in-situ during the growth, ex-situ incorporation by nitric acid and/or nano gold colloids (AuCl3). In this work, various characterization techniques were employed including atomic force microscopy (AFM), Raman spectroscopy, photoelectron spectroscopy (XPS and UPS), electrical transport measurements by Hall and field effect. These techniques have enabled us to determine the homogeneity , thecrystalline quality of the material, the carrier density, the electrical resistance and the electron mobility of different intrinsic and doped samples. Furthermore, we showed that it is possible to modulate the WF graphene by fabricating a heterostructure composed of PECVD amorphous silicon doped N or P deposited onto the graphene. This approach is of particular interest for replacement of ITO with graphene as transparent electrode. This result was confirmed by the study detailed spectra of the XPS and Raman vibrational states. The electronic transport measurements showed a charge transfer at the interface of the heterojunction graphene/amorphous silicon. The variation observed depends not only on the type of doping of the amorphous silicon but also on the crystallinity of the latter. This approach can readily be adapted to photovoltaic devices
38
Rotenberg, Elie. "Une approche pour l'estimation fiable des propriétés de la topologie de l'internet." Thesis, Paris 6, 2015. http://www.theses.fr/2015PA066005/document.
Full textAbstract:
Cette thèse propose une nouvelle approche pour estimer des propriétés de la topologie d’Internet. Contrairement aux approches historiques, qui se bases sur des données déclaratives très peu fiables, ou sur la lecture de cartes mesurées avec des outils de diagnostic, notre approche consiste à mettre au point des primitives de mesures très fiables, dont le fonctionnement, les hypothèses et les résultats sont bien définis formellement. Notre premier cas d’étude est celui de la distribution de degré de la topologie logique, ou L3. Nous utilisons l’outil traceroute dont nous étudions le fonctionnement, pour en déduire une primitive de mesure. Cette primitive de mesure, qui repose sur l’utilisation d’un ensemble de moniteurs distribué dans le réseau, permet d’obtenir une estimation du nombre de voisins dans la topologie logique, d’un routeur du cœur. Nous utilisons cette primitive vers un échantillon aléatoire de cibles, pour obtenir une estimation de la distribution de degré recherchée et établir les limites de cette approche. Notre deuxième cas d’étude est celui de la distribution de degré de la topologie physique, ou L2-L3. Nous utilisons l’outil UDP Ping, dont nous étudions le fonctionnement, pour en déduire une primitive de mesure. Elle est semblable à l’outil utilisé pour la topologie logique, mais repose sur des hypothèses bien plus clairement établies et vérifiées, et validée par des simulations très détaillées. Nous intégrons également au protocole de mesure, des garanties statistiques sur l’uniformité de l’échantillon de cibles, des routeurs du cœur, que nous mesurons. Nous obtenons une évaluation de la distribution de degré recherchée, d’une très grande fiabilité. Nous complétons ce cas d’étude par un travail complémentaire sur les tables de transmission des routeurs du cœur. Enfin, nous dressons un tableau assez large des perspectives qui s’ouvrent en se basant sur cette approche, par exemple en l’appliquant à d’autres types de réseaux (réseaux sociaux, etc.)<br>This thesis proposes a novel approach to reliably estimate properties of the Internet topology. Unlike historical approaches, based on declarative, hardly reliable data, or on readings from maps measured with diagnostic tools, our approach is to develop very reliable measure primitives, of which the operation, the hypotheses, and the results are well defined. Our first case study is the degree distribution of the logical topology, or L3. We use the traceroute tool, of which we study the operation, to derive a measurement primitive. This measurement primitive, which relies on using a distribution set of monitors over the network, allows us to get an estimation of the number of neighbors in L3 of a target core router. We use this primitive against a random sample of targets and obtain the sought distribution, and establish limits to this method. Our second case study is the degree distribution of the physical topology, or L2-L3. We use the UDP Ping tool, of which we study the operation, to derive a measurement primitive. It is alike the tool we used for the logical topology, but relies on much more clearly established and verified hypotheses, and is validated by very detailed simulations. We also include statistical guarantees of the sampling uniformity of the target core routers to the measurement protocol. We obtain an evaluation of the sought degree distribution, of an unprecedented reliability. We complete this case study by a complimentary study over the forwarding tables of the core routers. Finally, we picture the many perspectives opened by this approach, eg. By applying it to other types of networks (social networks, etc.)
39
Shah, Faaiz Hussain. "Gradual Pattern Extraction from Property Graphs." Thesis, Montpellier, 2019. http://www.theses.fr/2019MONTS025/document.
Full textAbstract:
Les bases de données orientées graphes (NoSQL par exemple) permettent de gérer des données dans lesquelles les liens sont importants et des requêtes complexes sur ces données à l’aide d’un environnement dédié offrant un stockage et des traitements spécifiquement destinés à la structure de graphe. Un graphe de propriété dans un environnement NoSQL est alors vu comme un graphe orienté étiqueté dans lequel les étiquettes des nœuds et les relations sont des ensembles d’attributs (propriétés) de la forme (clé:valeur). Cela facilite la représentation de données et de connaissances sous la forme de graphes. De nombreuses applications réelles de telles bases de données sont actuellement connues dans le monde des réseaux sociaux, mais aussi des systèmes de recommandation, de la détection de fraudes, du data-journalisme (pour les panama papers par exemple). De telles structures peuvent cependant être assimilées à des bases NoSQL semi-structurées dans lesquelles toutes les propriétés ne sont pas présentes partout, ce qui conduit à des valeurs non présentes de manière homogène, soit parce que la valeur n’est pas connue (l’âge d’une personne par exemple) ou parce qu’elle n’est pas applicable (l’année du service militaire d’une femme par exemple dans un pays et à une époque à laquelle les femmes ne le faisaient pas). Cela gêne alors les algorithmes d’extraction de connaissance qui ne sont pas tous robustes aux données manquantes. Des approches ont été proposées pour remplacer les données manquantes et permettre aux algorithmes d’être appliqués. Cependant,nous considérons que de telles approches ne sont pas satisfaisantes car elles introduisent un biais ou même des erreurs quand aucune valeur n’était applicable. Dans nos travaux, nous nous focalisons sur l’extraction de motifs graduels à partir de telles bases de données. Ces motifs permettent d’extraire automatiquement les informations corrélées. Une première contribution est alors de définir quels sont les motifs pouvant être extraits à partir de telles bases de données. Nous devons, dans un deuxième temps, étendre les travaux existant dans la littérature pour traiter les valeurs manquantes dans les bases de données graphe, comme décrit ci-dessus. L’application de telles méthodes est alors rendue difficile car les propriétés classiquement appliquées en fouille de données (anti-monotonie) ne sont plus valides. Nous proposons donc une nouvelle approche qui est testée sur des données réelles et synthétiques. Une première forme de motif est extrait à partir des propriétés des nœuds et est étendue pour prendre en compte les relations entre nœuds. Enfin, notre approche est étendue au cas des motifs graduels flous afin de mieux prendre en compte la nature imprécise des connaissances présentes et à extraire. Les expérimentations sur des bases synthétiques ont été menées grâce au développement d’un générateur de bases de données de graphes de propriétés synthétiques. Nous en montrons les résultats en termes de temps calcul et consommation mémoire ainsi qu’en nombre de motifs générés<br>Graph databases (NoSQL oriented graph databases) provide the ability to manage highly connected data and complex database queries along with the native graph-storage and processing. A property graph in a NoSQL graph engine is a labeled directed graph composed of nodes connected through relationships with a set of attributes or properties in the form of (key:value) pairs. It facilitates to represent the data and knowledge that are in form of graphs. Practical applications of graph database systems have been seen in social networks, recommendation systems, fraud detection, and data journalism, as in the case for panama papers. Often, we face the issue of missing data in such kind of systems. In particular, these semi-structured NoSQL databases lead to a situation where some attributes (properties) are filled-in while other ones are not available, either because they exist but are missing (for instance the age of a person that is unknown) or because they are not applicable for a particular case (for instance the year of military service for a girl in countries where it is mandatory only for boys). Therefore, some keys can be provided for some nodes and not for other ones. In such a scenario, when we want to extract knowledge from these new generation database systems, we face the problem of missing data that arise need for analyzing them. Some approaches have been proposed to replace missing values so as to be able to apply data mining techniques. However, we argue that it is not relevant to consider such approaches so as not to introduce biases or errors. In our work, we focus on the extraction of gradual patterns from property graphs that provide end-users with tools for mining correlations in the data when there exist missing values. Our approach requires first to define gradual patterns in the context of NoSQL property graph and then to extend existing algorithms so as to treat the missing values, because anti-monotonicity of the support can not be considered anymore in a simple manner. Thus, we introduce a novel approach for mining gradual patterns in the presence of missing values and we test it on real and synthetic data. Further to this work, we present our approach for mining such graphs in order to extract frequent gradual patterns in the form of ``the more/less $A_1$,..., the more/less $A_n$" where $A_i$ are information from the graph, should it be from the nodes or from the relationships. In order to retrieve more valuable patterns, we consider fuzzy gradual patterns in the form of ``The more/less the A_1 is F_1,...,the more/less the A_n is F_n" where A_i are attributes retrieved from the graph nodes or relationships and F_i are fuzzy descriptions. For this purpose, we introduce the definitions of such concepts, the corresponding method for extracting the patterns, and the experiments that we have led on synthetic graphs using a graph generator. We show the results in terms of time utilization, memory consumption and the number of patterns being generated
40
Feldner, Hélène. "Propriétés magnétiques de systèmes à deux dimensions : système frustré de spins sur réseau carré et propriétés magnétiques de systèmes finis de graphènes." Strasbourg, 2011. http://www.theses.fr/2011STRA6180.
Full textAbstract:
L’objet de cette thèse est l’étude des propriétés magnétiques de deux systèmes bidimensionels. Le premier correspond à des composés de cuprate ou vanadate qui peuvent être modélisés par un système de spins sur réseau carré et un modèle d’Heisenberg à trois couplages, avec un premier couplage ferromagnétique et des couplages deuxièmes et troisièmes voisins antiferromagnétiques. Le système ainsi obtenu constitue un système frustré. Après obtention du diagramme de phase classique en fonction des couplages, nous avons étudié l’effet sur celui-ci des fluctuations quantiques par la méthode des bosons de Holstein-Primakov et celle des bosons de Schwinger. Le deuxième type de système auquel nous nous sommes intéressés sont les systèmes finis de graphène. Pour étudier ce matériau, nous avons utilisé une approximation champ moyen du modèle d’Hubbard. Dans un premier temps nous avons retrouvé des résultats déjà connus confirmant ainsi une implémentation correcte de notre modèle. Nous avons ensuite cherché à établir la précision de cette méthode en comparant les résultats obtenus par cette méthode avec ceux obtenus par diagonalisation exacte du modèle et ceux obtenus par simulation Monte Carlo. Et en dernier lieu nous avons mis en évidence une signature dynamique de l'aimantation des bords en zigzag des systèmes finis de graphène<br>This thesis is about the magnetic properties of two different two dimensional systems. The first one corresponds to vanadates or cuprate crystals, which can be studied by a spin system on square lattice and a Heisenberg model with three couplings, a ferromagnetic first neighbor coupling and antiferromagnetic second and third neighbor couplings. This system is frustrated and lead to a non trivial classical phase diagram. We have studied the influence of quantum fluctuation using a Holstein-Primakov approach and the Schwinger bosons model. The second system studied corresponds to graphene of finite size. To study this system we use a mean field approximation of the Hubbard model. In a first step we recover within our method well known results and check that the model has been correctly implemented. In a second step, in order to assess the accuracy of this method, we perform complementary exact diagonalization calculations, and compare our results with quantum Monte Carlo simulations. And in the last part we will show evidence of a dynamical signature of the zigzag edge magnetization of finite sample of graphene
41
Forbes, Florence. "Modèles markoviens de ressources partagées." Phd thesis, Université Joseph Fourier (Grenoble), 1996. http://tel.archives-ouvertes.fr/tel-00004991.
Full textAbstract:
Selon les domaines d'applications, différentes façons de modéliser le partage de ressources ont été envisagées. Un des premiers modèles apparus est issu du "Dining Philosophers Problem" de Dijkstra, généralisé par la suite par Chandy et Misra à travers le "Drinking Philosophers Problem". Nous nous intéressons à des versions markoviennes de ces situations, dans lesquelles les durées pour la prise et l'utilisation des ressources sont aléatoires. L'évaluation puis l'optimisation des performances des systèmes de ressources partagées nous conduit à étudier l'équilibre de ces modèles. Cette étude s'inscrit dans le contexte des propriétés de Markov des champs aléatoires sur les graphes dont nous présentons quelques résultats généraux. Nous utilisons également le formalisme des systèmes de particules. Nous introduisons une nouvelle classe de modèles markoviens de ressources partagées pour lesquels nous généralisons des outils classiques. Nous présentons des résultats de réversibilité et envisageons des techniques de comparaison stochastique. Pour des systèmes finis, nous donnons quelques calculs explicites de mesures d'équilibre. Des systèmes qui augmentent en taille et en complexité peuvent être approchés par des systèmes infinis. Pour des systèmes sur des graphes infinis construits à partir d'un arbre, nous mettons en évidence des phénomenes de transition de phase.
42
Marceau, Jean-François. "Propriété de maintien des facteurs communs dans le cas An." Mémoire, Université de Sherbrooke, 2016. http://hdl.handle.net/11143/9712.
Full textAbstract:
L'objectif de ce mémoire est de fournir une nouvelle preuve pour la "Non-leaving face
property" dans le cas An à l'aide de l'approximation dans les catégories amassées. Cette
preuve ouvre la porte pour une généralisation pour d'autres cas.
43
Achir, Ali. "Contribution à l’étude de la propriété de platitude sur des modèles Bond Graphs non linéaires." Ecole Centrale de Lille, 2005. http://www.theses.fr/2005ECLI0005.
Full textAbstract:
Cette thèse a pour but l'étude de la propriété de platitude sur des modèles bond graphs (BGs) non linéaires et de contribuer à la résolution des problèmes rencontrés en pratique qui sont liés principalement à l'identification des sorties plates et le calcul de la paramétrisation différentielle. Pour atteindre cet objectif, de nouveaux concepts et outils graphiques ont été introduits. En particulier, grâce à l'introduction de la notion de modèle BG tangent ou variationnel à l'aide de l'utilisation des différentielles de Kähler, il est possible de calculer les sorties plates d'un modèle BG non linéaire par intégration des bases du module qui lui est associé. Par ailleurs, en définissant la notion d'anneau BG non commutatif, une nouvelle règle de gain connue sous le nom de "règle de Riegle" est introduite en BG. En montrant alors qu'un modèle BG variationnel est un cas particulier d'anneau BG non commutatif, l'obtention graphique de la paramétrisation différentielle en utilisant la règle de Riegle et la notion de bicausalité est rendue possible. Enfin, pour aller plus loin dans l'introduction de l'outil d'algèbre et de modules différentiels aux BGs, le cas des modèles BGs non linéaires régis par des équations différentielles polynômiales a été abordé. Dans ce contexte, le BG permet de faire une analyse directe des propriétés principales du système telles que le choix des variables d’entrée, les dynamiques correspondant à un choix d’entrée, le calcul des degrés de transcendance (non différentiel) différentiel, etc. à partir de son modèle BG associé. Il est également montré que la règle graphique de Riegle peut être étendue à cette classe de modèles BGs<br>This PHD thesis aims to study the differential flatness property on non-linear bond graph models (BGs) and to contribute to the resolution of the two principal problems encountered in practice, mainly the problems of flat outputs identification and differential parameterisation. In order to reach this objective, new concepts and graphical tools are introduced. Particularly, thanks to the use of the Kähler differentials, the notion of tangent or variationnel BG (VBG) model is defined. A BG method based on the use of the BGV model enables identifying the bases of the differential module associated with the VBG model, which become the flat outputs of the original non-linear system after integration. Besides, by defining the notion of non-commutative ring BGs, a new gain rule known as Riegle’s gain formula is extended to BGs. Then, by considering a VBG model as a particular case of non-commutative ring BGs, the problem of differential parameterisation is then solved using Riegle’s gain formula and the concept of bicausality. Finally, in order to introduce further concepts of differential algebra and modules theory to the BG methodology, the case of non-linear BG models governed by polynomial differential equations is approached. In this context, the BG allows to conduct a direct analysis of the main properties of the system from its associated BG model, such as the choices of inputs, the dynamics corresponding to these choices, the calculation of differential (non-differential) transcendence degrees, etc. . . It is also shown that Riegle's gain rule can be extended to this class of BGs models
44
Arbelot, Benoit. "Transferts d'apparence en espace image basés sur des propriétés texturelles." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM018/document.
Full textAbstract:
Les techniques de manipulation de l'apparence d'une image sont très utilisées dans de nombreux domaines comme la photographie, la biologie, l'astronomie ou le spectacle vivant. L'apparence d'une image dépend de ses couleurs et textures, mais aussi des informations 3D perçues comme les formes, les matériaux et l'éclairage. Ces caractéristiques créent aussi une atmosphère et une émotion spécifique à l'image, qui fait aussi partie de son apparence. Le but des techniques de manipulation en espace image est de modifier les couleurs et les textures pour modifier les formes, matériaux et illumination perçus, et de là éventuellement modifier l'atmosphère de l'image.Les méthodes de transfert d'apparence sont une classe spécifique de techniques de manipulation visant à rendre le processus plus intuitif en calculant automatiquement la modification à apporter à l'image. Pour ce faire, elles se basent sur une image supplémentaire fournie par l'utilisateur et représentant l'apparence désirée.Dans cette thèse, nous étudions le transfert d'apparence en espace image basé sur des propriétés texturelles. Les textures étant une partie intégrante de l'apparence, guider les transferts d'apparence par de l'information texturelle est une option attrayante. Nous présentons d'abord une technique de filtrage de descripteurs de texture pour mieux préserver les structures de l'image et les transitions entre textures. Nous utilisons ensuite ce filtrage couplé à différents descripteurs de texture pour effectuer un transfert de couleur, une colorisation et un transfert de texture localement, guidés par la texture<br>Image-space appearance manipulation techniques are widely used in various domains such as photography, biology, astronomy or performing arts. An image appearance depends on the image colors and texture, but also the perceived 3D informations such as shapes, materials and illumination. These characteristics also create a specific look and feel for the image, which is also part of the image appearance. The goal of image-space manipulation techniques is to modify colors and textures as a mean to alter perceived shapes, illumination, materials, and from this possibly alter the image look and feel.Appearance transfer methods are a specific type of manipulation techniques aiming to make the process more intuitive by automatically computing the image modification. In order to do so, they use an additional user-provided image depicting the desired appearance.In this thesis, we study image-space appearance transfer based on textural properties. Since textures are an integral part of the image appearance, guiding appearance transfers with textural information is an attractive approach. We first present a texture descriptor filtering framework to better preserve image edges and texture transitions in the texture analysis. We then use this framework coupled with different texture descriptors in order to apply local texture guided color transfer, colorization and texture transfer
45
Raymond, Jean-Florent. "Structural and algorithmic aspects of partial orderings of graphs." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT289.
Full textAbstract:
Le thème central à cette thèse est l'étude des propriétés des classes de graphes définies par sous-structures interdites et leurs applications.La première direction que nous suivons a trait aux beaux ordres. À l'aide de théorèmes de décomposition dans les classes de graphes interdisant une sous-structure, nous identifions celles qui sont bellement-ordonnées. Les ordres et sous-structures considérés sont ceux associés aux notions de contraction et mineur induit. Ensuite, toujours en considérant des classes de graphes définies par sous-structures interdites, nous obtenons des bornes sur des invariants comme le degré, la largeur arborescente, la tree-cut width et un nouvel invariant généralisant la maille.La troisième direction est l'étude des relations entre les invariants combinatoires liés aux problèmes de packing et de couverture de graphes. Dans cette direction, nous établissons de nouvelles relations entre ces invariants pour certaines classes de graphes. Nous présentons également des applications algorithmiques de ces résultats<br>The central theme of this thesis is the study of the properties of the classes of graphs defined by forbidden substructures and their applications.The first direction that we follow concerns well-quasi-orders. Using decomposition theorems on graph classes forbidding one substructure, we identify those that are well-quasi-ordered. The orders and substructures that we consider are those related to the notions of contraction and induced minor.Then, still considering classes of graphs defined by forbidden substructures, we obtain bounds on invariants such as degree, treewidth, tree-cut width, and a new invariant generalizing the girth.The third direction is the study of the links between the combinatorial invariants related to problems of packing and covering of graphs. In this direction, we establish new connections between these invariants for some classes of graphs. We also present algorithmic applications of the results
46
Leszczynski, Przemyslaw. "Propriétés optiques et magnéto-optiques de systèmes électroniques purement bidimensionnels graphène." Thesis, Grenoble, 2014. http://www.theses.fr/2014GRENY002/document.
Full textAbstract:
Malgré l'attention massive que le graphène a attiré ces dernières années, beaucoup de questions concernant ses propriétés fondamentales restent sans réponse. Dans ce travail, nous présentons les résultats d'une série d'expériences de magnéto-optique effectuées sur des systèmes de type graphène différents. La spectroscopie de diffusion micro-Raman a été utilisée comme une méthode de choix, en raison de son caractère non invasif, des puissantes possibilités de caractérisation qu’elle offre, et de la haute résolution spatiale. Les champs magnétiques élevés ont aussi été utilisés pour permettre d’ajuster de manière continue l'énergie des excitations électroniques inter-niveau de Landau et de les amener en résonance avec d'autres excitations existant dans le système. L’étude de l'évolution des excitations inter-niveau de Landau sous champs magnétique et les détails de la résonance magnéto-phonon, nous ont fourni des informations importantes sur les détails de l'interaction électron-phonon dans le graphène. Trois types de graphène différents sont étudiés dans ce manuscrit. Le premier se compose de flocons de graphène qui peuvent être trouvés sur la surface de graphite. Il est peut-être le système de graphène le moins étudié, mais est celui qui présente la qualité électronique la plus élevé. Dans le chapitre 7, nous présentons les résultats de nos expériences de diffusion magnéto-Raman sur ce système. Notre méthode de localisation de ces flocons à l'aide ou non d'un champ magnétique est présenté. L'évolution des excitations électroniques dans des champs magnétiques est discutée. Les effets de la température, la longueur d'onde d'excitation et de couplage différent sur le substrat sont présentés. Nous démontrons que, pour des champs magnétiques élevés une structure fine des principales excitations électroniques inter-bande se développe, et est discutée en termes de dopage et d’asymétrie électron-trou. Un nouveau type de résonance électron-phonon est observée, qui implique une diffusion inter-vallée des porteurs et l’émission d'un phonon au point K. Un procédé analogue pour les phonons du voisinage du point Γ est observé. Le deuxième système étudié est constitué d'un flocon de graphène encapsulé entre deux couches de nitrure de bore hexagonal (hBN) plat à l’échelle atomique. Il est le représentant d'une nouvelle classe de matériaux, où les différents cristaux 2D, sont empilés les uns sur les autres dans un ordre prédéfini, pour modifier certaines propriétés de ses constituants. Déposer le graphène sur une mince couche de hBN améliore largement ses propriétés électroniques, en comparaison à du graphène déposée sur Si/SiO2. Dans le chapitre 8, nous présentons des résultats obtenus sur ce système. Nous montrons comment la cartographie spatiale associée à la technique de spectroscopie Raman peut être utilisé pour la caractérisation et la visualisation sélective des composants individuels et des structures complexes empilés. La première observation non ambiguë de la résonance magnéto-phonon et d’une excitation électronique (L -1,1) dans du graphene exfolié neutre est présentée. Une dépendance de la vitesse de Fermi par rapport au champ magnétique est démontrée. En outre, la dépendance de la vitesse de Fermi et d’énergie de bande 2D sur le substrat est observée et discutée en termes de d’écrantage diélectrique de l'interaction électron-électron.Le dernier système étudié sont des flocons de graphène produit par croissance CVD, avec des contacts électriques. Dans le chapitre 9, nous détaillons les résultats d'une expérience, où la force de l'interaction électron-phonon dans un échantillon de graphène avec une grille électrostatique, peut être ajustée, avec succès, par la tension de grille appliquée. Nous comparons ces résultats avec les calculs théoriques et nous montrons que les excitations électroniques intra-bande jouent un rôle important dans la renormalisation de l'énergie des phonons<br>Despite the massive attention that graphene has attracted in recent years, there are still many unanswered questions about its fundamental properties. In this work we present the results of a series of magneto-optical experiments performed on different graphene systems. The micro-Raman scattering spectroscopy was used as our method of choice, due to its non-invasive character, powerful characterization possibilities and high spatial resolution. The high magnetic fields were used to continuously tune the energy of inter-Landau level electronic excitations into a resonance with other excitations existing in the system. The magnetic field evolution of Raman active inter-Landau level excitations, and the details of the magneto-phonon resonance, gave us important information about the details of the electron-phonon interaction in graphene. Three different types of graphene are studied in this work. The first one consists of graphene flakes that can be found on the surface of graphite. It is possibly the least investigated graphene system, yet the one that shows the highest electronic quality. In Chapter 7 we present results of our magneto-Raman scattering experiments on this system. Our method for locating these flakes with the use of the magnetic field and without it is presented. The evolution of electronic excitations in magnetic fields is discussed. The effects of temperature, excitation wavelength and different coupling to the substrate are shown. We demonstrate that at high magnetic fields a fine-structure of the principal interband electronic excitation develops and discuss it in terms of doping and electron-hole asymmetry. A new type of a resonant electron-phonon interaction is observed, which involve an inter-valley carrier scattering and an emission of a K-point phonon. An analogous process for the phonons from the vicinity of the Γ point is observed.The second studied system consists of a graphene flake encapsulated between two layers of atomically flat hexagonal boron nitride (hBN). It is a representative of a novel class of materials, where different 2D crystals, are stacked on top of each other in a predefined order, to modify some properties of its constituents. Depositing graphene on a thin layer of hBN is expected to largely improve its electronic properties, as compared to graphene deposited on Si/SiO2. In Chapter 8 we present results obtained on such system. We show how spatial mapping with Raman scattering technique can be used for characterization and selective visualization of each constituent of the complex, stacked structures. A first, clear observation of a magneto-phonon resonance and L(-1,1) electronic excitation in an intrinsic, exfoliated graphene is shown. The Fermi velocity dependence on the magnetic field is demonstrated. Also, the Fermi velocity and 2D band energy dependence on the substrate is observed and discussed in terms of dielectric screening of the electron-electron interaction.The last studied system is the CVD grown graphene flake with electrical contacts. In Chapter 9 we show the results of an experiment, where strength of the electron-phonon interaction in a gated, CVD grown, graphene was successfully tuned by the applied gate voltage. We compare these results with the theoretical calculations and show that the intra-band electronic excitations play an important role in the renormalization of the phonon energy
47
Noël, Amélie. "Electrical properties of film-forming polymer/graphene nanocomposites : Elaboration through latex route and characterization." Thesis, Saint-Etienne, EMSE, 2014. http://www.theses.fr/2014EMSE0767/document.
Full textAbstract:
Les dispersions de nanocomposite à base aqueuse sont produites pour des applications diverses telles que les adhésifs, les revêtements et plus récemment les encres. Ce projet consiste à réaliser des encres conductrices nanocomposites comprenant des particules de polymère (latex) à basse température de transition vitreuse, Tg, pour la formation de films à température ambiante, et des plaquettes de graphène, en raison de leurs excellentes propriétés conductrices. Les charges conductrices, appelées multi-feuillets de graphène, sont réalisées par broyage en voie aqueuse de graphite (1-10 µm) stabilisées par différents tensio-actifs et/ou stabilisants. Cette méthode sans solvant et à bas coût permet de produire des suspensions de multi-feuillets (1-10 feuillets) de graphène. Les particules de polymères utilisées sont synthétisées par polymérisation en émulsion de monomères acrylates. Dans un second temps, des mélanges physiques de suspensions de graphène et de latex acrylates ont permis d’obtenir des encres nanocomposites. L’ajout de graphène permet l’obtention d’un seuil de percolation à bas taux de charge et une nette amélioration des propriétés électriques et du renfort. Le diamètre des billes de latex a une influence importante sur ces propriétés et a également été étudié. Afin d’augmenter la stabilité des suspensions et les interactions graphène/latex, des nanocomposites structurés ont été synthétisés par polymérisation in situ en émulsion, miniemulsion ou dispersion en présence de graphène. Les excellentes propriétés électriques associées à leur flexibilité font de ces matériaux des candidats adaptés pour la réalisation d’encres conductrices pour impression sur textile<br>Printed electronics, particularly on flexible and textile substrates, raised a strong interest during the past decades. This project presents a procedure that provides a complete and consistent candidate for conductive inks based on a graphene/polymer nanocomposite material. It consists in the synthesis of conductive inks nanocomposites comprising polymer particles (latex) with low glass transition temperature, Tg, and graphene platelets, for the conductive properties. The conductive particles, named Nanosize Multilayered Graphene (NMG), are prepared by wet grinding delamination of micro-graphite suspensions stabilized by various surfactants and/or polymeric stabilizers. This solvent-free procedure allows the formation of NMG suspensions with low thickness (1-10 sheets). Polymer particles are synthetized by surfactant-free emulsion polymerization with acrylates monomers.Physical blending of latex particles and NMG platelets are performed to obtain conductive nanocomposites inks. Adding NMG induce a low percolation threshold and a sharp increase of the electrical and mechanical properties of the nanocomposites. Moreover, the polymer particles diameters have an impact on these properties.To increase the formation of a well-defined cellular microstructure, the nanocomposites are also synthetized by in situ polymerization in presence of NMG platelets, using emulsion, miniemulsion or dispersion polymerization. The excellent electrical properties of these nanocomposites associated to their flexibility make these materials suitable candidates for the production of conductive inks for textile printing applications
48
Poumirol, Jean-Marie. "Etude des propriétés électroniques du graphène et des matériaux à base de graphène sous champs magnétiques intenses." Thesis, Toulouse, INSA, 2011. http://www.theses.fr/2011ISAT0012/document.
Full textAbstract:
Cette thèse présente des mesures de transport électronique dans des systèmes bi-dimensionels et uni-dimensionels à base de graphène sous champ magnétique pulsé (60T). L'objectif de ces travaux consiste à sonder la dynamique des porteurs de charge en modifiant la densité d'états du système par l'application d'un champ magnétique. Une première partie est consacrée à l'étude de l'influence des îlots électrons-trous sur les propriétés de transport du graphène au voisinage du point de neutralité de charge. Nous avons constaté l'apparition de fluctuations de la magnéto-résistance liée à la transition progressive des îlots de taille finie dans le régime quantique lorsque le champ magnétique augmente. Nous avons aussi montré que la variation de l'énergie de Fermi, liée à l'augmentation de la dégénérescence orbitale des niveaux de Landau, est directement responsable d'une modification du ratio entre électrons et trous. Dans une deuxième partie consacrée à l'étude des nanorubans de graphène, nous avons exploré deux gammes de largeur différentes. Dans les rubans larges (W>60nm), la quantification de la résistance a été observée révélant ainsi une signature évidente de la quantification du spectre énergétique en niveaux de Landau. Le confinement magnétique des porteurs de charge sur les bords des nanorubans a permis de mettre en évidence, pour la première fois, la levée de dégénérescence de vallée liée à la configuration armchair du ruban. Pour des rubans plus étroits (W<30nm), en présence de défauts de bord et d'impuretés chargées, la formation progressive des états de bords chiraux donne lieu à une magnéto-conductance positive quelque soit la densité de porteurs. Enfin, la dernière partie traite du magnéto-transport dans le graphene multi-feuillet. En particulier, nous avons observé l'effet Hall quantique dans les systèmes tri-couche de graphène. Une étude comparative des résultats expérimentaux avec des simulations numériques a permis de déterminer l'empilement rhombohedral des trois couches de graphene constituant l'échantillon<br>This thesis presents transport measurements on two-dimensional and one-dimensional graphene-based systems under pulsed magnetic field (60T). The objective of this work is to probe the dynamics of charge carriers by changing the density of states of the system by applying a strong magnetic field. The first part is devoted to the study of the influence of electron-hole pockets on the transport properties of graphene near the charge neutrality point. We found the appearance of fluctuations in the magneto-resistance due to the progressive transition of the electron/hole puddles of finite size in the quantum regime as the magnetic field increases. We have also shown that the variation of the Fermi energy, due to the increase of orbital Landau level degeneracy, is directly responsible of a change in the electron and hole ratio. The second part is devoted to the study of graphene nano-ribbons, we explored two different ranges of width. In the broad nano-ribbons of width W larger than 60 nm, the quantification of the resistance is observed, revealing a clear signature of the quantization of the energy spectrum into Landau levels. We show for the first time the effect of valley degeneracy lifting induced by the magnetic confinement of charge carriers at the edges of the armchair nano-ribbons. For narrower nano-ribbons (W <30 nm) in presence of edge defects and charged impurities, the progressive formation of chiral edge states leads to a positive magneto-conductance whatever the carrier density. Finally, the last part of this thesis deals with magneto-transport fingerprints in multi-layer graphene as we observed the quantum Hall effect in tri-layer graphene. A comparative study of the experimental results with numerical simulations was used to determine the rhombohedral stacking of three layers of graphene in the sample
49
Cadic, Emmanuel. "Construction de Turbo Codes courts possédant de bonnes propriétés de distance minimale." Limoges, 2003. http://aurore.unilim.fr/theses/nxfile/default/2c131fa5-a15a-4726-8d49-663621bd2daf/blobholder:0/2003LIMO0018.pdf.
Full textAbstract:
L'objectif de cette thèse est de réaliser des turbo codes possédant de bonnes distances minimales et de contribuer ainsi à repousser le phénomène ``d'error floor'' qui correspond à un seuil de l'ordre de 10-6 pour le taux d'erreur résiduelles binaires en dessous duquel la pente de la courbe de TEB diminue de façon significative. Ce problème s'est sensiblement amélioré avec l'apparition des codes duo-binaires de Berrou [11] qui permettent notamment d'obtenir de meilleures distances minimales. Pour obtenir de bonnes distances minimales avec des turbo codes courts (longueur inférieure à 512), la construction initialement utilisée et étudiée dans cette thèse a été celle proposée par Carlach et Vervoux [26] qui permet d'obtenir d'excellentes distances minimales mais qui malheureusement s'avère moins performante en terme de décodage notamment pour des raisons propres à la structure. Après avoir identifié les raisons qui empêchent un décodage efficace de cette famille de codes, nous faisons évoluer ces codes en utilisant des structures graphiques différentes reposant toujours sur l'assemblage de codes composants de petite complexité. L'idée est de réaliser ce changement sans pour autant perdre les qualités de distance minimale de ces codes et par conséquent il est nécessaire de comprendre pourquoi les distances minimales de cette famille initiale de codes sont bonnes et de définir un critère de choix pour les codes composants. Le critère de choix ne dépend pas de la distance minimale des codes composants mais du polynôme de transition de ces codes et permet donc de sélectionner des codes composants de très faible complexité qui sont assemblés de façon à générer des treillis cycliques à seulement 4 états. Ces treillis sont alors utilisés pour élaborer des turbo codes parallèle ou série présentant de bonnes distances minimales. Certains codes auto-duaux extrémaux sont notamment construits ainsi<br>This thesis is aimed at building turbo codes with good minimum distances and delaying the``error-floor'' which corespond to a threshold of 10-6 for the binary error rate. Under this threshold, the slope of the curve decreases significantly. This problem is alleviated by the use of duo-binary turbo codes [11] which guarantee better minimum distances. In order to obtain good minimum distances with short turbo codes (length inferior to 512), the first construction used and studied is the one proposed by Carlach and Vervoux [26]. It allows to obtain very good minimum distances but its decoding is unfortunately very difficult because of its structure. After identifying the reasons for this problem, we have modified these codes by using some graphicals structures which are the gathering of low complexity components codes. The idea is to realize this change without loosing the minimum distances properties, and consequently we had to understand why minimum distances are good for this familly of codes and define a new criteria to choose ``good'' components codes. This criteria is independent from the minimum distance of the component codes because it is derived from the Input-Output Weight Enumerator (IOWE) of the components codes. It allows us to choose components codes with very low complexity which are combined in order to provide 4-state tail-biting trellises. These trellises are then used to build multiple parallel concatenated and serial turbo codes with good minimum distances. Some extremal self-dual codes have been built in that way
50
Godel, Florian. "Le graphène comme barrière tunnel : propriétés d'injection de charges et de spin." Thesis, Strasbourg, 2015. http://www.theses.fr/2015STRAE029/document.
Full textAbstract:
Mes travaux de thèse portent sur la fabrication et la caractérisation électrique et magnétique de jonctions tunnel à base de graphène. C’est autour de l’idée d’apporter une meilleur compréhension des mécanismes d’injection et de détection d’un courant de charge et de spin aux interfaces graphène/ferromagnétique que s’articule ce manuscrit. Après avoir démontré qu’il est possible de faire croître de manière épitaxiée une barrière tunnel de MgO sur graphène, nous avons étudié les mécanismes de transport dépendant en spin dans des jonctions verticales de Co/MgO/Gr/Ni. Nous avons mis en évidence l’interaction du graphène avec l’électrode de nickel à travers les inversions de signe de la magnétorésistance. Celles-ci peuvent être expliquées à l’aide d’un modèle de canaux de conduction assistés par phonons. Enfin du blocage de Coulomb reproductible a été mesuré dans des amas d’aluminium potentiellement mono disperses et auto assemblés sur graphène<br>My PhD thesis deals with the fabrication and the electric and magnetic characterizations of magnetic tunnel junctions based on graphene. The interaction of graphene with its close environment opens new possibilities for spintronics applications. The manuscript is focused on the improvement of the understanding of mechanisms involved in the injection and detection of a polarized spin current at the graphene/ferromagnetic interfaces. We show that it is possible to grow epitaxially MgO tunnel barrier on graphene. We study the spin transport mechanisms in vertical junctions of Co/MgO/Gr/Ni. The interaction of graphene with nickel electrode is probed through tunnel magnetoresistance inversions which can be explained by the activation of phonon assisted conduction channel. We also measure in vertical and lateral devices based on alumina barrier on graphene, reproducible Coulomb blockade processes linked to the presence of monodisperse aluminum clusters at the graphene edge