[pt] Neste trabalho estudamos os algoritmos de Pontos Interiores para programação Linear. Publicados após o Algoritmo de Karmarkar. Que seguem, de algum modo, a Trajetória Central. São considerados tanto algoritmos Primais quanto Primais-Duais e também verificadas a eficácia da aplicação da metodologia de busca bidirecional. Estes métodos foram implementados e testados resolvendo um conjunto de problemas gerados aleatoriamente. Através da comparação dos resultados analisamos o desempenho das diferentes metodologias. / [en] We study here the Interior Points Algorithms for Linear Programming, developed after Karmarkar s Algorithm, which follow the Central Path. Both Primal and Primal-dual Algorithms are considered and also the efficiency of applying a bidirecional Search procedure is verified. These methods were implemented and tested solving a set of randomly generated problems. Comparing these results we analyze the performance of the methodologies.

[pt] As doenças vasculares são enfermidades graves e seus tratamentos são complexos e necessitam de procedimentos cirúrgicos. Para a realização desses procedimentos, são necessários equipamentos, equipes qualificadas e unidade de terapia intensiva (UTI) equipada para o pós-operatório. Hospitais de ensino devem atender à legislação vigente que preconiza um número mínimo de cirurgias para aprovação do residente no programa de formação. Assim, propõe-se, via otimização, encontrar soluções eficientes para o planejamento e programação de cirurgias eletivas que atendam à legislação. Este problema é tratado em 2 níveis. O primeiro é relativo ao planejamento e é chamado de Master Surgical Schedule (MSS) que consiste em definir os recursos necessários para a realização de um conjunto de procedimentos. O segundo se refere à programação e é chamado de Surgical Case Assigment Problem (SCAP) e tem por objetivo alocar o médico a cada cirurgia. Assim, foram propostos dois modelos de programação matemática, um para o MSS e outro para o SCAP. Estes modelos foram aplicados no caso real da alocação de residentes para cirurgias vasculares no Hospital Universitário Pedro Ernesto. Como resultado do modelo MSS, identificou-se a necessidade de mais anestesistas e maior disponibilidade de equipamentos para atender à legislação de formação de residentes. Por fim, como resultado do SCAP, o quantitativo de cirurgias foi distribuído entre os cirurgiões de forma balanceada. / [en] Vascular diseases are serious diseases and their treatments are complex and require surgical procedures. In order to perform these procedures, is required equipment, qualified teams and an intensive care unit (ICU) equipped for the postoperative period. Teaching hospitals must comply with current legislation that recommend a minimum number of surgeries for the resident s approval in the training program. Thus, it is proposed, through optimization, to find efficient solutions for the planning and programming of elective surgeries that comply with the legislation. This problem is dealt with on two levels. The first is relative to planning and is called the Master Surgical Schedule (MSS), which consists of defining the necessary resources to perform a set of procedures. The second one refers to programming and is called Surgical Case Assigment Problem (SCAP) and aims to allocate the doctor to each surgery. Thus, two models of mathematical programming were proposed, one for MSS and another for SCAP. These models were applied in the real case of residents allocation for vascular surgeries at Pedro Ernesto University Hospital. As a result of MSS model were identified the need for more anesthesiologists and greater availability of equipment ensure the cover of resident training legislation. Finally, as a result of SCAP, the quantity of surgeries was distributed equitably distributed among surgeons.

[pt] A indústria de software vem ao longo dos anos aumentando a funcionalidade das aplicações, numa tentativa de satisfazer as necessidades do maior número de usuários possível. Esta solução, no entanto, implica grandes desafios de usabilidade, devido à complexidade cada vez maior destas aplicações. Uma tendência que visa a acomodar as necessidades dos usuários sem sobrecarregar o software com funcionalidade de uso infreqüente é permitir que os próprios usuários finais configurem ou programem as aplicações, através de mecanismos de extensão que suportam um tipo específico de programação, chamado programação feita por usuários finais. Entretanto, grande parte das técnicas existentes para tal não conseguem atingir níveis aceitáveis de utilidade e usabilidade. Este trabalho trata alguns desafios de aplicações extensíveis, propondo uma abordagem que rompe com algumas barreiras entre interface e extensão. Esta abordagem traz para a interface, e ao alcance dos usuários finais, mecanismos de extensão de software com base em recursos semântico-pragmáticos, utilizando cálculos de metáforas e metonímias. Estes mecanismos foram escolhidos devido ao reconhecimento das Ciências Cognitivas do papel que desempenham em nosso raciocínio, em especial quando tentamos descrever ou entender um conceito abstrato ou complexo (Lakoff e Johnson, 1980; Lakoff, 1987; Lakoff, 1993; Ortony, 1993). Descrevemos um modelo de aplicações extensíveis que utiliza uma base de conhecimento onde devem ser representados os elementos do domínio e da aplicação que podem ser estendidos, bem como as classificações necessárias aos mecanismos de extensão. Nosso modelo considera os aspectos comunicativos das aplicações computacionais. Para garantir a consistência entre a aplicação original e a aplicação estendida, seguimos princípios da Engenharia Semiótica (de Souza, 1993) e prevemos, no modelo, a representação de regras que restringem as extensões na interface, a fim de refletir adequadamente as extensões de funcionalidade. / [en] In the past few years, we have witnessed an increase in software functionality as an attempt to meet most users` needs. This approach brings about serious usability challenges, due to an increase in application complexity as well. In order to try and meet users` needs, without overloading the application with functionality that is rarely used, there is a tendency to allow end users to configure or program applications, by means of mechanisms that support the so-called end user programming. However, many existing techniques fail to attain acceptable thresholds of usefulness and usability. This work addresses some of the challenges posed by extensible applications. We follow an approach that drops some walls between interface and extension. This approach brings some extension mechanisms to the interface, and readily accessible to end- users, namely extensions based on the semantic-pragmatic resources of metaphors and metonymies. These mechanisms were chosen due to the acknowledgment of the Cognitive Sciences of their critical role in our reasoning processes, especially when we try to describe or understand complex or abstract concepts (Lakoff e Johnson, 1980; Lakoff, 1987; Lakoff, 1993; Ortony, 1993). We describe an extensible application model that makes use of a knowledge base in which we represent the domain and application elements that may be extended, as well as the necessary classifications for calculating the possible extensions. Our model takes into account the communicative aspects of computer applications, and follows Semiotic Engineering (de Souza, 1993) principles to guarantee the consistency between the original application and the extended one. For that purpose, our model entails the representation of rules that constrain interface amendments, so that extended functionality is adequately reflected at the resulting interface. / [es] La industria de software ha aumentado, a lo largo de los años, la funcionalidad de las aplicaciones, en un intento de satisfacer las necesidades del mayor número de usuarios posible. Esta solución, implica grandes desafíos de usabilidad, debido a la complejidad cada vez mayor de estas aplicaciones. Una tendencia que trata de acomodar las necesidades de los usuarios sin sobrecargar el software con funcionalidad de uso poco frecuente es permitir que los proprios usuarios finales configuren y programen las aplicaciones, a través de mecanismos de extensión que soportan un tipo específico de programación, llamado programación hecha por usuarios finales. Sin embargo, gran parte de las técnicas disponibles no consiguen alcanzar níveles aceptables de utilidad y usabilidad. Este trabajo trata algunos desafíos de aplicaciones extensibles, proponiendo un enfoque que rompe con algunas barreras entre interfaz y extensión. Este enfoque trae para la interfaz, y al alcance de los usuarios finales, mecanismos de extensión de software con base en recursos semántico-pragmáticos, utilizando cálculos de metáforas y metonímias. Estos mecanismos fueron escogidos debido al reconocimiento de las Ciencias Cognitivas del papel que desempeñan en nuestro raciocinio, en especial cuando tentamos describir o entender un concepto abstracto o complejo (Lakoff y Johnson, 1980; Lakoff, 1987; Lakoff, 1993; Ortony, 1993). Describimos un modelo de aplicaciones extensibles que utiliza una base de conocimiento donde deben ser representados los elementos del dominio y de la aplicación que pueden ser extendidos, bien como las clasificaciones necesarias a los mecanismos de extensión. Nuestro modelo considera los aspectos comunicativos de las aplicaciones computacionales. Para garantizar la consistencia entre la aplicación original y la aplicación extendida, seguimos los principios de la Ingeniería Semiótica (de Souza, 1993) y prevemos, en el modelo, la representación de reglas que limitan las extensiones en la interfaz, a fin de reflejar adecuadamente las extensiones de funcionalidad.

[pt] Esta dissertação estuda modelos e algoritmos para o Problema de Alocação Generalizada (PAG) . A motivação para este estudo foi uma nova aplicação do PAG: o Problema de Carregamento de Caminhões (PCC) . A pesquisa desenvolvida concentra-se no estudo e na proposta de algoritmos aproximados (metaeurísticas) e exatos para a resolução do PAG. Os algoritmos aproximados propostos baseiam-se em um conceito recentemente criado por Fischetti e Lodi (2003), que utiliza programação matemática inteira para a exploração eficiente de vizinhanças mais abrangentes. Os resultados obtidos foram comparáveis aos melhores conhecidos, com a vantagem de exigir um esforço pequeno de implementação e um menor tempo de processamento. O algoritmo exato proposto é um algoritmo de branch-and-cut- and-price, que tem como ponto de partida o algoritmo de branch-and-price de Savelsbergh (1997). Técnicas de estabilização da geração de colunas similares às propostas por Du Merle, Villeneuve, Desrosiers e Hansen (1999), foram estudadas no âmbito desta dissertação, que experimenta com diferentes implementações deste mecanismo. O algoritmo de branch-andcut-and-price estabilizado demonstrou sua eficiência ao resolver à otimalidade instâncias que se encontravam em aberto na literatura. Finalmente, experiências com PCC permitiram que os códigos desenvolvidos pudessem ser avaliados em problemas reais. / [en] This dissertation tackles the Generalized Assignment Problem (PAG), models and algorithms are studied and proposed. This work was motivated by a real world application: the Truck Loading Problem (PCC). Research was done on approximated (metaheuristics) and exact algorithm for solving the PAG. The approximated algorithms proposed were based on a recent idea from Fischetti and Lodi (2003). It uses integer programming to explore wider neighborhoods. The results were compared to the best known, while demanding much less implementation effort and using less cpu time. The exact algorithm proposed is a branch-and-cut- and-price developed from the branch-and-price algorithm of Savelsbergh (1997). We used stabilized column generation techniques similar to the one by Du Merle, Villeneuve, Desrosiers and Hansen (1999), and devised experiments with different implementations of this mechanism. The resulting algorithm proved its efficiency by solving to optimality open instances from the literature. Finally, experiments with the PCC turned possible the evaluation of the codes developed on real problems.

[pt] As aplicações na WWW são exemplos de aplicações hipermídia. O desenvolvimento destas aplicações, mesmo utilizando metodologias de projeto, tem uma complexidade elevada. Existem propostas dirigidas por modelos para ajudar ao projetista, mas estas requerem de uma curva de aprendizado alta para os não familiarizados com os modelos. Este trabalho aborda este problema oferecendo uma abordagem que, fazendo uso de uma metodologia dirigida por modelos, permite a autoria de aplicações em um ambiente mais próximo à intenção do usuário. Se apresenta uma ferramenta com características de assistente (wizard) que permite a criação de aplicações através de exemplos, utilizando interfaces com dados concretos. O assistente usa aspectos da técnica de programação por exemplo e do estilo de interação de manipulação direta que contribuem para facilitar o desenvolvimento. / [en] Web applications can be seen as examples of hypermedia applications. Developing such applications is a complex endeavor, even when using design methods. There are model-driven methods aimed at helping the designer, but they still require a steep learning curve for those unfamiliar with the models. This work addresses this problem through a model-driven wizard that helps the designer through the use of examples and concrete data-driven interfaces. This wizard uses direct manipulation techniques to help easing the designer s tasks.

