Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção. / Made available in DSpace on 2012-10-24T00:08:15Z (GMT). No. of bitstreams: 1 262017.pdf: 4380391 bytes, checksum: 4f3403a867051baad0790b3d60c9aedc (MD5) / Este trabalho tem por finalidade o desenvolvimento de uma ferramenta computacional baseada em conceitos de Diagramas de Voronoi e Programação Não-linear para estudar e definir o espaçamento ideal entre paradas de transporte coletivo de uma região urbana com o objetivo de minimizar o tempo médio de viagem dos passageiros até o seu destino. Foi utilizada como parâmetro a densidade demográfica da região afetada pela linha como parâmetro de demanda de utilização da linha. Ao final, aplica-se a ferramenta a uma região metropolitana com os dados reais disponíveis de sua densidade demográfica. Os resultados obtidos demonstraram a possibilidade de redução do número de paradas existentes atualmente, com redução no tempo de viagem dos usuários. O sistema também resolveu problemas de divisão regional de áreas afetas às paradas determinando a região de abrangência de cada uma delas. This work has the purpose to develop a computational tool based on the concepts of Voronoi Diagrams and Non-linear Programming to study and define the ideal bus-stop spacing in urban areas in order to minimize the total travel time of all passengers until their destination. The demographic density of the region was used as a parameter of the demand of the region. The tool will be applied to a metropolitan region with real data available about the population density function. The results showed that it is possible to reduce the number of bus stops with a considerable reduction in the travel time of the users. The model also solved problems of regional division of the affected areas to each bus-stop determining the scope area of each one of them.

[pt] A organização lógica de data centers recai principalmente na questão estratégica de distribuir os serviços nos equipamentos de forma que os custos operacionais sejam os menores possíveis. Além desses custos, devem ser considerados outros aspectos que envolvem a interdependência de seus serviços internos e a distribuição entre suas localidades, visando assim melhorar a qualidade de seu produto aos seus clientes. Este trabalho explora o problema de atribuição de processos a máquinas do desafio ROADEF de 2012 pelos métodos de programação inteira e geração de colunas. Apresenta estratégias para lidar com as dificuldades numéricas encontradas. Na geração de colunas, analisa técnicas para acelerar a convergência, por meio de resolver o mestre restrito após cada variável, geração prévia de colunas e estabilização das variávies duais. Ao final do trabalho, são comparados os resultados obtidos com os melhores resultados oficiais. / [en] A data center logic organization lies mainly by the strategic decision on how distribute services between machines, so the operational costs should be the smallest as possible. Beside those costs, must also consider the interdependence of their own services, the distribution between their localities, to improve the quality of their product to their customers. This work explores the challenge ROADEF 2012 machine assignment problem by the means of integer programming and column generation. Shows strategies to address numeric issues. At column generation, it analyzes techniques to speed up the convergence, by solving after each variable adiction, a previous generation of columns and stabilization of duals variables. At the end of the work, it compares the results obtained are compared with the best official results.

[pt] Os problemas de transporte marítimo são alvo de extensa bibliografia e constituem uma importante área de aplicação da programação matemática. Em particular, o transporte de granéis - entre os quais o petróleo e seus derivados - vem sendo estudado na Petrobrás há mais de duas décadas. Apesar dos esforços despendidos, os escopos das aplicações são ainda algo limitados e os resultados práticos relativamente escassos. O presente trabalho contribui para sistematização da área, definindo uma hierarquia de problemas de transporte marítimo, padronizando conceitos e notação e desenvolvendo modelos para cada classe de aplicação. São discutidos também alguns métodos de solução e propostos procedimentos para incrementar seus desempenhos. Dois destes métodos, designados por modelo de rotas e modelo de recobrimento, são implementados para instâncias de porte real e os resultados obtidos são analisados. / [en] Sea transportation problems have been the object of extensive literature and constitute an important area for the application of mathematical programming techniques. Bulk commodities transportation, particulary of oil and its by-products, has been studied at Petrobras for over two decades. Despite all efforts, the application scopes are still rather limeted and practical results relatively scarce. The present study contributes for a systenatization in the area, defining a hierarchy of sea transportation problems, standardizing concepts and terminology and developing models for each class of application. Some solution methods are also discussed and procedures are proposed to develop their performance. Two of these methods, named Routing model and instances and the results attained are anlysed.

[pt] O uso de multithreading tem se popularizado como forma de separar a execução de tarefas concorrentes e de alcançar maior desempenho aproveitando melhor o tempo das CPUs. No entanto, a programação com threads não é uma tarefa fácil. O uso dos recursos compartilhados deve ser coordenado, pois o acesso concorrente aos mesmos, na maioria dos casos, gera inconsistência na aplicação. O modelo de desenvolvimento orientado a eventos foi apontado por alguns como uma boa alternativa na criação de aplicações. Nesse modelo, a tarefa é realizada por um ou mais eventos, e um loop principal fica responsável por receber e despachar esses eventos. Investigamos, neste trabalho, um modelo em Lua que combina orientação a eventos com preempção sem trazer de volta os problemas de programação concorrente. Investigamos também como características da linguagem podem ser utilizadas para prover mecanismos de coordenação flexíveis. Essas características podem ajudar, por exemplo, a compor novos mecanismos a partir de existentes. / [en] Multithreading has become popular as a way to organize concurrent tasks and achieve better performance from CPUs. However, programming with threads is not an easy task. Usage of shared resources needs to be coordinated because concurrent access to them, in most cases, may create inconsistency in the application. The event-driven model has been pointed as a good alternative to multithreaded programming. In this model, a task is performed by one or more events, where a main loop is responsible for receiving and dispatching these events. In this work, we investigate a model to combine event-driven and preemption in Lua without bringing back all the concurrent programming problems. We also investigate how the language’s characteristics can be used to provide flexible coordination mechanisms. These characteristics can aid, for example, to create new mechanisms based on the ones already existent.

[pt] Este trabalho se propõe a estudar a mídia televisiva a partir de um mecanismo estratégico utilizado pela Rede Globo de Televisão, que pretende criar uma interação permanente entre a audiência e o conteúdo de suas novelas. A pesquisa estuda as relações que, através desse mecanismo, a emissora de televisão pretende estabelecer com seus telespectadores. Além de estudar as repercussões dessa estratégia massiva e permanente nos ambientes culturais da contemporaneidade, esse trabalho desvenda de que forma a mídia de chamadas de programação de uma telenovela é confeccionada, mostrando os instrumentos usados pela Rede Globo para alcançar seu objetivo de agendamento de seus temas junto à audiência. Investiga também, de que maneira essa mídia de chamada de programação pretende incorporar o conteúdo da telenovela nos discursos interpessoais. / [en] This work intends to study television media starting from a strategic mechanism used by Rede Globo de Televisão (Globo TV Network) that pretends to create a permanent interaction between the viewers and the contents of its soapoperas. The research will study the relations pretended to be established by the network with its audience through this mechanism. Aside of studying the repercussions of this massive and permanent strategy in cultural environment, this work will unmask how the commercial break calls media of a soap-opera is made, showing the instruments used by Globo Network to reach the aims of scheduling its themes next to the audience. It will investigate too by which means this media of commercial break calls intends to incorporate the soapopera s content in interpersonal speech.

Este trabalho apresenta um mapeamento centrado nas construções não usuais da linguagem Nautilus, para a linguagem convencional, no caso Java, mantendo propriedades com atomicidade que são requisitos da semântica formal da linguagem. Nautilus é originalmente uma linguagem de especificação baseada em objetos, textual que suporta objetos concorrentes e não deterministas. Desde então a linguagem foi modificada aom extensões como classes e uma notação diagramática, além de se investigar seu uso como linguagem de programação. Suas construções incomuns (reificação, agregação, etc.) são baseados em seu domínio semântico: Automâtos Não Sequenciais. Este domíno satisfaz composição diagonal, i.e refinamentos se compõem (verticalmente) refletindo uma descrição gradual de sistemas, envolvendo múltiplos níveis de abstração, e distribui-se através de combinadores (horizontalmente), o que significa que o refinamento de um sistema composto é a combinação de do refinamento de suas partes.O trabalho inclui um mapeamento inicial de um subconjunto da linguagem(objeto base, reificação, agregação e visão), uma versão ampliada para abranger mais construções( interação e classes), e uma versão refinada mais concorrente e sugestões de modificação na linguagem.

o objetivo deste trabalho é apresentar a implementação em Java de uma máquina abstrata para execução distribuída de programas funcionais. Mostra-se como as facilidades da linguagem Java foram utilizadas para a implementação de uma linguagem funcional paralela que roda os programas funcionais de forma distribuída em uma rede de computadores. Linguagens Funcionais geralmente são implementadas usando uma máquina abstrata para a execução dos programas. Essas máquinas são usualmente máquinas de redução de grafos. Para se rodar os programas funcionais na máquina virtual Java implementou-se a máquina de redução de grafos G-Machine em Java. Nesta dissertação, apresenta-se inicialmente a implementação da G-Machine em Java, realizada como primeira etapa do trabalho e discute-se a abordagem utilizada para essa implementação. Mostra-se em seguida, como os programas funcionais podem ser compilados para rodar nessa G-Machine. Na segunda etapa do trabalho, modifica-se o sistema implementado para permitir a execução distribuída dos programas funcionais. Finalmente apresenta-se uma avaliação de desempenho e mostra-se possíveis trabalhos futuros. / The objective of this work is to present the implementation in the Java language of an abstract machine for distributed execution of functional programs. We show how the Java facilities were used to implement a parallel functional programming language with a distributed runtime system. Functional Languages are usually implemented using an abstract machine to execute programs. These abstract machines are usually graph reduction machines. To mn the functional programs on the Java Virtual Machine we have implemented the G-Machine graph reduction machine in Java. In this text, we first present the implementation of the G-Machine in J ava, and discuss its implementation. Then we show how this implementation was modified to allow distributed execution of functional programs. Finally some benchmarks, possible future works and conclusions are presented.

Neste trabalho é descrita a organização de SINSEM, um sistema de processamento automático de especificação SINtático-SEMânticas de linguagens de programação. É colocada a motivação para um tal sistema, em relação ao uso que se daria a ele. O sistema é situado entre sistemas similares, dos quais alguns são brevemente descritos, incluindo-se exemplos de uso. Procura-se estabelecer conceitos relativos as trabalho com sistemas de auxilio ao projeto e à implementação de linguagens de programação. É discutida a estrutura lógica do sistema e uma filosofia de utilização, bem como é apresentada a nova metalinguagem proposta construído a partir da notação BNF, com extensões para se exprimir a semântica de uma linguagem de um modo construtivo, permitindo a especificação de gramáticas livres do contexto sem recursões a esquerda, visando a produção de reconhecedores recursivos descendentes dotados de ações semânticas. São apresentadas a sintaxe concreta e estática da metalinguagem, explicando-se também as funções semânticas (do tipo estático e do tipo concreto) pré-definidas no ambiente de desenvolvimento onde a ferramenta se integra. Tal ambiente pode ser operado por um conjunto de comandos que constituem uma interface (o "envelope"), que inclui também uma biblioteca sintático-semântica (que pode ser atualizada pelo usuário). A interface é descrita por meio de DFD'S E DE UM DICIONÁRIO DE DADOS. Ao final é apresentado um exemplo, parcialmente comentado (capítulo 5), de definição completa de uma linguagem de programação (CSSD), usando-se a metalinguagem proposta e os itens pré-definidos da biblioteca sintático-semântica. / In this work it is specified the constitution of SINSEM, an automatic processing system for SYNtactic and SEMantic specifications of programming languages. it is discussed motivation for such a system, according to uses it could have. The system is situated among similar systems, and some of these are briefly described, including examples. It is attempted to establish concepts about working with ,design and implementation aiding systems for programming languages. It is discussed the logical structure of the system and a philosophy of use, as well is presented a new metalanguage proposal for syntactic and semantic descriptions that is a production system constructed from BNF notation, with extensions to give language semantics in a constructive way, allowing specification of free context grammars with no left recursions, aiming the generation of preliminary versions of recursive descent parsers with semantic actions. The abstract and concrete syntax of the metalanguage are presented, and are also explained the semantic functions (of static and concrete type) predefined with and within the development environment where this frame is inserted. That environment can be operated by a set of commands that constitutes an interface ( the " envelope") wich includes too a syntactic-semantic library ( this can be made up to date by the user own). The interface is described by means of a set of DFD's and a data dictionary. At the end. it is presented an example, partially commented (chapter 5), of a complete definition of a programming language ( CSSD ), using the proposed metalanguage and the predefined items of the syntactic-semantic iibrary.

