A Computação Pervasiva tem sido tema de diversos trabalhos nos últimos anos. Essa emergente área de pesquisa propõe uma visão de futuro onde serviços computacionais são oferecidos para os usuários através de inúmeros dispositivos espalhados pelo ambiente. Os serviços são disponibilizados, tanto através da infraestrutura existente dos computadores ligados fisicamente à rede quanto através de dispositivos móveis. Esse espalhamento da computação deve acontecer de maneira natural e imperceptível ao usuário. Dados pessoais, programas e arquivos de dados poderão ser acessados de qualquer lugar em qualquer momento. O poder de processamento será um recurso do ambiente, acessado quando necessário, da mesma forma que é hoje a eletricidade. O usuário não precisará ter ciência de qual máquina realiza o processamento necessário às suas aplicações, contanto que o resultado esperado seja obtido. Acredita-se que essa realidade será atingida através da aliança entre áreas de pesquisa como a Computação em Grade, Computação Móvel e a Computação Consciente do Contexto. A Computação Consciente do Contexto busca enriquecer a comunicação entre os seres humanos e os dispositivos computacionais, tornando sua atuação mais eficaz. As aplicações conscientes do contexto conseguem perceber as modificações que ocorrem no ambiente e adaptar seu comportamento ao novo estado. Esse processo pode ser dividido em três etapas: monitoramento, reconhecimento de contexto e adaptação. Na etapa de monitoramento são coletadas, através de sensores, informações sobre o ambiente. Essas informações, entretanto, são geralmente, de baixo nível de abstração e, portanto, dificilmente usadas diretamente por aplicações. A etapa de reconhecimento de contexto relaciona os dados obtidos do ambiente e transforma-os para que possam ser úteis às aplicações no processo de escolha do comportamento mais adequado à cada circunstância, habilitando a etapa de adaptação a efetivar a transformação do comportamento da aplicação de acordo com a nova situação do ambiente. Este trabalho propõe um servidor de contexto chamado MultiS que tem como objetivo a resolução dos problemas relativos à etapa de reconhecimento de contexto: a produção de dado de contexto baseado em informações de diversos sensores e a capacidade de reagir a modificações no ambiente. Também é proposta uma linguagem para composição de dados do contexto chamada CD-XML utilizada pelas aplicações para descrever ao servidor de contexto os dados aos quais elas são sensíveis. / The Pervasive Computing has been studied on several papers in the last years. This emergent research area presents a vision of future where computational services will be available through uncountable devices scattered across the environment. This service network will be exposed to the users by both traditional wired computers and mobile devices. This distribution of the computing is going to happen smoothly and transparently to the users. Personal data, computer programs, and data files will be available anywhere, anytime. The processing power will be an environment resource and will be accessed whenever needed, in the same way which is the electricity nowadays. The users will no longer need to worry about where their program is being executed, as long as he gets the needed result. The ISAM group believes that this new reality will be achieved through the alliance of research areas such as Grid Computing, Mobile Computing and Context-Aware Computing. The Context-Aware Computing aims to enrich the communication between human being and computer devices. Context-aware applications are capable of recognize the changes on the environment and adapt its own behavior to the new context state. This process can be divided in tree steps: monitoring, context recognition and adaptation. On the monitoring layer, environment information is collected from sensors. Those sensors, however, usually return only low level information, which is hardly used by the applications on its original form. The context recognition layer processes the data acquired from the context and transforms into information aimed to be useful to the adaptation process. With that information the adaptation system can identify the correct behavior for the application on each different context situation. This dissertation propose a context server named MultiS, which target is to solve the problems related to context recognition layer: the production of new context data based on the information of several sensors and the capability of react to changes on the environment. It also presents a new programming language for composition of contextual information, named CD-XML. This language is used by the context-aware applications to communicate to the context server describing which information the application is sensible to.

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.

A crescente complexidade dos programas de computador e o crescimento da carga de trabalho a qual eles são submetidos têm sido tendências recorrentes nos sistemas computacionais, em especial para sistemas distribuídos como aplicações web e sistemas corporativos. O aumento da carga de trabalho gera uma demanda por sistemas que façam melhor uso dos recursos computacionais disponíveis, enquanto a maior complexidade gera uma demanda por sistemas que se preocupem em minimizar o número de erros. Portanto, podem-se identificar dois objetivos a serem perseguidos pelos desenvolvedores de sistemas de software: melhorar o desempenho e aumentar a confiabilidade dos sistemas. A fim de alcançar os objetivos expostos, são desenvolvidos sistemas de monitoramento para automatizar a coleta e análise de dados sobre os sistemas computacionais alvo. O presente trabalho visa contribuir nos seguintes aspectos: na identificação dos dados relevantes para o monitoramento de aplicações distribuídas desenvolvidas para a plataforma Java; e na criação de uma ferramenta de monitoramento de aplicações distribuídas, explorando os novos recursos do JDK 1.5, bem como os recursos já disponíveis em Java, como carga dinâmica de classes e transformação de bytecodes A fim de avaliar a ferramenta proposta foram elaborados três estudos de caso: um utiliza uma aplicação existente sem necessidade de sua adaptação; outro avalia a sobrecarga da ferramenta frente a diferentes parâmetros; e o terceiro avalia o monitoramento de um sistema distribuído. Entende-se que a ferramenta atinge o objetivo de monitoramento de aplicações distribuídas, por meio da incorporação de técnicas e APIs distintas, ao permitir: o monitoramento de uma aplicação distribuída por meio do monitoramento de diversos nodos de tal aplicação concomitantemente; e a visualização das informações coletadas de forma online. Adicionalmente, a coleta simultânea de dados de diferentes nodos de uma aplicação distribuída pode ser útil para a descoberta de relações entre eventos que ocorrem durante a execução de tal aplicação. / The growing complexity of software and the increasing workload to which systems have been submitted are known trends in the computing system field, especially when distributed and web systems are considered. The increasing workload generates demand for systems that can make a better use of computing resources, while the increment of system complexity demands specific actions to prevent design faults. Therefore, software engineers have two main objectives to be concerned with: optimization and dependability. In order to accomplish these objectives, monitoring systems have been proposed to gather data from running systems so that their behavior can be analyzed. The present dissertation intends to contribute in the following domains: identifying relevant metrics for monitoring distributed Java applications; and developing a tool to monitor and profile distributed applications, using the new resources available in JDK 1 .5 as well as some already known techniques like dynamic classloading and bytecode instrumentation. In order to evaluate the proposed tool, three test cases have been developed: one with a well known application running without modification; another for evaluating the tools’ overhead in different scenarios; and a third one to evaluate a distributed application been monitored. We understand that the proposed tool is successful in monitoring distributed applications by the use of distinct APIs and techniques because: Nprof can monitor a distributed application by monitoring different nodes of the application simultaneously; and Nprof allows the online visualization of the collected data. Also, simultaneous collection of data from different nodes of a distributed application can be useful for discovering relations among events that occur during the execution of the application.

Submitted by Paola Damato (repositorio@mackenzie.br) on 2016-04-14T14:03:05Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Gustavo Lassala Silva.pdf: 3262440 bytes, checksum: 7d9f78937b36a72f8dbc3ef091e41549 (MD5) / Made available in DSpace on 2016-04-14T14:03:05Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Gustavo Lassala Silva.pdf: 3262440 bytes, checksum: 7d9f78937b36a72f8dbc3ef091e41549 (MD5) Previous issue date: 2014-10-27 / Type of illegal urban intervention native of Sao Paulo, pixação is perpetrated by young people in outlying areas, which – in search of notoriety – they risk this modality to climb buildings to stamp their mark in places of high visibility. In its historical development, the practice has undergone a partial acceptance process in the arts district, resulting in social and aesthetic legitimacy of some of his characters. One is Djan Ivson Silva, selected as a subject focus of this research. With unusual personality, he holds a significant collection of documents and a great knowledge about the history of pixação. Djan was leading the groups in which he served and primarily responsible for bringing his practice to a field traditionally occupied by the intellectual elites. Defined by the media as an “artist / pixador” personal situation Djan expressed Ivson the ambiguity of the current character of this cultural manifestation that lies between the social and artistic phenomenon. This thesis – divided into three chapters, each subdivided between the description of the character’s personal history and the interpretation of the transformations of pixação – articulates the communicating vessels between the individual and collective levels, and gives a glimpse step by step how a young offender engages the periphery to the discussion of contemporary art without losing ties with their social base. / Tipo de intervenção urbana ilegal nativa de São Paulo, a pixação é praticada por jovens de bairros periféricos, que – em busca de notoriedade – se arriscam nessa modalidade ao escalar edificações para carimbar suas marcas em lugares de grande visibilidade. No seu desenvolvimento histórico, a prática passou por um processo parcial de aceitação na área artística, resultando na legitimação social e estética de alguns de seus personagens. Um deles é Djan Ivson Silva, sujeito selecionado como foco desta pesquisa. Com personalidade incomum, detentor de um significativo acervo de documentos e um grande conhecimento sobre a história da pixação, Djan foi líder dos grupos nos quais atuou e o principal responsável por levar sua prática para um campo tradicionalmente ocupado pelas elites intelectuais. Definido pela mídia como “artista/pixador”, a situação pessoal de Djan Ivson expressa a ambiguidade do caráter atual desta manifestação cultural, que se situa entre o fenômeno social e artístico. Esta tese – dividida em três capítulos, cada um deles subdivido entre a descrição da trajetória pessoal do personagem e a interpretação das transformações da pixação – articula os vasos comunicantes entre os âmbitos individual e coletivo, possibilitando vislumbrar passo a passo como um jovem transgressor da periferia se envolve com a discussão da arte contemporânea sem perder os laços com sua base social.

[pt] A natureza intrinsicamente combinatorial de muitos problemas advindos da área de logística de transportes, em especial aqueles que dizem respeito ao uso racional de frotas de veículos, sugere que boa parte dos mesmos pode ser formulada e resolvida como um problema de programação linear inteira. Contudo, a maioria dos algoritmos até o momento disponíveis não consegue encontrar, em tempos computacionais aceitáveis, a solução ótima para instâncias de porte razoável. O objeto de estudo desta tese é a exploração de técnicas mais recentes da área de programação linear inteira e suas aplicações a problemas de roteamento de veículos. A primeira parte da tese descreve, além das técnicas básicas de decomposição de problemas de programação linear e linear inteira e de geração de colunas, uma proposta de reformulação de problemas de programação linear inteira alternativa àquela que gera o tradicional problema mestre de Dantzig-Wolfe, geralmente utilizados em abordagens por geração de colunas. A resolução de problemas de programação linear inteira neste contexto é tratada em seguida, com a descrição do algoritmo branch-and-bound e das variações branch-and-cut, branch-and-price e branch-and-cut-and-price. Na segunda parte da tese, inicialmente, é apresentada a técnica denominada de Geração Projetada de Colunas e sua aplicação ao problema de Roteamento de Veículos com Restrição de Capacidade. Em seguida é abordada a resolução do problema de Roteamento de Veículos sobre Arcos, através de sua transformação ao primeiro problema citado e uso de um algoritmo branch-and- cut-and-price. Finalmente, é proposto um novo problema na área de redistribuição de veículos de aluguel, para o qual é proposta uma formulação segundo uma abordagem por geração de colunas. São apresentados, ainda, procedimentos para a geração de colunas e resultados computacionais obtidos com um algoritmo branch-and-price para essa formulação. / [en] Optimization techniques have an important role in Transportation Logistics. The combinatorial nature of the problems related to this area suggests integer programming as a natural approach to their resolution. Nevertheless there are many cases where even instances of reasonable size still beyond the resolution capability of the current known algorithms. The success of the known algorithms have therefore been limited. This can be justified by the fact the most of them leave important recent advances in the combinatorial optimization field unexplored. Some of these new techniques and their applications are the main subject of this thesis. In the first part, the basic decomposition techniques for linear and integer programming problems as well as the related column generation approach is addressed. This is followed by the presentation of a reformulation technique for linear and integer programming which is alternative to the well known Dantzig-Wolfe master program. The new possibilities coming from this approach are explored and the resulting consequences to the standard branch-and- bound algorithm and its variations branch-and-cut, branch-and- price and branchand- cut-and-price are presented. The second part of this text addresses the application of the metodologies described in part one to routing problems where capacity constraints are considered. First, a techinque named Projected Column Generation is described in the context of the Capacitated Vehicle Routing Problem. Then, it is presented a new transformation from the Capacitated Arc Routing Problem to the Capacitated Vehicle Routing Problem as well as a tailored branch-and-cut-and-price to solve this problem. Finally, a new problem in vehicle redistrubution is described together with a column generation approach for its resolution. Computational results for all applications are presented.

[pt] Este trabalho apresenta uma ferramenta de suporte à programação literária. Para seu desenvolvimento foi criado um framework de prestação dos serviços básicos requeridos por este tipo de ferramenta. Desenvolvido segundo uma arquitetura que o tornou flexível, via uma linguagem de extensão para definição de macros; eficiente, via um núcleo em C++ otimizado para realizar as operações a nível de caracter; e portável, graças a uma implementação em C/C++ padrão, o framework se mostrou adequado aos objetivos propostos. O desenvolvimento sobre este framework validou as soluções adotadas, resultando em uma ferramenta de ótimo desempenho. / [en] This thesis presents a support tool for literate programming.Its development was preceded by a research of the basic facilites usually required for programs of this class. After that, a framework has been developed to offer those facilites. The framework was developed in standard C++, in such away that would guarantee its portability. Its effciency is due to an optimzed kernel which performs all character-level operations, and a well defined application program interface(API)assures its fexibility.On top of this framework an access layer has been created using a confi- guration language. This layer allows that, through small programs written in the configuration language, a user can adapt the tool for diferent literate programming styles like modular or WWW-enabled documentation.

[pt] Métodos que combinam estratégias normalmente encontradas em algoritmos metaeurísticos com técnicas para resolver problemas de programação inteira mista (MIP) têm apresentado ótimos resultados nos últimos anos. Este trabalho propõe dois novos algoritmos nessa linha: um algoritmo que faz pós-processamento nas soluções encontradas pelo resolvedor MIP. Os dois algoritmos utilizam um novo tipo de vizinhança, chamada de vizinhança elipsoidal, que possui fortes semelhanças com as técnicas de relinking de algoritmos PR e que neste trabalho é generalizada e extendida para múltiplas soluções. O problema generalizado de alocação (GAP) é usado para os experimentos. São testados também um resolvedor MIP puro (ILOG CPLEX versão 11) e um algoritmo branch and price que utiliza as heurísticas RINS e guided dives. Os algoritmos testados são comparados entre e com heurísticas específicas para o GAP. Os resultados são satisfatórios e indicam que as vizinhanças elipsoidais conseguem frequentemente melhorar as soluções encontradas pelo resolvedor MIP, encontrando a melhor solução para algumas instâncias. / [en] Methods that mix strategies usually found in metaheristic algorithms with techniques to solve mixed integer programming problems (MIPs) have had great results over the past few years. This wprk proposes two new algorithms in this philosophy: one is based on the Path Relink (PR) metaheuristc, while the other one is a simple algorithm that does post-processing in the solutions found by the MIP solver. Both algorithms use a new neighborhood structure, called ellipsoidal neighborhood, that has strong resemblances with the relinking step from PR algorithms and that, in this work, is generalized and extended for multiple solutions. The generalized assignment problem (GAP) is used for the computational experiments. Also tested are MIP solver (ILOG CPLEX version 11) and a branch and price algorithm that uses the RINS and guides dives heuristics. The tested algorithms are compared among themselves and with GAP-specific heuristics. The results are satisfactory and show that the ellipsoidal neighborhood can frequently improve the solutions found by the MIP solver, even finding the best result for some instances.

