Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2016-12-12T16:55:40Z
No. of bitstreams: 2
Tese - Jesmmer da Silveira Alves - 2016.pdf: 4498358 bytes, checksum: e1a92f88800ddd8032e2b0c1039f216d (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2016-12-13T19:31:42Z (GMT) No. of bitstreams: 2
Tese - Jesmmer da Silveira Alves - 2016.pdf: 4498358 bytes, checksum: e1a92f88800ddd8032e2b0c1039f216d (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2016-12-13T19:31:42Z (GMT). No. of bitstreams: 2
Tese - Jesmmer da Silveira Alves - 2016.pdf: 4498358 bytes, checksum: e1a92f88800ddd8032e2b0c1039f216d (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2016-11-18 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Quadratic forms are algebraic expressions that have important role in different areas of
computer science, mathematics, physics, statistics and others. We deal with rational quadratic
forms and integral quadratic forms, with rational and integer coefficients respectively.
Existing methods for recognition of rational quadratic forms have exponential time
complexity or use approximation that weaken the result reliability. We develop a polinomial
algorithm that improves the best-case of rational quadratic forms recognition in
constant time. In addition, new strategies were used to guarantee the results reliability,
by representing rational numbers as a fraction of integers, and to identify linear combinations
that are linearly independent, using Gauss reduction. About the recognition of
integral quadratic forms, we identified that the existing algorithms have exponential time
complexity for weakly nonnegative type and are polynomial for weakly positive type,
however the degree of the polynomial depends on the algebra dimension and can be very
large. We have introduced a polynomial algorithm for the recognition of weakly nonnegative
quadratic forms. The related algorithm identify hypercritical restrictions testing every
subgraph of 9 vertices of the quadratic form associated graph. By adding Depth First Search
approach, a similar strategy was used in the recognition of weakly positive type. We
have also shown that the recognition of integral quadratic forms can be done by mutations
in the related exchange matrix. / Formas quadráticas são expressões algébricas que têm papel importante em diferentes
áreas da ciência da computação, matemática, física, estatística e outras. Abordamos nesta
tese formas quadráticas racionais e formas inteiras, com coeficientes racionais e inteiros
respectivamente. Os métodos existentes para reconhecimento de formas quadráticas racionais
têm complexidade de tempo exponencial ou usam aproximações que deixam o resultado
menos confiável. Apresentamos um algoritmo polinomial que aprimora o melhorcaso
do reconhecimento de formas quadráticas para tempo constante. Ainda mais, novas
estratégias foram usadas para garantir a confiabilidade dos resultados, representando nú-
meros racionais como frações de inteiros, e para identificar combinações lineares que
são linearmente independentes, usando a redução de Gauss. Sobre o reconhecimento de
formas inteiras, identificamos que os algoritmos existentes têm complexidade de tempo
exponencial para o tipo fracamente não-negativa e polinomial para o tipo fracamente positiva.
No entanto, o grau do polinômio depende da dimensão da álgebra e pode ser muito
grande. Apresentamos um algoritmo polinomial para o reconhecimento de formas inteiras
fracamente positivas. Este algoritmo identifica restrições hipercríticas avaliando todo
subgrafo com 9 vértices do grafo associado à forma inteira. Através da busca em profundidade,
uma estratégia similar pôde ser usada no reconhecimento do tipo fracamente
positiva. Por fim, mostramos que o reconhecimento de formas inteiras pode ser feito através
de mutações na matriz de troca relacionada.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/6586 |
| Date | 18 November 2016 |
| Creators | Alves, Jesmmer da Silveira |
| Contributors | Castonguay, Diane, Brustle, Thomas, Castonguay, Diane, Centeno, Carmen, Alvares, Edson Ribeiro, Martinez, Fabio Henrique Viduani, Longo, Humberto José |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, 600, -7712266734633644768, 1231144342511031835, -961409807440757778, 2075167498588264571 |
Page generated in 0.0028 seconds