[pt] As despesas anuais em saúde para a maioria dos países são crescentes. Segundo a Organização Mundial de Saúde (OMS), em 2011 o Brasil gastou aproximadamente 10 porcento do produto interno bruto em saúde. Consequentemente, incrementar a eficiência na prestação de serviços médicos está se tornando cada vez mais importante. Em um hospital as salas de cirurgia representam um dos principais centros de custos e de rendimentos. As salas de cirurgia são um aspecto difícil de gerenciar devido à prioridade das partes envolvidas no processo, nomeadamente, pacientes, cirurgiões, staff, pessoal administrativo, e a escassez de recursos como leitos, salas de cirurgia, equipamentos especiais, etc. A presente dissertação aborda um problema real de programação de salas de cirurgia para pacientes eletivos de um hospital em Lisboa, onde é proposta uma reformulação do modelo de PLI proposto por Marques et al. (2012). Esta reformulação é baseada no problema da mochila, com o objetivo de encontrar soluções mais eficientes em termos computacionais. De acordo com os testes realizados, uma modificação no modelo que quebre sua simetria além de fornecer uma solução mais eficiente computacionalmente, melhora a solução original pois diminui o gap inicial de 782,59 porcento para 2,25 porcento. Também foi proposto um modelo de simulação no que foram criados vários cenários para avaliar a incerteza envolvida, nos quais a duração média das cirurgias foi submetida a valores majorados. Esta simulação pode servir como ferramenta de apoio na tomada de decisões, pois de acordo com o grau de conservadorismo de quem toma as decisões, podem ser estabelecidas políticas de programação das Salas de Cirurgia. / [en] For most countries annual health expenditures are increasing. According to the World Health Organization (WHO), in 2011, Brazil expends about 10 percent of its gross domestic product on health. Hence, improving health care efficiency is becoming increasingly important. Within a hospital, the Operating Rooms represent a major cost and incomes center. Operating Rooms are a difficult aspect to manage because many stakeholders involved in the process, namely, patients, surgeons, staff, hospital manager, and the scarcity of resources like beds, operating rooms, especial equipment, etc. This dissertation deals with a real problem of operating rooms programming for elective patients in a Lisbon hospital. For this problem, we propose a reformulation of the integer programming model proposed by Marques et al. (2012). This reformulation is based on the knapsack problem, in order to find a more efficient solution in terms of time. According to tests carried out, a reformulation in the model that breaks symmetry, computationally provides a more efficient solution and enhance the original solution because it reduces the initial gap from 782.59 percent to 2.25 percent. In addition, a simulation model was proposed to create various scenarios to assess the involved uncertainty, mainly due to surgery duration variation. This simulation can serve as a support tool in decision-making, according to the degree of conservatism of the decision maker, Operating Rooms scheduling policies can be established.

[pt] A migração heterogênea de computações se refere ao movimento de uma computação em execução entre plataformas diferentes. Trata-se de um procedimento difícil, que requer mecanismos de captura e restauração do estado de execução que permitam a identificação da estrutura da computação e seus dados. Estes mecanismos, quando oferecidos, aparecem tradicionalmente na forma de soluções ad-hoc que são difíceis de adaptar aos requisitos de diferentes aplicações. Esta tese discute a necessidade da presença de suporte para captura e restauração de execuções nas linguagens de programação. Este suporte deve ser genérico o suficiente para que sobre ele possam ser implantadas diferentes políticas de captura e restauração, tanto no contexto de migração como no de persistência heterogêneas. Este trabalho estende a linguagem de programação Lua com uma API que permite ao programador reificar estruturas internas de execução em entidades manipuláveis da linguagem, para estudar os mecanismos básicos que uma linguagem deveria oferecer para permitir a implementação de diferentes políticas. / [en] The heterogeneous migration of computations allow computations to move between different platforms. It is a difficult procedure, that demands mechanisms for the capture and restoration of the state of the execution allowing for the identification of the structure of the computation and its data. This support, when offered, commonly appears in the form of ad-hoc solutions which are difficult to tailor or adapt to different needs. This thesis discusses the need for this support in current programming languages. This support must allow the implementation of different appliications that can profit from the ability of capturing and restoring computations heterogeneously, like migration and persistence. To experiment with this item, we extend the Lua programming language with an API that allows the programmer to reify the internal structures of execution into manipulable language entities, to explore the basic mechanisms a language should provide in order to support the implementation of diferent policies.

[pt] Muitas aplicações são tornadas programáveis para usuários finais avançados adicionando recursos como scripting e macros. Outras aplicações dão a uma linguagem de programação um papel central na sua interface com o usuário. Esse é o caso, por exemplo, da linguagem de fórmulas de planilhas de cálculo. Enquanto a área de scripting se beneficiou dos avanços das pesquisas em linguagens de programação, produzindo linguagens maduras e reusáveis, o estado das linguagens em nível de interface não teve o mesmo grau de desenvolvimento. Argumentamos que um melhor entendimento desta classe de linguagens se faz necessário. Neste trabalho, modelamos semânticas de linguagens de usuário final existentes, em três diferentes domínios: multimídia, planilhas e engenharia. Nosso foco é em linguagens de dataflow, um paradigma representativo em aplicações programáveis por usuários finais. Com base nessa análise, temos como objetivo prover um melhor entendimento do design de linguagens de dataflow no contexto de programação de usuários finais e propor linhas-guia para o projeto de linguagens de nível de interface baseadas neste paradigma para aplicações programáveis. / [en] Many applications are made programmable for advanced end-users by adding facilities such as scripting and macros. Other applications take a programming language to the center stage of its UI. That is the case, for example, of the spreadsheet formula language. While scripting has benefited from the advances of programming language research, producing mature and reusable languages, the state of UI-level languages lags behind. We claim that a better understanding of such languages is necessary. In this work, we model the semantics of existing end-user programming languages in three different domains: multimedia, spreadsheets and engineering. Our focus is on dataflow languages, a representative paradigm for end-user programmable applications. Based on this analysis, we aim to provide a better understanding of dataflow semantics as used in the context of end-user programming and propose guidelines for the design of UI-level languages for end-user programmable applications.

Desde a introdução da World Wide Web para o mundo nos inícios de 1990, usando a Internet como uma rede para transferir dados, empregando uma forma de expressão chamada de Hipertexto, a qual liga as informações relacionadas e combinadas com multimídia, os Webs resultantes têm aberto novas possibilidades de expressão e comunicação. A quantidade de tráfego de dados na Web e o número de computadores ofertando informação vem crescendo dramaticamente, mas falta expressividade e qualidade interativa na Web; ainda assim, vem despertando um grande interesse instrutivo e útil. O ilimitado universo de possibilidades da Web para acessar aplicações seguras, portáveis e independentes para cada plataforma em hardware e software e que possam chegar a qualquer lugar sobre a Internet, surge a linguagem Java da Sun Microsystem [DEC 95]. A habilidade de Java para executar código sobre hosts remotos de uma maneira segura é uma necessidade crítica para muitas organizações de desenvolvedores de software e provedores de Internet na atualidade [ARN 96]. A linguagem Java é realmente valiosa para redes de ambientes distribuídos como a Web. Entretanto, Java vai mais longe deste domínio ao fornecer uma linguagem de programação de propósito geral poderosa e adequada para construir uma variedade de aplicações que não dependem das características da rede [ARN 96]. O modelo imperativo tradicional é padrão e quase universal vem tendo uma profunda influência sobre a natureza das linguagens de programação e ainda continua a tendência de sempre ter uma direção para fornecer mais e mais formas abstratas de resolver problemas, tentando mudar a simplicidade na programação com rapidez na execução de programas [FIE 88]. Parece. portanto, natural e quase inevitável o desenvolvimento em tecnologia das linguagens. Os amplos esforços gastos em desenvolver métodos rigorosos para especificar, produzir, verificar software e produtos de hardware, mas os esforços foram restringidos às linguagens convencionais. A aproximação natural de Von Neumann tem contribuído a esta falha desde a noção de um estado global que pode mudar arbitrariamente em cada passo da computação e vem sendo provado ser intuitivamente e matematicamente intratável. Esta falha tem tornado ao software o componente mais caro para muitos sistemas de computação [GLA 84]. Os primeiros passos para solucionar estas falhas foram tomadas pela programação estruturada ao trabalhar nas áreas de especificação formal, verificação de programas e na semântica formal que ainda continuam em pesquisa. O crescimento numeroso de pesquisadores têm certeza de que os problemas originam-se da aproximação fundamental à filosofia de Von Neumann e estão voltando-se para uma linguagem de um novo tipo. Uma de tais aproximações é a tomada pelas linguagens de programação funcional [PLA 93]. Num programa funcional, o resultado de uma função chamada é unicamente determinado pelos valores atuais dos argumentos da função [PLA 93]. As linguagens de programação funcional têm a vantagem que elas oferecem um uso geral das funções, o qual não esta disponível nas linguagens imperativas clássicas. Devido a ausência de efeitos colaterais, as provas de correção dos programas são mais fáceis que nas linguagens imperativas. As funções podem ser avaliadas em qualquer ordem assim como a disponibilidade total das mesmas, a nova geração de linguagens funcionais também oferecem uma elegante noção de uso amigável [PLA 93]. Os padrões e a proteção que fornecem ao usuário um acesso simples a estruturas de dados complexos, basicamente não tendo a preocupação do gerenciamento da memória, como faz a linguagem Java. O objetivo principal deste trabalho é a descrição da implementação de um Construtor de Funções Java (LispJ), usado para gerar funções Lisp em código Java utilizando a linguagem Java da Sun Microsystem como ambiente de desenvolvimento. A descrição compreende a codificação de um Interpretador Lisp da linguagem funcional LISP, e a codificação do Construtor de Funções Java visualizado através de um applet Java utilizado como interface entre o Construtor de Funções Java e o usuário sobre a Internet. / Since the introduction of the World Wide Web to the world in the beginning of the nineties, using the Internet as a network to transfer data, using a form of expression called Hypertext, which connects related and combined information with multimedia, the resulting Webs have opened new possibilities of expression and communication. The amount of data traffic in the Web and the number of computers offering information have been growing dramatically, but there is a lack of interactive expressivity and quality in the Web; nevertheless, its instructive and useful interest is growing wider. From the unlimited universe of possibilities of the Web to access safe, portable and independent applications for each platform in hardware and software and that are able to get anywhere on the Internet, there is the Java Sun Mycrosystem language [DEC 95]. Java's ability to perform code on remote hosts in a safe way is a critical need for many software developing organizations and Internet providers nowadays [ARN 96]. Java language is really valuable for network environments arranged as the Web. However, Java extends further from this domain as it provides a broad programming language that is powerful and adequate to build a variety of applications which do not depend on the characteristics of the network [ARN 96]. The prevailing traditional model is a pattern and almost universal, has had a deep influence on the nature of the programming languages and there is still a trend of one direction to provide more and more abstract ways of solving problems, trying to change the simplicity in the fast programming in programs run [FIE 88]. It seems, therefore, natural and almost inevitable the development in technology of the programming languages. Wide efforts were made to develop strict methods to specify, produce, check software and hardware products, but the efforts were restricted to conventional languages. Von Neumann's natural approximation has contributed to this gap since the notion of a global state which can change arbitrarily in each step of the computer science and has proven to be intuitively and mathematically intractable. This gap has turned the software into the most expensive component for many computing systems [GLA 84]. The first steps to solve these gaps were taken by the structured programming when working on the areas of formal specification, programs checking and the formal semantics, which are still being researched. The ever growing number of researchers are sure that the problems come from the fundamental approximation to Von Neumann's philosophy and are turning to a new kind of language. One of such approximations is the one through the functional programming languages [PLA 93]. In a functional program, the result of a called function is determined only by the present values of the function arguments [PLA 93]. The functional programming languages have the advantage of offering a general use of the functions, which is not available in the classic prevailling lan guages [PLA 93]. Due to absence of side effects, the correction tests in the programs are easier than in the prevailing languages. The functions may be evaluated in any order and so may their total disposal. The new generation of functional languages also offers an elegant notion of friendly use [PLA 93]. The patterns and protection offer the user a simple access to complex data structures, basically by not worrying about memory management, as occurs with the Java language. The main objetive of this work is the description of the implementation of a Java Functions Builder (Lisp1), used do generate Lisp functions in Java code utilizing the Java language from Sun microsystem as a developing environment. The description covers the code of the Lisp Interpreter of the LISP functional language, and the Java Functions Builder code visualized through a Java applet utilized as interface between the Java Functions Builder and the users on the Internet.

Este trabalho e dedicado ao estudo da exploração de paralelismo na Programação em Lógica. O aspecto declarativo das linguagens de Programação em Lógica permite uma exploração eficiente do paralelismo implícito no código, de forma mais simples que as linguagens imperativas. Ao mesmo tempo, o paralelismo tem-se mostrado uma forte opção para procura de aumentos significativos do desempenho dos computadores. Como conseqüência, nos últimos anos, diversas maquinas paralelas tem surgido no mercado. No entanto, a sua efetiva utilização ainda ressente-se de uma dificuldade de programação maior que a das maquinas sequênciais. Por outro lado, o alto nível das linguagens de Programação em Lógica permite o desenvolvimento de programas de forma mais rápida e concisa do que as linguagens tradicionais (imperativas). Porem, apesar dos importantes progressos nas técnicas de compilação destas linguagens, elas permanecem menos eficientes que as linguagens imperativas. 0 aumento na eficiência de execução da Programação em Lógica, com o use do paralelismo, certamente estenderá o seu emprego. Em função disto, a unido da Programação em Lógica e maquinas paralelas tem sido proposta como uma alternativa para facilitar a programação das maquinas paralelas, bem como para aumentar o desempenho na Programação em Lógica. O ponto central do trabalho e a concepção de um modelo para exploração do paralelismo E Restrito na execução de Prolog, voltado para arquiteturas multiprocessadoras sem memória comum. Como ponto de partida foi utilizado o modelo já definido para exploração do paralelismo OU do projeto OPERA, do Instituto de Informática da UFRGS, de maneira que o modelo de paralelismo E proposto possa vir a compor, com aquele, uma plataforma que integre a exploração simultânea dos paralelismos E e OU. O modelo concebido compreende uma proposta de compilação e um ambiente de execução. A detecção e o controle do paralelismo é iniciado na compilação. Nesta fase, a gerada uma Expressão Condicional de Execução para cada clausula do programa Prolog, cuja avaliação em tempo de processamento determina a execução, em paralelo ou não, dos literais que compõem a clausula. A Maquina Abstrata Prolog, projetada para o emulador paralelo, é baseada na WAM (Warren Abstract Machine), uma das mais eficientes e difundidas técnicas para compilação Prolog. Isto, dentre outros aspectos, confere uma boa portabilidade ao modelo. O ambiente de execução compreende a concepção de uma arquitetura de processos formada por trabalhadores OPERA, uma filosofia de escalonamento de serviço entre estes trabalhadores, uma política para gerencia de sua memória e uma estratégia para as comunicações. Para validar o modelo proposto para exploração do paralelismo E, o mesmo foi implementado em rede local de estações Unix, obtendo bons resultados. / This work is devoted to the study of the exploration of parallelism in Logic Programming. The declarative aspect of the Logic Programming languages allows an efficient exploration of the implicit parallelism in the code, in a simpler form than the imperative languages. At the same time, parallelism has been shown as a strong option to the search for significant increases in the performance of the computers. As a consequence, in the last years, several parallel machines have been sprung up into the market. Nevertheless, their effective usefulness still undergoes some difficulties in programming which are greater than those of the sequential machines. On the other hand, the high level of Logic Programming languages allows programs development to be faster and concise than in the traditional languages (imperatives). However, despite the important progress in compiling techniques for these languages, they remain less efficient than the imperatives languages. The increase in execution efficiency of logic programs, with the use of parallelism, will probabily extend their use. Having this in mind, the union of the Logic Programming and parallel machines has been proposed as an alternative to make programming of the parallel machines easier, as well as to increase the performance of Logic Programming. The central aspect of the work is the conception of a model to explore the Restricted AND Parallelism in the execution of Prolog, turned to multiprocessing architectures without a common memory. As a starting point, the already defined model for exploring OR parallelism of the OPERA project, from the Instituto de Informatica da UFRGS was used. This happened so that the proposed model of AND parallelism can make up a plataform with that one to integrate the simultaneous exploration of the AND and OR parallelisms. The conceived model holds a proposal of compilation and execution environment. The detection and the control of the parallelism is started in the compilation. A Conditional Expression of Execution to each clause of the Prolog program is generated on this phase. Its evaluation, during the time of processing, determines the execution, whether or not in parallel, of the literals that constitute the clause. The Abstract Prolog Machine, projected for the parallel emulator, is based on the WAM (Warren Abstract Machine) which is one of the most efficient and spread techniques for Prolog compilation. This aspects, among others, gives a good portability to the model. The environmente of execution comprises the conception of an architecture of processes formed by OPERA workers and a philosophy of scheduling service among these workers; it also comprise a policy to manage its memory and a strategy for the communications. So that the proposed model for the exploitation of AND parallelism got validated, it was implemented on a local net of Unix workstations, obtaining good results.

