• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.1996.tde-20210729-013117
Documento
Autor
Nome completo
Jair Donadelli Junior
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 1996
Orientador
Título em português
Arranjos de subespacos, colapso de complexos simpliciais e complexidade computacional
Palavras-chave em português
Ciência Da Computação
Combinatória
Topologia Algébrica
Resumo em português
Neste trabalho descrevemos algumas aplicacoes da topologia algebrica em complexidade computacional. Bjorner e lovaz usaram metodos topologicos para estimar a altura de uma arvore de decisao linear que testa pertinencia em unioes finitas de poliedros convexos. Como aplicacoes eles obtiveram as cotas inferiores 'OMEGA' (n log(n/k)) para o problema dos k-iguais, 'OMEGA' (n log k) para o problema dos k-distintos e 'OMEGA' (n log(n/k)) para o problema de k-divisibilidade. Descrev emos tambem os metodos topologicos usados por kahn, saks e sturtevant para mostrar que propriedades de grafos de ordem potencia de primo sao evasivas. Estes mesmos metodos foram usados por yao para mostrar que propriedades de grafos bipartidos sao evasivas
Título em inglês
not available
Resumo em inglês
not available
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2021-07-29
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2021. Todos os direitos reservados.