Seja K um conjunto de Cantor. Neste trabalho apresentamos dois teoremas relacionados a densidade do conjunto das dinâmicas simbólicas. No caso de endomorfismos provamos que, dado uma dinâmica T : K K, existe uma T : K K próxima a T, tal que toda órbita é finalmente periódica. Já no caso de homeomorfismos, mostramos que, dado uma dinâmica T : K K, existe uma T : K K próxima a T, tal que o w-limite de toda órbita de T é uma órbita periódica. Em particular, mostramos que, em ambos os casos, todas as medidas ergódicas estão suportadas em órbitas periódicas. / Let K be a Cantor set. In this work we present two theorems related to the density of symbolic dynamics. We prove that given an endomorphism T : K K then there exists an endomorphism ~ T : K K close to T such that every orbit is finally periodic. We also prove that given a homeomorphism T : K K then there exists a homeomorphism ~ T : K K close to T such that the w-limit of every orbit is a periodic orbit. In particular, we have shown, in both cases, that all ergodic measures have support on periodic orbits.

This manuscript deals with the problem of markerless motion capture. An approach to thisproblem is model-based and is divided into two steps : an initialization step in which the initialpose is estimated, and a tracking which computes the current pose of the subject using infor-mation of previous ones. Classically, the initialization step is done manually, for bidding the possibility to be used online, or requires constraining actions of the subject. We propose an automatic real-time markerless initialization step, that relies on topological information provided by skeletonization of a 3D reconstruction of the subject. This topological information is then represented as a tree, which is matched with another tree used as modeldescription, in order to identify the different parts of the subject. In order to provide such a method, we propose some contributions in both digital topology and graph theory researchfields. As our method requires real-time computation, we first focus on the speed optimization of skeletonization methods, and on the design of new fast skeletonization schemes providing good results. In order to efficiently match the tree representing the topological information with the tree describing the model, we propose new matching definitions and associated algorithms. Finally, we study how to improve the robustness of our method by the use of innovative con-straints in the model. This manuscript ends by a study of the application of our method on several data sets, demon-strating its interesting properties : fast computation, robustness, and adaptability to any kindof subjects

“Homeomorphic'' is the standard equivalence relation in topology. To a topologist, spaces which are homeomorphic to each other aren't merely similar to each other, they are the same space. We study a class of functions which are homeomorphic at “most'' of the points of their domains and codomains, but which may fail to satisfy some of the properties required to be a homeomorphism at a “small'' portion of the points of these spaces. Such functions we call “almost homeomorphisms.'' One of the nice properties of almost homeomorphisms is the preservation of almost open sets, i.e. sets which are “close'' to being open, except for a “small'' set of points where the set is “defective.'' We also find a surprising result that all non-empty, perfect, Polish spaces are almost homeomorphic to each other.A standard technique in algebraic topology is to pass between a continuous map between topological spaces and the corresponding homomorphism of fundamental groups using the π1 functor. It is a non-trivial question to ask when a specific homomorphism is induced by a continuous map; that is, what is the image of the π1 functor on homomorphisms?We will call homomorphisms in the image of the π1 functor “tangible homomorphisms'' and call homomorphisms that are not induced by continuous functions “intangible homomorphisms.'' For example, Conner and Spencer used ultrafilters to prove there is a map from HEG to Z2 not induced by any continuous function f : HE→ Y , where Y is some topological space with π1(Y ) = Z2. However, in standard situations, such as when the domain is a simplicial complex, only tangible homomorphisms appear..Our job is to describe conditions when intangible homomorphisms exist and how easily these maps can be constructed. We use methods from Shelah and Pawlikowski to prove that Conner and Spencer could not have constructed these homomorphisms with a weak version of the Axiom of Choice. This leads us to define and examine a class of pathological objects that cannot be constructed without a strong version of the Axiom of Choice, which we call the class of inscrutable objects. Objects that do not need a strong version of the Axiom of Choice are scrutable. We show that the scrutable homomorphisms from the fundamental group of a Peano continuum are exactly the homomorphisms induced by a continuous function.

Dans cette thèse, nous nous intéressons à diverses propriétés algébriques des groupes d'homéomorphismes et de difféomorphismes de variétés. On appelle fragmentation la possibilité d'écrire un homéomorphisme en tant que composé d'homéomorphismes supportés dans des boules. Tout d'abord, nous étudions la longueur des commutateurs sur le groupe des homéomorphismes du tore et de l'anneau, ainsi que la norme de fragmentation, qui associe à tout homéomorphisme le nombre minimal de facteurs nécessaires pour écrire cet homéomorphisme en tant que composé d'homéomorphismes supportés dans des boules. Dans une deuxième partie de la thèse, nous abordons una autre propriété algébrique des groupes d'homéomorphismes et de difféomorphismes : la distorsion. Celle-ci est reliée de manière surprenante à des propriétés de fragmentation des homéomorphismes. / In this thesis, we are interested in various algebraic properties of groups of homeomorphisms and diffeomorphisms of manifolds. We call fragmentation the possibility to write a homeomorphism as a composition of homeomorphisms supported in balls. First, we study the commutator length on the group of homeomorphisms of the torus and of the annulus, as well as the fragmentation norm, which associates to any homeomorphism the minimal number of factors necessary to write this homeomorphism as a composition of homeomorphisms supported in balls. In a second part of this thesis, we deal with another algebraic property of homeomorphism and diffeomorphism groups: the distortion. This last notion is surprisingly related to fragmentation properties of homeomorphisms.

Dans quelle mesure peut-on lire les propriétés dynamiques (quand le temps tend vers l’infini) d’un système sur des simulations numériques ? Pour tenter de répondre à cette question, on étudie dans cette thèse un modèle rendant compte de ce qui se passe lorsqu’on calcule numériquement les orbites d’un système à temps discret f (par exemple un homéomorphisme). L’ordinateur travaillant à précision numérique finie, il va remplacer f par une discrétisation spatiale de f, notée f_N (où l’ordre de la discrétisation N rend compte de la précision numérique). On s’intéresse en particulier au comportement dynamique des applications finies f_N pour un système f générique et pour l’ordre N tendant vers l’infini, où générique sera à prendre dans le sens de Baire (principalement parmi des ensembles d’homéomorphismes ou de C^1-difféomorphismes). La première partie de cette thèse est consacrée à l’étude de la dynamique des discrétisations f_N lorsque f est un homéomorphisme conservatif/dissipatif générique d’une variété compacte. L’étude montre qu’il est illusoire de vouloir retrouver la dynamique du système de départ f à partir de celle d’une seule discrétisation f_N : la dynamique de f_N dépend fortement de l’ordre N. Pour détecter certaines dynamiques de f il faut considérer l’ensemble des discrétisations f_N, lorsque N parcourt N.La seconde partie traite du cas linéaire, qui joue un rôle important dans l’étude du cas des C^1-difféomorphismes génériques, abordée dans la troisième partie de cette thèse. Sous ces hypothèses, on obtient des résultats similaires à ceux établis dans la première partie, bien que plus faibles et de preuves plus difficiles. / How is it possible to read the dynamical properties (ie when the time goes to infinity) of a system on numerical simulations ? To try to answer this question, we study inthis thesis a model reflecting what happens when the orbits of a discrete time system f (for example an homeomorphism) are computed numerically. The computer working in finite numerical precision, it will replace f by a spacial discretization of f, denotedby f_N (where the order N of discretization stands for the numerical accuracy). In particular, we will be interested in the dynamical behaviour of the finite maps f_N for a generic system f and N going to infinity, where generic will be taken in the sense of Baire (mainly among sets of homeomorphisms or C^1-diffeomorphisms). The first part of this manuscript is devoted to the study of the dynamics of the discretizations f_N, when f is a generic conservative/dissipative homeomorphism of a compact manifold. We show that it would be mistaken to try to recover the dynamics of f from that of a single discretization f_N : its dynamics strongly depends on the order N. To detect some dynamical features of f we have to consider all thediscretizations f_N when N goes through N.The second part deals with the linear case, which plays an important role in the study of C^1-generic diffeomorphisms, discussed in the third part of this manuscript. Under these assumptions, we obtain results similar to those established in the first part,though weaker and harder to prove.