[pt] Os problemas de roteamento estão entre os problemas combinatórios mais difíceis de encontrar limites melhores do que os existentes ou de provar novas soluções ótimas. Nesta tese, são abordados o Capacitated Arc Routing Problem (CARP) e o Generalized Vehicle Routing Problem (GVRP). Em ambos os problemas, existe um conjunto de clientes os quais estão espalhados por um grafo dado, onde cada cliente possui uma demanda que deve ser atendida por exatamente um veículo de um conjunto de veículos idênticos. Os custos de travessia e o vértice de depósito são dados. O objetivo é encontrar rotas que coletam todas as demandas com custo mínimo, sem exceder a capacidade de nenhum veículo. No CARP, os clientes são um subconjunto de arestas, chamadas de arestas requireds, e para o GVRP, cada cliente é um subconjunto de vértices, chamado de grupo, onde cada grupo deve ser atendido visitando-se exatamente um vértice deste grupo. Além disto, vale notar que quando cada grupo possui apenas um vértice, o problema passa a ser o Capacitated Vehicle Routing Problem (CVRP). Primeiramente, são investigados métodos para melhorar os limites inferiores de instâncias de grande porte. É proposta a exploração da velocidade de uma heurística dual ascent para gerar cortes de capacidade. Em seguida, é apresentado um algoritmo de geração de colunas com um pricing eficiente para um tipo especial de rota não-elementar. O pricing proposto combina a técnica Decremental State-Space Relaxation (DSSR) com limites de complemento. Estas técnicas permitem o fortalecimento da regra de dominância entre as rotas, reduzindo drasticamente o número total de rótulos utilizados pela programação dinâmica. Finalmente, um algoritmo de branch-cut-and-price é criado o qual usa a geração de colunas e a separação de cortes previamente apresentadas. Além disto, este branch-cut-and-price é implementado usando strong branching e fixação por custo reduzido. Ao fim de cada parte, são apresentados resultados computacionais os quais avaliam a qualidade dos algoritmos propostos, os quais obtém novos limites inferiores para um grande número de instâncias do CARP e do GVRP. / [en] Routing problems stand among the hardest combinatorial problems to find high quality bounds or to prove new optimal solutions. In this thesis, we tackle the Capacitated Arc Routing Problem (CARP) and the Generalized Vehicle Routing Problem (GVRP). For both problems, there are a set of customers spread over a given graph, where each customer has a demand which must be serviced by exactly one vehicle from a set of identical vehicles. The traversal costs and a depot vertex are given. The objective is to find routes that collect all the demands, without exceeding the capacity of any vehicle, at minimum cost. For the CARP, the customers are a subset of edges, called the required edges, and for the GVRP, each customer is a subset of vertices, called clusters, where each cluster must be serviced by visiting exactly one vertex of it. Furthermore, it is noteworthy that when every cluster contains just a single vertex, the problem is the Capacitated Vehicle Routing Problem (CVRP). Firstly, we investigate methods to improve lower bounds for large scale instances. We propose to explore the speed of a new dual ascent heuristic to generate capacity cuts. The quality of the cuts found is next improved with a new exact separation which is used in the linear program resolution that follows the dual heuristic. Following, we present a column generation algorithm with an efficient pricing for a special kind of non-elementary routes. The proposed pricing algorithm combines Decremental State-Space Relaxation(DSSR) technique with completion bounds. These techniques allow the strengthening of the domination rule between routes, drastically reducing the total number of labels used during the dynamic programming. Finally, we devise a branch-cut-and-price algorithm which uses the previously presented column generation and cut separation. Moreover, this branch-cutand- price is implemented using strong branching and reduced cost fixing. At the end of each part, we present computational experiments which evaluate the quality of the proposed algorithms and show new best lower bounds for a large number of CARP and GVRP instances.

[pt] Ambientes de Execução Gerenciada tornaram-se alvos populares para compiladores de linguagens de programação de alto nível. Eles provêem um sistema tipos de alto nível com segurança de memória garantida, assim como facilidades como coleta de lixo, acesso a serviços da plataforma subjacente (possivelmente através de uma sandbox), multithreading, e uma rica biblioteca de estruturas de dados e algorithmos, mas não possuem um modelo de desempenho claro, o que atrapalha as tentativas de otimização de qualquer linguagem que não tenha um mapeamento direto na semântica do ambiente de execução, especialmente se a linguagem é dinamicamente tipada. Nós afirmamos que é possível construir um compilador para uma linguagem dinâmica que tem como alvo um ambiente de execução gerenciada que rivaliza um compilador que tem como alvo linguagem de máquina na eficiência do código que ele gera. Essa tese apresenta um compilador com tal característica, descrevendo as otimizações necessárias para sua construção, e testes de desempenho que validam essas otimizações. Nossas otimizações não dependem de geração de código em tempo de execução, apenas em informação estaticamente disponível no código fonte. Nós usamos uma nova análise de inferência de tipos para aumentar a quantidade de informação disponível. / [en] Managed runtime environments have become popular targets for compilers of high-level programming languages. They provide a high-level type system with enforced runtime safety, as well as facilities such as garbage collection, possibility sandboxed access to services of the underlying platform, multithreadng, and a rich library of data structures and algorithms. But managed runtime environments lack a clear performance model, which hinders attempts ar optimizing the compilation of any language that does nor have a direct mapping to the runtime environments semantics. This is aggravated if the language is dynamically typed. We assert that it is possible to build a compiler for a dynamic language that targets a managed runtime environment so that it rivals a compiler that targets machine code directly in efficiency of the code it generates. This dissertation presents such a compiler, describing the optimizations that were needed to build it, and benchmarks that validate these optimizations. Our optimizations do not depend on runtime code generation, only on information that is statically available from the source program. We use a novel type inference analysis to increase the amount of information available.

[pt] O presente trabalho teve como objetivo principal investigar o potencial de algoritmos computacionais evolutivos, construídos a partir das técnicas de programação genética, combinados com diferenciação automática, na obtenção de soluções analíticas, exatas ou aproximadas, para problemas de equações diferenciais ordinárias (EDO), parciais (EDP) e estocásticas. Com esse intuito, e utilizando-se o ambiente de programação Matlab, diversos algoritmos foram elaborados e soluções analíticas de diferentes tipos de equações diferenciais foram determinadas. No caso das equações determinísticas, EDOs e EDPs, foram abordados problemas de diferentes graus de dificuldade, do básico até problemas complexos como o da equação do calor e a equação de Schrödinger para o átomo de hélio. Os resultados obtidos são promissores, com soluções exatas para a grande maioria dos problemas tratados e que atestam, empiricamente, a consistência e robustez da metodologia proposta. Com relação às equações estocásticas, o trabalho apresenta uma nova proposta de solução e metodologia alternativa para a precificação de opções europeias, de compra e de venda, e realiza algumas aplicações para o mercado brasileiro, com ações da Petrobras e da Vale. Além destas aplicações, são apresentadas as soluções de alguns modelos clássicos, usualmente utilizados na modelagem de preços e retornos de ativos financeiros, como, por exemplo, o movimento Browniano geométrico. De uma forma geral, os resultados obtidos nas aplicações indicam que a metodologia proposta nesta tese pode ser uma alternativa eficiente na modelagem de problemas científicos complexos. / [en] The main objective of this work was to investigate the potential of evolutionary algorithms, built from genetic programming techniques and combined with automatic differentiation, in obtaining exact or approximate analytical solutions for problems of ordinary (ODE), partial (PDE), and stochastic differential equations. To this end, and using the Matlab programming environment, several algorithms were developed and analytical solutions of different types of differential equations were determined. In the case of deterministic equations, ODE and PDE problems of varying degrees of difficulty were discussed, from basic to complex problems such as the heat equation and the Schrödinger equation for the helium atom. The results are promising, including exact solutions for the vast majority of the problems treated, which attest empirically the consistency and robustness of the proposed methodology. Regarding the stochastic equations, the work presents a new proposal for a solution and alternative methodology for European options pricing, buying and selling, and performs some applications for the Brazilian market, with stock prices of Petrobras and Vale. In addition to these applications, there are presented solutions of some classical models, usually used in the modeling of prices and returns of financial assets, such as the geometric Brownian motion. In a general way, the results obtained in applications indicate that the methodology proposed in this dissertation can be an efficient alternative in modeling complex scientific problems.

[pt] Nos últimos anos, as linguagens de script ganharam muita importância em diversas áreas da computação. Uma das áreas onde essas linguagens ainda são pouco exploradas é na área de computação paralela. A computação paralela sempre foi fortemente associada a computação científica, mas recentemente ela ganhou uma nova importância com a popularização de processadores multi-core. Com esse crescimento se torna necessário o surgimento de novos paradigmas de programação paralela para facilitar o desenvolvimento e dinamizar as aplicações, e linguagens de script podem ser usadas para isso, trazendo dinamismo, simplicidade e flexibilidade às aplicações. Esta dissertação visa estudar um modelo híbrido de programação entre duas linguagens de programação, Lua e Charm plus plus. / [en] Recently, scripting languages have become very important in many fields of computer science. One area in which these languages have not been explored is paralel programming. Paralel programming has always been strongly associated with scientific usage, but recently, with the growth in popularity of multi core systems, it has gained a new field of action. With this change, the development of new programming paradigms of paralel programming become necessary in order to make development easier and applications more dynamic. Scripting languages may be used for this, bringing dynamics, flexibility and simplicity to aplications. This dissertation aims to study a hybrid programming model with two programming languages, Charm plus plus and Lua.

[pt] A logística do petróleo no Brasil encontra-se atualmente em franca expansão e desenvolvimento. Impulsionada por novas descobertas, além da entrada de novos players, os desafios têm se revelado cada vez mais complexos. Desta forma, uma previsibilidade da demanda por transporte adequada e aderente, principalmente, implica na redução nos custos de transporte advinda de uma melhor estratégia de contratação. Este trabalho busca mensurar o tamanho de frota necessário para o transporte de petróleo em seu estado cru, fornecendo subsídios para o processo de tomada de decisão em uma empresa de petróleo integrada. Para tal, são utilizadas modelagens matemáticas considerando-se as diversas viagens e destinos a serem atendidos pelos navios petroleiros. Simulações envolvendo tamanhos de lotes e roteamento de veículos também são utilizadas com o intuito de auferir ganhos mediante o aumento da eficiência no transporte. Ao final deste documento, pretende-se esclarecer aspectos importantes que impactam na atividade de programação de navios em âmbito operacional. São analisados dois tipos de serviços com finalidades distintas: transporte de petróleo em cabotagem e longo curso. Por fim, é calculado o tamanho de frota, de acordo com o porte de navio ideal, conforme os vários cenários abordados. / [en] The Crude Oil s logistics in Brasil currently raises faster than last ten years. Driven by new discoveries, in addition to the entry of new players, the problems have been increased in complexity. Thus, an adequate forecast could be interesting to reduce transport s costs by an application of a better strategy for hiring. This paper seeks measure the size of fleet needed for the transport of petroleum in its raw state, providing subsidies to the decision process in oil companies. Therefore are used mathematical modelings considering the various destinations and the commercials contracts. Simulations involving cargo quantities and vehicles routing also had been employed in point of obtaining gains through increasing fleet s efficiency. The purpose of this work is to intend the impacts of some operational problems in scheduling. Two types of services are going to be analysed considering their finalities: the navigation along the Brasilian coast and the navigation between several countries. Finally, fleet will be calculated according to the size of vessel and attempting some different scenarios.