Desde a introdução da World Wide Web para o mundo nos inícios de 1990, usando a Internet como uma rede para transferir dados, empregando uma forma de expressão chamada de Hipertexto, a qual liga as informações relacionadas e combinadas com multimídia, os Webs resultantes têm aberto novas possibilidades de expressão e comunicação. A quantidade de tráfego de dados na Web e o número de computadores ofertando informação vem crescendo dramaticamente, mas falta expressividade e qualidade interativa na Web; ainda assim, vem despertando um grande interesse instrutivo e útil. O ilimitado universo de possibilidades da Web para acessar aplicações seguras, portáveis e independentes para cada plataforma em hardware e software e que possam chegar a qualquer lugar sobre a Internet, surge a linguagem Java da Sun Microsystem [DEC 95]. A habilidade de Java para executar código sobre hosts remotos de uma maneira segura é uma necessidade crítica para muitas organizações de desenvolvedores de software e provedores de Internet na atualidade [ARN 96]. A linguagem Java é realmente valiosa para redes de ambientes distribuídos como a Web. Entretanto, Java vai mais longe deste domínio ao fornecer uma linguagem de programação de propósito geral poderosa e adequada para construir uma variedade de aplicações que não dependem das características da rede [ARN 96]. O modelo imperativo tradicional é padrão e quase universal vem tendo uma profunda influência sobre a natureza das linguagens de programação e ainda continua a tendência de sempre ter uma direção para fornecer mais e mais formas abstratas de resolver problemas, tentando mudar a simplicidade na programação com rapidez na execução de programas [FIE 88]. Parece. portanto, natural e quase inevitável o desenvolvimento em tecnologia das linguagens. Os amplos esforços gastos em desenvolver métodos rigorosos para especificar, produzir, verificar software e produtos de hardware, mas os esforços foram restringidos às linguagens convencionais. A aproximação natural de Von Neumann tem contribuído a esta falha desde a noção de um estado global que pode mudar arbitrariamente em cada passo da computação e vem sendo provado ser intuitivamente e matematicamente intratável. Esta falha tem tornado ao software o componente mais caro para muitos sistemas de computação [GLA 84]. Os primeiros passos para solucionar estas falhas foram tomadas pela programação estruturada ao trabalhar nas áreas de especificação formal, verificação de programas e na semântica formal que ainda continuam em pesquisa. O crescimento numeroso de pesquisadores têm certeza de que os problemas originam-se da aproximação fundamental à filosofia de Von Neumann e estão voltando-se para uma linguagem de um novo tipo. Uma de tais aproximações é a tomada pelas linguagens de programação funcional [PLA 93]. Num programa funcional, o resultado de uma função chamada é unicamente determinado pelos valores atuais dos argumentos da função [PLA 93]. As linguagens de programação funcional têm a vantagem que elas oferecem um uso geral das funções, o qual não esta disponível nas linguagens imperativas clássicas. Devido a ausência de efeitos colaterais, as provas de correção dos programas são mais fáceis que nas linguagens imperativas. As funções podem ser avaliadas em qualquer ordem assim como a disponibilidade total das mesmas, a nova geração de linguagens funcionais também oferecem uma elegante noção de uso amigável [PLA 93]. Os padrões e a proteção que fornecem ao usuário um acesso simples a estruturas de dados complexos, basicamente não tendo a preocupação do gerenciamento da memória, como faz a linguagem Java. O objetivo principal deste trabalho é a descrição da implementação de um Construtor de Funções Java (LispJ), usado para gerar funções Lisp em código Java utilizando a linguagem Java da Sun Microsystem como ambiente de desenvolvimento. A descrição compreende a codificação de um Interpretador Lisp da linguagem funcional LISP, e a codificação do Construtor de Funções Java visualizado através de um applet Java utilizado como interface entre o Construtor de Funções Java e o usuário sobre a Internet. / Since the introduction of the World Wide Web to the world in the beginning of the nineties, using the Internet as a network to transfer data, using a form of expression called Hypertext, which connects related and combined information with multimedia, the resulting Webs have opened new possibilities of expression and communication. The amount of data traffic in the Web and the number of computers offering information have been growing dramatically, but there is a lack of interactive expressivity and quality in the Web; nevertheless, its instructive and useful interest is growing wider. From the unlimited universe of possibilities of the Web to access safe, portable and independent applications for each platform in hardware and software and that are able to get anywhere on the Internet, there is the Java Sun Mycrosystem language [DEC 95]. Java's ability to perform code on remote hosts in a safe way is a critical need for many software developing organizations and Internet providers nowadays [ARN 96]. Java language is really valuable for network environments arranged as the Web. However, Java extends further from this domain as it provides a broad programming language that is powerful and adequate to build a variety of applications which do not depend on the characteristics of the network [ARN 96]. The prevailing traditional model is a pattern and almost universal, has had a deep influence on the nature of the programming languages and there is still a trend of one direction to provide more and more abstract ways of solving problems, trying to change the simplicity in the fast programming in programs run [FIE 88]. It seems, therefore, natural and almost inevitable the development in technology of the programming languages. Wide efforts were made to develop strict methods to specify, produce, check software and hardware products, but the efforts were restricted to conventional languages. Von Neumann's natural approximation has contributed to this gap since the notion of a global state which can change arbitrarily in each step of the computer science and has proven to be intuitively and mathematically intractable. This gap has turned the software into the most expensive component for many computing systems [GLA 84]. The first steps to solve these gaps were taken by the structured programming when working on the areas of formal specification, programs checking and the formal semantics, which are still being researched. The ever growing number of researchers are sure that the problems come from the fundamental approximation to Von Neumann's philosophy and are turning to a new kind of language. One of such approximations is the one through the functional programming languages [PLA 93]. In a functional program, the result of a called function is determined only by the present values of the function arguments [PLA 93]. The functional programming languages have the advantage of offering a general use of the functions, which is not available in the classic prevailling lan guages [PLA 93]. Due to absence of side effects, the correction tests in the programs are easier than in the prevailing languages. The functions may be evaluated in any order and so may their total disposal. The new generation of functional languages also offers an elegant notion of friendly use [PLA 93]. The patterns and protection offer the user a simple access to complex data structures, basically by not worrying about memory management, as occurs with the Java language. The main objetive of this work is the description of the implementation of a Java Functions Builder (Lisp1), used do generate Lisp functions in Java code utilizing the Java language from Sun microsystem as a developing environment. The description covers the code of the Lisp Interpreter of the LISP functional language, and the Java Functions Builder code visualized through a Java applet utilized as interface between the Java Functions Builder and the users on the Internet.

Este trabalho e dedicado ao estudo da exploração de paralelismo na Programação em Lógica. O aspecto declarativo das linguagens de Programação em Lógica permite uma exploração eficiente do paralelismo implícito no código, de forma mais simples que as linguagens imperativas. Ao mesmo tempo, o paralelismo tem-se mostrado uma forte opção para procura de aumentos significativos do desempenho dos computadores. Como conseqüência, nos últimos anos, diversas maquinas paralelas tem surgido no mercado. No entanto, a sua efetiva utilização ainda ressente-se de uma dificuldade de programação maior que a das maquinas sequênciais. Por outro lado, o alto nível das linguagens de Programação em Lógica permite o desenvolvimento de programas de forma mais rápida e concisa do que as linguagens tradicionais (imperativas). Porem, apesar dos importantes progressos nas técnicas de compilação destas linguagens, elas permanecem menos eficientes que as linguagens imperativas. 0 aumento na eficiência de execução da Programação em Lógica, com o use do paralelismo, certamente estenderá o seu emprego. Em função disto, a unido da Programação em Lógica e maquinas paralelas tem sido proposta como uma alternativa para facilitar a programação das maquinas paralelas, bem como para aumentar o desempenho na Programação em Lógica. O ponto central do trabalho e a concepção de um modelo para exploração do paralelismo E Restrito na execução de Prolog, voltado para arquiteturas multiprocessadoras sem memória comum. Como ponto de partida foi utilizado o modelo já definido para exploração do paralelismo OU do projeto OPERA, do Instituto de Informática da UFRGS, de maneira que o modelo de paralelismo E proposto possa vir a compor, com aquele, uma plataforma que integre a exploração simultânea dos paralelismos E e OU. O modelo concebido compreende uma proposta de compilação e um ambiente de execução. A detecção e o controle do paralelismo é iniciado na compilação. Nesta fase, a gerada uma Expressão Condicional de Execução para cada clausula do programa Prolog, cuja avaliação em tempo de processamento determina a execução, em paralelo ou não, dos literais que compõem a clausula. A Maquina Abstrata Prolog, projetada para o emulador paralelo, é baseada na WAM (Warren Abstract Machine), uma das mais eficientes e difundidas técnicas para compilação Prolog. Isto, dentre outros aspectos, confere uma boa portabilidade ao modelo. O ambiente de execução compreende a concepção de uma arquitetura de processos formada por trabalhadores OPERA, uma filosofia de escalonamento de serviço entre estes trabalhadores, uma política para gerencia de sua memória e uma estratégia para as comunicações. Para validar o modelo proposto para exploração do paralelismo E, o mesmo foi implementado em rede local de estações Unix, obtendo bons resultados. / This work is devoted to the study of the exploration of parallelism in Logic Programming. The declarative aspect of the Logic Programming languages allows an efficient exploration of the implicit parallelism in the code, in a simpler form than the imperative languages. At the same time, parallelism has been shown as a strong option to the search for significant increases in the performance of the computers. As a consequence, in the last years, several parallel machines have been sprung up into the market. Nevertheless, their effective usefulness still undergoes some difficulties in programming which are greater than those of the sequential machines. On the other hand, the high level of Logic Programming languages allows programs development to be faster and concise than in the traditional languages (imperatives). However, despite the important progress in compiling techniques for these languages, they remain less efficient than the imperatives languages. The increase in execution efficiency of logic programs, with the use of parallelism, will probabily extend their use. Having this in mind, the union of the Logic Programming and parallel machines has been proposed as an alternative to make programming of the parallel machines easier, as well as to increase the performance of Logic Programming. The central aspect of the work is the conception of a model to explore the Restricted AND Parallelism in the execution of Prolog, turned to multiprocessing architectures without a common memory. As a starting point, the already defined model for exploring OR parallelism of the OPERA project, from the Instituto de Informatica da UFRGS was used. This happened so that the proposed model of AND parallelism can make up a plataform with that one to integrate the simultaneous exploration of the AND and OR parallelisms. The conceived model holds a proposal of compilation and execution environment. The detection and the control of the parallelism is started in the compilation. A Conditional Expression of Execution to each clause of the Prolog program is generated on this phase. Its evaluation, during the time of processing, determines the execution, whether or not in parallel, of the literals that constitute the clause. The Abstract Prolog Machine, projected for the parallel emulator, is based on the WAM (Warren Abstract Machine) which is one of the most efficient and spread techniques for Prolog compilation. This aspects, among others, gives a good portability to the model. The environmente of execution comprises the conception of an architecture of processes formed by OPERA workers and a philosophy of scheduling service among these workers; it also comprise a policy to manage its memory and a strategy for the communications. So that the proposed model for the exploitation of AND parallelism got validated, it was implemented on a local net of Unix workstations, obtaining good results.

Desde a introdução da World Wide Web para o mundo nos inícios de 1990, usando a Internet como uma rede para transferir dados, empregando uma forma de expressão chamada de Hipertexto, a qual liga as informações relacionadas e combinadas com multimídia, os Webs resultantes têm aberto novas possibilidades de expressão e comunicação. A quantidade de tráfego de dados na Web e o número de computadores ofertando informação vem crescendo dramaticamente, mas falta expressividade e qualidade interativa na Web; ainda assim, vem despertando um grande interesse instrutivo e útil. O ilimitado universo de possibilidades da Web para acessar aplicações seguras, portáveis e independentes para cada plataforma em hardware e software e que possam chegar a qualquer lugar sobre a Internet, surge a linguagem Java da Sun Microsystem [DEC 95]. A habilidade de Java para executar código sobre hosts remotos de uma maneira segura é uma necessidade crítica para muitas organizações de desenvolvedores de software e provedores de Internet na atualidade [ARN 96]. A linguagem Java é realmente valiosa para redes de ambientes distribuídos como a Web. Entretanto, Java vai mais longe deste domínio ao fornecer uma linguagem de programação de propósito geral poderosa e adequada para construir uma variedade de aplicações que não dependem das características da rede [ARN 96]. O modelo imperativo tradicional é padrão e quase universal vem tendo uma profunda influência sobre a natureza das linguagens de programação e ainda continua a tendência de sempre ter uma direção para fornecer mais e mais formas abstratas de resolver problemas, tentando mudar a simplicidade na programação com rapidez na execução de programas [FIE 88]. Parece. portanto, natural e quase inevitável o desenvolvimento em tecnologia das linguagens. Os amplos esforços gastos em desenvolver métodos rigorosos para especificar, produzir, verificar software e produtos de hardware, mas os esforços foram restringidos às linguagens convencionais. A aproximação natural de Von Neumann tem contribuído a esta falha desde a noção de um estado global que pode mudar arbitrariamente em cada passo da computação e vem sendo provado ser intuitivamente e matematicamente intratável. Esta falha tem tornado ao software o componente mais caro para muitos sistemas de computação [GLA 84]. Os primeiros passos para solucionar estas falhas foram tomadas pela programação estruturada ao trabalhar nas áreas de especificação formal, verificação de programas e na semântica formal que ainda continuam em pesquisa. O crescimento numeroso de pesquisadores têm certeza de que os problemas originam-se da aproximação fundamental à filosofia de Von Neumann e estão voltando-se para uma linguagem de um novo tipo. Uma de tais aproximações é a tomada pelas linguagens de programação funcional [PLA 93]. Num programa funcional, o resultado de uma função chamada é unicamente determinado pelos valores atuais dos argumentos da função [PLA 93]. As linguagens de programação funcional têm a vantagem que elas oferecem um uso geral das funções, o qual não esta disponível nas linguagens imperativas clássicas. Devido a ausência de efeitos colaterais, as provas de correção dos programas são mais fáceis que nas linguagens imperativas. As funções podem ser avaliadas em qualquer ordem assim como a disponibilidade total das mesmas, a nova geração de linguagens funcionais também oferecem uma elegante noção de uso amigável [PLA 93]. Os padrões e a proteção que fornecem ao usuário um acesso simples a estruturas de dados complexos, basicamente não tendo a preocupação do gerenciamento da memória, como faz a linguagem Java. O objetivo principal deste trabalho é a descrição da implementação de um Construtor de Funções Java (LispJ), usado para gerar funções Lisp em código Java utilizando a linguagem Java da Sun Microsystem como ambiente de desenvolvimento. A descrição compreende a codificação de um Interpretador Lisp da linguagem funcional LISP, e a codificação do Construtor de Funções Java visualizado através de um applet Java utilizado como interface entre o Construtor de Funções Java e o usuário sobre a Internet. / Since the introduction of the World Wide Web to the world in the beginning of the nineties, using the Internet as a network to transfer data, using a form of expression called Hypertext, which connects related and combined information with multimedia, the resulting Webs have opened new possibilities of expression and communication. The amount of data traffic in the Web and the number of computers offering information have been growing dramatically, but there is a lack of interactive expressivity and quality in the Web; nevertheless, its instructive and useful interest is growing wider. From the unlimited universe of possibilities of the Web to access safe, portable and independent applications for each platform in hardware and software and that are able to get anywhere on the Internet, there is the Java Sun Mycrosystem language [DEC 95]. Java's ability to perform code on remote hosts in a safe way is a critical need for many software developing organizations and Internet providers nowadays [ARN 96]. Java language is really valuable for network environments arranged as the Web. However, Java extends further from this domain as it provides a broad programming language that is powerful and adequate to build a variety of applications which do not depend on the characteristics of the network [ARN 96]. The prevailing traditional model is a pattern and almost universal, has had a deep influence on the nature of the programming languages and there is still a trend of one direction to provide more and more abstract ways of solving problems, trying to change the simplicity in the fast programming in programs run [FIE 88]. It seems, therefore, natural and almost inevitable the development in technology of the programming languages. Wide efforts were made to develop strict methods to specify, produce, check software and hardware products, but the efforts were restricted to conventional languages. Von Neumann's natural approximation has contributed to this gap since the notion of a global state which can change arbitrarily in each step of the computer science and has proven to be intuitively and mathematically intractable. This gap has turned the software into the most expensive component for many computing systems [GLA 84]. The first steps to solve these gaps were taken by the structured programming when working on the areas of formal specification, programs checking and the formal semantics, which are still being researched. The ever growing number of researchers are sure that the problems come from the fundamental approximation to Von Neumann's philosophy and are turning to a new kind of language. One of such approximations is the one through the functional programming languages [PLA 93]. In a functional program, the result of a called function is determined only by the present values of the function arguments [PLA 93]. The functional programming languages have the advantage of offering a general use of the functions, which is not available in the classic prevailling lan guages [PLA 93]. Due to absence of side effects, the correction tests in the programs are easier than in the prevailing languages. The functions may be evaluated in any order and so may their total disposal. The new generation of functional languages also offers an elegant notion of friendly use [PLA 93]. The patterns and protection offer the user a simple access to complex data structures, basically by not worrying about memory management, as occurs with the Java language. The main objetive of this work is the description of the implementation of a Java Functions Builder (Lisp1), used do generate Lisp functions in Java code utilizing the Java language from Sun microsystem as a developing environment. The description covers the code of the Lisp Interpreter of the LISP functional language, and the Java Functions Builder code visualized through a Java applet utilized as interface between the Java Functions Builder and the users on the Internet.

