Abertura do Evento

Alan José dos Santos Borges, diretor  da ETEAB/FAETEC

Palestra de abertura - Matemática Discreta e Combinatória

Simone Dantas,  IME/UFF

Celina de Figueiredo, COPPE/UFRJ

Bastam quatro cores

Faremos uma homenagem a Kenneth Appel (1932–2013), através do histórico Teorema das Quatro Cores: bastam quatro cores para pintar qualquer mapa de modo que países vizinhos recebam cores diferentes. O teorema foi provado em 1976 por Appel e Haken e, para comemorar, o correio norte-americano emitiu um carimbo com os dizeres: Four Colors Suffice. Como introdução à coloração em grafos, consideraremos coloração de vértices (países) e coloração da arestas (fronteiras), discutindo variações combinatórias, de modo a apreciar a dificuldade e o impacto desse grande teorema, que pela primeira vez na história da Matemática utilizou o computador como parte da prova.

Sessão 1 

Luerbio Faria, UERJ

Limites para o número de número de cruzamentos em             2-páginas do n-cubo

Desenhos de diagramas ou grafos com muitos cruzamentos, normalmente, dificultam a compreensão do que estes diagramas realmente representam. Computadores com múltiplos processadores também chamados de supercomputadores, atualmente, são de uso público. As novas versões de com-putadores possuem cada vez mais processadores que as an-teriores. Os grafos n-cubos desempenham um grande papel na produção de circuitos para a conexão de processadores, porque têm poucas arestas, e têm o diâmetro (distância máxima entre dois processadores) bem pequeno. Nesta palestra falamos sobre como desenhar um n-cubo no plano com o menor número possível de cruzamentos tal que todas as suas arestas são particionadas em dois semiplanos.

Raphael Machado, INMetro

Algoritmos, Combinatória e Aplicações à Segurança da Informação

 O objetivo desta palestra é apresentar alguns temas de pesquisa aplicada em Segurança da Informação e fundamentados nas áreas de Complexidade de Algoritmos e em Matemática Combinatória. Começamos apresentando alguns objetos fundamentais para a segurança da informação (funções one-way, geradores de números pseudo-aleatórios, provas de conhecimento nulo), passamos pelo problema de análise de programas, e concluímos com três aplicações a proteção de software: ofuscação, incorruptibilidade, e rastreabilidade.

Christiane Campos, UNICAMP

 Conjuntos dominantes em grafos

Dado um grafo G, um conjunto dominante de G é um subconjunto D de vértices tal que todo vértice não pertencente a D é adjacente a pelo menos um vértice de D. O problema do conjunto dominante mínimo consiste em encontrar, num dado grafo G, um conjunto dominante de cardinalidade mínima. Embora vários problemas que se reduzem a este problema já viessem sendo considerados há muito tempo, um tratamento mais formal destes problemas só surgiu por volta de 1962. Com esta formalização, diversos problemas, de natureza mais aplicada, foram formulados como problemas de conjuntos dominantes. Estas aplicações levaram à definição de variantes do problema original, onde o que se procura agora é determinar conjuntos dominantes que satisfaçam alguma propriedade estrutural adicional como, por exemplo, conexidade ou independência. Nesta palestra serão introduzidos o problema do conjunto dominante mínimo, algumas de suas variações e aplicações, bem como algumas conjeturas importantes.

Mitre Dourado, UFRJ

Tempo máximo de propagação de influência para a regra de dois vizinhos

Considere um grafo G e uma convexidade C sobre G. O tempo de percolação de um subconjunto S de V(G) é a quantidade necessária de aplicações da função intervalo para se obter o fecho convexo de S, denotado por H(S). Neste trabalho consideramos o problema de encontrar o conjunto S com valor máximo de percolação tal que H(S) = V(G) na convexidade P₃.

Maise da Silva, UFF

Algoritmos fonéticos

A falta de mecanismos eficientes para recuperação de informações resulta não somente em resultados inconsistentes com o conteúdo buscado, como também compromete a qualidade das informações armazenadas, facilitando, por exemplo, a existência de registros duplicados. A recuperação de informação por similaridade fonética em textos de bancos de dados envolve o uso de várias técnicas, ainda não padronizadas. Basicamente, um algoritmo fonético indexa palavras de acordo com sua pronúncia. Dessa forma, palavras homófonas são emparelhadas, apesar das diferenças na escrita. Atualmente, há vários algoritmos fonéticos disponíveis no mercado, como Soundex, Phonix e MetaPhone, por exemplo. No entanto, eles foram desenvolvidos considerando-se a fonética da língua inglesa, sendo muitas vezes inadequados para textos em português.

Luis Kowada, UFF

Grafos de Cayley: propriedades e aplicações

Um grafo de Cayley é um grafo associado a um grupo e a um conjunto gerador deste grupo. Se o conjunto gerador não possuir o elemento neutro, o grafo não possui laços; se  este conjunto for simétrico então o grafo é não-direcionado. Os grafos de Cayley podem ser usados em situações bem diversas como por exemplo para mapear operações de rearranjo de genomas ou síntese de circuitos reversíveis. Nesta palestra, apresentaremos os grafos de Cayley e mostrando algumas destas aplicações.

Danilo Artigas, UFF

Convexidade em grafos: história, presente e perspectivas

Nesta palestra será exibida a evolução do estudo sobre convexidade em grafos. Começando pelos resultados iniciais, passando pelos conceitos fundamentais e principais resultados, até os dias de hoje e os resultados mais recentes. Além disso, problemas em aberto e novas perspectivas de abordagem do tema serão propostos.

Rosiane Freitas, UFAM

O jogo Sudoku, coloração em hipergrafos e algoritmos de enumeração implícita

O jogo japonês Sudoku consiste em um quebra-cabeça de lógica numérica disposto em uma grade de 9x9 células, onde algumas já estão preenchidas com valores de 1 a 9. O objetivo é completar o preenchimento de toda a grade, de tal forma que cada linha, cada coluna e cada subgrade de 3x3 células, contenha os valores de 1 a 9 exatamente uma vez. Nesta palestra, a teoria matemática e computacional envolvida no jogo Sudoku é discutida, onde o mesmo pode ser modelado como um problema de coloração especial em grafos. Sendo assim, é apresentada a prova da NP-completude do problema e proposto um modelo baseado em um problema de pré-coloração estendida em hipergrafo 9-uniforme/9-colorido, bem como algoritmos exatos de enumeração implícita, aplicando manipulação de bits na estrutura de representação do grafo, de tal forma a eliminar a verificação de um grande sub-conjunto de casos possíveis, possibilitando a resolução das versões mais difíceis do jogo Sudoku.

Telma Pará, ETEAB/FAETEC

Jogos  em Grafos:  o Jogo  Clobber

 O objetivo desta palestra  é apresentar a Teoria de Grafos e suas aplicações em jogos. O jogo que tenho estudado se chama “Clobber”. As regras são as seguintes: posicionamos pedras pretas e brancas nos vértices de um grafo. Um movimento consiste em pegar uma pedra e “comer” uma outra pedra da cor oposta, localizada em um vértice adjacente, ocupando o seu lugar.  A pedra “comida” é então removida da do grafo e é substituída pela que efetuou o movimento. O jogador não é obrigado a alternar jogadas com pedras brancas e pretas e o jogo termina quando ele não consegue mais se movimentar, isto é, não é possível “comer” mais pedras. O objetivo do jogo é o de minimizar o número de pedras que restam no grafo. A partir da prática do Clobber apresentaremos alguns resultados teóricos obtidos utilizando como ferramenta de modelagem a Teoria dos Grafos.