Métodos eficientes para planejamento de caminhos têm sido explorados ao longo dos anos para permitir movimento de robôs autônomos ou agentes virtuais. Basicamente, estes algoritmos buscam pelo ambiente por um caminho com pouca probabilidade de colisão com obstáculos, e que conduza o agente de uma posição inicial para uma posição objetivo. Apesar de os primeiros algoritmos para planejamento de caminhos para calcular rotas em grafos foram apresentados a mais de 50 anos atrás, ainda existe muito trabalho sendo realizado para melhorar as técnicas existentes hoje em dia. Os algoritmos de planejamento de caminhos atuais normalmente assumem que o ambiente pode ser facilmente projetado em um plano. Também existem diversos algoritmos que podem trabalhar facilmente com mais dimensões. Porém, uma classe de ambientes que não podem ser facilmente tratadas pelos algoritmos atuais é composta por superfícies arbitrárias. Estas superfícies, com buracos e torções, por exemplo, não podem ser facilmente projetadas em um plano. O fato de o caminho ser restrito à superfície faz com que, em um dado ponto o algoritmo precise calcular um caminho 2D em uma superfície 3D, o que não é trivial de mapear em um algoritmo de planejamento de caminhos para várias dimensões. Este trabalho apresenta uma nova técnica de planejamento de caminhos em superfícies 3D, chamada 3DS-BVP. Este novo planejador de caminhos é baseado em um algoritmo de planejamento de caminhos para ambientes 2D. O algoritmo anterior, chamado BVPPath- Planner, utiliza problemas de valor de contorno (Boundary Value Problems, BVP) e funções harmônicas para gerar campos potenciais. Ao seguir o gradiente descente destes campos potenciais, é possível produzir caminhos suaves livres de mínimos locais, partindo de qualquer posição do ambiente para um dado objetivo. Nosso algoritmo gera um campo potencial diretamente na superfície 3D utilizando um método numérico que foi inspirado por aquele utilizado no BVP-Path-Planner. O 3DS-BVP trabalha sobre superfícies complexas com buracos ou curvaturas, representadas por malhas de triângulos, sem a necessidade de parametrizar a superfície em uma representação 2D. Nossos resultados demonstram que a técnica pode gerar caminhos com qualidade similar àqueles gerados pelo BVP-Path-Planner em ambientes planos. O mesmo algoritmo é capaz de gerar caminhos em superfícies arbitrárias a taxas de atualização interativas. / Efficient path planning methods are being explored along the years to allow the movement of autonomous robots or virtual agents. Basically these algorithms search the environment for a path with low probability of collision with obstacles that conduces the agent from an initial to a goal position. Although the first path planning algorithms to compute routes in graphs were presented more than 50 years ago, there is still a lot of effort into improving the current approaches. The current path planning algorithms usually assume that the environment can be easily projected on a plane. There are also other algorithms that can easily deal with higher dimensional spaces. But a class of environments that cannot be easily treated by current algorithms is the one composed by arbitrary surfaces. These surfaces, with holes and bends for instance, cannot be directly projected on a plane. Because the path must be on the surface, it has only 2 degrees of freedom in any point of the surface, which is not trivial to map for a higher dimensional path planning algorithm. This work presents a new technique for path planning on 3D surfaces called 3DS-BVP. This new path planner is based on a previous path planning algorithm for 2D environments. The former algorithm, called BVP-Path-Planner, uses Boundary Value Problems (BVP) and harmonic functions to generate potential fields. By following the gradient descent of these potential fields, it is possible to produce smooth paths free from local minima from any point of the environment to a given goal position. Our algorithm generates a potential field directly on the 3D surface using a numerical method inspired on the one used by the BVP-Path-Planner. The 3DS-BVP works over complex surfaces of arbitrary genus or curvature, represented by a triangle mesh, without the need of 2D parametrizations. Our results demonstrate that our technique can generate paths with similar quality as those generated by the BVP-Path-Planner in planar environments. The same algorithm is also able to generate paths in arbitrary surfaces at interactive frame rates.