[pt] Expressões regulares são um formalismo utilizado para descrever linguagens regulares e compõem a base de diversas bibliotecas de casamento de padrão. No entanto, existem determinados padrões úteis que são complexos ou impossíveis de serem descritos com expressões regulares puras. Devido a essas limitações, linguagens de script modernas disponibilizam bibliotecas de casamento de padrões baseadas em regexes, isto é, extensões de expressões regulares compostas, principalmente, por construções ad-hoc que focam em problemas específicos. Apesar de serem muito úteis na prática, os regexes possuem implementações complexas e distantes do formalismo original de expressões regulares. Parsing Expression Grammars (PEG) são uma alternativa formal para reconhecer padrões e possuem mais expressividade que expressões regulares sem necessitar de contruções ad-hoc. O objetivo deste trabalho é estudar formas de conversão de regexes para PEGs. Para isso, estudamos as implementações atuais de regexes e mostramos a conversão de algumas construções para PEGs. Por fim, apresentamos uma implementação da conversão de regexes para PEGs para a linguagem Lua. / [en] Regular expressions are a formalism used to describe regular languages and form the basis of several pattern-matching libraries. However, many interesting patterns either are difficult to describe or cannot be described by pure regular expressions. Because of these limitations, modern scripting languages have pattern matching libraries based on regexes, ie, extensions of regular expressions mainly composed by a set of ad-hoc constructions that focus on specific problems. Although very useful in practice, these implementations are complex and distant from the original formalism of regular expressions. Parsing Expression Grammars (PEG) are a formal alternative to recognize patterns and it is much more expressive than pure regular expressions and does not need use ad-hoc constructions. The goal of this work is to study the convertion of regexes to PEGs. To accomplish this task, we studied the current implementations of regexes and show how to convert some constructions to PEGs. Finally, we present an implementation that convert regexes to PEGs for the Lua language.

[pt] As decisões de cunho operacional tomadas no dia-a-dia das atividades de programação de movimentação de petróleo têm um forte impacto sobre o custo total desta cadeia de suprimentos. O desafio das áreas que tomam estas decisões diárias é elaborar uma programação de movimentação com o menor custo, com um alto nível de confiança e que seja factível para um determinado horizonte de tempo. Neste contexto, a utilização de programação matemática na programação de refinarias, dutos e terminais da cadeia de petróleo e derivados vem atraindo atenção crescente da indústria de petróleo. Este trabalho apresenta uma formulação matemática baseada em Programação Linear Inteira Mista (MILP) para o problema da movimentação de petróleo de um terminal até uma refinaria. No caso estudado, a movimentação acontece através de navios que descarregam seu produto no terminal de São Francisco do Sul, localizado no Estado de Santa Catarina, passando pelo duto OSPAR até chegar a seu destino final – a Refinaria de Araucária (REPAR), localizada no Estado do Paraná. Os principais resultados do modelo são a programação do sequenciamento de qual navio irá atracar no terminal, qual petróleo será descarregado e qual o volume e tipo de petróleo que será bombeado no duto para chegar a refinaria. O objetivo do modelo é minimizar os custos operacionais tomando-se em consideração o atendimento à demanda da refinaria, restrições de capacidade, disponibilidade de petróleo, manutenção dos estoques da refinaria e o bombeio ou não durante o período conhecido como horosazonal. Cenários testados com dados fornecidos pela Petrobras demonstram que através dos resultados do modelo é possível definir se há necessidade de utilizar o duto durante o horário de ponta ou não, garantindo a contratação de energia previamente junto às concessionárias, evitando desta forma o pagamento de multas, reduzindo um custo evitável. A partir dos resultados numéricos, ficou comprovado que o modelo pode gerar uma programação de movimentação de petróleo otimizada, em cenários de uma semana e um mês, ou indicar que não existe programação viável para tal cenário. / [en] The operational decisions of crude oil scheduling activities taken on a daily basis have a strong influence upon the overall supply chain cost. The challenge is to create a crude oil schedule that minimizes the total cost, and at the same time is feasible considering a limited scheduling horizon. The use of mathematical programming for the oil industry has increasingly drawn attention. This study presents a mathematical programming model based on mixed integer linear programming (MILP) for the crude oil scheduling of a system connecting a terminal to a refinery. On the case studied, the transfer occurs through tankers that unload their crude oil on the São Francisco do Sul terminal, located at Santa Catarina state, going through the OSPAR pipeline until it reaches its final destiny – Araucaria refinery (REPAR), located at Paraná state. The main results of the model are the scheduling of ships at the terminal, the scheduling of the pipeline and stocks levels at the terminal and at the refinery. The main goal of this model is to minimize the cost involved in operation, meeting the refinery demand, oil supply, capacity constraints, and the maintenance of refinery crude oil stock levels. This formulation was applied to real scenarios, with time-horizon from a week to a month, and was effectively solved with the proposed solution approach.