Resumos
PL1: Introdução ao Uso de Ontologias Formais para Representação de Conhecimento
Profa: Renata Wassermann (IME-USP)
Resumo: Há cerca de dez anos, com o início da busca por uma web semântica, ressurgiu o interesse por representações de conceitos e relações baseadas
em formalismos lógicos. Neste seminário, pretendo mostrar como o conceito de ontologias é definido e utilizado em inteligência artificial. Em particular, como a representação baseada em ontologias é utilizada em alguns projetos de que participo.
PL2: Testabilidade de parâmetros e propriedades
Prof: Carlos Hoppen (UFRGS)
Resumo: O grande interesse em redes complexas nas últimas décadas levou a uma série de desafios práticos e teóricos para a Ciência da Computação. Procuramos calcular parâmetros associados a redes de dimensões gigantescas, sejam elas de comunicação (Internet), redes sociais, redes de transporte, redes biológicas, etc. Pelo seu tamanho e dinamismo, muitas dessas redes não podem sequer ser descritas em sua totalidade, e é necessário fazer estimativas a partir de amostras limitadas. Grosso modo, um parâmetro é testável se pode ser estimado, com alta probabilidade, por um algoritmo randomizado. Nessa palestra, apresentarei os conceitos de testabilidade de propriedades e parâmetros, e discutirei sua relação com diversos conceitos fundamentais da Combinatória Extremal e Probabilística, como regularidade, estabilidade e limites de sequências de objetos discretos.
PL3: Ciência da Computação em Humanidades Digitais
Prof: Prof: Ricardo C. Corrêa (UFRRJ)
A difusão de artefatos computacionais na vida moderna tem impulsionado a penetração da Ciência da Computação em diversas disciplinas do conhecimento humano, permeando e transformando seus métodos e, em vários casos, ampliando seus horizontes. Frutos dessa combinação de saberes, novas disciplinas nasceram, primeiramente com predominância das Ciências Naturais, como a Biologia Computacional. Mais recentemente, esse fenômeno atingiu as disciplinas que se dedicam a estudar o comportamento humano e as dinâmicas sociais dele decorrentes.
O termo Humanidades está associado ao conjunto das diferentes abordagens no estudo dessas interações e dinâmicas sociais, econômicas, políticas, culturais e até acadêmicas. As linguagens desempenham um papel central de Intermediação dessas interações pois é através de objetos dessas linguagens (sob diversas formas, tais como idiomas falados e escritos, expressões artísticas, matemática, entre outras) que são produzidos os seus registros. O termo Digital começa a se aproximar quando os objetos de linguagens passam a ter registros digitais sob a forma de textos, imagens, vídeos, áudios e, mais recentemente, de outras formas sensoriais, como o tato e o equilíbrio, comum em jogos e outros sistemas de realidade virtual ou aumentada. Ao tornarem-se disponíveis na rede mundial de computadores, deu-se início uma inundação de informações de relevância nas diversas áreas de Humanidades.
As respostas metodológicas e tecnológicas que a Ciência da Computação tem trazido, em um ritmo muito acelerado, tornou o termo Digital indissociado do termo Humanidades, trazendo o nascimento da área de Humanidades Digitais, hoje efervescente tanto no meio acadêmico quanto empresarial. Profissionais de Ciência da Computação encontram uma vasta gama de oportunidades de atuação nesse novo cenário. De uma forma geral, o especialista de alguma área de Humanidades, em sua atuação profissional, tende a problematizar o cenário sob análise de maneira ampla, frequentemente eivada de subjetividades, imprecisões, contradições e ambiguidades como a realidade exige, mas de difícil formalização objetiva. Por outro lado, a formação tradicional do profissional em Ciência da Computação procura simplificar os cenários a fim de obter soluções formais e genéricas, ao preço de lançar mão de premissas que mantêm certa distância dos cenários reais.
A confluência entre esses dois mundos demanda uma habilidade adicional que permita ao profissional transitar no terreno de imprecisões das Humanidades servindo-se do formalismo do Digital. Trata-se, portanto, da habilidade de, a partir de uma problematização realista, encontrar uma adequada configuração e combinação de diverdos métodos algorítmicos de forma a obter soluções concretas, mesmo que somente aplicáveis a casos bem específicos. Ao apresentar exemplos que ilustram a disciplina de Humanidades Digitais, mostraremos nessa palestra desafios em computação que surgem em concomitância com o desenvolvimento de formas de combinar métodos algorítmicos em aplicações nas diversas vertentes das Humanidades, com ênfase em processamento de linguagem natural e seus métodos de análise léxica, com aplicações em problemas relacionados a classificação de textos científicos, históricos e políticos.
PL4: Conexões entre Lógica e Geometria via Reescrita de Termos
Prof: Ruy de Queiroz (UFPE)
Resumo: A breve citação para o “Prêmio Rolf Schock de 2020 em Lógica e Filosofia” diz que foi concedido a Per Martin-Löf (compartilhado com Dag Prawitz) “pela criação da teoria dos tipos construtivos”. Em uma declaração mais longa, o comitê do prêmio lembra que a teoria dos tipos construtivos é “uma linguagem formal em que é possível expressar matemática construtiva” (…) “[que] também funciona como uma linguagem de programação poderosa e teve um enorme impacto na lógica, ciência da computação e, recentemente, matemática.” Com efeito, ao introduzir um arcabouço teórico-conceitual em que uma formalização da noção lógica de igualdade, via o chamado “tipo identidade”, permite uma ligação surpreendente entre a reescrita de termos e conceitos geométricos como caminho e homotopia. Na verdade, a teoria dos tipos de Martin-Löf (MLTT) permite fazer pontes úteis entre a teoria da computação, topologia algébrica, lógica, categorias e álgebra superior, e um único conceito parece servir como um elo de ligação: “caminho”. O impacto na matemática foi sentido com mais força desde o início do programa de Vladimir Voevodsky (Medalha Fields, 2002) sobre os fundamentos univalentes da matemática por volta de 2005, e um aspecto específico sobre o qual gostaríamos de falar é o cálculo de grupos fundamentais de superfícies. Tirando da entrada da Wikipédia sobre “grupo de homotopia”, o cálculo de grupos de homotopia é em geral muito mais difícil do que alguns dos outros invariantes de homotopia aprendidos em topologia algébrica. Agora, usando uma formulação alternativa do “tipo identidade” que fornece uma explicação formal explícita de “caminho”, operacionalmente entendido como uma sequência inversível de reescritas (como a “conversão” de Church) e interpretado como uma homotopia, desejamos mostrar exemplos de cálculo de grupos fundamentais de superfícies, como o círculo, o toro, o toro com 2 furos, a garrafa de Klein e o plano projetivo real. Parece razoável sugerir que esses exemplos dão conta de testemunhar o impacto da MLTT na matemática, oferecendo ferramentas formais para calcular e provar grupos fundamentais. Por outro lado, com base numa semântica “homotópica” do lambda-cálculo, buscamos a generalização da teoria dos domínios de Dana Scott em que “complete partial orders” são substituídas por “infinito-grupóides”.
PL5: O Problema das Pontes de Konisberg: e se Euler fosse de ônibus?
Prof: Ana Shirley Ferreira da Silva (UFC)
Resumo: No clássico Problema das Pontes de Konisberg, os cidadãos dessa cidade desejavam saber se era possível fazer um passeio ao longo da mesma de forma a visitar cada uma das 7 pontes existentes, mas sem repetir nenhuma delas. Euler resolveu este problema negativamente, apresentando o resultado mais antigo na Teoria dos Grafos (foi provado no ano de 1736), numa prova extremamente elegante que caracteriza o que ficou conhecido como grafos Eulerianos. Imagine agora um Euler moderno, que precisaria usar o transporte público para visitar as famosas pontes. Neste caso, o tempo se tornaria uma variável importante no problema, uma vez que os horários devem ser respeitados. Para levar em consideração este tipo de restrição, são empregados os grafos temporais, que podem ser vistos como grafos que mudam ao longo do tempo. Nesta apresentação, iremos estudar os vários problemas relacionados à existência de passeios e trilhas Eulerianas em um grafo temporal. Provamos que quase todas as possíveis variações levam a problemas NP-completos, mesmo em casos onde o grafo considerado permanece constante ao longo do tempo. Este trabalho está foi aceito no IWOCA’21 e foi desenvolvido em co-autoria com Andréa Marino (Università degli Studi di Firenze).
PL6: O problema de formação de múltiplas equipes
Prof Manoel B. Campêlo Neto (UFC)
Resumo: Dado um conjunto de indivíduos, cada um com uma habilidade/competência específica, e uma rede social captando a afinidade mútua entre eles, o Problema de Formação de Equipe (TFP – Team Formation Problem) visa encontrar uma única equipe que reúna as habilidades necessárias para realizar uma tarefa, enquanto busca otimizar os custos de comunicação entre os indivíduos envolvidos. Neste trabalho, estudamos uma generalização do TFP denominada Problema de Formação de Múltiplas Equipes (MTFP – Multiple Team Formation Problem), que permite demandas distintas de trabalhadores para cada tipo de habilidade, assim como requisições de múltiplas equipes de trabalho e possibilidade de fracionamento do tempo de dedicação de cada indivíduo entre os times. Nesse caso, o custo total de comunicação é dado pela soma dos pesos das relações dos pares de indivíduos de um mesmo time. Propomos uma formulação de Programação Linear Inteira (ILP) e famílias de desigualdades válidas. Experimentos computacionais atestam que o modelo ILP fortalecido por desigualdades válidas supera consistentemente a formulação quadrática apresentada na literatura para resolução do MTFP. Também consideramos uma versão generalizada do MTFP em que os indivíduos podem ter múltiplas habilidades. Para lidar com esta versão, adaptamos o modelo ILP inicial, gerando dois novos modelos, um deles com mais variáveis e outro com um número exponencial de restrições, mas que mostramos serem separáveis em tempo polinomial. Também para o segundo problema, apresentamos um outro conjunto de desigualdades válidas que fortalecem os dois modelos.(Trabalho em conjunto com Tatiane Figueiredo (UFC-Russas))
MC2: Um convite para entender o caos: Uma breve introdução à Combinatória extremal e Teoria de Ramsey.
Profs: Roberto Parente (UFBA) e Antônio Josefran (UFC)
Resumo: Devido a explosão tecnológica que experienciamos nas últimas décadas, a combinatória tem recebido uma crescente atenção de pesquisadores de diversas áreas. Por ser uma área tanto da matemática quanto da teoria da computação, a combinatória possibilita a modelagem de problemas, sejam teóricos ou práticos, e estudar o comportamento de estruturas no mundo real. Em poucas palavras, combinatória é a área que está interessada em compreender o comportamento de estruturas discretas finitas. Neste curso, introduziremos alguns conceitos e ideias básicas de duas linhas de problemas conhecidas como “Combinatória Extremal” e “Teoria de Ramsey”. A “Teoria de Ramsey” investiga a garantia da existência de padrões em cenários quaisquer. Um problema introdutório e clássico da área seria “Qual é a menor quantidade de pessoas em uma festa tal que sempre existem 3 que se conhecem ou 3 que não se conhecem mutuamente?”. Ou seja, podemos dizer que Teoria de Ramsey afirma que por mais caótico que pareça um cenário, sempre conseguiremos encontrar padrões em conjuntos grandes. Em “Combinatória extremal”, investigamos situações que procuram responder perguntas como “Qual o pior/melhor cenário para acontecer algo?”. A pergunta está colocada de maneira informal de propósito, mas podemos entender cenário como as regras de existência do conjunto de estruturas discretas com as quais estamos interessados em trabalhar, tais como conjuntos, permutações, grafos, reticulados, etc; e, em geral, associamos pior/melhor com situações extremais de existência (ou não) de padrões. Um exemplo simples poderia ser “Qual o maior subconjunto de {1,2, … ,n} tal que não existem três elementos tais que a+b=c?”.