A map is an embedding of the vertices and edges of a graph into a compact 2-manifold such that the remainder of the surface has components homeomorphic to open disks. With the goal of proving the Four Colour Theorem, Tutte began the field of map enumeration in the 1960's. His methods included developing the edge deletion decomposition, developing and solving a recurrence and functional equation based on this decomposition, and developing the medial bijection between two equinumerous infinite families of maps. Beginning in the 1980's Jackson, Goulden and Visentin applied algebraic methods in enumeration of non-planar and non-orientable maps, to obtain results of interest for mathematical physics and algebraic geometry, and the Quadrangulation Conjecture and the Map-Jack Conjecture. A special case of the former is solved by Tutte's medial bijection. The latter uses Jack symmetric functions which are a topic of active research. In the 1960's Walsh and Lehman introduced a method of encoding orientable maps. We develop a similar method, based on depth first search and extended to non-orientable maps. With this, we develop a bijection that extends Tutte's medial bijection and partially solves the Quadrangulation Conjecture. Walsh extended Tutte's recurrence for planar maps to a recurrence for all orientable maps. We further extend the recurrence to include non-orientable maps, and express it as a partial differential equation satisfied by the generating series. By appropriately interpolating the differential equation and applying the depth first search method, we construct a parameter that empirically fulfils the conditions of the Map-Jack Conjecture, and we prove some of its predicted properties. Arques and Beraud recently obtained a continued fraction form of a specialisation of the generating series for maps. We apply the depth search method with an ordinary differential equation, to construct a bijection whose existence is implied by the continued fraction.

A map is an embedding of the vertices and edges of a graph into a compact 2-manifold such that the remainder of the surface has components homeomorphic to open disks. With the goal of proving the Four Colour Theorem, Tutte began the field of map enumeration in the 1960's. His methods included developing the edge deletion decomposition, developing and solving a recurrence and functional equation based on this decomposition, and developing the medial bijection between two equinumerous infinite families of maps. Beginning in the 1980's Jackson, Goulden and Visentin applied algebraic methods in enumeration of non-planar and non-orientable maps, to obtain results of interest for mathematical physics and algebraic geometry, and the Quadrangulation Conjecture and the Map-Jack Conjecture. A special case of the former is solved by Tutte's medial bijection. The latter uses Jack symmetric functions which are a topic of active research. In the 1960's Walsh and Lehman introduced a method of encoding orientable maps. We develop a similar method, based on depth first search and extended to non-orientable maps. With this, we develop a bijection that extends Tutte's medial bijection and partially solves the Quadrangulation Conjecture. Walsh extended Tutte's recurrence for planar maps to a recurrence for all orientable maps. We further extend the recurrence to include non-orientable maps, and express it as a partial differential equation satisfied by the generating series. By appropriately interpolating the differential equation and applying the depth first search method, we construct a parameter that empirically fulfils the conditions of the Map-Jack Conjecture, and we prove some of its predicted properties. Arques and Beraud recently obtained a continued fraction form of a specialisation of the generating series for maps. We apply the depth search method with an ordinary differential equation, to construct a bijection whose existence is implied by the continued fraction.

The present work consists of three parts. In the first part (chapters III and IV), the dynamics of Lorentz lattice gases (LLG) on graphs is analyzed. We study the fixed scatterer model on finite graphs. A tight bound is established on the size of the orbit for arbitrary graphs, and the model is shown to perform a depth-first search on trees. Rigidity models on trees are also considered, and the size of the resulting orbit is established. In the second part (chapter V), we give a complete description of dynamics for LLG on the one-dimensional integer lattice, with a particular interest in showing that these models are not capable of universal computation. Some statistical properties of these models are also analyzed. In the third part (chapter VI) we attempt to partition a pool of workers into teams that will function as independent TSS lines. Such partitioning may be aimed to make sure that all groups work at approximately the same rate. Alternatively, we may seek to maximize the rate of convergence of the corresponding dynamical systems to their fixed points with optimal production at the fastest rate. The first problem is shown to be NP-hard. For the second problem, a solution for splitting into pairs is given, and it is also shown that this solution is not valid for partitioning into teams composed of more than two workers.

In recent years, the music has become popular due to the evolution of the technology. Various kinds of music around us become complexities and huge. The explosive growth in the music has generated the urgent need for new techniques and tools that can intelligently and automatically transform the music into useful information. Many researches consider the music object as an continuously discrete note in time order. Repeating patterns are some subsequences which appear frequently in the music sequence. The repeating patterns usually can represent the theme of a music object. Moreover, it also can be utilized in music classification. Many methods have been proposed for finding the repeating patterns in music objects, for example, the M2P (Mining Maximum-length Patterns) method. It constructs a directed graph and uses the depth-first search to traverse the graph. It calculates the paths by the string matching algorithm to decide whether they are repeating pattern, and finds out the maximum-length repeating pattern in a music sequence. Although the M2P method is a straightforward method to find out the patterns, it consumes time in creating too many candidate patterns and performing the string matching algorithm. Therefore, in this thesis, we propose the PJ (Position-Join) method to efficiently find out the maximum-length repeating pattern. In the constructing graph step, we find out that we can modify the information in the graph, and avoid to use the string matching algorithm to decide whether a path is repeating pattern. We record the positions of length two repeating patterns in the matrix. While traversing the graph, we calculate the frequency by the information of positions. Moreover, we record the repeated path by the positions. We create terminal edges, and record the information of paths which have been traversed. We dynamically modify the graph by terminal edges. It can avoid to traverse some paths repeatedly in traversing the graph step. From our performance study based on the synthetic data and real music data, we show that our proposed PJ method is more efficient than the M2P method.

The diploma thesis deals with creating of electronic schematics in editor using web interface. The editor generates electrical circuit text file according to Spice netlist specification. The program has been created in Java and takes an advantage of object oriented programming language. The editor is a part of a web page and is executable as an applet. The diploma thesis describes a programming language selection, program layout and implementation. Thesis contains programming code examples, window illustration and component drawings. Depth-first search algorithm has been used for nodes number assignment. An OrCAD PSpice reference guide was used for netlist.

No description available.

Esta pesquisa trata o Problema de Programação de Tripulantes (PPT), presente no planejamento operacional das empresas aéreas. O principal objetivo do PPT é atribuir um conjunto de tarefas aos tripulantes, considerando as regulamentações trabalhistas, as regras de segurança e as políticas das empresas, de tal maneira que o custo da tripulação seja mínimo. O PPT é normalmente dividido em dois subproblemas, resolvidos sequencialmente: Problema de Determinação das Viagens (PDV) e Problema de Atribuição de Escalas (PAE). No PDV, determina-se um conjunto de viagens que cubra todos os voos planejados. Em seguida, no PAE, as escalas, compostas pelas viagens escolhidas e outras atividades como folgas, sobreavisos, reservas, treinamentos e férias, são atribuídas aos tripulantes. Esta decomposição justifica-se pela natureza combinatória do PPT, porém não incorpora as disponibilidades e as preferências dos tripulantes em ambos os subproblemas (PDV e PAE), gerando assim custos extras relacionados aos conflitos que surgem durante a atribuição das escalas aos tripulantes no PAE. Além disso, as estimativas de custos adotadas no PDV não possuem caráter global, já que o custo real da programação só pode ser obtido após a atribuição das escalas. O estado da arte envolve a solução integrada do PPT, em que se elimina a necessidade de resolver inicialmente o PDV, provendo assim uma melhor estimativa de custo e uma programação final com melhor qualidade, por considerar os custos da tripulação, as disponibilidades e preferências dos tripulantes de forma global. O problema, no entanto, é NP-Difícil. Assim sendo, a metodologia proposta nesta pesquisa objetiva a solução do PPT de forma integrada, através de um Algoritmo Genético Híbrido (AGH) associado a um procedimento de busca em profundidade, levando em conta as particularidades da legislação brasileira. A metodologia foi testada, com sucesso, para a solução de instâncias baseadas na malha real de uma empresa aérea brasileira. / This master of science research treats the Crew Scheduling Problem (CSP), as part of the airlines operational planning. The main aim of the CSP is to assign a set of tasks to crew members, considering the labor regulations, safety rules and policies of companies, such that the crew cost is minimal. The CSP is divided into two subproblems, solved sequentially: Crew Pairing Problem (CPP) and Crew Rostering Problem (CRP). First, CPP provides a set of pairings that covers all the planned flights. Then, in the CRP, the rosters, encompassing the pairings and other activities such as rest periods, alert duties, reserve duties, training times and vacations, are assigned to the crew members. This decomposition is justified by the combinatorial nature of the CSP, but it not incorporates the crew members availabilities and preferences in both subproblems (CPP and CRP), generating extra costs related to conflicts that arise during the assignment of rosters to the crew members in the CRP. Besides, the costs estimations adopted in the CPP does not have a global character, since the real cost of the global schedule can be only obtained after the assignment of the rosters. The state of the art involves the integrated solution of CSP, where the CPP does not need to be solved, thus providing a better estimated cost and a better schedule quality, considering crew costs and also crew members availabilities and preferences globally. The problem, however, is NP-Hard. Therefore, the methodology proposed in this master of science research aims to obtain an integrated solution of the CSP, through an hybrid algorithm genetic associated with a depth-first search procedure, taking into account the Brazilian legislation. The methodology was tested, with success, to solve instances related a real network of a Brazilian airline.

Esta pesquisa trata o Problema de Programação de Tripulantes (PPT), presente no planejamento operacional das empresas aéreas. O principal objetivo do PPT é atribuir um conjunto de tarefas aos tripulantes, considerando as regulamentações trabalhistas, as regras de segurança e as políticas das empresas, de tal maneira que o custo da tripulação seja mínimo. O PPT é normalmente dividido em dois subproblemas, resolvidos sequencialmente: Problema de Determinação das Viagens (PDV) e Problema de Atribuição de Escalas (PAE). No PDV, determina-se um conjunto de viagens que cubra todos os voos planejados. Em seguida, no PAE, as escalas, compostas pelas viagens escolhidas e outras atividades como folgas, sobreavisos, reservas, treinamentos e férias, são atribuídas aos tripulantes. Esta decomposição justifica-se pela natureza combinatória do PPT, porém não incorpora as disponibilidades e as preferências dos tripulantes em ambos os subproblemas (PDV e PAE), gerando assim custos extras relacionados aos conflitos que surgem durante a atribuição das escalas aos tripulantes no PAE. Além disso, as estimativas de custos adotadas no PDV não possuem caráter global, já que o custo real da programação só pode ser obtido após a atribuição das escalas. O estado da arte envolve a solução integrada do PPT, em que se elimina a necessidade de resolver inicialmente o PDV, provendo assim uma melhor estimativa de custo e uma programação final com melhor qualidade, por considerar os custos da tripulação, as disponibilidades e preferências dos tripulantes de forma global. O problema, no entanto, é NP-Difícil. Assim sendo, a metodologia proposta nesta pesquisa objetiva a solução do PPT de forma integrada, através de um Algoritmo Genético Híbrido (AGH) associado a um procedimento de busca em profundidade, levando em conta as particularidades da legislação brasileira. A metodologia foi testada, com sucesso, para a solução de instâncias baseadas na malha real de uma empresa aérea brasileira. / This master of science research treats the Crew Scheduling Problem (CSP), as part of the airlines operational planning. The main aim of the CSP is to assign a set of tasks to crew members, considering the labor regulations, safety rules and policies of companies, such that the crew cost is minimal. The CSP is divided into two subproblems, solved sequentially: Crew Pairing Problem (CPP) and Crew Rostering Problem (CRP). First, CPP provides a set of pairings that covers all the planned flights. Then, in the CRP, the rosters, encompassing the pairings and other activities such as rest periods, alert duties, reserve duties, training times and vacations, are assigned to the crew members. This decomposition is justified by the combinatorial nature of the CSP, but it not incorporates the crew members availabilities and preferences in both subproblems (CPP and CRP), generating extra costs related to conflicts that arise during the assignment of rosters to the crew members in the CRP. Besides, the costs estimations adopted in the CPP does not have a global character, since the real cost of the global schedule can be only obtained after the assignment of the rosters. The state of the art involves the integrated solution of CSP, where the CPP does not need to be solved, thus providing a better estimated cost and a better schedule quality, considering crew costs and also crew members availabilities and preferences globally. The problem, however, is NP-Hard. Therefore, the methodology proposed in this master of science research aims to obtain an integrated solution of the CSP, through an hybrid algorithm genetic associated with a depth-first search procedure, taking into account the Brazilian legislation. The methodology was tested, with success, to solve instances related a real network of a Brazilian airline.

No description available.

Background. Procedural Content Generation (PCG) in Video Games can be used as a tool for efficiently producing large varieties of new content using less manpower, making it ideal for smaller teams of developers who wants to compete with games made by larger teams. One particular facet of PCG is the generation of mazes. Designers that want their game to feature mazes also need to know how to evaluate their maze-complexity, in order to know which maze fits the difficulty curve best. Objectives. This project aims to investigate the difference in complexity between the maze generation algorithms recursive backtracker (RecBack), Prim’s algorithm (Prims), and recursive division (RecDiv), in terms completion time, when solved using a depth-first-search (DFS) algorithm. In order to understand which parameters affect completion time/complexity, investigate possible connections between completion time, and the distribution of branching paths, distribution of corridors, and length of the path traversed by DFS. Methods. The main methodology was an implementation in the form of a C# application, which randomly generated 100 mazes for each algorithm for five different maze grid resolutions (16x16, 32x32, 64x64, 128x128, 256x256). Each one of the generated mazes was solved using a DFS algorithm, whose traversed nodes, solving path, and completion time was recorded. Additionally, branch distribution and corridor distribution data was gathered for each generated maze. Results. The initial results showed that mazes generated by Prims algorithm had the lowest complexity (shortest completion time), the shortest solving path, the lowest amount of traversed nodes, and the lowest proportion of 2-branches, but the highest proportion of all other branch types. Additionally Prims had the highest proportion of 4-6 length paths, but the lowest proportion of 2 and 3 length paths. Later mazes generated by RecDiv had intermediate complexity, intermediate solving path, intermediate traversed nodes, intermediate proportion of all branch types, and the highest proportion of 2-length paths, but the lowest proportion of 4-6 length paths. Finally mazes generated by RecBack had opposite statistics from Prims: the highest complexity, the longest solving path, the highest amount of traversed nodes, the highest proportion of 2-branches, but lowest proportion of all other branch types, and the highest proportion of 3-length paths, but the lowest of 2-length paths. Conclusions. Prims algorithm had the lowest complexity, RecDiv intermediate complexity, and RecBack the highest complexity. Increased solving path length, traversed nodes, and increased proportions of 2-branches, seem to correlate with increased complexity. However the corridor distribution results are too small and diverse to identify a pattern affecting completion time. However the corridor distribution results are too diverse to make it possible to discern a pattern affecting completion time by just observing the data.