E se um dia alguém, perdido nas ruas do Porto, telefonar para o ISEP a perguntar qual o caminho que o traz até cá? E se essa pessoa não conseguir explicar-nos o local onde se encontra? Será possível definir um conjunto de instruções que a levem ao destino, independentemente do sítio onde esteja? Haverá alguma sequência de direções que traga todos os 833 novos alunos ao nosso Instituto?

Em 1970, questões desta natureza motivaram Adler, Goodwyn e Weiss a conjeturarem que, mediante certas condições do grafo que representa as ruas da cidade, o então denominado "Road Coloring Problem" tem solução afirmativa.

Foi um dos problemas em aberto mais conhecidos da Matemática, chegando a ser considerado impossível de provar, e captou interesse de muitos especialistas em Teoria de Grafos, Autómatos Finitos e Dinâmica Simbólica. Só 37 anos depois, Avraham Trahtman encontrou uma solução para o problema.

Agora, o Departamento de Matemática (DMA) dinamiza o seminário “Para o ISEP? Segue Este Caminho”, onde apresenta o “Road Coloring Problem” e as técnicas combinatórias que levaram Trahtman a solucioná-lo.

ORADORA
Ana Moura, docente ISEP e investigadora LEMA e CMUP.
 
+INFO: Ana Moura | DMA