Título: Agradecimento de Celina à SBC pelo Prêmio de Mérito Científico
Palestrante: Profa. Celina Miraglia Herrera de Figueiredo (UFRJ)
Data: 30/09/2026
Horário: 14h (Brasil)
Local: Sala 257 do INF, presencial
Resumo: Professora Titular da UFRJ, pesquisadora 1A do CNPq, membro da Academia Brasileira de Ciências e Fellow da The World Academy of Sciences (TWAS), Celina de Figueiredo possui destacada trajetória nas áreas de Algoritmos e Combinatória, Teoria dos Grafos, Complexidade Computacional e Otimização Combinatória. Em reconhecimento à sua contribuição à Computação brasileira, recebeu o Prêmio de Mérito Científico da Sociedade Brasileira de Computação (SBC). Na palestra, Celina apresentará uma retrospectiva de sua relação de três décadas com a SBC, passando por momentos marcantes de sua trajetória no CSBC, JAI, CTD e JBCS, além de sua atuação na consolidação da CE-ACO e do Encontro de Teoria da Computação. A apresentação também oferecerá uma perspectiva histórica sobre o desenvolvimento e o fortalecimento da comunidade brasileira de Algoritmos, Combinatória e Teoria da Computação.
Título: Computação Quântica e Problemas NP-Completos
Palestrante: Prof. Dr. Leandro Zatesko, UTFPR
Data: 24/06/2026
Horário: 14h (Brasil)
Sala: https://meet.google.com/tgj-mcyg-ogn
Resumo: Desde quando o modelo teórico de computação quântica foi proposto, muitos resultados surpreendentes foram obtidos, reforçando a supremacia do modelo quântico sobre o modelo clássico. Dentre os exemplos mais notáveis, está a Transformada Quântica de Fourier, com a qual podemos, em tempo polinomial, encontrar a ordem de grupos abelianos e, portanto, resolver o problema da fatoração inteira. Por outro lado, computadores quânticos não parecem poderosos o suficiente para resolver problemas NP-completos. Na realidade, não parecem poderosos nem mesmo para vários problemas importantes candidatos a NP-intermediários, como os problemas da classe SZK, que admitem provas de conhecimento zero estatístico. Nesta palestra será apresentada uma discussão sobre alguns resultados de Complexidade Computacional — especialmente inclusões e separações oraculares — envolvendo as principais classes da computação quântica e suas relações com outras classes importantes.
Título: Qualificação de Mestrado - Atribuição de papéis em grafos com poucos P4's
Palestrante: Athos José de Araújo UFG
Data: 18/06/2026
Horário: 14h (Brasil)
Sala: Sala 250 do INF com transmissão pelo link: https://conferenciaweb.rnp.br/ufg/instituto-de-informatica-sala-1-ufg.
Resumo: Na Teoria dos Grafos, o problema de atribuição de papéis (role assignment) é definido por um homomorfismo localmente sobrejetor entre grafos. Como decidir se um grafo geral admite uma r-atribuição de papéis é um problema NP-completo para r ≥ 2, uma abordagem comum é estudar o problema em classes específicas. Este trabalho investiga a atribuição de papéis em famílias de grafos com poucos P4’s. Para a classe dos grafos P4-redutíveis, apresentamos resultados que garantem a existência de 2-atribuição e 3-atribuição de papéis. Também demonstramos uma forma de estender atribuições menores para encontrar (r+2)-atribuição de papéis utilizando uma operação específica da construção desses grafos. O trabalho também atua sobre a classe dos grafos P4-esparsos, analisando especificamente as estruturas de grafos aranhas. Para esses grafos, verificamos a existência de 2-atribuições e 3-atribuições, considerando características específicas das suas partições. Por fim, indicamos os próximos passos da pesquisa, que incluem avançar o estudo para a família dos grafos P4-tidy.
Título: O que é a Computação Quântica?
Palestrante: Prof. Dr. Luis Kowada, IC-UFF
Data: 28/05/2026
Horário: 14h (Brasil)
Sala: https://meet.google.com/tgj-mcyg-ogn
Neste seminário será apresentado, de forma acessível, o que é Computação Quântica e por que ela tem atraído tanta atenção nos últimos anos. Serão explicadas as diferenças entre bits clássicos e qubits, os conceitos de superposição e portas lógicas quânticas, bem como a forma pela qual isso permite um tipo de “paralelismo” capaz de resolver certos problemas muito mais rapidamente do que computadores tradicionais, como busca em listas e fatoração de números grandes relacionados à segurança na internet. Ao longo da palestra, serão mostrados exemplos de circuitos quânticos, comentado o impacto da Computação Quântica em Criptografia e discutido o estágio atual da tecnologia, incluindo limitações de hardware, ruído e o número ainda reduzido de qubits disponíveis.
Título: Prévia de Defesa de Tese - Coloração de Identificação Local em Algumas Classes de Grafos
Palestrante: Robson Medrado de Oliveira (Doutorando INF-UFG)
Data: 15 de abril de 2026
Horário: 9h
Local: Sala 257 do INF-UFG
Uma coloração de identificação local (lid-coloração) de um grafo é uma coloração própria tal que, para qualquer aresta uv, se u e v têm vizinhanças fechadas distintas, então os conjuntos de cores usados nos vértices das vizinhanças fechadas de u e v são distintos. O número cromático de identificação local (número lid-cromático) do grafo G, denotado por χlid(G), é o menor número de cores necessárias em qualquer lid-coloração de G. Investigamos a lid-coloração em grafos split e em subclasses, como grafo split completo e grafo split-comparabilidade, obtemos valores exatos e limites para o número lid-cromático nessas classes. Além disso, mostramos que o problema de decidir se um grafo split admite uma lid-coloração com um número dado de cores é NP-completo. Na sequência, estudamos a lid-coloração no produto corona de grafos. Nesse contexto, além de resultados estruturais e de limites, mostramos que o problema de decidir a existência de uma lid-coloração em grafos obtidos pelo produto corona também é NP-completo. Determinamos ainda valores exatos do número lid-cromático para diversas famílias de grafos, incluindo casos em que os fatores são caminhos, ciclos, grafos completos e o complemento de grafos completos. Também estabelecemos limites inferiores e superiores para o número lid-cromático em casos mais gerais. Finalmente, estudamos o número lid-cromático do produto Cartesiano do grafo completo por caminho. Além disso, fornecemos limites inferiores e superiores para os grafos resultantes do produto Cartesiano entre o grafo completo e o ciclo, bem como entre dois grafos completos.
Título: Formulações matemáticas para o problema de escalonamento de tarefas em máquinas paralelas com tempos de setup, famílias de tarefas e com o objetivo de minimizar a soma ponderada dos tempos de conclusão das tarefas
Palestrante: Arthur Kramer (École des Mines de Saint-Étienne – França)
Data: 03 de março de 2026 (terça-feira)
Horário: 10h às 12h
Local: Auditório da PRPI – UFG
Resumo: O problema considera um conjunto de máquinas paralelas e tarefas organizadas em famílias. Quando tarefas de famílias diferentes são processadas consecutivamente na mesma máquina, é necessário um tempo de setup. Trata-se de um problema fortemente NP-difícil, geralmente abordado por heurísticas e métodos de branch-and-bound. Na palestra serão apresentadas cinco novas formulações de programação inteira mista, com análise experimental baseada em mais de 13.000 instâncias da literatura.
Mais detalhes em:https://ime.ufg.br/n/198745-palestra-com-o-prof-arthur-kramer-emse-franca
Título: Dominação como ferramenta de identificação local em grafos: aspectos estruturais, de complexidade e variações envolvendo dominação total e dominação independente
Palestrante: Márcia Cappelle – Universidade Federal de Goiás (UFG)
Data: 12/05/2025
Horário: 13:00 (horário de Brasília)
Sala: https://meet.google.com/cde-osms-aqn
Resumo: Uma abordagem comum para o desafio de localizar intrusões indesejadas em redes — como a presença de um invasor ou a falha de um processador — consiste no uso de modelos da Teoria dos Grafos baseados em conjuntos que distinguem vértices. Nesta palestra, exploramos problemas de dominação com localização, nos quais os conjuntos diferenciadores são conjuntos dominantes localizadores ou códigos identificadores. Apresentamos resultados estruturais e de complexidade para esses problemas em algumas classes de grafos, incluindo variações envolvendo dominação total e dominação independente.
Event: 30 Years of Graph Sandwich Problems: A Celebration
Date: March 27, 2025
Time: 2:00 PM (GMT -3), São Paulo, Brazil
Link: https://meet.google.com/sur-pmun-evy
In 1995, the publication of the seminal paper:
"M.C. Golumbic, H. Kaplan, R. Shamir, "Graph Sandwich Problems," Journal of Algorithms 19 (1995) 449-473" opened a rich and extensive research area that continues to inspire publications worldwide.
To celebrate the 30th anniversary of this influential work, we are honored to welcome Professors Martin Golumbic and Ron Shamir, who will give talks during this special session.
TPTP World e aplicação de provadores automatizados
Palestrante: Geoff Sutcliffe, University of Miami
O EFFA/UFG convida à participação da palestra e tutorial do Prof. Geoff Sutcliffe sobre o TPTP World e aplicação de provadores automatizados (veja resumo abaixo), durante a sua visita ao INF/UFG entre os dias 24 e 26 de fevereiro.
Palestra: The TPTP World - Infrastructure for Automated Reasoning
Data: 24/02
Horário: 10.00 - 12.00
Local: Auditório IME - UFG
Tutorial: The TPTP World - Talk Tutorial
Data: 25/02
Horário: 14.00 - 18.00
Local: Laboratório INF 154
Abstract The TPTP World is a well known and established infrastructure that supports research, development, and deployment of Automated Theorem Proving (ATP) systems. The data, standards, and services provided by the TPTP World have made it increasingly easy to build, test, and apply ATP technology. This talk and tutorial reviews the key components of the TPTP World, examines the logics supported in the TPTP World, shows how problems can be encoded in logic using the TPTP languages, demonstrates and provides practive in solving logic problems using TPTP World online tools, and discusses "logic engineering" principles for solving problems using automated reasoning.
A participação é gratuita mas será necessária a inscrição via google forms: https://forms.gle/tncVG9ucYFboFo5H7
Defesa de Mestrado: Gustavo Machado Leal
Título do trabalho: "A study on the complexity of 2-path validity graph labeling problems"
Local da defesa: sala 257 do INF e sala 1 da RNP (https://conferenciaweb.rnp.br/ufg/instituto-de-informatica-sala-1-ufg)
Data: 20/02/2025, Horário: 14h
Membros da banca:
Prof. Dr. Hebert Coelho da SIlva (INF/UFG) - ORIENTADOR
Prof. Dr. Humberto José Longo(INF/UFG) - COORIENTADOR
Profa. Dra. Márcia Rodrigues Cappelle Santana (INF/UFG)
Profa. Dra. Carmen Cecilia Centeno (Escola Politécnica/PUCGO)
Resumo:
A Teoria dos Grafos é um campo que estuda estruturas matemáticas (grafos) que modelam relações paritárias (arestas) entre objetos (vértices). A subárea de Rotulação de Grafos (Graph Labeling) concentra-se na atribuição de rótulos aos vértices e/ou arestas de um grafo, sujeita a condições predefinidas. Uma rotulação de um grafo consiste na atribuição de rótulos aos seus vértices e/ou arestas. O Problema de Bicaminhos Validos (2-Path Validity Problem) busca otimizar a quanti dade de bicaminhos em que o rótulo inteiro do vértice intermediário é menor do que os rótulos dos vértices terminais. Pesquisas recentes exploraram o comportamento da rotu lação ótima em várias classes de grafos. Este trabalho apresenta avanços recentes no es tudo desse problema desafiador, demonstrando que o problema de decisão, tanto em sua variante de maximização quanto de minimização, é NP-Completo. Além disso, mostra que a variante de maximização permanece NP-Completa mesmo quando restrita a grafos cúbicos, mas admite uma solução em tempopolinomial quando restrita a grafos bipartidos e cografos. Outro resultado significativo apresentado é que ambas as variantes possuem soluções em tempo linear quando restritas a grafos split.
Data: 19/02/2025
Horário: 14:00h (Brasil)
Sala: https://meet.google.com/cde-osms-aqn
Número de P3-Carathéodory em Grafos de diâmetro 2
The spread of influence in social networks, disease transmission in a community, or failures in interconnected systems are topics studied across various fields. Convexity in graphs provides a powerful framework for modeling this diffusion behaviors, and several parameters, such as the hull number, interval number, and percolation number, can be analyzed to understand their dynamics.
The Carathéodory number is one such parameter, which is known to be NP-Complete and is an interesting convexity parameter. In this talk, we establish bounds on the $P_3$-Carathéodory number of graphs with diameter two.
This is a joint work with: Braully R. Silva, Erika M. M. Coelho and Simone Dantas.
Data: 28/11/2024
Horário: 14:00h (Brasil)
Sala: https://meet.google.com/cde-osms-aqn
Título: Desvendando o número lid-cromático: Avanços e desafios.
Resumo: Uma lid-coloração (coloração de identificação local) de um grafo é uma coloração própria tal que, para qualquer aresta uv, se u e v têm vizinhanças fechadas distintas, então os conjuntos de cores usados nos vértices das vizinhanças fechadas de u e v são distintos. O número lid-cromático (número cromático de identificação local) do grafo G, denotado por \chi_{lid}(G), é o menor número de cores necessárias em qualquer lid-coloração de G. Nesta palestra, apresentaremos o conceito de lid-coloração em grafos, discutiremos resultados existentes na literatura e compartilharemos nossos avanços e contribuições sobre o tema.
Data: 30/10/2024
Horário: 14:00h (Brasil)
Vídeo: https://www.youtube.com/watch?v=7sCs1RXYJkY
Título: O que é atribuição de papéis em grafos?
Resumo: A teoria dos grafos desempenha um papel crucial no campo da inteligência artificial através da estruturação de problemas e algoritmos que envolvem dados relacionais. Por exemplo, na análise de redes sociais, a teoria dos grafos é utilizada para analisar a estrutura das relações entre entidades sociais. Ela ajuda a identificar usuários influentes, detectar comunidades e entender a disseminação de informações ou epidemias através de uma rede. Mas esses grafos são muito grandes, e é aí que entram as atribuições de papéis. Uma atribuição de papéis agrupa nós que desempenham papéis semelhantes na estrutura do grafo, substituindo grupos de nós por um único nó ao mesmo tempo que preserva a relação de vizinhança entre os papéis. Isso ajuda a simplificar a rede mantendo informações estruturais importantes. Nesta palestra, exploraremos o conceito de atribuição de papéis em grafos, com uma breve revisão da literatura sobre os problemas associados a esse tema. Também apresentaremos resultados para algumas classes simples de grafos, enfatizando as similaridades e diferenças entre atribuição de papéis e coloração de vértices.
Data: 18/10/2024
Horário: 9:00h (Brasil)
Sala: https://meet.google.com/dkn-mvjy-zzb
Apresentações:
Robson Oliveira, Márcia Cappelle, Hebert Coelho - Locally identifying coloring of split graphs
Lauane Moraes, Erika Coelho - On open-independent dominating sets for some subclasses of cubic graphs
Gustavo Leal, Hebert Coelho, Leslie Foulds, Humberto Longo - The Path Validity Problem
Luiz Belisário, Diane Castonguay, Julliano Nascimento - Estudo sobre 3-atribuição de papéis para produtos direto de grafos
Data: 09/10/2024
Horário: 11:00h (Brasil)
Link: https://www.youtube.com/watch?v=o0GUGnn7n2Q
Palestrante: Jayme L. Szwarcfiter
Título: Uma História da Computação, Dos Primórdios à Atualidade,
organizada pelo PESC-UFRJ como uma homenagem ao prof. Jayme Luiz Szwarcfiter.
Abstract: Apresentamos uma visão histórica da Computação, desde os seus primórdios até a atualidade. Os primórdios, na realidade, retroagem à pré-história, enquanto que a atualidade, corresponde aos dias de hoje. A história gira em torno do personagem central da computação, que é sem dúvida, o computador. Apresentamos os estágios percorridos pela ciência, até o desenvolvimento atual. Uma ênfase especial é dedicada à história da computação brasileira.
Short Bio: Jayme Luiz Szwarcfiter graduou-se em Engenharia Eletrônica, na Escola de Engenharia da UFRJ, em 1967, concluiu o mestrado na COPPE, Programa de Engenharia de Sistemas e Computação, em 1971, e o doutorado em Ciência da Computação, na University of Newcastle upon Tyne, Inglaterra, em 1975. Realizou pós-doutorados na University of California Berkeley, University of Cambridge, Inglatera e Université de Paris-Sud (Orsay) França. Realizou toda a sua carreira acadêmica na UFRJ: Professor do Instituto de Matemática, em 1968, onde alcançou o título de Professor Emérito da Universidade. Possui algumas centenas de trabalhos publicados, nas áreas de ciência da computação e otimização. Orientou diversas de teses de doutorado, cujos autores são atualmente destacados docentes e pesquisadores em universidades do país e do exterior, notadamente Argentina. Membro titular da Academia Brasileira de Ciências, recebeu diversos prêmios e distinções, entre os quais o Prêmio Álvaro Alberto, do MCTI/CNPq, possivelmente um dos principais do país, na área científica. No ano corrente foi agraciado pela Asociación Latino-Ibero- Americana de Investigación Operativa, com a Medalha ALIO 2024.
Data: 26/06/2024
Horário: 11h
Link: https://www.youtube.com/watch?v=CGD41rr6Jg0
Título: Are you a Mathematician or a Computer Scientist?
Abstract: The 2023 ACM A.M. Turing award for foundational contributions to the theory of computation for Avi Wigderson follows his 2021 Abel prize, together with László Lovász, for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics. I will celebrate the unprecedented Abel + Turing recognition, and give my answer to the question that is often asked to Avi Wigderson.
Short Bio: Celina chegou na UFRJ em 1987 quando iniciou o seu doutorado no PESC sob a orientação do professor Jayme Szwarcfiter. Ela começou em 1989 sua carreira docente como professora assistente no Instituto de Matemática e é professora titular da COPPE desde 2011. Foi eleita para a Academia Brasileira de Ciências em 2022. Celina é grata aos seus alunos, seus co-autores mais frequentes, os seus 120 artigos em periódicos internacionais, ao longo de 30 anos como doutor, são na maioria em co-autoria com os seus alunos.