Experimentos e métodos de otimização combinatória para o problema de subconjuntos ...
Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Aproximabilidade de problemas de otimização NP e programação evolutiva
![]() | |
Autor(es): |
Igor Carboni Oliveira
Número total de Autores: 1
|
Tipo de documento: | Dissertação de Mestrado |
Imprenta: | Campinas, SP. |
Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
Data de defesa: | 2010-02-08 |
Membros da banca: |
Arnaldo Vieira Moura;
José Coelho de Pina Junior;
Flávio Keidi Miyazawa
|
Orientador: | Arnaldo Vieira Moura |
Resumo | |
A teoria de complexidade computacional procura estabelecer limites para a eficiência dos algoritmos, investigando a dificuldade inerente dos problemas computacionais. O problema P vs NP é uma questão central em complexidade computacional. Informalmente, ele procura determinar se, para uma classe importante de problemas computacionais, a busca exaustiva por soluções é essencialmente a melhor alternativa algorítmica possível. Esta dissertação oferece tanto uma introdução clássica ao tema, quanto uma exposição a diversos teoremas mais avançados, resultados recentes e problemas em aberto. Em particular, o método da diagonalização é discutido em profundidade. Os principais resultados obtidos por diagonalização são os teoremas de hierarquia de tempo e de espaço (Hartmanis e Stearns [54, 104]). Apresentamos uma generalização desses resultados, obtendo como corolários os teoremas clássicos provados por Hartmanis e Stearns. Essa é a primeira vez que uma prova unificada desses resultados aparece na literatura (AU) | |
Processo FAPESP: | 08/07040-0 - Complexidade Computacional e o Problema P vs NP |
Beneficiário: | Igor Carboni Oliveira |
Modalidade de apoio: | Bolsas no Brasil - Mestrado |