Researchers have been investigating the optimal route query problem for a long time. Optimal route queries are categorized as either unconstrained or constrained queries. Many main memory based algorithms have been developed to deal with the optimal route query problem. Among these, Dijkstra's shortest path algorithm is one of the most popular algorithms for the unconstrained route query problem. The constrained route query problem is more complicated than the unconstrained one, and some constrained route query problems such as the Traveling Salesman Problem and Hamiltonian Path Problem are NP-hard. There are many algorithms dealing with the constrained route query problem, but most of them only solve a specific case. In addition, all of them require that the entire graph resides in the main memory. Recently, due to the need of applications in very large graphs, such as the digital maps managed by Geographic Information Systems (GIS), several disk-based algorithms have been derived by using divide-and-conquer techniques to solve the shortest path problem in a very large graph. However, until now little research has been conducted on the disk-based constrained problem. <br /><br /> This thesis presents two algorithms: 1) a new disk-based shortest path algorithm (DiskSPNN), and 2) a new disk-based optimal path algorithm (DiskOP) that answers an optimal route query without passing a set of forbidden edges in a very large graph. Both algorithms fit within the same divide-and-conquer framework as the existing disk-based shortest path algorithms proposed by Ning Zhang and Heechul Lim. Several techniques, including query super graph, successor fragment and open boundary node pruning are proposed to improve the performance of the previous disk-based shortest path algorithms. Furthermore, these techniques are applied to the DiskOP algorithm with minor changes. The proposed DiskOP algorithm depends on the concept of collecting a set of boundary vertices and simultaneously relaxing their adjacent super edges. Even if the forbidden edges are distributed in all the fragments of a graph, the DiskOP algorithm requires little memory. Our experimental results indicate that the DiskSPNN algorithm performs better than the original ones with respect to the I/O cost as well as the running time, and the DiskOP algorithm successfully solves a specific constrained route query problem in a very large graph.

Finding a shortest path is one of the most well-studied optimization problems. In this thesis we focus on shortest paths in geometric and graph theoretic settings subject to different feasibility constraints that arise in practical applications of such paths. One of the most fundamental problems in computational geometry is finding shortest paths in terrains, which has many applications in robotics, computer graphics and Geographic Information Systems (GISs). There are many variants of the problem in which the feasibility of a path is determined by some geometric property of the terrain. One such variant is the shortest descending path (SDP) problem, where the feasible paths are those that always go downhill. We need to compute an SDP, for example, for laying a canal of minimum length from the source of water at the top of a mountain to fields for irrigation purpose, and for skiing down a mountain along a shortest route. The complexity of finding SDPs is open. We give a full characterization of the bend angles of an SDP, showing that they follow a generalized form of Snell's law of refraction of light. We also reduce the SDP problem to the problem of finding an SDP through a given sequence of faces, by adapting the sequence tree approach of Chen and Han for our problem. Our results have two implications. First, we isolate the difficult aspect of SDPs. The difficulty is not in deciding which face sequence to use, but in finding the SDP through a given face sequence. Secondly, our results help us identify some classes of terrains for which the SDP problem is solvable in polynomial time. We give algorithms for two such classes. The difficulty of finding an exact SDP motivates the study of approximation algorithms for the problem. We devise two approximation algorithms for SDPs in general terrains---these are the first two algorithms to handle the SDP problem in such terrains. The algorithms are robust and easy-to-implement. We also give two approximation algorithms for the case when a face sequence is given. The first one solves the problem by formulating it as a convex optimization problem. The second one uses binary search together with our characterization of the bend angles of an SDP to locate an approximate path. We introduce a generalization of the SDP problem, called the shortest gently descending path (SGDP) problem, where a path descends but not too steeply. The additional constraint to disallow a very steep descent makes the paths more realistic in practice. For example, a vehicle cannot follow a too steep descent---this is why a mountain road has hairpin bends. We give two easy-to-implement approximation algorithms for SGDPs, both using the Steiner point approach. Between a pair of points there can be many SGDPs with different number of bends. In practice an SGDP with fewer bends or smaller total turn-angle is preferred. We show using a reduction from 3-SAT that finding an SGDP with a limited number of bends or a limited total turn-angle is hard. The hardness result applies to a generalization of the SGDP problem called the shortest anisotropic path problem, which is a well-studied computational geometry problem with many practical applications (e.g., robot motion planning), yet of unknown complexity. Besides geometric shortest paths, we also study a variant of the shortest path problem in graphs: given a weighted graph G and vertices s and t, and given a set X of forbidden paths in G, find a shortest s-t path P such that no path in X is a subpath of P. Path P is allowed to repeat vertices and edges. We call each path in X an exception, and our desired path a shortest exception avoiding path. We formulate a new version of the problem where the algorithm has no a priori knowledge of X, and finds out about an exception x in X only when a path containing x fails. This situation arises in computing shortest paths in optical networks. We give an easy-to-implement algorithm that finds a shortest exception avoiding path in time polynomial in |G| and |X|. The algorithm handles a forbidden path using vertex replication, i.e., replicating vertices and judiciously deleting edges so as to remove the forbidden path but keep all of its subpaths. The main challenge is that vertex replication can result in an exponential number of copies of any forbidden path that overlaps the current one. The algorithm couples vertex replication with the "growth" of a shortest path tree in such a way that the extra copies of forbidden paths produced during vertex replication are immaterial.

Szemerédi's Regularity Lemma is powerful tool in Graph Theory, yielding many applications in areas such as Extremal Graph Theory, Combinatorial Number Theory and Theoretical Computer Science. Strong hypergraph extensions of graph regularity techniques were recently given by Nagle, Rödl, Schacht and Skokan, by W.T. Gowers, and subsequently, by T. Tao. These extensions have yielded quite a few non-trivial applications to Extremal Hypergraph Theory, Combinatorial Number Theory and Theoretical Computer Science. A main drawback to the hypergraph regularity techniques above is that they are highly technical. In this thesis, we consider a less technical version of hypergraph regularity which more directly generalizes Szemeredi's regularity lemma for graphs. The tools we discuss won't yield all applications of their stronger relatives, but yield still several applications in extremal hypergraph theory (for so-called linear or simple hypergraphs), including algorithmic ones. This thesis surveys these lighter regularity techiques, and develops three applications of them.

Cette recherche propose une réflexion sur les enjeux que recouvre la pédophilie dans la société occidentale contemporaine. Dans le premier chapitre, il sera d’abord question d’autorité : afin de bien comprendre le rapport entretenu avec l’autorité et l’importance accordée au système hiérarchique dans la société occidentale contemporaine, nous établirons une comparaison avec les sociétés grecques puisque celles-ci ont accepté et valorisé les relations intergénérationnelles. C’est à travers une lecture de différents textes de Michel Foucault et de Kenneth James Dover que nous approfondirons ces rapports. Cette première partie sera essentielle en ce qu’elle nous aidera à comprendre la façon dont les bases de la société occidentale contemporaine ont été édifiées, l’importance de la catégorisation des genres et les raisons du rejet des relations pédophiliques aujourd’hui. Dans le second chapitre, nous analyserons plus spécifiquement deux œuvres littéraires, La Mort à Venise de Thomas Mann et Quand mourut Jonathan de Tony Duvert, afin de percevoir le malaise que provoque la pédophilie. C’est notamment à travers une étude des figures sociales et de l’éducation que nous tenterons de saisir la place attribuée à la pédophilie. Cette étude se terminera par une réflexion autour de la photographie et du cinéma, afin de souligner l’impact apporté par le réalisme de ces arts. Nous aborderons ici des œuvres non pornographiques qui exposent des sexualités existantes mais non reconnues. Les différents aspects abordés nous permettront non seulement de saisir l’embarras que suscite la pédophilie, mais également de capter la place qu’on y accorde, ou non, au sein de la société contemporaine. / This research proposes a reflection on the stakes of pedophilia in contemporary western society. In the first chapter, we will raise the question of authority: in order to understand the relation with authority and the importance of a hierarchic system in the contemporary western society, we will compare it with the Greek society which accepted and valued intergenerational relationships. It is especially through a reading of various texts from Michel Foucault and Kenneth James Dover that this study will be conducted. This first part is necessary to understand how the bases of contemporary western society were established, the importance of genders’ categorization and the reason behind the rejection of pedophilia today. In the second chapter, we will more specifically analyze two novels, Thomas Mann’s La Mort à Venise and Tony Duvert’s Quand mourut Jonathan. It is mainly through a study of social figures and education that we will be able to understand the place given to pedophilia. This study will close in a reflection about photography and cinema in order to emphasize the impact of these arts’ realism. We will therefore approach non-pornographic works of art that present existing but never recognized sexualities. These different aspects will enable us to fully understand the embarrassment provoked by pedophilia today, but also to recognize the place it is given, or not, within contemporary society.

