Orientador: João Meidanis / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-27T09:25:12Z (GMT). No. of bitstreams: 1
Braga_MariliaDiasVieira_M.pdf: 1562326 bytes, checksum: e2bde728b7016815f56abc118722d3d4 (MD5)
Previous issue date: 2000 / Resumo: Este trabalho está relacionado à Biologia Computacional, uma área da Ciência da Computação cuja existência é motivada pela busca de métodos computacionais que resolvam ou ajudem a resolver problemas de origem biológica. Esta ciência tem sido largamente utilizada no âmbito da genética, contribuindo essencialmente no seqüenciamento de cadeias de DNA e no mapeamento de genomas [11]. O foco do nosso projeto foi uma família de problemas denominada Minimum Contig Problems (MCP) [4], que é um modelo teórico para a abordagem da Montagem de Fragmentos de DNA [11] e que possui uma grande semelhança com um problema de grafos denominado Cobertura de Vértices por Caminhos (CVC) [4]. O principal resultado da nossa pesquisa foi a apresentação de provas formais da NP-dificuldade dos problemas de MCP. A partir daí, complementamos o nosso trabalho propondo um algoritmo de aproximação para instâncias restritas de cada problema de MCP. / Abstract: Not informed. / Mestrado / Mestre em Ciência da Computação
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/275909 |
| Date | 27 July 2018 |
| Creators | Braga, Marília Dias Vieira |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Meidanis, João, 1960-, Laber, Eduardo Sany, Souza, Cid Carvalho de |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Graduação em Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 60p. : il., application/octet-stream |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds