O presente trabalho apresenta uma investigação sobre algumas operações categoriais baseadas em grafos e a aplicação das mesmas a uma área específica da Ciência da Computação, a saber, animações computacionais baseadas em autômatos finitos com saída. As operações categoriais estudadas neste trabalho são: Produto, Coproduto, Soma Amalgamada e Produto Fibrado. O modelo AGA (Animação Gráfica baseada em Autômatos finitos) foi o escolhido para ser utilizado como base desta dissertação. Inspirado nestes estudos, o trabalho contém uma proposta de como aplicar tais operações com o objetivo de definir animações aparentemente complexas, de forma simples, precisa e de fácil implementação. O enfoque está baseado em J. Stoy que diz que um dos objetivos para o uso da semântica formal de teoria das categorias é “sugerir meios ou formas para o projetista desenvolver sistemas melhores, mais elegantes (“limpos”) e com descrições formais mais simples”. Entretanto, não é objetivo deste trabalho verificar se a utilização destas operações é ou não melhor do que a utilização de qualquer outra solução para criar novas animações. Esta dissertação traz uma nova versão do modelo AGA, denominada AGANd (Animação Gráfica baseada em Autômatos finitos Não determinísticos), sendo que o AGA utiliza apenas autômatos finitos determinísticos para criar os atores de uma animação. Com a utilização do AGANd obtém-se animações mais realistas e mais flexíveis. A aplicação destas operações se dá nos dois modelos, os resultados obtidos a partir de cada uma das operações sobre os mesmos são apresentados de forma detalhada e ilustrados com os autômatos resultantes no decorrer do trabalho. É apresentada uma sugestão de implementação para cada uma das operações, visando estender o protótipo já implementado do modelo AGA. Isso faz com que o leitor seja estimulado a aplicar estas e outras operações categoriais em novas animações baseadas ou não nos modelos apresentados, despertando até mesmo para seu uso em outras áreas da Ciência da Computação.

Um span em uma categoria é um par ordenado de morfismos dessa categoria, ambos com origem num mesmo objeto. O destino do primeiro morfismo é a origem do span e o destino do segundo morfismo é o destino do span. Spans, embora sejam uma estrutura bastante simples numa categoria e tenham uma definição também bastante simples, são versáteis, pois, com especializações sutis apresentadas aqui, são capazes de representar outras estruturas, tais como as tratadas nesses trabalho: relações binárias, multirrelações binárias, grafos e, em conjunto com um morfismo adicional, sistemas de transições etiquetadas (LTS). Permitem ainda, como proposto nesse trabalho, definir de forma também simples, redes de Petri como sendo um endospan em uma categoria. Mostra-se que a composição de spans aplicada a essas estruturas é capaz de expresar a composição de multirrelações — mas não de relações —, uma composição de grafos cujo grafo resultante indica caminhos em que cada parte é uma aresta de um dos grafos operados, uma composição de LTS cujo LTS resultante apresenta transações que podem ser compostas por transições de diferentes LTS e uma composição de redes de Petri cujo resultado também apresenta transações compostas por transições que podem ser realizadas em redes de Petri distintas. Mostra-se algumas propriedades dessas composições, bem como suas provas. Como verificar propriedades de relações e de grafos através de spans também é proposto.

O presente trabalho apresenta uma investigação sobre algumas operações categoriais baseadas em grafos e a aplicação das mesmas a uma área específica da Ciência da Computação, a saber, animações computacionais baseadas em autômatos finitos com saída. As operações categoriais estudadas neste trabalho são: Produto, Coproduto, Soma Amalgamada e Produto Fibrado. O modelo AGA (Animação Gráfica baseada em Autômatos finitos) foi o escolhido para ser utilizado como base desta dissertação. Inspirado nestes estudos, o trabalho contém uma proposta de como aplicar tais operações com o objetivo de definir animações aparentemente complexas, de forma simples, precisa e de fácil implementação. O enfoque está baseado em J. Stoy que diz que um dos objetivos para o uso da semântica formal de teoria das categorias é “sugerir meios ou formas para o projetista desenvolver sistemas melhores, mais elegantes (“limpos”) e com descrições formais mais simples”. Entretanto, não é objetivo deste trabalho verificar se a utilização destas operações é ou não melhor do que a utilização de qualquer outra solução para criar novas animações. Esta dissertação traz uma nova versão do modelo AGA, denominada AGANd (Animação Gráfica baseada em Autômatos finitos Não determinísticos), sendo que o AGA utiliza apenas autômatos finitos determinísticos para criar os atores de uma animação. Com a utilização do AGANd obtém-se animações mais realistas e mais flexíveis. A aplicação destas operações se dá nos dois modelos, os resultados obtidos a partir de cada uma das operações sobre os mesmos são apresentados de forma detalhada e ilustrados com os autômatos resultantes no decorrer do trabalho. É apresentada uma sugestão de implementação para cada uma das operações, visando estender o protótipo já implementado do modelo AGA. Isso faz com que o leitor seja estimulado a aplicar estas e outras operações categoriais em novas animações baseadas ou não nos modelos apresentados, despertando até mesmo para seu uso em outras áreas da Ciência da Computação.

Um span em uma categoria é um par ordenado de morfismos dessa categoria, ambos com origem num mesmo objeto. O destino do primeiro morfismo é a origem do span e o destino do segundo morfismo é o destino do span. Spans, embora sejam uma estrutura bastante simples numa categoria e tenham uma definição também bastante simples, são versáteis, pois, com especializações sutis apresentadas aqui, são capazes de representar outras estruturas, tais como as tratadas nesses trabalho: relações binárias, multirrelações binárias, grafos e, em conjunto com um morfismo adicional, sistemas de transições etiquetadas (LTS). Permitem ainda, como proposto nesse trabalho, definir de forma também simples, redes de Petri como sendo um endospan em uma categoria. Mostra-se que a composição de spans aplicada a essas estruturas é capaz de expresar a composição de multirrelações — mas não de relações —, uma composição de grafos cujo grafo resultante indica caminhos em que cada parte é uma aresta de um dos grafos operados, uma composição de LTS cujo LTS resultante apresenta transações que podem ser compostas por transições de diferentes LTS e uma composição de redes de Petri cujo resultado também apresenta transações compostas por transições que podem ser realizadas em redes de Petri distintas. Mostra-se algumas propriedades dessas composições, bem como suas provas. Como verificar propriedades de relações e de grafos através de spans também é proposto.

Um span em uma categoria é um par ordenado de morfismos dessa categoria, ambos com origem num mesmo objeto. O destino do primeiro morfismo é a origem do span e o destino do segundo morfismo é o destino do span. Spans, embora sejam uma estrutura bastante simples numa categoria e tenham uma definição também bastante simples, são versáteis, pois, com especializações sutis apresentadas aqui, são capazes de representar outras estruturas, tais como as tratadas nesses trabalho: relações binárias, multirrelações binárias, grafos e, em conjunto com um morfismo adicional, sistemas de transições etiquetadas (LTS). Permitem ainda, como proposto nesse trabalho, definir de forma também simples, redes de Petri como sendo um endospan em uma categoria. Mostra-se que a composição de spans aplicada a essas estruturas é capaz de expresar a composição de multirrelações — mas não de relações —, uma composição de grafos cujo grafo resultante indica caminhos em que cada parte é uma aresta de um dos grafos operados, uma composição de LTS cujo LTS resultante apresenta transações que podem ser compostas por transições de diferentes LTS e uma composição de redes de Petri cujo resultado também apresenta transações compostas por transições que podem ser realizadas em redes de Petri distintas. Mostra-se algumas propriedades dessas composições, bem como suas provas. Como verificar propriedades de relações e de grafos através de spans também é proposto.

O presente trabalho apresenta uma investigação sobre algumas operações categoriais baseadas em grafos e a aplicação das mesmas a uma área específica da Ciência da Computação, a saber, animações computacionais baseadas em autômatos finitos com saída. As operações categoriais estudadas neste trabalho são: Produto, Coproduto, Soma Amalgamada e Produto Fibrado. O modelo AGA (Animação Gráfica baseada em Autômatos finitos) foi o escolhido para ser utilizado como base desta dissertação. Inspirado nestes estudos, o trabalho contém uma proposta de como aplicar tais operações com o objetivo de definir animações aparentemente complexas, de forma simples, precisa e de fácil implementação. O enfoque está baseado em J. Stoy que diz que um dos objetivos para o uso da semântica formal de teoria das categorias é “sugerir meios ou formas para o projetista desenvolver sistemas melhores, mais elegantes (“limpos”) e com descrições formais mais simples”. Entretanto, não é objetivo deste trabalho verificar se a utilização destas operações é ou não melhor do que a utilização de qualquer outra solução para criar novas animações. Esta dissertação traz uma nova versão do modelo AGA, denominada AGANd (Animação Gráfica baseada em Autômatos finitos Não determinísticos), sendo que o AGA utiliza apenas autômatos finitos determinísticos para criar os atores de uma animação. Com a utilização do AGANd obtém-se animações mais realistas e mais flexíveis. A aplicação destas operações se dá nos dois modelos, os resultados obtidos a partir de cada uma das operações sobre os mesmos são apresentados de forma detalhada e ilustrados com os autômatos resultantes no decorrer do trabalho. É apresentada uma sugestão de implementação para cada uma das operações, visando estender o protótipo já implementado do modelo AGA. Isso faz com que o leitor seja estimulado a aplicar estas e outras operações categoriais em novas animações baseadas ou não nos modelos apresentados, despertando até mesmo para seu uso em outras áreas da Ciência da Computação.

Com o objetivo de desenvolver uma fundamentação teórica para o estudo formal de problemas de otimização NP-difíceis, focalizando sobre as propriedades estruturais desses problemas relacionadas à questão da aproximabilidade, este trabalho apresenta uma abordagem semântica para tratar algumas questões originalmente estudadas dentro da Teoria da Complexidade Computacional, especificamente no contexto da Complexidade Estrutural. Procede-se a uma investigação de interesse essencialmente teórico, buscando obter uma formalização para a teoria dos algoritmos aproximativos em dois sentidos. Por um lado, considera-se um algoritmo aproximativo para um problema de otimização genérico como o principal objeto de estudo, estruturando-se matematicamente o conjunto de algoritmos aproximativos para tal problema como uma ordem parcial, no enfoque da Teoria dos Domínios de Scott. Por outro lado, focaliza-se sobre as reduções entre problemas de otimização, consideradas como morfismos numa abordagem dentro da Teoria das Categorias, onde problemas de otimização e problemas aproximáveis são os objetos das novas categorias introduzidas. Dentro de cada abordagem, procura-se identificar aqueles elementos universais, tais como elementos finitos, objetos totais, problemas completos para uma classe, apresentando ainda um sistema que modela a hierarquia de aproximação para um problema de otimização NP-difícil, com base na teoria categorial da forma. Cada uma destas estruturas matemáticas fornecem fundamentação teórica em aspectos que se complementam. A primeira providencia uma estruturação interna para os objetos, caracterizando as classes de problemas em relação às propriedades de aproximabilidade de seus membros, no sentido da Teoria dos Domínios, enquanto que a segunda caracteriza-se por relacionar os objetos entre si, em termos de reduções preservando aproximação entre problemas, num ponto de vista externo, essencialmente categorial.

O conceito de parcialidade e importante em diversas áreas como a Matemática e a Ciência da Computação; ele pode ser utilizado, por exemplo, para expressar computações que não terminam e para definir funções recursivas parciais. Com rela cão a grafos, categorias de homomorfismos parciais são comuns (por exemplo, em gramáticas de grafos com a técnica de single-pushout). Este trabalho propõe uma abordagem diferente: a parcialidade é usada na estrutura interna dos objetos (não nos morfismos).Istoéfeito utilizando uma extensão do conceito de Categoria das Setas, chamada de Categoria das Setas Parciais. E definida entãoa categoria Grp de grafos parciais(tais que arcos podem possuir ou não vértices de origem e/ou destino) e homomorfismos totais.A generalização deste modelo resulta em categorias de grafos parciais internos.Émostrado que Grp é bicompleta e, se C é um topos, a categoria dos grafos parciais internos a C é cocompleta. Grafos parciais podem ser utilizados para definir modelos computacionais tais como autômatos. Uma categoria de Autômatos Parciais, denominada Autp, é construída a partir da categoria de Grafos Parciais. Usando uma extensão de composição de spans de grafos para autômatos, chamada de Composição de Transições, e possível definir as computações de autômatos. Brevemente, uma composição de transi cões de dois autômatos parciais resulta em um autômato parcial onde cada transição representa um caminho de tamanho dois (entre vértices), tal que a primeira metade é uma transição do primeiro autômato e a segunda metade é uma transição do segundo. É possível compor um autômato consigo mesmo diversas vezes; no caso de n sucessivas composições de transições, pode-se obter as palavras da linguagem aceita pelo autômato que necessitam de n+1 passos de computação nos arcos que não possuem origem e nem destino definidos do autômato parcial resultante.

Teoria das Categorias é uma ramificação da Matemática Pura relativamente recente, tendo sua base sido enunciada ao final da primeira metade do século XX. Embora seja Teoria de grande expressividade, sua aplicação efetiva tem encontrado até o momento grandes obstáculos, todos decorrência natural da brevidade de sua História. A baixa oferta de bibliografia (e predominantemente em 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. Consegue, a despeito destes obstáculos, arrebanhar admiradores em inúmeros centros de reconhecida excelência técnica e científica. Dentre todas as áreas do conhecimento, atrai em especial a atenção da Ciência da Computação, por características como independência de implementação, dualidade, herança de resultados, possibilidade de comparação da expressividade de outros formalismos, forte embasamento em notação gráfica e, sobretudo, pela expressividade de suas construções [MEN2001]. No Brasil, já conta com o reconhecimento de seu papel no futuro da Ciência da Computação por parte de instituições como SBC e MEC. Os obstáculos aqui descritos, entretanto, ainda necessitam ser transpostos. O presente trabalho foi desenvolvido visando contribuir nesta tarefa. O projeto consiste em uma iniciativa aplicada em Ciência da Computação, a qual visa oportunizar o franco acesso aos conceitos categoriais introdutórios: uma aplicação de computador que faça amplo uso de representação diagramática para apresentar a proposição de conceitos básicos do grupo de pesquisa em Teoria das Categorias do Instituto de Informática da UFRGS. A proposição e implementação de uma ferramenta, embora não constitua iniciativa inédita no mundo, até onde se sabe é a segunda experiência desta natureza. Ademais, vale destacar que os conceitos tratados, assim como os objetivos visados, são atendidos de forma única e exclusiva por esta aplicação. Conjuntamente, vislumbra-se a aplicação desenvolvida desempenhando importante papel de agente catalisador na propagação da visão dos Grupos de Pesquisa em Teoria das Categorias da UFRGS e da PUC/RJ do que sejam os "conceitos categoriais introdutórios".

Teoria das Categorias é uma ramificação da Matemática Pura relativamente recente, tendo sua base sido enunciada ao final da primeira metade do século XX. Embora seja Teoria de grande expressividade, sua aplicação efetiva tem encontrado até o momento grandes obstáculos, todos decorrência natural da brevidade de sua História. A baixa oferta de bibliografia (e predominantemente em 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. Consegue, a despeito destes obstáculos, arrebanhar admiradores em inúmeros centros de reconhecida excelência técnica e científica. Dentre todas as áreas do conhecimento, atrai em especial a atenção da Ciência da Computação, por características como independência de implementação, dualidade, herança de resultados, possibilidade de comparação da expressividade de outros formalismos, forte embasamento em notação gráfica e, sobretudo, pela expressividade de suas construções [MEN2001]. No Brasil, já conta com o reconhecimento de seu papel no futuro da Ciência da Computação por parte de instituições como SBC e MEC. Os obstáculos aqui descritos, entretanto, ainda necessitam ser transpostos. O presente trabalho foi desenvolvido visando contribuir nesta tarefa. O projeto consiste em uma iniciativa aplicada em Ciência da Computação, a qual visa oportunizar o franco acesso aos conceitos categoriais introdutórios: uma aplicação de computador que faça amplo uso de representação diagramática para apresentar a proposição de conceitos básicos do grupo de pesquisa em Teoria das Categorias do Instituto de Informática da UFRGS. A proposição e implementação de uma ferramenta, embora não constitua iniciativa inédita no mundo, até onde se sabe é a segunda experiência desta natureza. Ademais, vale destacar que os conceitos tratados, assim como os objetivos visados, são atendidos de forma única e exclusiva por esta aplicação. Conjuntamente, vislumbra-se a aplicação desenvolvida desempenhando importante papel de agente catalisador na propagação da visão dos Grupos de Pesquisa em Teoria das Categorias da UFRGS e da PUC/RJ do que sejam os "conceitos categoriais introdutórios".