Detalhes bibliográficos
Ano de defesa: |
2017 |
Autor(a) principal: |
Szutkoski, Jonas |
Orientador(a): |
Trevisan, Vilmar |
Banca de defesa: |
Não Informado pela instituição |
Tipo de documento: |
Tese
|
Tipo de acesso: |
Acesso aberto |
Idioma: |
por |
Instituição de defesa: |
Não Informado pela instituição
|
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: |
|
Link de acesso: |
http://hdl.handle.net/10183/172180
|
Resumo: |
Neste trabalho, consideramos o problema de calcular o reticulado de subcorpos de uma extensão separável e de grau nito k( )/k. Isto e, queremos encontrar todos os corpos L tais que k L k( ). Até recentemente, o algoritmo utilizado pela maioria dos Sistemas Algébricos Computacionais baseava-se em um problema combinatorial nas raízes do polinômio minimal f de sobre k. Em 2013, um algoritmo foi apresentado para encontrar tais subcorpos. Este método calcula um pequeno conjunto de subcorpos, chamados de subcorpos principais, com a propriedade de que todo subcorpo de k( )/k e a interseção de alguns destes subcorpos. Assim, calcular o reticulado de subcorpos e dividido em duas etapas: 1) Encontrar os subcorpos principais de k( )/k e 2) Calcular todas as interseções destes subcorpos. A primeira etapa pode ser feita em tempo polinomial. Entretanto, a segunda etapa não pode e assim, domina a complexidade do algoritmo. Nosso objetivo e melhorar a segunda etapa, tanto em teoria quanto na prática. Para isso, mostramos como rapidamente calcular todas as interseções entre os subcorpos principais. Embora a complexidade continue não sendo limitada polinomialmente (e também não poderia ser, pois o número total de subcorpos não o é), conseguimos melhorar a complexidade do algoritmo. Também notamos um melhoramento na prática, principalmente quando o número de subcorpos e grande. Além disso, estudamos dois casos especiais: corpos numéricos e o corpo das funções racionais. Para corpos numéricos (i.e., quando k = Q), também apresentamos um melhoramento para a primeira etapa. No segundo caso, os subcorpos da extensão k(t)=k(f(t)), definida por f(t) 2 k(t), nos fornecem decomposições da função racional f(t). Nosso algoritmo tem uma performance melhor que algoritmos anteriores para calcular as decomposições de funções racionais. |