Submitted by Fernanda Rodrigues de Lima (fernanda.rlima@ufpe.br) on 2018-11-09T19:27:14Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Arthur Freitas Ramos.pdf: 743456 bytes, checksum: cb16d9c33d78bebe371f455a60b25b34 (MD5) / Approved for entry into archive by Alice Araujo (alice.caraujo@ufpe.br) on 2019-01-25T17:02:05Z (GMT) No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Arthur Freitas Ramos.pdf: 743456 bytes, checksum: cb16d9c33d78bebe371f455a60b25b34 (MD5) / Made available in DSpace on 2019-01-25T17:02:05Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Arthur Freitas Ramos.pdf: 743456 bytes, checksum: cb16d9c33d78bebe371f455a60b25b34 (MD5) Previous issue date: 2015-07-25 / CAPES / O presente trabalho tem como objetivo o estudo de uma entidade computacional conhecida como caminhos computacionais. Proposta originalmente por QUEIROZ; OLIVEIRA (2011) como ’sequências de reescritas’, a ideia é que os caminhos computacionais funcionam como os termos do tipo identidade da Teoria dos Tipos de Martin-Löf’. Esse trabalho expande essa ideia, mostrando uma formalização completa do tipo identidade a partir dos caminhos computacionais. É mostrado que os caminhos computacionais tornam o tipo identidade uma entidade muito mais intuitiva e simples, quando comparado com a abordagem tradicional. Um outro foco desse trabalho é o estudo das propriedades matemáticas dos caminhos computacionais. Em particular, o interesse é em explorar a relação entre os caminhos e a teoria das categorias. Especificamente, é provado que os caminhos computacionais são capazes de induzir uma estrutura algébrica conhecida como grupóide. Esse resultado está de acordo com os resultados obtidos por HOFMANN; STREICHER (1994), que mostram que a abordagem tradicional do tipo identidade induzem um modelo de grupóide. / The current work aims to study a computational entity known as computational paths. Originally proposed by QUEIROZ; OLIVEIRA (2011) as ’sequence of rewrites’, the idea is that computational paths are terms of Martin-Löf’s identity type. This work expands this idea, showing a complete formalization of the identity type using computational paths. It is shown that computational paths makes the identity type a much simpler and more intuitive entity, when compared to the tradional approach. Another focus of this work is the study of the mathematical properties of computational paths. In particular, the main aim is the relation between computational paths and category theory. Specifically, this work shows that computational paths are capable of inducing an algebraic structure known as groupoid. This results is on a par with the one obtained by HOFMANN; STREICHER (1994), which shows that the traditional approach of the identity type also induces a grupoid model.

O aumento da escala e funcionalidade dos sistemas de computação e sua crescente complexidade envolvem um aumento significante de custos e exigem recursos humanos altamente qualificados para o desenvolvimento de software. Integrando-se o uso de métodos formais ao desenvolvimento de sistemas complexos, permite-se realizar análises e verificações destes sistemas, garantindo assim sua correção. Existem diversos formalismos que permitem descrever sistemas, cada qual com diferentes níveis de abstração. Quando consideramos sistemas complexos, surge a necessidade de um modelo que forneça construções abstratas que facilitem o entendimento e a especificação destes sistemas. Um modelo baseado em objetos fornece um nível de abstração que tem sido muito aplicado na prática, onde os dados e os processos que os manipulam são descritos juntos em um objeto. Gramática de Grafos Baseada em Objetos (GGBO) é um modelo baseado em objetos, que além de ser uma linguagem visual, apresenta a vantagem de as especificações adquirirem um estilo baseado em objetos, que é bastante familiar à maioria dos desenvolvedores. Porém, as GGBOs não possuem ainda ferramentas para verificação automática de propriedades desejadas nos sistemas modelados. Uma alternativa para resolver isso é definir uma tradução (que preserve a semântica) desta linguagem para outra, para a qual existam verificadores automáticos. Um formalismo bastante conhecido e estabelecido para descrição de sistemas concorrentes, para o qual existem verificadores automáticos, é o cálculo-π. Porém, sob o aspecto de especificação de sistemas complexos, GGBOs parecem ser mais adequadas como linguagem de especificação que o cálculo-π, pois são visuais, mais intuitivas e possuem um estilo baseado em objetos. Neste trabalho foi definido um formalismo (baseado nas GGBOs), denominado Gramática de Hipergrafos Baseada em Objetos e uma tradução deste formalismo para o cálculo-π, aliando assim as vantagens desses dois métodos. Além disso, para validar a tradução definida, foram feitas provas de que a semântica das gramáticas de hipergrafos baseadas em objetos é preservada na tradução.

A análise de um algoritmo tem por finalidade melhorar, quando possível, seu desempenho e dar condições de poder optar pelo melhor, dentre os algoritmos existentes, para resolver o mesmo problema. O cálculo da complexidade de algoritmos é muito dependente da classe dos algoritmos analisados. O cálculo depende da função tamanho e das operações fundamentais. Alguns aspectos do cálculo da complexidade, entretanto, não dependem do tipo de problema que o algoritmo resolve, mas somente das estruturas que o compõem, podendo, desta maneira, ser generalizados. Com base neste princípio, surgiu um método para o cálculo da complexidade de algoritmos no pior caso. Neste método foi definido que cada estrutura algorítmica possui uma equação de complexidade associada. Esse método propiciou a análise automática da complexidade de algoritmos. A análise automática de algoritmos tem como principal objetivo tornar o processo de cálculo da complexidade mais acessível. A união da metodologia para o pior caso, associada com a idéia da análise automática de programas, serviu de motivação para o desenvolvimento do protótipo de sistema ANAC, que é uma ferramenta para análise automática da complexidade de algoritmos não recursivos. O objetivo deste trabalho é implementar esta metodologia de cálculo de complexidade de algoritmos no pior caso, com a utilização de técnicas de construção de compiladores para que este sistema possa analisar algoritmos gerando como resultado final a complexidade do algoritmo dada em ordens assintóticas.

A análise de um algoritmo tem por finalidade melhorar, quando possível, seu desempenho e dar condições de poder optar pelo melhor, dentre os algoritmos existentes, para resolver o mesmo problema. O cálculo da complexidade de algoritmos é muito dependente da classe dos algoritmos analisados. O cálculo depende da função tamanho e das operações fundamentais. Alguns aspectos do cálculo da complexidade, entretanto, não dependem do tipo de problema que o algoritmo resolve, mas somente das estruturas que o compõem, podendo, desta maneira, ser generalizados. Com base neste princípio, surgiu um método para o cálculo da complexidade de algoritmos no pior caso. Neste método foi definido que cada estrutura algorítmica possui uma equação de complexidade associada. Esse método propiciou a análise automática da complexidade de algoritmos. A análise automática de algoritmos tem como principal objetivo tornar o processo de cálculo da complexidade mais acessível. A união da metodologia para o pior caso, associada com a idéia da análise automática de programas, serviu de motivação para o desenvolvimento do protótipo de sistema ANAC, que é uma ferramenta para análise automática da complexidade de algoritmos não recursivos. O objetivo deste trabalho é implementar esta metodologia de cálculo de complexidade de algoritmos no pior caso, com a utilização de técnicas de construção de compiladores para que este sistema possa analisar algoritmos gerando como resultado final a complexidade do algoritmo dada em ordens assintóticas.

A análise de um algoritmo tem por finalidade melhorar, quando possível, seu desempenho e dar condições de poder optar pelo melhor, dentre os algoritmos existentes, para resolver o mesmo problema. O cálculo da complexidade de algoritmos é muito dependente da classe dos algoritmos analisados. O cálculo depende da função tamanho e das operações fundamentais. Alguns aspectos do cálculo da complexidade, entretanto, não dependem do tipo de problema que o algoritmo resolve, mas somente das estruturas que o compõem, podendo, desta maneira, ser generalizados. Com base neste princípio, surgiu um método para o cálculo da complexidade de algoritmos no pior caso. Neste método foi definido que cada estrutura algorítmica possui uma equação de complexidade associada. Esse método propiciou a análise automática da complexidade de algoritmos. A análise automática de algoritmos tem como principal objetivo tornar o processo de cálculo da complexidade mais acessível. A união da metodologia para o pior caso, associada com a idéia da análise automática de programas, serviu de motivação para o desenvolvimento do protótipo de sistema ANAC, que é uma ferramenta para análise automática da complexidade de algoritmos não recursivos. O objetivo deste trabalho é implementar esta metodologia de cálculo de complexidade de algoritmos no pior caso, com a utilização de técnicas de construção de compiladores para que este sistema possa analisar algoritmos gerando como resultado final a complexidade do algoritmo dada em ordens assintóticas.

O aumento da escala e funcionalidade dos sistemas de computação e sua crescente complexidade envolvem um aumento significante de custos e exigem recursos humanos altamente qualificados para o desenvolvimento de software. Integrando-se o uso de métodos formais ao desenvolvimento de sistemas complexos, permite-se realizar análises e verificações destes sistemas, garantindo assim sua correção. Existem diversos formalismos que permitem descrever sistemas, cada qual com diferentes níveis de abstração. Quando consideramos sistemas complexos, surge a necessidade de um modelo que forneça construções abstratas que facilitem o entendimento e a especificação destes sistemas. Um modelo baseado em objetos fornece um nível de abstração que tem sido muito aplicado na prática, onde os dados e os processos que os manipulam são descritos juntos em um objeto. Gramática de Grafos Baseada em Objetos (GGBO) é um modelo baseado em objetos, que além de ser uma linguagem visual, apresenta a vantagem de as especificações adquirirem um estilo baseado em objetos, que é bastante familiar à maioria dos desenvolvedores. Porém, as GGBOs não possuem ainda ferramentas para verificação automática de propriedades desejadas nos sistemas modelados. Uma alternativa para resolver isso é definir uma tradução (que preserve a semântica) desta linguagem para outra, para a qual existam verificadores automáticos. Um formalismo bastante conhecido e estabelecido para descrição de sistemas concorrentes, para o qual existem verificadores automáticos, é o cálculo-π. Porém, sob o aspecto de especificação de sistemas complexos, GGBOs parecem ser mais adequadas como linguagem de especificação que o cálculo-π, pois são visuais, mais intuitivas e possuem um estilo baseado em objetos. Neste trabalho foi definido um formalismo (baseado nas GGBOs), denominado Gramática de Hipergrafos Baseada em Objetos e uma tradução deste formalismo para o cálculo-π, aliando assim as vantagens desses dois métodos. Além disso, para validar a tradução definida, foram feitas provas de que a semântica das gramáticas de hipergrafos baseadas em objetos é preservada na tradução.

O aumento da escala e funcionalidade dos sistemas de computação e sua crescente complexidade envolvem um aumento significante de custos e exigem recursos humanos altamente qualificados para o desenvolvimento de software. Integrando-se o uso de métodos formais ao desenvolvimento de sistemas complexos, permite-se realizar análises e verificações destes sistemas, garantindo assim sua correção. Existem diversos formalismos que permitem descrever sistemas, cada qual com diferentes níveis de abstração. Quando consideramos sistemas complexos, surge a necessidade de um modelo que forneça construções abstratas que facilitem o entendimento e a especificação destes sistemas. Um modelo baseado em objetos fornece um nível de abstração que tem sido muito aplicado na prática, onde os dados e os processos que os manipulam são descritos juntos em um objeto. Gramática de Grafos Baseada em Objetos (GGBO) é um modelo baseado em objetos, que além de ser uma linguagem visual, apresenta a vantagem de as especificações adquirirem um estilo baseado em objetos, que é bastante familiar à maioria dos desenvolvedores. Porém, as GGBOs não possuem ainda ferramentas para verificação automática de propriedades desejadas nos sistemas modelados. Uma alternativa para resolver isso é definir uma tradução (que preserve a semântica) desta linguagem para outra, para a qual existam verificadores automáticos. Um formalismo bastante conhecido e estabelecido para descrição de sistemas concorrentes, para o qual existem verificadores automáticos, é o cálculo-π. Porém, sob o aspecto de especificação de sistemas complexos, GGBOs parecem ser mais adequadas como linguagem de especificação que o cálculo-π, pois são visuais, mais intuitivas e possuem um estilo baseado em objetos. Neste trabalho foi definido um formalismo (baseado nas GGBOs), denominado Gramática de Hipergrafos Baseada em Objetos e uma tradução deste formalismo para o cálculo-π, aliando assim as vantagens desses dois métodos. Além disso, para validar a tradução definida, foram feitas provas de que a semântica das gramáticas de hipergrafos baseadas em objetos é preservada na tradução.

Orientador: João Meidanis / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-27T16:09:11Z (GMT). No. of bitstreams: 1 Lin_TzyLi_M.pdf: 15544121 bytes, checksum: ee3531bbac213c133eae17175d876d68 (MD5) Previous issue date: 2001 / Resumo: Esta dissertação é na área de Biologia Computacional e se propõe a estudar a montagem de fragmentos de DNA pelo método Ordered Shotgun Sequencing (088). A montagem de fragmentos de DNA é uma das etapas de um projeto de seqüenciamento total do genoma de um organismo. Com o crescimento do tamanho dos genomas a serem seqüenciados e do aumento da complexidade dos organismos estudados, os problemas para se montar um DNA, como trechos repetidos no genoma, também aumentaram. Até os anos noventa, o método mais popular de montagem de fragmentos era o 8hotgun, que quebra a molécula de DNA em fragmentos de mais ou menos 500 pares de bases que serão desvendados em laboratórios de seqüenciamento. Conhecendo-se os fragmentos, é a vez de se descobrir como eles se encaixam, através de sobreposições, e ordená-los. No final, espera-se que os algoritmos nos retomem a seqüência do DNA. Em 1993, dois biólogos propuseram a montagem de fragmentos 088, que quebra a molécula de DNA em intervalos bem maiores, resultando em fragmentos que chamaremos de clones, e seqüencia apenas as suas pontas, deixando a parte central desconhecida. Agora, além da seqüência dos fragmentos, teremos a informação de ligação e distância entre as pontas do clone. Com essas informações e das sobreposições entre as pontas" tenta-se encontrar as posições relativas dos clones no DNA. Um bloco ordenado de fragmentos de DNA por causa das sobreposições e das ligações de clone, será denominado scaffold. As suas partes desconhecidas serão desvendadas em outras iterações, que é uma característica da montagem de fragmentos de DNA 08S. Em 1998, ano que nossos estudos começaram, não haviam trabalhos computacionais que tirassem proveito dessa técnica, até que em 2000 surgiram trabalhos relatando projetos genoma que utilizaram a montagem OS8 com sucesso. Em nosso trabalho, propusemos dois algoritmos para encontrar scaffolds e um ambiente de simulação para executar as iterações feitas pelo método 088 e montar genomas artificialmente gerados. Foram feitos vários testes para medir o desempenho dos algoritmos propostos em termos de tempo total de processamento em CPU, e número de iterações e de clones seqüenciados para terminar a montagem 088. Por último, identificamos várias questões importantes sobre os algoritmos que merecem um estudo mais aprofundado. / Abstract: This is a dissertation in the area of Computational Biology. We propose to study the DNA fragment assembly problem using the Ordered Shotgun Sequencing (OSS) method. The DNA fragment assembly problem is one step of a complete genome sequencing project. With the growing size of the sequenced genomes and the increasing complexity of the studied organisms, problems such as repeated regions increased as well. The OSS method is an attempt to mitigate those problems. Until the nineties, the most popular method of DNA fragment assembly was Shotgun, which breaks the DN A inolecule into pieces of about 500 base pairs that are revealed by sequencing laboratories. Given the fragments, it is necessary to find out what their relative position is in the original DNA molecule by using overlap information to order them. In the end, the algorithms are supposed to give us the DNA sequence. In 1993 two biologists proposed the OSS method for fragment assembly, which breaks the DNA into quite bigger pieces, resulting in fragments called clones in this dissertation. Just the ends of the clones are sequenced, leaving the central part unknown. Besides the fragment sequences, we know how far one end is from the other, and their relative orientation. Based on this information and on the overlaps between done ends, a~ ordered block of DNA fragments called scaffold can be formed. The unknown part will be revealed by subsequent iterations, an intrinsic characteristic of OSS DNA fragment assembly. Our studies began in 1998 when there was no computational work exploring the OSS technique. The first papers reporting on the successful use of OSS assembly in genome projects appeared in 2000 In this work, we propose two scaffold-finding algorithms and present a simulation environment built to test them. The environment generates artificial data, promotes the iterations, and keeps track of the amount of sequencing, number of iterations, and processing time for the algorithm being tested. Finally, we identified many important questions about the algorithms which deserve further studies. / Mestrado / Mestre em Ciência da Computação

Orientador : Ricardo Dahab / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-28T09:27:15Z (GMT). No. of bitstreams: 1 Silva_CandidaNunesda_M.pdf: 9020782 bytes, checksum: 72d783f2186f3848f226c74b427014de (MD5) Previous issue date: 2001 / Mestrado

Orientador : Flavio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-03T07:42:27Z (GMT). No. of bitstreams: 1 Xavier_EduardoCandido_M.pdf: 3835404 bytes, checksum: be10ff1a60ae5a8a7f5f399f1d509bc0 (MD5) Previous issue date: 2003 / Mestrado