Por favor, use este identificador para citar o enlazar este ítem:
https://repositorio.ufpe.br/handle/123456789/7639
Comparte esta pagina
| Título : | Uma redução do problema de fatorização de inteiros para o problema de programação 0-1 |
| Autor : | Happ Botler, Fábio |
| Palabras clave : | Algoritmos; Análise combinatória |
| Fecha de publicación : | 31-ene-2011 |
| Editorial : | Universidade Federal de Pernambuco |
| Citación : | Happ Botler, Fábio; Luiz Soares Lins, Sóstenes. Uma redução do problema de fatorização de inteiros para o problema de programação 0-1. 2011. Dissertação (Mestrado). Programa de Pós-Graduação em Matemática, Universidade Federal de Pernambuco, Recife, 2011. |
| Resumen : | O problema de Fatorização de Inteiros, assim como os outros em NP, pode ser reduzido em tempo polinomial para o problema de Satisfabilidade, devido ao Teorema de Cook. O problema de Satisfabilidade, por sua vez, pode ser reduzido facilmente ao problema de Programação Inteira. Este trabalho apresenta uma dessas reduções, isto é, Fatorização 􀀀! Programação Inteira e algumas particularidades encontradas. Obtemos uma redução de ordem O(n2) no número de dígitos binários de um inteiro N a ser fatorado e, além disso, encontramos algumas propriedades locais da matriz final que podem auxiliar um possível estágio de pré-processamento |
| URI : | https://repositorio.ufpe.br/handle/123456789/7639 |
| Aparece en las colecciones: | Dissertações de Mestrado - Matemática |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| arquivo994_1.pdf | 580,91 kB | Adobe PDF |  Visualizar/Abrir |
Este ítem está protegido por copyright original |
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons
