Complexidade computacional, probabilidades e transição de fase

Data de Início: 
quinta-feira, 31 Agosto, 2017 - 16:00
Palestrante: 
Prof. Dr. Marcelo Finger - IME
Local: 
Auditório Abrahão de Moraes - IFUSP

A transição de fase é um fenômeno que ocorre na natureza mas pode também ocorrer em computação e está associado ao problema denominado Não-Determinístico Polinominal (NP) completo. Há uma conjectura, feita por Cheeseman em 1991, de que todo problema NP-completo está associado a uma transição de fase. Embora não haja até hoje uma demonstração matemática da validade desta conjectura, ela foi verificada em diversas classes de problemas NP-completos. Neste colóquio iremos descrever o fenômeno da transição de fase, seu  aparecimento em diversos contextos e a forma como a robustez deste fenômeno tem guiado pesquisas na área de algoritmos para problemas NP-completos.

INFORMAÇÕES SOBRE O PALESTRANTE: É professor titular do Instituto de Ciência da Computação do Instituto de Matemática e Estatística da Universidade de São Paulo, bolsista 1C de produtividade em pesquisa do CNPq. Possui graduação em Engenharia Eletrônica pela Universidade de São Paulo (1988), mestrado (1990) e doutorado (1994) em Ciência da Computação pelo Imperial College of Science and Technology, University of London (1994), Livre-docente (2001) e titular (2011) em Ciência da Computação pelo Instituto de Matemática e Estatística da Universidade de São Paulo. Foi professor visitante em departamentos de Ciência da Computação na Universitée Paul Sabatier - Toulouse (2011) e na Cornell University (2012-2013). Tem conduzido pesquisas na área de Ciência da Computação, com ênfase em Dedução Automática, Raciocínio Lógico-Probabilístico e atuando principalmente nos seguintes temas: Lógica, Inteligência Artificial, Bancos de Dados, Humanidades Digitais e Linguística Computacional.

 

Palavras chaves: NP-completude, mudança de fase, algoritmos de decisão

Transmissão via IPTV - http://iptv.usp.br/portal/video.action?idItem=37499