Os algoritmos baseados no paradigma Simulated Annealing e suas variações são atualmente usados de forma ampla na resolução de problemas de otimização de larga escala. Esta popularidade é resultado da estrutura extremamente simples e aparentemente universal dos algoritmos, da aplicabilidade geral e da habilidade de fornecer soluções bastante próximas da ótima. No início da década de 80, Kirkpatrick e outros apresentaram uma proposta de utilização dos conceitos de annealing (resfriamento lento e controlado de sólidos) em otimização combinatória. Esta proposta considera a forte analogia entre o processo físico de annealing e a resolução de problemas grandes de otimização combinatória. Simulated Annealing (SA) é um denominação genérica para os algoritmos desenvolvidos com base nesta proposta. Estes algoritmos combinam técnicas de busca local e de randomização. O objetivo do presente trabalho é proporcionar um entendimento das características do Simulated Annealing e facilitar o desenvolvimento de algoritmos com estas características. Assim, é apresentado como Simulated Annealing e suas variações estão sendo utilizados na resolução de problemas de otimização combinatória, proposta uma formalização através de um método de desenvolvimento de algoritmos e analisados aspectos de complexidade. O método de desenvolvimento especifica um programa abstrato para um algoritmo Simulated Annealing seqüencial, identifica funções e predicados que constituem os procedimentos deste programa abstrato e estabelece axiomas que permitem a visualização das propriedades que estes procedimentos devem satisfazer. A complexidade do Simulated Annealing é analisada a partir do programa abstrato desenvolvido e de seus principais procedimentos, permitindo o estabelecimento de uma equação genérica para a complexidade. Esta equação genérica é aplicável aos algoritmos desenvolvidos com base no método proposto. Uma prova de correção é apresentada para o programa abstrato e um código exemplo é analisado com relação aos axiomas estabelecidos. O estabelecimento de axiomas tem como propósito definir uma semântica para o algoritmo, o que permite a um desenvolvedor analisar a correção do código especificado para um algoritmo levando em consideração estes axiomas. O trabalho foi realizado a partir de um estudo introdutório de otimização combinatória, de técnicas de resolução de problemas, de um levantamento histórico do uso do Simulated Annealing, das variações em torno do modelo e de embasamentos matemáticos documentados. Isto permitiu identificar as características essenciais dos algoritmos baseados no paradigma, analisar os aspectos relacionados com estas características, como as diferentes formas de realizar uma prescrição de resfriamento e percorrer um espaço de soluções, e construir a fundamentação teórica genérica proposta.

Teoria das Categorias é uma ramificação da Matemática Pura com campo científico aparentemente distinto daquele que é objeto de estudo e pesquisa para a Ciência da Computação. Entretanto, algumas características dessa teoria matemática demonstram sua utilidade na pesquisa computacional. Dentre essas características podemos citar independência de implementação, dualidade, herança de resultados, possibilidade de comparação da expressividade de formalismos, notação gráfica e, sobretudo, expressividade das construções categoriais. Sua expressividade é explicitamente destacada pelo MEC nas Diretrizes Curriculares de Cursos da Área de Computação e Informática, onde afirma-se que “Teoria das Categorias possui construções cujo poder de expressão não possui, em geral, paralelo em outras teorias”. Entretanto, Teoria das Categorias tem encontrado obstáculos para ser efetivamente aplicada na Ciência da Computação. A baixa oferta de bibliografia - predominantemente de língua inglesa - e a falta de uniformidade na exposição do que sejam os tópicos introdutórios convergem e potencializam outro grande empecilho à sua propagação: a baixa oferta de cursos com enfoque em Teoria das Categorias. A fim de transpor essas dificuldades, Fábio Victor Pfeiff desenvolveu o CaTLeT, um aplicativo de interface visual que tinha como objetivo facilitar o acesso aos conceitos introdutórios de Teoria das Categorias Com inspiração fortemente educacional, CaTLeT somente é capaz de representar objetos e morfismos atômicos, o que o limita a servir somente aos conceitos iniciais. Em 2003, o CaTLeT foi ampliado e os objetos e morfismos, antes atômicos, passaram a representar conjuntos e relações, respectivamente. Este projeto consiste em uma ampliação tanto do CaTLeT quanto dos objetivos que justificaram sua criação. Esta dissertação trata de um projeto de simulador categorial e de sua respectiva implementação as quais visam fornecer suporte computacional a fim de facilitar o acesso a conceitos intermediários de Teoria das Categorias e servir como suporte à pesquisa na área. A construção desse simulador possui três critérios de avaliação como parâmetro: boa acessibilidade, alta relevância das estruturas implementadas e alta cobertura. A nova ferramenta - denominada CaTReS - deve manter a acessibilidade a usuários leigos que sua predecessora possui e ampliar significativamente as estruturas suportadas, além de incluir tratamento à conceitos funtoriais. Dessa maneira, este projeto vem para auxiliar na superação dos obstáculos anteriormente mencionados.

Nos últimos 70 anos têm sido apresentadas várias propostas para caracteriza ção da noção intuitiva de computabilidade. O modelo de Computação mais conhecido para expressar a noção intuitiva de algoritmo é a Máquina de Turing. Esse trabalho apresenta máquinas abstratas que representam diferentes formas de comportamento computacional, sendo possível abordar a diversidade entre a Teoria da Computação Clássica (Máquina de Turing) e a Teoria da Computa- ção Interativa (Máquina de Turing Persistente). Com a evolução dos sistemas de computação, surgiu a necessidade de estender a de nição de Máquina de Turing para tratar uma diversidade de novas situações, esses problemas conduziram a uma mudança de paradigma. Neste contexto foi desenvolvido a Máquina de Turing Persistente, que é capaz de fundamentar a Teoria da Computação Interativa. Máquinas de Turing Persistentes (PeTM) são modelos que expressam comportamento interativo, esse modelo é uma extensão da Máquina de Turing. O presente trabalho tem como objetivo explorar paralelismo na Máquina de Turing Persistente, através da formalização de uma extensão paralela da PeTM e o estudo dos efeitos sobre essa extensão, variando o número de tas de trabalho. Contribui- ções desse trabalho incluem a de nição de uma máquina de Turing Persistente Paralela para modelar computação interativa e uma exposição de conceitos fundamentais e necessários para o entendimento desse novo paradigma. Os métodos e conceitos apresentados para formalização da computação na Máquina de Turing Persistente Paralela desenvolvidos nessa dissertação, podem servir como base para uma melhor compreensão da Teoria da Computação Interativa e da forma como o paralelismo pode ser especi cado em modelos teóricos.

Nos últimos 70 anos têm sido apresentadas várias propostas para caracteriza ção da noção intuitiva de computabilidade. O modelo de Computação mais conhecido para expressar a noção intuitiva de algoritmo é a Máquina de Turing. Esse trabalho apresenta máquinas abstratas que representam diferentes formas de comportamento computacional, sendo possível abordar a diversidade entre a Teoria da Computação Clássica (Máquina de Turing) e a Teoria da Computa- ção Interativa (Máquina de Turing Persistente). Com a evolução dos sistemas de computação, surgiu a necessidade de estender a de nição de Máquina de Turing para tratar uma diversidade de novas situações, esses problemas conduziram a uma mudança de paradigma. Neste contexto foi desenvolvido a Máquina de Turing Persistente, que é capaz de fundamentar a Teoria da Computação Interativa. Máquinas de Turing Persistentes (PeTM) são modelos que expressam comportamento interativo, esse modelo é uma extensão da Máquina de Turing. O presente trabalho tem como objetivo explorar paralelismo na Máquina de Turing Persistente, através da formalização de uma extensão paralela da PeTM e o estudo dos efeitos sobre essa extensão, variando o número de tas de trabalho. Contribui- ções desse trabalho incluem a de nição de uma máquina de Turing Persistente Paralela para modelar computação interativa e uma exposição de conceitos fundamentais e necessários para o entendimento desse novo paradigma. Os métodos e conceitos apresentados para formalização da computação na Máquina de Turing Persistente Paralela desenvolvidos nessa dissertação, podem servir como base para uma melhor compreensão da Teoria da Computação Interativa e da forma como o paralelismo pode ser especi cado em modelos teóricos.

Teoria das Categorias é uma ramificação da Matemática Pura com campo científico aparentemente distinto daquele que é objeto de estudo e pesquisa para a Ciência da Computação. Entretanto, algumas características dessa teoria matemática demonstram sua utilidade na pesquisa computacional. Dentre essas características podemos citar independência de implementação, dualidade, herança de resultados, possibilidade de comparação da expressividade de formalismos, notação gráfica e, sobretudo, expressividade das construções categoriais. Sua expressividade é explicitamente destacada pelo MEC nas Diretrizes Curriculares de Cursos da Área de Computação e Informática, onde afirma-se que “Teoria das Categorias possui construções cujo poder de expressão não possui, em geral, paralelo em outras teorias”. Entretanto, Teoria das Categorias tem encontrado obstáculos para ser efetivamente aplicada na Ciência da Computação. A baixa oferta de bibliografia - predominantemente de língua inglesa - e a falta de uniformidade na exposição do que sejam os tópicos introdutórios convergem e potencializam outro grande empecilho à sua propagação: a baixa oferta de cursos com enfoque em Teoria das Categorias. A fim de transpor essas dificuldades, Fábio Victor Pfeiff desenvolveu o CaTLeT, um aplicativo de interface visual que tinha como objetivo facilitar o acesso aos conceitos introdutórios de Teoria das Categorias Com inspiração fortemente educacional, CaTLeT somente é capaz de representar objetos e morfismos atômicos, o que o limita a servir somente aos conceitos iniciais. Em 2003, o CaTLeT foi ampliado e os objetos e morfismos, antes atômicos, passaram a representar conjuntos e relações, respectivamente. Este projeto consiste em uma ampliação tanto do CaTLeT quanto dos objetivos que justificaram sua criação. Esta dissertação trata de um projeto de simulador categorial e de sua respectiva implementação as quais visam fornecer suporte computacional a fim de facilitar o acesso a conceitos intermediários de Teoria das Categorias e servir como suporte à pesquisa na área. A construção desse simulador possui três critérios de avaliação como parâmetro: boa acessibilidade, alta relevância das estruturas implementadas e alta cobertura. A nova ferramenta - denominada CaTReS - deve manter a acessibilidade a usuários leigos que sua predecessora possui e ampliar significativamente as estruturas suportadas, além de incluir tratamento à conceitos funtoriais. Dessa maneira, este projeto vem para auxiliar na superação dos obstáculos anteriormente mencionados.

Teoria das Categorias é uma ramificação da Matemática Pura com campo científico aparentemente distinto daquele que é objeto de estudo e pesquisa para a Ciência da Computação. Entretanto, algumas características dessa teoria matemática demonstram sua utilidade na pesquisa computacional. Dentre essas características podemos citar independência de implementação, dualidade, herança de resultados, possibilidade de comparação da expressividade de formalismos, notação gráfica e, sobretudo, expressividade das construções categoriais. Sua expressividade é explicitamente destacada pelo MEC nas Diretrizes Curriculares de Cursos da Área de Computação e Informática, onde afirma-se que “Teoria das Categorias possui construções cujo poder de expressão não possui, em geral, paralelo em outras teorias”. Entretanto, Teoria das Categorias tem encontrado obstáculos para ser efetivamente aplicada na Ciência da Computação. A baixa oferta de bibliografia - predominantemente de língua inglesa - e a falta de uniformidade na exposição do que sejam os tópicos introdutórios convergem e potencializam outro grande empecilho à sua propagação: a baixa oferta de cursos com enfoque em Teoria das Categorias. A fim de transpor essas dificuldades, Fábio Victor Pfeiff desenvolveu o CaTLeT, um aplicativo de interface visual que tinha como objetivo facilitar o acesso aos conceitos introdutórios de Teoria das Categorias Com inspiração fortemente educacional, CaTLeT somente é capaz de representar objetos e morfismos atômicos, o que o limita a servir somente aos conceitos iniciais. Em 2003, o CaTLeT foi ampliado e os objetos e morfismos, antes atômicos, passaram a representar conjuntos e relações, respectivamente. Este projeto consiste em uma ampliação tanto do CaTLeT quanto dos objetivos que justificaram sua criação. Esta dissertação trata de um projeto de simulador categorial e de sua respectiva implementação as quais visam fornecer suporte computacional a fim de facilitar o acesso a conceitos intermediários de Teoria das Categorias e servir como suporte à pesquisa na área. A construção desse simulador possui três critérios de avaliação como parâmetro: boa acessibilidade, alta relevância das estruturas implementadas e alta cobertura. A nova ferramenta - denominada CaTReS - deve manter a acessibilidade a usuários leigos que sua predecessora possui e ampliar significativamente as estruturas suportadas, além de incluir tratamento à conceitos funtoriais. Dessa maneira, este projeto vem para auxiliar na superação dos obstáculos anteriormente mencionados.

Nos últimos 70 anos têm sido apresentadas várias propostas para caracteriza ção da noção intuitiva de computabilidade. O modelo de Computação mais conhecido para expressar a noção intuitiva de algoritmo é a Máquina de Turing. Esse trabalho apresenta máquinas abstratas que representam diferentes formas de comportamento computacional, sendo possível abordar a diversidade entre a Teoria da Computação Clássica (Máquina de Turing) e a Teoria da Computa- ção Interativa (Máquina de Turing Persistente). Com a evolução dos sistemas de computação, surgiu a necessidade de estender a de nição de Máquina de Turing para tratar uma diversidade de novas situações, esses problemas conduziram a uma mudança de paradigma. Neste contexto foi desenvolvido a Máquina de Turing Persistente, que é capaz de fundamentar a Teoria da Computação Interativa. Máquinas de Turing Persistentes (PeTM) são modelos que expressam comportamento interativo, esse modelo é uma extensão da Máquina de Turing. O presente trabalho tem como objetivo explorar paralelismo na Máquina de Turing Persistente, através da formalização de uma extensão paralela da PeTM e o estudo dos efeitos sobre essa extensão, variando o número de tas de trabalho. Contribui- ções desse trabalho incluem a de nição de uma máquina de Turing Persistente Paralela para modelar computação interativa e uma exposição de conceitos fundamentais e necessários para o entendimento desse novo paradigma. Os métodos e conceitos apresentados para formalização da computação na Máquina de Turing Persistente Paralela desenvolvidos nessa dissertação, podem servir como base para uma melhor compreensão da Teoria da Computação Interativa e da forma como o paralelismo pode ser especi cado em modelos teóricos.

Este trabalho propõe o estudo dos espaços coerentes do ponto de vista da teoria dos topos, ou seja, consiste em uma análise, em termos de topos, das principais categorias de espaços coerentes. Os espaços coerentes constituem um tipo de domínio que apresenta algumas particularidades que o distinguem dos demais, por exemplo, considera admissíveis no conjunto de funções somente aquelas que, além de contínuas no sentido de Scott - preservam supremos de conjuntos dirigidos, também são estáveis e lineares. Um topos e uma categoria Cartesiana fechada com classificador de subobjetos. Isso faz com que todo topos se comporte como Set (conjuntos como objetos e funções como morfismos), ou seja, uma categoria na qual as interpretações de suas construções básicas seguem a Teoria dos Conjuntos. Entre as categorias de Espaços Coerentes, tem-se a categoria STAB, cujos objetos são os espaços coerentes e os morfismos são funções estáveis entre esses espaços, que é uma categoria cartesiana fechada. Isto significa que STAB é uma categoria especial no sentido computacional: além de possuir o produto binário para todos os seus objetos, STAB apresenta objeto exponencial e morfismo de avaliação, garantindo significado para processos computacionais. A subcategoria LIN da categoria STAB, cujos morfismos são as funções lineares, não é uma categoria cartesiana fechada. Entretanto, LIN é uma categoria monoidal simétrica que e fechada. Este, condição e suficiente para que em LIN também se tenha a garantia de se obter significado para processos computacionais. Apresenta-se então, uma interpretação computacional da estrutura destas categorias e uma análise das mesmas do ponto de vista de topos, isto é, da existência ou não de classificador de subobjetos. / This work proposes the study of coherent spaces from the point of view of the Topos Theory, that is, it consists of an analysis of the main categories of coherent spaces in terms of topos. The coherent spaces make up a kind of domain which presents some peculiarities that separate it from the rest, for example, in the complex whole of the functions it only considers permissible, those which, apart from being continuous in the sense of Scott - preserving supremo of directed sets, it is also stable and linear. A topos is a Cartesian closed with subobject classifier. This makes topos behaves like Set (sets as objects and functions as morphisms), that is, a category in which the interpretations of its basic constructions follow the Theory of Sets. Among the categories of Coherent Spaces, there is the STAB category, a closed Cartesian category, the objects of which are the coherent spaces, having morphisms as stable functions among these spaces. This means that STAB is a special category in the computational sense: apart from having a binary product for all its objects, STAB presents an exponential object and a morphism of evaluation, ensuring meaning for computational processes. The subcategory LIN of the STAB category, the morphisms of which are linear functions, is not a closed Cartesian category. However, LIN is a symmetrical monoidal category which is closed. This condition is sufficient to also have in LIN the guarantee of obtaining meaning for computational processes. Thus, a computational interpretation of the structure of these categories will be presented, as well as an analysis of them from the point of view of the Topos Theory, that is, if subobject classifier exists or not.

Este trabalho versa sobre a avaliação da compressão de dados e da qualidade de imagens e animações usando-se complexidade de Kolmogorov, simulação de máquinas e distância de informação. Complexidade de Kolmogorov é uma teoria da informação e da aleatoriedade baseada na máquina de Turing. No trabalho é proposto um método para avaliar a compressão de dados de modelos de animação gráfica usando-se simulação de máquinas. Também definimos formalmente compressão de dados com perdas e propomos a aplicação da distância de informação como uma métrica de qualidade de imagem. O desenvolvimento de uma metodologia para avaliar a compressão de dados de modelos de animação gráfica para web é útil, a medida que as páginas na web estão sendo cada vez mais enriquecidas com animações, som e vídeo, e a economia de banda de canal tornase importante, pois os arquivos envolvidos são geralmente grandes. Boa parte do apelo e das vantagens da web em aplicações como, por exemplo, educação à distância ou publicidade, reside exatamente na existência de elementos multimídia, que apoiam a idéia que está sendo apresentada na página. Como estudo de caso, o método de comparação e avaliação de modelos de animação gráfica foi aplicado na comparação de dois modelos: GIF (Graphics Interchange Format) e AGA (Animação Gráfica baseada em Autômatos finitos), provando formalmente que AGA é melhor que GIF (“melhor” significa que AGA comprime mais as animações que GIF). Foi desenvolvida também uma definição formal de compressão de dados com perdas com o objetivo de estender a metodologia de avalição apresentada Distância de informação é proposta como uma nova métrica de qualidade de imagem, e tem como grande vantagem ser uma medida universal, ou seja, capaz de incorporar toda e qualquer medida computável concebível. A métrica proposta foi testada em uma série de experimentos e comparada com a distância euclidiana (medida tradicionalmente usada nestes casos). Os resultados dos testes são uma evidência prática que a distância proposta é efetiva neste novo contexto de aplicação, e que apresenta, em alguns casos, resultados superiores ao da distância euclidiana. Isto também é uma evidência que a distância de informação é uma métrica mais fina que a distância euclidiana. Também mostramos que há casos em que podemos aplicar a distância de informação, mas não podemos aplicar a distância euclidiana. A métrica proposta foi aplicada também na avaliação de animações gráficas baseadas em frames, onde apresentou resultados melhores que os obtidos com imagens puras. Este tipo de avaliação de animações é inédita na literatura, segundo revisão bibliográfica feita. Finalmente, neste trabalho é apresentado um refinamento à medida proposta que apresentou resultados melhores que a aplicação simples e direta da distância de informação.

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.