Olá professor Carlos, Fico feliz pelo interesse. Vou disponibilizar a versão final da dissertação nos próximos dias, assim que eu terminar de fazer algumas correções e receber os comentários da banca.
Abraços, Igor Carboni Em 28 de julho de 2010 22:16, Carlos Camarão <[email protected]> escreveu: > Olá. Imagino que o texto da tese esteja disponível eletronicamente. > Gostaria de ler. > > Abraços, obrigado pela divulgação, > > Carlos Camarão > > > Caros Colegas: > > > > gostaria de divulgar a defesa de Dissertação de Mestrado de > > Igor Carboni Oliveira. Embora não se trate de meu orientando, nem > > eu esteja na Banca, Igor estudou comigo durante dois anos > > (Iniciação Científica) e o que trabalhamos, Lógica e > > Computabilidade, ajudou a moldar seu trabalho. > > > > > > Att., > > > > Walter Carnielli > > ---------------------------------------- > > Universidade Estadual de Campinas - UNICAMP Instituto de > > Computação - IC > > > > > > D E F E S A D E DISSERTAÇÃO DE MESTRADO > > > > Segunda-feira, 02/08/2010 às 10h > > Sala: Auditório do IC sala 85 (IC-02 ) > > > > Titulo: Complexidade Computacional e o Problema P vs NP > > Nome do aluno: Igor Carboni Oliveira > > > > Banca Examinadora > > > > Prof. Dr. Arnaldo Vieira Moura (Orientador) -- IC / UNICAMP > > Prof. Dr. José Coelho de Pina - IME / USP Prof. Dr. Flávio Keidi > > Miyazawa - IC / UNICAMP Prof. Dr. Julio C. López Hernández > > (Suplente) -- IC / UNICAMP Profa. Dra. Ana Cristina Vieira de > > Melo (Suplente) - IME / USP > > > > > > RESUMO > > > > A teoria de complexidade computacional procura estabelecer > > limites para o universo algorítmico, 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. Embora a > > diagonalização seja uma técnica clássica em complexidade > > computacional, esse é o único método conhecido capaz de separar > > certas classes de complexidade importantes. > > > > Os principais resultados obtidos por diagonalização são os > > teoremas de hierarquia (Hartmanis e Stearns). Intuitivamente, > > esses resultados estabelecem que, com mais recursos, é possível > > resolver mais problemas computacionais. Apresentamos uma > > generalização dos teoremas de hierarquia determinísticos, 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. > > ---------------------------------------- > > > > > > -- > > +++++++++++++++++++++++++++++++++++++++++++++++++ > > Walter Carnielli > > Centre for Logic, Epistemology and the History of Science – CLE > > State University of Campinas –UNICAMP > > P.O. Box 6133 13083-970 Campinas -SP, Brazil > > Phone: (+55) (19) 3521-6515 > > Fax: (+55) (19) 3289-3269 > > e-mail: [email protected] > > Website: http://www.cle.unicamp.br/prof/carnielli > > _______________________________________________ > > Logica-l mailing list > > [email protected] > > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l > > > > >
_______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