Title: Extremal combinatorics of matrices, sequences and sets of permutations Author: Josef Cibulka Department: Department of Applied Mathematics Supervisor: Doc. RNDr. Pavel Valtr, Dr., Department of Applied Mathematics Abstract: This thesis studies questions from the areas of the extremal theory of {0, 1}-matrices, sequences and sets of permutations, which found many ap- plications in combinatorial and computational geometry. The VC-dimension of a set P of n-element permutations is the largest integer k such that the set of restrictions of the permutations in P on some k-tuple of positions is the set of all k! permutation patterns. We show lower and upper bounds quasiexponential in n on the maximum size of a set of n-element permutations with VC-dimension bounded by a constant. This is used in a paper of Jan Kynčl to considerably improve the upper bound on the number of weak isomorphism classes of com- plete topological graphs on n vertices. For some, mostly permutation, matrices M, we give new bounds on the number of 1-entries an n × n M-avoiding matrix can have. For example, for every even k, we give a construction of a matrix with k2 n/2 1-entries that avoids one specific k-permutation matrix. We also give almost tight bounds on the maximum number of 1-entries in matrices avoiding a fixed layered...

abstract: Shunt capacitors are often added in transmission networks at suitable locations to improve the voltage profile. In this thesis, the transmission system in Arizona is considered as a test bed. Many shunt capacitors already exist in the Arizona transmission system and more are planned to be added. Addition of these shunt capacitors may create resonance conditions in response to harmonic voltages and currents. Such resonance, if it occurs, may create problematic issues in the system. It is main objective of this thesis to identify potential problematic effects that could occur after placing new shunt capacitors at selected buses in the Arizona network. Part of the objective is to create a systematic plan for avoidance of resonance issues. For this study, a method of capacitance scan is proposed. The bus admittance matrix is used as a model of the networked transmission system. The calculations on the admittance matrix were done using Matlab. The test bed is the actual transmission system in Arizona; however, for proprietary reasons, bus names are masked in the thesis copy in-tended for the public domain. The admittance matrix was obtained from data using the PowerWorld Simulator after equivalencing the 2016 summer peak load (planning case). The full Western Electricity Coordinating Council (WECC) system data were used. The equivalencing procedure retains only the Arizona portion of the WECC. The capacitor scan results for single capacitor placement and multiple capacitor placement cases are presented. Problematic cases are identified in the form of ‘forbidden response. The harmonic voltage impact of known sources of harmonics, mainly large scale HVDC sources, is also presented. Specific key results for the study indicated include: • The forbidden zones obtained as per the IEEE 519 standard indicates the bus 10 to be the most problematic bus. • The forbidden zones also indicate that switching values for the switched shunt capacitor (if used) at bus 3 should be should be considered carefully to avoid resonance condition from existing. • The highest sensitivity of 0.0033 per unit for HVDC sources of harmonics was observed at bus 7 when all the HVDC sources were active at the same time. / Dissertation/Thesis / Masters Thesis Electrical Engineering 2015

Made available in DSpace on 2014-10-09T12:45:56Z (GMT). No. of bitstreams: 0 / Made available in DSpace on 2014-10-09T14:04:42Z (GMT). No. of bitstreams: 1 07541.pdf: 9270192 bytes, checksum: 625d1a8ce146718eee35be24d9a360a3 (MD5) / Tese (Doutoramento) / IPEN/T / Instituto de Pesquisas Energeticas e Nucleares - IPEN/CNEN-SP

La difusión de la literatura francesa en el virreinato peruano en la segunda mitad del siglo XVIII es el tema de estudio de este artículo. El autor reconstruye cómo por medio del comercio y del contrabando los libros franceses prohibidos y no prohibidos llegaron a manos de los lectores de la sociedad colonial. Argumenta que el estudio de la circulación de la literatura francesa permite examinar las contradicciones de la política cultural impulsada por la administración borbónica.---The dissemination of French literature in the Peruvian viceroyalty in the second part of the XVIII century is the theme of this article. The author reconstructs how, via commerce and contraband, forbidden and non-forbidden French books reached the hands of readers in colonial society. The author argues that the study of the circulation of French literature allows us to examine the contradictions in the cultural policy fostered by the Bourbon administration.

Made available in DSpace on 2014-10-09T12:45:56Z (GMT). No. of bitstreams: 0 / Made available in DSpace on 2014-10-09T14:04:42Z (GMT). No. of bitstreams: 1 07541.pdf: 9270192 bytes, checksum: 625d1a8ce146718eee35be24d9a360a3 (MD5) / Tese (Doutoramento) / IPEN/T / Instituto de Pesquisas Energeticas e Nucleares - IPEN/CNEN-SP

Interval minors of binary matrices were introduced by Jacob Fox in the study of Stanley-Wilf limits. We study what can be implied from their relation to the theory of pattern avoidance of submatrices, which is a very popular area of discrete mathematics. We start by characterizing matrices avoiding small interval minors. We then consider classes of matrices closed under interval minors and we find classes of matrices that cannot be described by a finite number of forbidden interval minors. We also define and study a variant of a classical extremal Tur'an- type question studied in the area of combinatorics of permutations and binary matrices and in combinatorial geometry. 1