Definitividade de formas quadráticas – uma abordagem polinomial

Página do item simplificado
dc.contributor.advisor-co1Brustle, Thomas
dc.contributor.advisor-co1Latteshttp://www2.ubishops.ca/algebra/brustleCv.pdfpor
dc.contributor.advisor1Castonguay, Diane
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/4005898623592261por
dc.contributor.referee1Castonguay, Diane
dc.contributor.referee1Latteshttp://lattes.cnpq.br/4005898623592261por
dc.contributor.referee2Centeno, Carmen
dc.contributor.referee3Alvares, Edson Ribeiro
dc.contributor.referee4Martinez, Fabio Henrique Viduani
dc.contributor.referee5Longo, Humberto José
dc.creatorAlves, Jesmmer da Silveira
dc.creator.Latteshttp://lattes.cnpq.br/0742389762650364por
dc.date.accessioned2016-12-13T19:31:42Z
dc.date.issued2016-11-18
dc.description.abstractQuadratic 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.eng
dc.description.provenanceSubmitted 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)eng
dc.description.provenanceApproved 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)eng
dc.description.provenanceMade 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-18eng
dc.description.resumoFormas 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.por
dc.description.sponsorshipFundação de Amparo à Pesquisa do Estado de Goiás - FAPEGpor
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESpor
dc.formatapplication/pdf*
dc.identifier.citationALVES, J. S. Definitividade de formas quadráticas: uma abordagem polinomial. 2016. 64 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2016.por
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/6586
dc.languageporpor
dc.publisherUniversidade Federal de Goiáspor
dc.publisher.countryBrasilpor
dc.publisher.departmentInstituto de Informática - INF (RG)por
dc.publisher.initialsUFGpor
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)por
dc.rightsAcesso Abertopor
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectFormas quadráticaspor
dc.subjectRedução de Gausspor
dc.subjectFormas unitáriaspor
dc.subjectFormas críticaspor
dc.subjectFormas hipercríticaspor
dc.subjectAlgoritmo polinomialpor
dc.subjectQuadratic formseng
dc.subjectGauss reductioneng
dc.subjectUnit formeng
dc.subjectCritical restrictionseng
dc.subjectHypercritical restrictionseng
dc.subjectPolynomial algorithmeng
dc.subject.cnpqCIENCIA DA COMPUTACAO::MATEMATICA DA COMPUTACAOpor
dc.titleDefinitividade de formas quadráticas – uma abordagem polinomialpor
dc.title.alternativeDefiniteness of quadratic forms – a polynomial approacheng
dc.typeTesepor

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Tese - Jesmmer da Silveira Alves - 2016.pdf
Tamanho:
4.29 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
2.11 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Doutorado em Ciência da Computação em Rede - UFMS/UFG (INF)