In 1966, Claude Berge proposed the following sorting problem. Given a string of n alternating white and black pegs, rearrange the pegs into a string consisting of all white pegs followed immediately by all black pegs (or vice versa) using only moves which take 2 adjacent pegs to 2 vacant adjacent holes. Berge's original question was generalized by considering the same sorting problem using only Berge k-moves, i.e., moves which take k adjacent pegs to k vacant adjacent holes. Let h(n,k) denote the minimum number of Berge k-moves to sort a string of n alternating white and black pegs.The generalized Berge sorting conjecture states that h(n,k) is equal to the ceiling of n/2 for any k and large enough n. We develop a computational framework to determine h(n,k) for small instances with a focus on the most computationally challenging instances; that is, the determination of (k+2,k). / Thesis / Master of Applied Science (MASc)

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T03:38:43Z (GMT). No. of bitstreams: 1 Pereira_LuizFernandodeFaria_M.pdf: 862122 bytes, checksum: 06f038348723d2201293366e75808ffd (MD5) Previous issue date: 2013 / Resumo: Uma partição em caminhos de um grafo dirigido é uma partição do conjunto de vértices deste grafo em caminhos dirigidos. Dada uma métrica sobre partições em caminhos chamada k-norma, o problema de interesse é estabelecer para um dado grafo quais das suas partições em caminhos tem a menor k-norma dentre todas as suas possíveis partições em caminhos. Chamamos estas partições de k-ótimas. Na década de 1980, Claude Berge conjecturou que para toda partição k-ótima, existe um conjunto de k conjuntos independentes disjuntos que, em certo sentido, interceptam o maior número possível de caminhos desta partição. A validade ou a falsidade desta proposição ainda não foi demonstrada, e ela é conhecida como a conjectura de Berge sobre partições em caminhos. Nesta dissertação, fizemos um estudo geral sobre a conjectura de Berge, sua história recente, e o trabalho matemático que foi desenvolvido sobre ela. Exibimos demonstrações para diversos casos particulares da conjectura que já foram resolvidos, como para grafos bipartidos, hamiltonianos, acíclicos, partições compostas somente de caminhos curtos, partições compostas somente de caminhos longos, e para valores fixos de k. Uma parte significativa do trabalho foi dedicada à reescrita da demonstração recente do caso particular onde k = 2, feita por Eli Berger e Irith Hartman, e uma análise do método usado / Abstract: A path partition of a directed graph is a partition of its vertex set into directed paths. Given a metric over path partitions called the k-norm, the problem we are interested in is to determine for a given graph which of its path partitions have the smallest k-norm among all possible path partitions. These partitions are called k-optimal. In the 1980's, Claude Berge conjectured that for every k-optimal path partition, there exists a set of k disjoint independent sets which intercepts the maximum number of paths in this partition. The validity of this proposition has not yet been demonstrated, and it is known as Berge's conjecture on path partitions. In this work, we consider Berge's conjecture, its recent history, and the related mathematical work that has been accomplished. We show proofs for many particular cases of the conjecture, including for acyclic graphs, bipartite graphs, hamiltonian graphs, partitions which include only short paths, partitions which include only long paths, and for fixed values of k. A significant part of this work was dedicated to the rewriting of a recent proof for the particular case where k = 2 by Eli Berger and Irith Hartman, and an analysis of their method / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Since the early fifties “open form” has become a generic description for many different compositional concepts having in common musical outcomes which to a certain degree are indeterminate. The introduction looks into different meanings given to “form” in music and gives a historical survey of the origins of compositional indeterminacy. Next, the concept of “open form” is elaborated into a territory which is usually not associated with it: jazz. The introduction is followed by five case studies. Folio (1952-54) by Earle Brown is considered to contain the first intentionally “open form” works. It is driven by improvisational ideas, either at the compositional stage or at the interpretative stage. Brown's affinity with jazz also offers connections to other topics of the thesis. Miles Davis' Ife (1972) may at first seem like an odd inclusion in this study, but it is not. Its only oddity could be that of all the works discussed it has no score. But it is a composition; it is recognizable throughout its various incarnations and repeatable, and its outcome is indeterminate. Adam Rudolph did not conceive Ostinatos of Circularity as an “open form” work, but it is an indeterminate composition: it does have a score the musical result of which depends on the decisions made by the composer/conductor during the performance as well as the choices made by the performers. In Peter Zummo's Experimenting with Household Chemicals the performers play the same, often ambiguous, score, moving in the same direction at their own speed and discretion. The lack of synchronicity and the ambiguous notation result in a very elastic organic form. Anne La Berge refers to her recent works as “guided improvisations”. The scores mainly consist of suggestive text materials, software preset descriptions and rudimentary verbal indications, leaving major decisions to the performers. The last chapter is about my own work. It presents seven works (the scores of which can be found in the accompanying portfolio), composed between 2007 and 2011. Each of these works uses the score as a “field” through which the performers roam.

Berge and Fulkerson conjectured that for each cubic bridgeless graph there are six perfect matchings such that each edge is contained in exactly two of them. Another conjecture due to Berge says that we can cover cubic bridgeless graphs by five perfect matchings. Both conjectures are studied for over forty years. Abreu et al. [2016] introduce a new class of graphs (called treelike snarks) which cannot be covered by less then five perfect matchings. We show that their lower bound on number of perfect matchings is tight. Moreover we prove that a bigger class of cubic bridgeless graphs admits Berge conjecture. Finally, we also show that Berge-Fulkerson conjecture holds for treelike snarks.

L'image de la ville de Bénarès (Kāśī, Varanasi) est liée à son ensemble de ghāṭ – berges en forme de gradins – qui se déploie de façon monumentale sur la rive concave d'un méandre du Gange. L'aménagement de ce front d'eau s'inscrit dans un contexte culturel particulier qui nécessite un rapport de proximité avec l'eau du fleuve. La construction et le développement de ce front d'eau dans le temps et la manière composite dont les éléments architecturaux s'y sont intégrés, interrogent aujourd'hui cette grande unité urbaine qui forme un espace public de plus de 6 km de long. L'objectif de cette thèse est de comprendre les éléments qui ont concouru à la naissance et au développement de ce front. La forme architecturale et urbaine du ghāṭ est considérée comme un dispositif construit modulable adapté à un milieu fluvial, à une topographie et à des pratiques liées à la culture du lieu, qui facilite l'accès à l'eau quel que soit son niveau. M'appuyant sur des images anciennes, sur une série d'enquêtes de terrain et de relevés architecturaux, ainsi que sur des plans de travaux officiels, j'étudie les techniques de construction face aux contraintes de l'eau, j'observe et j'analyse le dialogue de cette forme de berge avec la géographie et le paysage urbain pour en mieux approcher son architecture et j'explique la matérialisation du ghāṭ par les pratiques diverses qui s'y déploient et les parcours symboliques qui y font référence. La relation toute particulière que la ville entretient avec son fleuve par l'architecture des ghāṭ explique son potentiel urbanistique inhérent à son développement dans le temps et le long de la berge / The image of Benares (Kāśī, Varanasi) is closely associated to the architecture of its riverfront composed of ghats – steps and terraces – that stretch out in a monumental way on the concave bank of a meander formed by the river Ganges. The expansion of this riverfront has to be understood in relation to a cultural tradition that demands a close proximity to the waters of the river. The construction and development of this riverfront in time and the various ways in which each architectural element is integrated with the river bank, calls into question its impressive urban unity that forms a public space extending more than 6 km. The aim of this thesis is to identify the elements that have contributed to the origin and the development of this front. The architectural and urban form of the ghat is considered as a constructed flexible device adapted to a specific river environment, a characteristic topography and to practices linked to the culture of the place, which allows for easy access to the varying levels of the river's water level. Based on pictorial archives, interviews, measure drawings done on site and on official planners' drawings, I examine the techniques of hydraulic constructions best adapted to counter the river's currents, I observe and analyze the relations between the riverbank, the geography and the urban landscape so as to better approach the ghats' architecture and I explain the materialization of the ghat through the diverse practices and the symbolic trajectories that surround it. The particular relation that the city entertains with its river, through the architecture of ghats, explains its urban potential inherent to its development in time and space i.e. along its river bank

Es werden Prozesse der Verwitterung und des Stoffaustrages aus Halden des Kupferschieferbergbaus untersucht. An zwei Halden unterschiedlichen Typs und Alters wurden mineralogische und geochemische Untersuchungen durchgeführt. Die Ergebnisse belegen eine geringe Mobilität der Schwermetalle in den älteren Armerzhalden. In den modernen Großhalden stellt die Salinität ein mobilisierendes Moment für die Metalle dar. Aus den erhobenen standort- und stoffspezifischen Daten wurden unter Einbeziehung des Ionenwechselwirkungsansatzes nach PITZER geochemische Modellvorstellungen entwickelt, die eine adäquate Beschreibung der Lösungs- und Mischungsprozesse in der Halde sowie eine Prognose der künftigen Sickerwasserqualität erlauben. Die Ergebnisse werden im Hinblick auf die Umweltrelevanz und Möglichkeiten des weiteren Umgangs mit den Halden diskutiert.

Es werden Prozesse der Verwitterung und des Stoffaustrages aus Halden des Kupferschieferbergbaus untersucht. An zwei Halden unterschiedlichen Typs und Alters wurden mineralogische und geochemische Untersuchungen durchgeführt. Die Ergebnisse belegen eine geringe Mobilität der Schwermetalle in den älteren Armerzhalden. In den modernen Großhalden stellt die Salinität ein mobilisierendes Moment für die Metalle dar. Aus den erhobenen standort- und stoffspezifischen Daten wurden unter Einbeziehung des Ionenwechselwirkungsansatzes nach PITZER geochemische Modellvorstellungen entwickelt, die eine adäquate Beschreibung der Lösungs- und Mischungsprozesse in der Halde sowie eine Prognose der künftigen Sickerwasserqualität erlauben. Die Ergebnisse werden im Hinblick auf die Umweltrelevanz und Möglichkeiten des weiteren Umgangs mit den Halden diskutiert.

The main goal of this thesis is the evaluation of the environmental contamination risk from the tailings materials. In order to achieve this task, hydrogeological, mineralogical, geochemical, hydrochemical, and isotope studies were conducted at the uranium tailings Schneckenstein. Four cores were taken at the tailing sites by drilling to different depths. Two borings were located in each tailing respectively. Samples were collected at an interval of 1 m. From the study, the cover layers has a coefficient of permeability of approximately 10-5 m/s, whereas for the tailings material, it ranges between 10-8 and 10-7 m/s except the last two intervals of the fourth borehole. The dry density is very low, whereas the grain density exceed 2.7 g/cm³ in almost all the materials. The total porosity is very high exceeding 30 % in almost all tailings. In addition, the infiltration rate in the tailings is low with a mean value approximately 8.8 cm/a. Muscovite and quartz dominate the mineralogy of the tailing sediments. For the analysed elements, the non residual fraction is in association with the iron and manganese oxides. Hence, the decrease of the oxygen contents in the environment will increase their solubility. Assuming an equilibrium between most of the radionuclides in the uranium chain before the ore processing and assuming that radium has not left the system e.g. as solute in water, not more than about 70 % of the total uranium content was removed during the ore processing. Also, the presence of organic matter and sulphur in the tailings material are the major factors controlling the solubility of elements in the areas. The hydrochemical model PHREEQC shows high solubility of most of elements. It also shows the change in chemical conditions between the heap materials and the tailing sediments which is characterised by a decrease of the Eh values with depth. This indicates the change of the medium to post aerobic or anaerobic conditions.

The main goal of this thesis is the evaluation of the environmental contamination risk from the tailings materials. In order to achieve this task, hydrogeological, mineralogical, geochemical, hydrochemical, and isotope studies were conducted at the uranium tailings Schneckenstein. Four cores were taken at the tailing sites by drilling to different depths. Two borings were located in each tailing respectively. Samples were collected at an interval of 1 m. From the study, the cover layers has a coefficient of permeability of approximately 10-5 m/s, whereas for the tailings material, it ranges between 10-8 and 10-7 m/s except the last two intervals of the fourth borehole. The dry density is very low, whereas the grain density exceed 2.7 g/cm³ in almost all the materials. The total porosity is very high exceeding 30 % in almost all tailings. In addition, the infiltration rate in the tailings is low with a mean value approximately 8.8 cm/a. Muscovite and quartz dominate the mineralogy of the tailing sediments. For the analysed elements, the non residual fraction is in association with the iron and manganese oxides. Hence, the decrease of the oxygen contents in the environment will increase their solubility. Assuming an equilibrium between most of the radionuclides in the uranium chain before the ore processing and assuming that radium has not left the system e.g. as solute in water, not more than about 70 % of the total uranium content was removed during the ore processing. Also, the presence of organic matter and sulphur in the tailings material are the major factors controlling the solubility of elements in the areas. The hydrochemical model PHREEQC shows high solubility of most of elements. It also shows the change in chemical conditions between the heap materials and the tailing sediments which is characterised by a decrease of the Eh values with depth. This indicates the change of the medium to post aerobic or anaerobic conditions.

No description available.