This work, which is intended for secondary school pupils and teachers, is fo- cused on orthogonal axonometry for pupils and teachers at secondary schools. The thesis consists of exercises, some of them are stepped in presentations and can be found on the attached CD. Templates of models that students can build themselves are included in the first exercises for better understanding. The text is supplemented by the development of orthogonal axonometry and an analysis of the current state of orthogonal axonometry education in the Czech Republic, based on a questionnaire survey and an analysis of textbooks. The theoretical part of the work was prepared for publication on the website. 1

La congestión vehicular se ha convertido en una constante en la vida citadina y Lima no es la excepción. Sin embargo, existen acciones que pueden ser implementadas para minimizar el tiempo que se pierde al circular por vías de alto tránsito, especialmente durante horas pico, como es el caso de la red constituida por las avenidas Faustino Sánchez Carrión. y La Marina, desde la Av. Gregorio Escobedo hasta la Av. Antonio José de Sucre. En ese contexto, el propósito del presente trabajo es brindar una alternativa de gestión de la oferta vial que contribuya con la optimización de los indicadores de medición del tráfico; entre ellos, el grado de saturación, el nivel de servicio de las intersecciones que forman parte de la investigación y las demoras por tiempo de espera. Para ello, se hace uso de Synchro 8, un software de simulación que sirve de soporte para la generación del modelo de solución, efectuado a nivel mesoscópico. Synchro es compatible con el Highway Capacity Manual - HCM 2000 y 2010; pero además, cuenta con una serie de herramientas que le permiten incorporar su propia técnica de análisis. En el caso de este proyecto, la evaluación del tráfico se desarrolla mediante la Metodología del Automóvil de HCM 2010; sin considerar el análisis de peatones ni ciclistas. Los resultados obtenidos demuestran que es posible optimizar el tráfico vehicular a través del uso correcto de simuladores de tránsito y no solo con intervenciones geométricas de gran escala o excesiva inversión en nueva infraestructura. / Traffic congestion has become a constant in city life, and Lima is not the exception. However, there are actions that can be implemented to minimize the time lost when traveling on high-traffic routes, especially during rush hours, such as the case of the road network formed by the Faustino Sánchez Carrión and La Marina avenues, from Gregorio Escobedo Ave. to Antonio José de Sucre Ave. In that context, the purpose of this project is to provide an alternative of road offer management which contributed to improving traffic measurement indicators; among them, saturation degree, intersections level of service that are part of the research, and delays due to waiting time. In doing so, Synchro 8 is used. This simulation software functions as a support for the solution model generation, which is performed at the mesoscopic level. Synchro is compatible with the Highway Capacity Manual - HCM 2000 and 2010; but also, it has a set of tools that allow it to incorporate its own analysis technique. In the case of this project, traffic evaluation is developed on the basis of vehicular operation system by means of the HCM 2010 Automobile Methodology; that is, the pedestrians and cyclists analysis are not taken into consideration. The results obtained show that it is possible to optimize vehicular traffic through the correct use of traffic simulators and not only through large-scale geometric interventions, or with excessive investment in new infrastructure. / Tesis