Computaçãao quântica pode ser entendida como transformação da informação codificada no estado de um sistema físico quântico. A idéia básica da computação quântica é codificar dados utilizando bits quânticos (qubits). Diferentemente do bit clássico, o qubit pode existir em uma superposição dos seus estados básicos permitindo o “paralelismo quântico”, o qual é uma característica importante da computação quântica visto que pode aumentar consideravelmente a velocidade de processamento dos algoritmos. Entretanto, tipos de dados quânticos são bastante poderosos não somente por causa da superposição de estados. Existem outras propriedades ímpares como medida e emaranhamento. Nesta tese, nós discutimos que um modelo realístico para computações quânticas deve ser geral com respeito a medidas, e completo com respeito a comunicação entre o mundo quântico e o mundo clássico. Nós, então, explicamos e estruturamos computações quânticas gerais e completas em Haskell utilizando construções conhecidas da área de semântica e linguagens de programação clássicas, como mônadas e setas. Em mais detalhes, esta tese se concentra nas seguintes contribuições. Mônadas e Setas. Paralelismo quântico, emaranhamento e medida quântica certamente vão além do escopo de linguagens funcionais “puras”. Nós mostramos que o paralelismo quântico pode ser modelado utilizando-se uma pequena generalização de mônadas, chamada mônadas indexadas ou estruturas Kleisli. Além disso, nós mostramos que a medida quântica pode ser explicada utilizando-se uma generalização mais radical de mônadas, as assim chamadas setas, mais especificamente, setas indexadas, as quais definimos nesta tese. Este resultado conecta características quânticas “genéricas” e “completas” `a construções semânticas de linguagens de programação bem fundamentadas. Entendendo as Interpretações da Mecânica Quântica como Efeitos Computacionais. Em um experimento hipotético, Einstein, Podolsky e Rosen demonstraram algumas consequências contra-intuitivas da mecânica quântica. A idéia básica é que duas partículas parecem sempre comunicar alguma informação mesmo estando separadas por uma distância arbitrariamente grande. Existe muito debate e muitos artigos sobre esse tópico, mas é interessante notar que, como proposto por Amr Sabry, essas características estranhas podem ser essencialmente modeladas por atribuições a variáveis globais. Baseados nesta idéia nós modelamos este comportamento estranho utilizando noções gerais de efeitos computacionais incorporados nas noções de mônadas e setas. Provando Propriedades de Programas Quânticos Utilizando Leis Algébricas. Nós desenvolvemos um trabalho preliminar para fazer provas equacionais sobre algoritmos quânticos escritos em uma sublinguagem pura de uma linguagem de programação funcional quântica, chamada QML. / Quantum computation can be understood as transformation of information encoded in the state of a quantum physical system. The basic idea behind quantum computation is to encode data using quantum bits (qubits). Differently from the classical bit, the qubit can be in a superposition of basic states leading to “quantum parallelism”, which is an important characteristic of quantum computation since it can greatly increase the speed processing of algorithms. However, quantum data types are computationally very powerful not only due to superposition. There are other odd properties like measurement and entangled. In this thesis we argue that a realistic model for quantum computations should be general with respect to measurements, and complete with respect to the information flow between the quantum and classical worlds. We thus explain and structure general and complete quantum programming in Haskell using well known constructions from classical semantics and programming languages, like monads and arrows. In more detail, this thesis focuses on the following contributions. Monads and Arrows. Quantum parallelism, entanglement, and measurement certainly go beyond “pure” functional programming. We have shown that quantum parallelism can be modelled using a slightly generalisation of monads called indexed monads, or Kleisli structures. We have also build on this insight and showed that quantum measurement can be explained using a more radical generalisation of monads, the so-called arrows, more specifically, indexed arrows, which we define in this thesis. This result connects “generic” and “complete” quantum features to well-founded semantics constructions and programming languages. Understanding of Interpretations of QuantumMechanics as Computational Effects. In a thought experiment, Einsten, Podolsky, and Rosen demonstrate some counter-intuitive consequences of quantum mechanics. The basic idea is that two entangled particles appear to always communicate some information even when they are separated by arbitrarily large distances. There has been endless debate and papers on this topic, but it is interesting that, as proposed by Amr Sabry, this strangeness can be essentially modelled by assignments to global variables. We build on that, and model this strangeness using the general notions of computational effects embodied in monads and arrows. Reasoning about Quantum Programs Using Algebraic Laws. We have developed a preliminary work to do equational reasoning about quantum algorithms written in a pure sublanguage of a functional quantum programming language, called QML.