Graphen sind in vielen Bereichen des Lebens zu finden, wobei wir speziell an Graphen in der Biologie interessiert sind. Knoten in solchen Graphen sind chemische Komponenten, Enzyme, Reaktionen oder Interaktionen, die durch Kanten miteinander verbunden sind. Eine effiziente Ausführung von Graphanfragen ist eine Herausforderung. In dieser Arbeit präsentieren wir GRIcano, ein System, das die effiziente Ausführung von Graphanfragen erlaubt. Wir nehmen an, dass Graphen in relationalen Datenbankmanagementsystemen (RDBMS) gespeichert sind. Als Graphanfragesprache schlagen wir eine erweiterte Version der Pathway Query Language (PQL) vor. Der Hauptbestandteil von GRIcano ist ein kostenbasierter Anfrageoptimierer. Diese Arbeit enthält Beiträge zu allen drei benötigten Komponenten des Optimierers, der relationalen Algebra, Implementierungen und Kostenmodellen. Die Operatoren der relationalen Algebra sind nicht ausreichend, um Graphanfragen auszudrücken. Daher stellen wir zuerst neue Operatoren vor. Wir schlagen den Erreichbarkeits-, Distanz-, Pfadlängen- und Pfadoperator vor. Zusätzlich geben wir Regeln für die Umformung von Ausdrücken an. Des Weiteren präsentieren wir Implementierungen für jeden vorgeschlagenen Operator. Der Hauptbeitrag ist GRIPP, eine Indexstruktur, die die effiziente Ausführung von Erreichbarkeitsanfragen auf sehr großen Graphen erlaubt. Wir zeigen, wie GRIPP und die rekursive Anfragestrategie genutzt werden können, um Implementierungen für alle Operatoren bereitzustellen. Die dritte Komponente von GRIcano ist das Kostenmodell, das Kardinalitätsabschätzungen der Operatoren und Kostenfunktionen für die Implementierungen benötigt. Basierend auf umfangreichen Experimenten schlagen wir in dieser Arbeit Funktionen dafür vor. Der neue Ansatz unserer Kostenmodelle ist, dass die Funktionen nur Kennzahlen der Graphen verwenden. Abschließend zeigen wir die Wirkungsweise von GRIcano durch Beispielanfragen auf echten biologischen Graphen. / Graphs occur in many areas of life. We are interested in graphs in biology, where nodes are chemical compounds, enzymes, reactions, or interactions that are connected by edges. Efficiently querying these graphs is a challenging task. In this thesis we present GRIcano, a system that efficiently executes graph queries. For GRIcano we assume that graphs are stored and queried using relational database management systems (RDBMS). We propose an extended version of the Pathway Query Language PQL to express graph queries. The core of GRIcano is a cost-based query optimizer. This thesis makes contributions to all three required components of the optimizer, the relational algebra, implementations, and cost model. Relational algebra operators alone are not sufficient to express graph queries. Thus, we first present new operators to rewrite PQL queries to algebra expressions. We propose the reachability, distance, path length, and path operator. In addition, we provide rewrite rules for the newly proposed operators in combination with standard relational algebra operators. Secondly, we present implementations for each proposed operator. The main contribution is GRIPP, an index structure that allows us to answer reachability queries on very large graphs. GRIPP has advantages over other existing index structures, which we review in this work. In addition, we show how to employ GRIPP and the recursive query strategy as implementation for all four proposed operators. The third component of GRIcano is the cost model, which requires cardinality estimates for operators and cost functions for implementations. Based on extensive experimental evaluation of our proposed algorithms we present functions to estimate the cardinality of operators and the cost of executing a query. The novelty of our approach is that these functions only use key figures of the graph. We finally present the effectiveness of GRIcano using exemplary graph queries on real biological networks.

We study the complexity of the homeomorphism relation on the classes of metrizable compacta and Peano continua using the notion of Borel reducibil- ity. For each of these two classes we consider two different codings. Metrizable compacta can be naturally coded by the space of compact subsets of the Hilbert cube with the Vietoris topology. Alternatively, we can use the space of continuous functions from the Cantor space to the Hilbert cube with the topology of uniform convergence, where two functions are considered as equivalent iff their images are homeomorphic. Similarly, Peano continua can be coded either by the space of Peano subcontinua of the Hilbert cube, or (due to the Hahn-Mazurkiewicz theo- rem) by the space of continuous functions from r0, 1s to the Hilbert cube. We show that for both classes the two codings have the same complexity (the complexity of the universal orbit equivalence relation). Among other results, we also prove that the homeomorphism relation on the space of nonempty compact subsets of any given Polish space is Borel bireducible with the above mentioned equivalence relation on the space of continuous functions from the Cantor space to the Polish space.

We study the optimal conditions on a homeomorphism f : Ω → Rn which guarantee that the composition u◦f is weakly differentiable and its weak derivative belongs to the some function space. We show that if f has finite distortion and q-distortion Kq = |Df|q /Jf is integrable enough, then the composition operator Tf (u) = u ◦ f maps functions from W1,q loc into space W1,p loc and the well-known chain rule holds. To prove it we characterize when the inverse mapping f−1 maps sets of measure zero onto sets of measure zero (satisfies the Luzin (N−1 ) con- dition). We also fully characterize conditions for Sobolev-Lorentz space WLn,q for arbitrary q and for Sobolev Orlicz space WLq log L for q ≥ n and α > 0 or 1 < q ≤ n and α < 0. We find a necessary condition on f for Sobolev rearrangement invariant function space WX close to WLq , i.e. X has q-scaling property. 1