Les domaines de géométrie algébrique et de géométrie algorithmique, bien qu'étroitement liés, sont traditionnellement représentés par des communautés de recherche disjointes. Chacune d'entre elles utilisent des courbes et surfaces, mais représentent les objets de différentes manières. Alors que la géométrie algébrique définit les objets par le biais d'équations polynomiales, la géométrie algorithmique a pour habitude de manipuler des modèles linéaires. La tendance actuelle est d'appliquer les algorithmes traditionnels de géométrie algorithmique sur des modèles non linéaires tels que ceux trouvés en géométrie algébrique. De tels algorithmes jouent un rôle important dans de nombreux champs d'application tels que la Conception Assistée par Ordinateur. Leur utilisation soulève d'importantes questions en matière de développement logiciel. Tout d'abord, la manipulation de leur représentation implique l'utilisation de calculs symboliques numériques qui représentent toujours un domaine de recherche majeur. Deuxièmement, leur visualisation et leur manipulation n'est pas évidente, en raison de leur caractère abstrait.<br /><br />La première partie de cette thèse porte sur l'utilisation de méthodes algébriques en modélisation géométrique, l'accent étant mis sur la topologie, l'intersection et l'auto-intersection dans le cadre du calcul d'arrangement d'ensembles semi-algébriques comme les courbes et surfaces à représentation implicite ou paramétrique. Une attention particulière est portée à la généricité des algorithmes qui peuvent être spécifiés quel que soit le contexte, puis spécialisés pour répondre aux exigences d'une certaine représentation.<br /><br />La seconde partie de cette thèse présente le prototypage d'un environnement de modélisation géométrique dont le but est de fournir un moyen générique et efficace pour modéliser des solides à partir d'objets géométriques à re\-pré\-sen\-ta\-tion algébrique tels que les courbes et surfaces implicites ou paramétriques, à la fois d'un point de vue utilisateur et d'un point de vue de développeur, par l'utilisation de librairies de calcul symbolique numérique pour la<br />manipulation des polynômes définissant les objets géométriques.

Le travail présenté ici a pour thème le développement et la mise en oeuvre d'une méthode d'implicitisation et d'inversion ainsi que son application à la visualisation de surfaces polynomiales et rationnelles parametrées par la technique du lancer de rayons. l'implicitisation est un problème d'élimination pour lequel les méthodes de résultant s'avèrent mieux adaptées à notre application. la méthode de dixon (1908) pour les surfaces obtenues par produit tensoriel (surfaces de bi-degré) est particulièrement bien adaptée. Nous proposons une extension algorithmique de cette méthode qui conserve ses propriétés de simplicité et de compacité. la programmation en langage REDUCE a permis une expérimentation sur de nombreux exemples: elle montre que l'équation implicite est obtenue, et ceci de façon efficace, bien que la justification théorique de l'algorithme reste incomplète. L'étude de cette dernière nous a amené à considérer les problèmes de paramétrisations non fidèles et de l'apparition de facteurs parasites. Ensuite le problème de l'inversion (identification et détermination des paramètres d'un point de la surface rationnelle) est résolu complètement. Nous proposons enfin une application numérique de ces algorithmes (en langage C) au problème de l'intersection d'une Bezier rationnelle et d'une demi-droite (rayon). les aspects de stabilité numérique et d'optimisation sont mis en avant: à chaque surface est associée une table pre-calculée, permettant d'obtenir simplement l'équation d'intersection dans le paramètre rayon. Les images données attestent des qualités numériques de cette méthode d'implicitisation-inversion<br />~

Dans une première partie, nous définissons un nouveau langage à base fonctionnelle et avec récursion généralisée, en utilisant le système de types avec degrés de Boudol pour éliminer les récursions dangereuses. Ce langage est ensuite étendu par des enregistrements récursifs, puis par des mixins, permettant ainsi de mêler totalement les paradigmes fonctionnels et objets. Nous présentons également une implémentation, MlObj, ainsi que la machine abstraite servant à son exécution.<br /><br />Dans une deuxième partie, nous présentons un nouvel algorithme d'inférence pour les systèmes de types avec intersection, dans le cadre d'une extension du lambda-calcul. Après avoir prouvé sa correction, nous étudions sa généralisation aux références et à la récursion, nous le comparons aux algorithmes d'inférence déjà existants, notamment à celui de Système I, et nous montrons qu'il devient décidable à rang fini.

Dans ce travail de thèse une étude théorique et pratique du résultant résiduel est proposée. Ce résultant résiduel fournit une condition nécessaire et suffisante pour qu'un système algébrique possède des solutions sur une variété résiduelle obtenue par éclatement. Des méthodes effectives pour calculer ce résultant résiduel ainsi que son degré sont proposées, les résultats les plus précis étant obtenus lorsque le lieu que l'on éclate est une intersection complète ou encore une intersection complète locale projective Cohen-Macaulay de codimension deux. Un algorithme pour résoudre le problème d'implicitisation dans le cas ou la paramétrisation possède des points base localement intersection complète est explicité à l'aide du résultant résiduel. On montre également comment ce résultant résiduel permet d'obtenir la forme de Chow des points isolés d'un système algébrique. Enfin le dernier chapitre de cette thèse présente une définition et une première étude du résultant déterminantal qui donne une condition nécessaire et suffisante pour qu'une matrice générique soit de rang inférieur ou égal à un entier positif donné.

A graph Gis said to be an intersection graph of sets from a family of sets if there exists a function ƒ : V(G)→ such that for u,v V(G), (u,v) E(G) ƒ (u) ƒ (v) ≠ . Interval graphs are thus the intersection graphs of closed intervals on the real line and unit interval graphs are the intersection graphs of unit length intervals on the real line. An interval on the real line can be generalized to a “kbox” in Rk.A kbox B =(R1,R2,...,Rk), where each Riis a closed interval on the real line, is defined to be the Cartesian product R1x R2x…x Rk. If each Ri is a unit length interval, we call B a k-cube. Thus, 1-boxes are just closed intervals on the real line whereas 2-boxes are axis-parallel rectangles in the plane. We study the intersection graphs of k-boxes and k-cubes. The parameter boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as cub(G), is the minimum integer k such that G is an intersection graph of k-cubes. Thus, interval graphs are the graphs with boxicity at most 1 and unit interval graphs are the graphs with cubicity at most 1. These parameters were introduced by F. S.Roberts in 1969. In some sense, the boxicity of a graph is a measure of how different a graph is from an interval graph and in a similar way, the cubicity is a measure of how different the graph is from a unit interval graph. We prove several upper bounds on the boxicity and cubicity of general as well as special classes of graphs in terms of various graph parameters such as the maximum degree, the number of vertices and the bandwidth. The following are some of the main results presented. 1. We show that for any graph G with maximum degree Δ , box(G)≤ Δ 22 . This result implies that bounded degree graphs have bounded boxicity no matter how large the graph might be. 2. It was shown in [18] that the boxicity of a graph on n vertices with maximum degree Δ is O(Δ ln n). But a similar bound does not hold for the average degree davof a graph. [18] gives graphs in which the boxicity is exponentially larger than davln n. We show that even though an O(davln n) upper bound for boxicity does not hold for all graphs, for almost all graphs, boxicity is O(davln n). 3. The ratio of the cubicity to boxicity of any graph shown in [15] when combined with the results on boxicity show that cub(G) is O(Δ ln 2 n) and O(2 ln n) for any graph G on n vertices and with maximum degree . By using a randomized construction, we prove the better upper bound cub(G) ≤ [4(Δ + 1) ln n.] 4. Two results relating the cubicity of a graph to its bandwidth b are presented. First, it is shown that cub(G) ≤ 12(Δ + 1)[ ln(2b)] + 1. Next, we derive the upper bound cub(G) ≤ b + 1. This bound is used to derive new upper bounds on the cubicity of special graph classes like circular arc graphs, cocomparability graphs and ATfree graphs in relation to the maximum degree. 5. The upper bound for cubicity in terms of the bandwidth gives an upper bound of Δ + 1 for the cubicity of interval graphs. This bound is improved to show that for any interval graph G with maximum degree , cub(G) ≤[ log2 Δ] + 4. 6. Scheinerman [54] proved that the boxicity of any outerplanar graph is at most 2. We present an independent proof for the same theorem. 7. Halin graphs are planar graphs formed by adding a cycle connecting the leaves of a tree none of whose vertices have degree 2. We prove that the boxicity of any Halin graph is equal to 2 unless it is a complete graph on 4 vertices, in which case its boxicity is 1.

