iNIGMA


Seminário Diagonal
Setembro 21, 2009, 6:38 pm
Filed under: Seminário Diagonal 2009/2010

Olá a todos!!!🙂

Antes de mais esperamos que as férias tenham sido do teu agrado… Agora que mais um ano está a começar, é altura de desenferrujar os neurónios, e é por isso que o iNIGMA continua a preparar novas actividades especialmente para ti!

O primeiro seminário deste ano será no Departamento de Matemática Pura da FCUP, no anf. 0.07, pelas 13:10h, do dia 30 de Setembro (próxima 4ª feira).

Orador: Rui Miguel Soares Barbosa, 3º ano da Licenciatura em Ciências da Computação (UM) (2008/2009)

Título: “A Topologia de um Problema de Decisão”

Resumo: Nesta palestra, tentaremos mostrar uma utilização de métodos da Topologia no contexto de um problema de origem algorítmica/combinatórica.
Consideramos o problema de decidir se um dado grafo com n vértices satisfaz determinada propriedade. O algoritmo procede por observação do grafo através de perguntas do tipo “a aresta {i,j} pertence ao grafo?”.
Particularmente importantes são as propriedades monótonas: fechadas para subgrafos. A maioria das propriedades interessantes é monótona (ser planar, bipartido, k-colorível, …) ou é-o a sua negação (ser completo, hamiltoniano, conter determinado subgrafo, …).
Nos início dos anos 70, Karp conjecturou que qualquer algoritmo de decisão de uma propriedade monótona (exceptuando as sempre verdadeiras ou sempre falsas) necessita de observar todas as arestas candidatas no pior caso.
A conjectura pode ser reformulada num contexto topológico, em termos de complexos simpliciais abstractos. Esta conexão revelou-se bastante fértil: a exploração de propriedades topológicas permitiu progresso significativo, onde se destaca a demonstração da conjectura no caso em que n é potência de um primo.

Não te esqueças que podes levar contigo umas sandes para que possas almoçar enquanto assistes.

Não faltes!:)

———————-

P(ós).S(eminário). Clicando aqui poderás ver o pdf da palestra.


Deixe um Comentário so far
Deixe um comentário



Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s



%d bloggers like this: