Mostrar registro simples

dc.contributor.advisorClaudio, Dalcidio Moraespt_BR
dc.contributor.authorLeal, Liara Aparecida dos Santospt_BR
dc.date.accessioned2007-06-06T17:33:19Zpt_BR
dc.date.issued2002pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/4144pt_BR
dc.description.abstractCom o objetivo de desenvolver uma fundamentação teórica para o estudo formal de problemas de otimização NP-difíceis, focalizando sobre as propriedades estruturais desses problemas relacionadas à questão da aproximabilidade, este trabalho apresenta uma abordagem semântica para tratar algumas questões originalmente estudadas dentro da Teoria da Complexidade Computacional, especificamente no contexto da Complexidade Estrutural. Procede-se a uma investigação de interesse essencialmente teórico, buscando obter uma formalização para a teoria dos algoritmos aproximativos em dois sentidos. Por um lado, considera-se um algoritmo aproximativo para um problema de otimização genérico como o principal objeto de estudo, estruturando-se matematicamente o conjunto de algoritmos aproximativos para tal problema como uma ordem parcial, no enfoque da Teoria dos Domínios de Scott. Por outro lado, focaliza-se sobre as reduções entre problemas de otimização, consideradas como morfismos numa abordagem dentro da Teoria das Categorias, onde problemas de otimização e problemas aproximáveis são os objetos das novas categorias introduzidas. Dentro de cada abordagem, procura-se identificar aqueles elementos universais, tais como elementos finitos, objetos totais, problemas completos para uma classe, apresentando ainda um sistema que modela a hierarquia de aproximação para um problema de otimização NP-difícil, com base na teoria categorial da forma. Cada uma destas estruturas matemáticas fornecem fundamentação teórica em aspectos que se complementam. A primeira providencia uma estruturação interna para os objetos, caracterizando as classes de problemas em relação às propriedades de aproximabilidade de seus membros, no sentido da Teoria dos Domínios, enquanto que a segunda caracteriza-se por relacionar os objetos entre si, em termos de reduções preservando aproximação entre problemas, num ponto de vista externo, essencialmente categorial.pt_BR
dc.format.mimetypeapplication/pdf
dc.language.isoporpt_BR
dc.rightsOpen Accessen
dc.subjectTeoria : Ciência : Computaçãopt_BR
dc.subjectTeoria : Categoriaspt_BR
dc.subjectTeoria : Complexidadept_BR
dc.titleUma fundamentação teórica para a complexidade estrutural de problemas de otimizaçãopt_BR
dc.typeTesept_BR
dc.contributor.advisor-coToscani, Laira Vieirapt_BR
dc.identifier.nrb000397370pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Informáticapt_BR
dc.degree.programPrograma de Pós-Graduação em Computaçãopt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2002pt_BR
dc.degree.leveldoutoradopt_BR


Thumbnail
   

Este item está licenciado na Creative Commons License

Mostrar registro simples