[pt] A atividade de Planejamento de Suprimento de Petróleo é um elo importante para a integração da Cadeia de Suprimento de Petróleo na PETROBRAS, uma vez que é responsável por refinar as informações do planejamento estratégico a ser implementado no nível operacional. Nesta tese, esse problema é definido e explicado em detalhes e um modelo de programação Inteira Mista é proposto para resolvê-lo. Embora os resolvedores de problemas de programação Inteira Mista tenham evoluído de forma surpreendente na última década, para esta aplicação em particular, com o modelo inicial proposto não é possível obter soluções com qualidade satisfatória em tempo computacional aceitável. Desta forma, a linha de pesquisa desta tese consistiu em investigar, em detalhe, a estrutura deste problemaa fim de encontrar reformulações mais adequadas e novos algoritmos para a solução deste problema. O foco principal desta tese é resolver de forma eficiente o problema de planejamento de suprimento de petróleo na PETROBRAS, no entanto, como subprodutos desse esforço são propostos um novo algoritmo de decomposição e reformulações que podem ser aplicados a uma ampla gama de problemas. No que diz respeito à realização do objetivo principal, todos os casos testados foram resolvidos de maneira eficiente através dos desenvolvimentos propostos. O novo algoritmo de decomposição se mostrou o método mais adequado para resolver as instâncias com mais de duas classes de navios operando em cada plataforma. Já para os casos com uma ou duas classes de navios, a formulação denominada Hull Relaxation, que tem como base uma estrutura definida neste trabalho como Cascading Knapsack Inequalities, é a melhor alternativa de solução. Tendo em vista estas alternativas de soluções, é implementado um algoritmo geral que automaticamente escolhe a melhor opção de solução, em função da estrutura do problema. Para a situação onde o número de classes de navios operando nas diversas plataformas varia entre um e quatro, pode-se usar mais de uma abordagem em paralelo e considerar como solução a alternativa mais rápida ou com melhor resultado. Este modelo está sendo testado na PETROBRAS e tem-se mostrado uma ferramenta eficaz para a integração de sua cadeia de suprimentos de petróleo, bem como permitindo a análise de cenários para a obtenção de soluções alternativas até então não exploradas. / [en] The Petroleum Supply Planning activity is an important link for the integration of the Petroleum Supply Chain at PETROBRAS as it is responsible for refining the strategic supply planning information to be used at the operational level. In this thesis we set the ground for understanding this important problem and we propose a mathematical model to solve it. Although the solvers in the last decade have evolved enormously, for this particular application we cannot get solutions with satisfactory quality in reasonable computational time with only the initial proposed model. This directed the line of research of this thesis into investigating, in detail, the structure of this problem in order to find more suitable reformulations and algorithms to tackle it. Our primary goal is to solve efficiently the petroleum supply planning problem at PETROBRAS. Nevertheless as a by-product of this endeavor, we propose a novel decomposition algorithm and reformulations based on a cascading knapsack structures that turn out to be applicable in a wide range of problems. Concerning the achievement of the main objective, we obtain good results for all instances we tested. We show that the novel decomposition algorithm is the most fitted method to solve the petroleum supply planning problem if we consider more than two tankers to offload each platform. In the case of one or two tankers to offload each platform, the hull relaxation formulation based on the cascading knapsack structure introduced after an inventory reformulation at platforms is the best option if one is to solve this problem. For the real application, these solution alternatives allow to implement a general algorithm that automatically switches to the best solution option depending on the structure of the problem. For the mixed situation, i.e., number of tanker varying from one to four, one can use more than one approaches in parallel and take the fastest or the best result obtained. This model is being tested at PETROBRAS and is showing to be an effective tool to help integrate its petroleum supply chain as well as to do what-if analysis to look for alternative solutions never thought before.

[pt] As técnicas de programação genética permitem flexibilidade no processo de otimização, possibilitando sua aplicação em diferentes áreas do conhecimento e fornecendo novas maneiras para que especialistas avancem em suas áreas com mais rapidez. Parameter mapping approach é um método de otimização numérica que utiliza a programação genética para mapear valores iniciais em parâmetros ótimos para um sistema. Embora esta abordagem produza bons resultados para problemas com soluções triviais, o uso de grandes equações/árvores pode ser necessário para tornar este mapeamento apropriado em sistemas mais complexos.A fim de aumentar a flexibilidade e aplicabilidade do método a sistemas de diferentes níveis de complexidade, este trabalho introduz uma generalização utilizando a programação genética multigênica, para realizar um mapeamento multivariado, evitando grandes estruturas complexas. Foram considerados três conjuntos de funções de benchmark, variando em complexidade e dimensionalidade. Análises estatísticas foram realizadas, sugerindo que este novo método é mais flexível e mais eficiente (em média), considerando funções de benchmark complexas e de grande dimensionalidade. Esta tese também apresenta uma abordagem do novo algoritmo para otimização numérica multimodal.Este segundo algoritmo utiliza algumas técnicas de niching, baseadas no procedimento chamado de clearing, para manter a diversidade da população. Um conjunto benchmark de funções multimodais, com diferentes características e níveis de dificuldade,foi utilizado para avaliar esse novo algoritmo. A análise estatística sugeriu que esse novo método multimodal, que também utiliza programação genética multigênica,pode ser aplicado para problemas que requerem mais do que uma única solução. Como forma de testar esses métodos em problemas do mundo real, uma aplicação em nanotecnologia é proposta nesta tese: ao timização estrutural de fotodetectores de infravermelho de poços quânticos a partir de uma energia desejada. Os resultados apresentam novas estruturas melhores do que as conhecidas na literatura (melhoria de 59,09 por cento). / [en] Genetic programming techniques allow flexibility in the optimization process, making it possible to use them in different areas of knowledge and providing new ways for specialists to advance in their areas more quickly and more accurately.Parameter mapping approach is a numerical optimization method that uses genetic programming to find an appropriate mapping scheme among initial guesses to optimal parameters for a system. Although this approach yields good results for problems with trivial solutions, the use of large equations/trees may be required to make this mapping appropriate for more complex systems.In order to increase the flexibility and applicability of the method to systems of different levels of complexity, this thesis introduces a generalization by thus using multi-gene genetic programming to perform a multivariate mapping, avoiding large complex structures.Three sets of benchmark functions, varying in complexity and dimensionality, were considered. Statistical analyses carried out suggest that this new method is more flexible and performs better on average, considering challenging benchmark functions of increasing dimensionality.This thesis also presents an improvement of this new method for multimodal numerical optimization.This second algorithm uses some niching techniques based on the clearing procedure to maintain the population diversity. A multimodal benchmark set with different characteristics and difficulty levels to evaluate this new algorithm is used. Statistical analysis suggested that this new multimodal method using multi-gene genetic programming can be used for problems that requires more than a single solution. As a way of testing real-world problems for these methods, one application in nanotechnology is proposed in this thesis: the structural optimization of quantum well infrared photodetector from a desired energy.The results present new structures better than those known in the literature with improvement of 59.09 percent.