Symplectic geometry can be traced back to Lagrange and his work on celestial mechanics and has since then been a very active field in mathematics, partly because of the applications it offers but also because of the beauty of the objects it deals with. I this thesis we begin by the simplest fact of symplectic geometry. We give the definition of a symplectic space and of the symplectic group, Sp(n). A symplectic space is the data of an even-dimensional space and of a form which satisfies a number of properties. Having done this we give a definition of the Lagrangian Grassmannian Lag(n) which consists of all n-dimensional subspaces of the symplectic space on which the symplectic form vanishes. We carefully study the topology of these spaces and their universal coverings. It is of great interest to know how the elements of the Lagrangian Grassmannian intersect each other. A lot of efforts have therefore been made to construct intersection indices for elements of Lag(n). They have gone under many names but have had a sole purpose, namely to give us a way to determine how these elements intersect. We show how these elements are constructed and extend the definition to paths of elements of Lag(n) and Sp(n). We end this thesis by extending the definition of an index defined by Conley and Zehnder bu using the properties of the Leray index. Their index plays a significant role in the theory of periodic Hamiltonian orbit.

Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Richard Rado conjectured 1/4 and proved 1/4.41. In this thesis, we consider a variant of this problem where the disjointness constraint is relaxed: selected disks must be k-colourable with disks of the same colour pairwise-disjoint. Rado's problem is then the case where k = 1, and we focus our investigations on what can be proven for k > 1. Motivated by the problem of channel-assignment for Wi-Fi wireless access points, in which the use of 3 or fewer channels is a standard practice, we show that for k = 3 we can cover at least 1/2.09 and for k = 2 we can cover at least 1/2.82. We present a randomized algorithm to select and colour a subset of n disks to achieve these bounds in O(n) expected time. To achieve the weaker bounds of 1/2.77 for k = 3 and 1/3.37 for k = 2 we present a deterministic O(n^2) time algorithm. We also look at what bounds can be proven for arbitrary k, presenting two different methods of deriving bounds for any given k and comparing their performance. One of our methods is an extension of the method used to prove bounds for k = 2 and k = 3 above, while the other method takes a novel approach. Rado's proof is constructive, and uses a regular lattice positioned over the given set of disks to guide disk selection. Our proofs are also constructive and extend this idea: we use a k-coloured regular lattice to guide both disk selection and colouring. The complexity of implementing many of the constructions used in our proofs is dominated by a lattice positioning step. As such, we discuss the algorithmic issues involved in positioning lattices as required by each of our proofs. In particular, we show that a required lattice positioning step used in the deterministic O(n^2) algorithm mentioned above is 3SUM-hard, providing evidence that this algorithm is optimal among algorithms employing such a lattice positioning approach. We also present evidence that a similar lattice positioning step used in the constructions for our better bounds for k = 2 and k = 3 may not have an efficient exact implementation.

Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Richard Rado conjectured 1/4 and proved 1/4.41. In this thesis, we consider a variant of this problem where the disjointness constraint is relaxed: selected disks must be k-colourable with disks of the same colour pairwise-disjoint. Rado's problem is then the case where k = 1, and we focus our investigations on what can be proven for k > 1. Motivated by the problem of channel-assignment for Wi-Fi wireless access points, in which the use of 3 or fewer channels is a standard practice, we show that for k = 3 we can cover at least 1/2.09 and for k = 2 we can cover at least 1/2.82. We present a randomized algorithm to select and colour a subset of n disks to achieve these bounds in O(n) expected time. To achieve the weaker bounds of 1/2.77 for k = 3 and 1/3.37 for k = 2 we present a deterministic O(n^2) time algorithm. We also look at what bounds can be proven for arbitrary k, presenting two different methods of deriving bounds for any given k and comparing their performance. One of our methods is an extension of the method used to prove bounds for k = 2 and k = 3 above, while the other method takes a novel approach. Rado's proof is constructive, and uses a regular lattice positioned over the given set of disks to guide disk selection. Our proofs are also constructive and extend this idea: we use a k-coloured regular lattice to guide both disk selection and colouring. The complexity of implementing many of the constructions used in our proofs is dominated by a lattice positioning step. As such, we discuss the algorithmic issues involved in positioning lattices as required by each of our proofs. In particular, we show that a required lattice positioning step used in the deterministic O(n^2) algorithm mentioned above is 3SUM-hard, providing evidence that this algorithm is optimal among algorithms employing such a lattice positioning approach. We also present evidence that a similar lattice positioning step used in the constructions for our better bounds for k = 2 and k = 3 may not have an efficient exact implementation.