Na primeira parte do minicurso farei uma introdução à Teoria de Ramsey, onde serão apresentados resultados clássicos e discutirei algumas técnicas comumente aplicadas na resolução dos problemas da área. Na segunda parte do mini curso serão apresentados resultados recentes envolvendo números de Ramsey para potências de caminhos. Mais especificamente, o número de Ramsey relativo a arestas de um grafo é definido como a menor quantidade de arestas tal que existe um grafo com arestas com a seguinte propriedade: toda coloração das arestas de com cores contém uma cópia monocromática de . Respondendo uma pergunta sugerida por Conlon, provaremos que para todo fixo, onde é a -ésima potência do caminho com vértices , i.e., o grafo com conjunto de vértices e todas as arestas tais que a distância entre e em é no máximo . Discutiremos como estender esse resultado para mais cores e para potências de árvores. Os trabalhos que serão discutidos foram obtidos pelos seguintes autores:

• Clemens, Jenssen, Kohayakawa, Morrison, Mota, Reding e Roberts (2018).
• Han, Jenssen, Kohayakawa, Mota e Roberts (2019+).
• Berger, Kohayakawa, Maesaka, Martins, Mendonça, Mota and Parczyk (2019+).

A solução para diversos problemas reais frequentemente exige eficientes (usualmente de tempo polinomial). Como nem sempre isso é possível, a teoria da NP-completude foi desenvolvida para fornecer indícios de quais problemas não podem ser resolvidos por algoritmos polinomiais. Entretanto, como muitos problemas NP-difíceis precisam ser resolvidos na prática, algumas possibilidades adotadas são o uso de algoritmos aproximativos ou de heurísticas, em vez de algoritmos exatos, cujo tempo de execução teria uma dependência exponencial no tamanho da entrada.

Uma recente e promissora alternativa para a tratabilidade desses problemas, é recorrer a uma análise sob o ponto de vista da Teoria da Complexidade Parametrizada. Esta teoria, desenvolvida por Downey e Fellows, estuda a existência de algoritmos cuja dependência exponencial no tempo de execução depende apenas de certos aspectos da entrada, e não de seu tamanho. Problemas que admitem tais algoritmos são denominados tratáveis por parâmetro fixo (ou simplesmente algoritmos FPT). Este curso, introduzirá os conceitos fundamentais da complexidade parametrizada, algumas técnicas básicas de desenvolvimento de algoritmos FPT, e também discutirá resultados negativos, análogos à teoria da NP-completude, envolvendo problemas onde não se espera ser possível desenvolver algoritmos FPT. Os exemplos utilizados serão focados em problema em grafos.

Diagramas de Decisão Binária (BDD's - Binary Decision Diagrams) são estruturas de dados que têm sido amplamente utilizadas na área de verificação de modelos por permitir representar sistemas com até 10 elevado a 20 estados. Estas estruturas têm um grande poder de compactação, armazenando conjuntos de estados (representação simbólica) no lugar de representá-los individualmente (representação enumerativa). Nos últimos anos, a aplicação dos BDDs têm sido expandida para outras áreas tais como Planejamento em Inteligência Artificial. Neste tutorial, abordaremos a fundamentação teórica dos BDDs, propriedades, operações, algoritmos e aspectos de implementação tais como o uso de bibliotecas (C++, Java e Python). Por fim, mostraremos os avanços recentes da busca simbólica na área de Planejamento em Inteligência Artificial.

Inicialmente será feita uma breve introdução à Combinatória Extremal, explicando que tipos de problemas são estudados nessa área. Em um segundo momento, analisamos uma conjectura proposta por Bal e DeBiasio [Partitioning random graphs into monochromatic components, Electron. J. Combin. 24 (2017), Paper 1.18] a respeito de funções limiares para a seguinte propriedade tipo Ramsey: em toda -coloração do conjunto das arestas de um grafo , existem árvores monocromáticas que particionam todo o conjunto de vértices de . Mais precisamente, determinamos a função limiar para essa propriedade para duas cores. Este trabalho foi feito em conjunto com Yoshiharu Kohayakawa e Mathias Schacht.

Planejamento Automatizado é a subárea da Inteligência Artificial que se preocupa com a escolha de ações para que um agente inteligente possa alcançar seus objetivos. De fato, a habilidade de planejar tarefas é um aspecto fundamental do comportamento inteligente e sua automação têm sido um dos principais objetivos da pesquisa realizada em Inteligência Artificial. Aplicações de planejamento estão relacionadas à logística, navegação de robôs, automação de processos industriais, jogos, dentre outras. Nesta palestra, abordaremos os conceitos básicos da área de Planejamento Automatizado, as diferentes formas de planejamento, a representação de estados, ações, especificações formais e algoritmos de busca por uma solução para domínios com ações determinísticas e não-determinísticas.

Quantas das suas demonstrações matemática estão garantidamente corretas? O computador poderia lhe ajudar nisso? Esta palestra irá analisar algumas das conquistas recentes na geração mecanizada de demonstrações e refutações para várias conjecturas matemáticas significativas.

Given a graph , a proper -coloring of is a partition of into stable sets . Given a weight function , the weight of a color is defined as and the weight of a coloring as . Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair , denoted by , as the minimum weight of a proper coloring of . The problem of determining has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. In this article we provide some positive results for the problem, by considering its so-called dual parameterization: given a vertex-weighted graph and an integer , the question is whether . We prove that this problem is FPT by providing an algorithm running in time , and it is easy to see that no algorithm in time exists under the ETH. On the other hand, we present a kernel with at most vertices, and we rule out the existence of polynomial kernels unless , even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

Joint work with Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Ignasi Sau and Ana Silva

Dado um grafo , colorir os vértices de significa atribuir cores aos mesmos de forma que vértices adjacentes tenham cores distintas. O número cromático de um grafo é o menor inteiro k tal que admite uma coloração de vértices com -cores. Nessa palestra, veremos algoritmos combinatórios exatos de coloração na classe de grafos perfeitos, usando o conceito de pares de amigos, além de heurísticas clássicas de coloração, com a definição de seus parâmetros relacionados, apresentando as ferramentas usadas para lidar com a determinação desses parâmetros.

Em 1968 Bollobás introduziu o conceito de saturação fraca. Um grafo é dito fracamente -saturado se existe uma ordem das arestas que não estão em tal que se elas forem adicionadas, uma de cada vez, cada nova aresta adicionada cria uma nova cópia de . O menor número de arestas de um grafo com vértices fracamente -saturado é denotado por . Bollobás estabeleceu para e para em geral, o valor foi originalmente determinado por Lovász e provas alternativas foram dadas por Alon, Frankl, Yu e Kalai, independentemente. Faudree, Gould e Jacobson determinaram o número de saturação fraca de diversos grafos esparsos e em particular, mostraram que . Nessa palestra, discutimos os valores de saturação fraca para grafos bipartidos completos e determinamos para todo . Esse é um trabalho em conjunto com Gal Kronenberg e Natasha Morrison.

An edge coloring of the -vertex complete graph is a Gallai coloring if it does not contain any rainbow triangle, that is, a triangle whose edges are colored with three distinct colors. We prove that the number of Gallai colorings of with at most three colors is at most , which improves the best known upper bound of in [Discrete Mathematics, 2017].

We present a new result about the curse of dimensionality affecting similarity search in intrinsically high-dimensional metric spaces with measure, when an indexing scheme uses 1-Lipschitz functions.

Paraconsistent Logic has demonstrated good results in several fields of study, but with little application in games. In order to interconnect these two fields of knowledge, this work consists in the implementation of a Paraconsistent Battle System, based on the principles of Paraconsistent Logic, with the aim to control actions of non-player characters. Matches experiments were performed, and our system demonstrate efficient and higher performance against scripts and algorithms from literature, proving to be sufficiently robust and challenging.

Na contemporaneidade ensinar Teoria da Computação (TC) implica em ter diferentes ferramentas pedagógicas para auxiliar o processo de ensino-aprendizagem. Uma dessas ferramentas é a utilização de recursos digitais como jogos e simuladores, por serem recursos atrativos, que fornecem feedback visual e interação. No entanto, nem todos os recursos são capazes de fomentar a aprendizagem, fazendo-se necessária uma análise prévia do recurso, anterior a sua aplicação em sala de aula. Desta forma, este relato aborda os critérios pedagógicos, tecnológicos e aspectos referentes a abrangência de conteúdos para a analise do recurso digital. Mais especificamete, foram analisados alguns simuladores de formalismos de TC com base nos critérios e aspectos supracitados na avaliação de recursos digitais. Como esse relato é um préludio de um projeto em andamento que visa analisar os simuladores/jogos mais utilizados em disciplinas de TC no Brasil, os resultados preliminares apontam um possível ganho no processo de ensino-aprendizagem de TC mediado por recursos digitais.

Este projeto busca apresentar uma análise detalhada do desempenho das estruturas de vizinhança para o Problema de programação de tarefas em ambiente Job shop. Com o objetivo de investigar a capacidade da busca das diferentes estruturas de vizinhança, são apresentados quatro critérios de avaliação: Eficiência, Convergência, Força e Aprimoramento. Para alcançar esses objetivos, este trabalho será realizado considerando a aplicação de procedimentos de busca local baseados na heurística Hill Climbing e na metaheurística Iterated Local Search.

Este artigo apresenta um modelo de Programação Lógica por Restrições para o Problema de Escalonamento e Roteamento de Enfermeiras com o objetivo de maximizar o número de pacientes e minimizar a distância percorrida, levando em consideração o estudo de caso realizado junto à equipe de Serviço de Atenção Domiciliar do Hospital Geral do Estado em Salvador.

AGM's belief revision is one of the main paradigms in the study of belief change operations. In this context, belief bases have been largely used to specify the agent's belief state. While the connection of iterated AGM-like operations and their encoding in dynamic logics have been studied before, few works considered how well-known postulates from iterated belief revision theory can be characterised by means of belief bases and their counterpart in a dynamic epistemic logic. This work investigates how priority graphs can be used to characterise belief change operators.

Provamos a seguinte conjectura de Gy"ori and Tuza: as arestas de todo grafo G com n vértices podem ser decompostas em grafos completos , cada um de tamanho ou , de forma que . Esse resultado implica a versão assintótica do resultado de Erd"os, Goodman e Pósa que mostra a existência de tal decomposição com . Esse é um trabalho em conjunto com Daniel Král’, Bernard Lidický e Yanitsa Pehova.

Given a weighted graph , the minimum weighted feedback vertex set problem (MWFVS) consists in obtaining a minimum weight subset of the vertex set whose removal makes the graph acyclic. Differently from other approaches in the literature, in this work we tackle this problem via the maximum weighted induced forest problem (MWIF). First, we propose two new compact mixed integer programming (MIP) formulations, using a polynomial number of variables and constraints. Next, we develop a matheuristic that hybridizes a multi-start iterated local search metaheuristic with a MIP-based local search procedure. Extensive computational experiments carried out on a set of benchmark instances show that a combination of the newly proposed techniques is extremely competitive with the best heuristics available in the literature in terms of solution quality.

Problemas de corte bidimensional (2BP, do inglês \textit{-Dimensional bin packing problem}) são problemas clássicos de otimização combinatória e da indústria têxtil, metalúrgica e de vidro, e consistem em alocar um conjunto de itens retangulares em placas retangulares maiores com tamanho padronizado com a finalidade de minimizar o desperdício de matéria-prima. No presente trabalho apresenta-se uma abordagem para um problema restrito de corte bidimensional guilhotinado presente no \textit{ROADEF/EURO Challenge 2018: Cutting Optimization Problem}, no qual existe a possibilidade de rotacionar itens em 90º e as placas retangulares a serem cortadas podem possuir defeitos em determinados pontos. Propõe-se uma heurística \textit{multi-start} gulosa randomizada e técnica de aprimoramento que combina a heurística com uma modelagem de programação lógica por restrições. Experimentos realizados produziram resultados que se aproximam dos melhores conhecidos, o que classificou o trabalho para a etapa final do \textit{ROADEF/EURO Challenge 2018}.

We consider a gravity fed water distribution network design (WDND) optimization problem, which consists in determining the pipe diameters of a water network such that hydraulic constraints are satisfied and the total cost is minimized. We propose an improved simulation based iterated local search metaheuristc. Preliminary computational experiments show that our approach outperforms the state-of-the-art metaheuristic for several of the benchmark instances.