Made available in DSpace on 2015-05-14T12:36:51Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1355559 bytes, checksum: fe1c88470e43ce75f706ec9d15cc7bb1 (MD5) Previous issue date: 2014-07-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / With the advent of technological advances, increasingly demand solutions that use fewer resources, are faster and low cost. As a result, this paper proposed a hybrid approach using metaheuristics Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Local Search (ILS) applied to the Response Time Variability Problem (RTVP). Since this problem may involve allocation of scarce resources, such as industrial machinery or meeting rooms, going for scheduling of banking customers that require certain conditions, planning of TV ads or route taken by vehicles of logistic companies, etc. For application of the procedure, the movements of shifting symbols, swapping positions between symbols and one called double bridge, which is a mix of movements of shifting and swapping involving opposite symbols were used. The neighborhood structures were based on the movements described above, varying the number of symbols involved. Thus, the results obtained demonstrate that such procedures satisfied the problem and brought consistent results when compared with the literature. / Com o advento dos avanços tecnológicos, cada vez mais se procura soluções que utilizem menos recursos, sejam mais rápidos e de baixo custo. Em virtude disso, este trabalho propôs uma abordagem meta-heurística híbrida utilizando Greedy Randomized Adaptive Search Procedure (GRASP) e Iterated Local Search (ILS) aplicados ao Problema da Variabilidade do Tempo de Resposta. Este problema pode envolver desde alocação de recursos escassos, como por exemplo, máquinas industriais ou salas de reunião, passando pelo agendamento de clientes de um banco que requerem certas condições, o planejamento das propagandas de TV ou o percurso feito por caminhões de empresas transportadoras, dentre outros. Para a aplicação do procedimento, foram utilizados os movimentos de deslocamento do mesmo, permuta de posição entre símbolos e de um movimento chamado double brigde, que é uma mistura dos movimentos de deslocamento e permutação envolvendo símbolos opostos. As estruturas de vizinhança compostas basearam-se nos movimentos descritos anteriormente, variando a quantidade de símbolos envolvidos. Desta forma, os resultados obtidos demonstram que tais procedimentos trouxeram resultados satisfatórios ao problema e condizentes quando comparados com a literatura.

Made available in DSpace on 2015-05-14T12:36:54Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 2485062 bytes, checksum: ad2a2349ad56d837e75386f8c9ba1027 (MD5) Previous issue date: 2010-03-27 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The present dissertation deals with the Routing Circuits for Field Programable Gate Arrays (FPGAs). Due to the combinatorial nature of the problem, heuristics methods are commonly used to generate good quality solutions in an acceptable computationally time. In this context, a procedure based on GRASP (Greedy Randomized Adaptive Search Procedure) with a procedure of local search based on ILS (Iterated Local Search) is proposed. The algorithm has been tested in benchmark problems found in the literature, MCNC, exploring timing-driven and channel-width criteria, being able to improve 55% of the benchmarks on timing drive criteria and improve 5,3% of the benchmarks on channel width criteria. / A presente dissertação trata do problema de roteamento de circuitos para Field Programable Gate Arrays (FPGAs). Em função da natureza combinatória do problema, métodos heurísticos são comumente utilizados para gerar soluções de boa qualidade em um tempo computacionalmente aceitável. Neste contexto, um procedimento baseado na metaheurística GRASP (Greedy Randomized Adaptive Search Procedure) com um procedimento de busca local baseado em ILS (Iterated Local Search) é proposto. O algoritmo foi testado em instâncias encontradas na literatura, benchmark MCNC, explorando os critérios de tempo crítico e números de trilhas, onde mostrou-se capaz de melhorar 55% das instancias no critério de tempo crítico e 5,3% quanto ao número de trilhas.

Games have been investigated as computationally complex problems since the inception of artificial intelligence in the 1950’s. Originally, search-based techniques were applied to create a competent (and sometimes even expert) game player. The search-based techniques, such as game trees, made use of human-defined knowledge to evaluate the current game state and recommend the best move to make next. Recent research has shown that neural networks can be evolved as game state evaluators, thereby removing the human intelligence factor completely. This study builds on the initial research that made use of evolutionary programming to evolve neural networks in the game learning domain. Particle Swarm Optimisation (PSO) is applied inside a coevolutionary training environment to evolve the weights of the neural network. The training technique is applied to both the zero sum and non-zero sum game domains, with specific application to Tic-Tac-Toe, Checkers and the Iterated Prisoners Dilemma (IPD). The influence of the various PSO parameters on playing performance are experimentally examined, and the overall performance of three different neighbourhood information sharing structures compared. A new coevolutionary scoring scheme and particle dispersement operator are defined, inspired by Formula One Grand Prix racing. Finally, the PSO is applied in three novel ways to evolve strategies for the IPD – the first application of its kind in the PSO field. The PSO-based coevolutionary learning technique described and examined in this study shows promise in evolving intelligent evaluators for the aforementioned games, and further study will be conducted to analyse its scalability to larger search spaces and games of varying complexity. / Dissertation (MSc)--University of Pretoria, 2005. / Computer Science / unrestricted

In this dissertation we focus on the application of thermodynamic formalism to non-autonomous and random dynamical systems. Specifically we use the thermodynamic formalism to investigate the dimension of various fractal constructions via the, now standard, technique of Bowen which he developed in his 1979 paper on quasi-Fuchsian groups. Bowen showed, roughly speaking, that the dimension of a fractal is equal to the zero of the relevant topological pressure function. We generalize the results of Rempe-Gillen and Urbanski on non-autonomous iterated function systems to the setting of non-autonomous graph directed Markov systems and then show that the Hausdorff dimension of the fractal limit set is equal to the zero of the associated pressure function provided the size of the alphabets at each time step do not grow too quickly. In trying to remove these growth restrictions, we present several other systems for which Bowen's formula holds, most notably ascending systems. We then use these various constructions to investigate the Hausdorff dimension of various subsets of the Julia set for different large classes of transcendental meromorphic functions of finite order which have been perturbed non-autonomously. In particular we find lower and upper bounds for the dimension of the subset of the Julia set whose points escape to infinity, and in many cases we find the exact dimension. While the upper bound was known previously in the autonomous case, the lower bound was not known in this setting, and all of these results are new in the non-autonomous setting. We also use transfer operator techniques to prove an almost sure invariance principle for random dynamical systems for which the thermodynamical formalism has been well established. In particular, we see that if a system exhibits a fiberwise spectral gap property and the base dynamical system is sufficiently well behaved, i.e. it exhibits an exponential decay of correlations, then the almost sure invariance principle holds. We then apply these results to uniformly expanding random systems like those studied by Mayer, Skorulski, and Urbanski and Denker and Gordin.

For a dynamical system on a metric space a shrinking-target set consists of those points whose orbit hit a given ball of shrinking radius infinitely often. Historically such sets originate in Diophantine approximation, in which case they describe the set of well-approximable numbers. One aspect of such sets that is often studied is their Hausdorff dimension. We will show that an analogue of Bowen's dimension formula holds for such sets when they are generated by conformal non-autonomous iterated function systems satisfying some natural assumptions.

The aim of this thesis is to develop the dimension theory of self-affine carpets in several directions. Self-affine carpets are an important class of planar self-affine sets which have received a great deal of attention in the literature on fractal geometry over the last 30 years. These constructions are important for several reasons. In particular, they provide a bridge between the relatively well-understood world of self-similar sets and the far from understood world of general self-affine sets. These carpets are designed in such a way as to facilitate the computation of their dimensions, and they display many interesting and surprising features which the simpler self-similar constructions do not have. For example, they can have distinct Hausdorff and packing dimensions and the Hausdorff and packing measures are typically infinite in the critical dimensions. Furthermore, they often provide exceptions to the seminal result of Falconer from 1988 which gives the `generic' dimensions of self-affine sets in a natural setting. The work in this thesis will be based on five research papers I wrote during my time as a PhD student. The first contribution of this thesis will be to introduce a new class of self-affine carpets, which we call box-like self-affine sets, and compute their box and packing dimensions via a modified singular value function. This not only generalises current results on self-affine carpets, but also helps to reconcile the `exceptional constructions' with Falconer's singular value function approach in the generic case. This will appear in Chapter 2 and is based on a paper which appeared in 'Nonlinearity' in 2012. In Chapter 3 we continue studying the dimension theory of self-affine sets by computing the Assouad and lower dimensions of certain classes. The Assouad and lower dimensions have not received much attention in the literature on fractals to date and their importance has been more related to quasi-conformal maps and embeddability problems. This appears to be changing, however, and so our results constitute a timely and important contribution to a growing body of literature on the subject. The material in this Chapter will be based on a paper which has been accepted for publication in 'Transactions of the American Mathematical Society'. In Chapters 4-6 we move away from the classical setting of iterated function systems to consider two more exotic constructions, namely, inhomogeneous attractors and random 1-variable attractors, with the aim of developing the dimension theory of self-affine carpets in these directions. In order to put our work into context, in Chapter 4 we consider inhomogeneous self-similar sets and significantly generalise the results on box dimensions obtained by Olsen and Snigireva, answering several questions posed in the literature in the process. We then move to the self-affine setting and, in Chapter 5, investigate the dimensions of inhomogeneous self-affine carpets and prove that new phenomena can occur in this setting which do not occur in the setting of self-similar sets. The material in Chapter 4 will be based on a paper which appeared in 'Studia Mathematica' in 2012, and the material in Chapter 5 is based on a paper, which is in preparation. Finally, in Chapter 6 we consider random self-affine sets. The traditional approach to random iterated function systems is probabilistic, but here we allow the randomness in the construction to be provided by the topological structure of the sample space, employing ideas from Baire category. We are able to obtain very general results in this setting, relaxing the conditions on the maps from `affine' to `bi-Lipschitz'. In order to get precise results on the Hausdorff and packing measures of typical attractors, we need to specialise to the setting of random self-similar sets and we show again that several interesting and new phenomena can occur when we relax to the setting of random self-affine carpets. The material in this Chapter will be based on a paper which has been accepted for publication by 'Ergodic Theory and Dynamical Systems'.

This thesis concerns an active research area within fractal geometry. In the first part, in Chapters 2 and 3, for directed graph iterated function systems (IFSs) defined on ℝ, we prove that a class of 2-vertex directed graph IFSs have attractors that cannot be the attractors of standard (1-vertex directed graph) IFSs, with or without separation conditions. We also calculate their exact Hausdorff measure. Thus we are able to identify a new class of attractors for which the exact Hausdorff measure is known. We give a constructive algorithm for calculating the set of gap lengths of any attractor as a finite union of cosets of finitely generated semigroups of positive real numbers. The generators of these semigroups are contracting similarity ratios of simple cycles in the directed graph. The algorithm works for any IFS defined on ℝ with no limit on the number of vertices in the directed graph, provided a separation condition holds. The second part, in Chapter 4, applies to directed graph IFSs defined on ℝⁿ . We obtain an explicit calculable value for the power law behaviour as r → 0⁺ , of the qth packing moment of μ[subscript(u)], the self-similar measure at a vertex u, for the non-lattice case, with a corresponding limit for the lattice case. We do this (i) for any q ∈ ℝ if the strong separation condition holds, (ii) for q ≥ 0 if the weaker open set condition holds and a specified non-negative matrix associated with the system is irreducible. In the non-lattice case this enables the rate of convergence of the packing L[superscript(q)]-spectrum of μ[subscript(u)] to be determined. We also show, for (ii) but allowing q ∈ ℝ, that the upper multifractal q box-dimension with respect to μ[subscript(u)], of the set consisting of all the intersections of the components of F[subscript(u)], is strictly less than the multifractal q Hausdorff dimension with respect to μ[subscript(u)] of F[subscript(u)].

Logic-based formalizations of dynamical systems are central to the field of knowledge representation and reasoning. These formalizations can be used to model agents that act, reason,and perceive in a changing and incompletely known environment. A key aspect of reasoning about agents and their behaviors is the notion of joint ability. A team of agents is jointly able to achieve a goal if despite any incomplete knowledge or even false beliefs about the world or each other, they still know enough to be able to get to a goal state, should they choose to do so. A particularly challenging issue associated with joint ability is how team members can coordinate their actions. Existing approaches often require the agents to communicate to agree on a joint plan. In this thesis, we propose an account of joint ability that supports coordination among agents without requiring communication, and that allows for agents to have incomplete (or even false) beliefs about the world or the beliefs of other agents. We use ideas from game theory to address coordination among agents. We introduce the notion of a strategy for each agent which is basically a plan that the agent knows how to follow. Each agent compares her strategies and iteratively discards those that she believes are not good considering the strategies that the other agents have kept. Our account is developed in the situation calculus, a logical language suitable for representing and reasoning about action and change that is extended to support reasoning about multiple agents. Through several examples involving public, private, and sensing actions, we demonstrate how symbolic proof techniques allow us to reason about team ability despite incomplete specifications about the beliefs of agents.

Neste trabalho estudamos relações entre expoente de Lyapunov e continuidade absoluta da folheação central para difeomorfismos parcialmente hiperbólicos conservativos de \'T POT. 3\'. Sobre tal tema, provamos que tipicamente (\'C POT. 1\' aberto e \'C POT. 2\' denso) os difeomorfismos parcialmente hiperbólicos, conservativos de classe \'C POT. 2\' , do toro \'T POT. 3\', apresentam folheação central não absolutamente contínua. Desta maneira, respondemos positivamente uma pergunta proposta em [20]. Também neste trabalho, estudamos entropia topológica para Sistema Iterado de Funções. Neste contexto, damos uma nova demonstração para uma conjectura proposta em [14] e provada primeiramente em [15]. Apresentamos um método geométrico que nos permite calcular entropia para transformações de \'S POT. 1\', como em [15]. Além de disso o método apresentado se verifica para casos mais gerais, como por exemplo: transformações não comutativas / In this work we study relations between Lyapunov exponents, absolute continuity of center foliation for conservative partially hyperbolic diffeomorphisms of \'T POT. 3\'. About this theme, (on a \'C POT. 1\' open and \'C POT. 2\'dense set) of conservative partially hyperbolic \'C POT. 2\' diffeomorphisms of the 3-torus presents non absolutely continuous center foliation. So, we answer positively a question proposed in [20]. Also in this work, we study topological entropy for Iterated Functions Systems. In this setting, we give a proof for a conjecture proposed in [14] and firstly proved in [15]. We present a geometrical method that allows us to calcule the entropy for transformations of \'S POT. 1\', like in [15]. Furthermore this method holds for more general cases, for example: non commutative transformations

Esse trabalho é um estudo sobre circuitos resistivos que apresentam a característica da autossimilaridade em sua configuração. A construção desses circuitos é feita de uma maneira recursiva, de forma análoga a um fractal autossimilar. Os circuitos são analisados pelas suas resistências equivalentes, sendo obtida uma condição para convergência desse valor. Os conceitos auxiliares necessários ao tema desta dissertação abordam a representação de um circuito resistivo como um grafo, além de conceitos envolvendo fractais autossimilares. São propostas ao final de cada capítulo atividades interdisciplinares acessíveis a alunos de ensino médio, com conteúdos envolvendo resistência equivalente, sequências, conjuntos, e noções de área e perímetro. / This work is a study of resistive circuits which present a characteristic of self similarity in their configuration. The construction of these circuits is made in a self recursive way, analogously to a self similar fractal. The circuits are analyzed by their equivalent resistance, and a condition for convergence of this quantity is obtained. Auxiliary concepts that are necessary to this dissertation theme treat the resistive circuit as a graph, and concepts involving self similar fractals. It is proposed at the end of each chapter interdisciplinary activities that are accessible to high school students, with topics involving equivalent resistence, sequences, sets, and notions of area and perimeter.