Trabalho Prático da Disciplina de Projeto e Análise de Algoritmos: Implementação de Algoritmos Satisfatibilidade, Clique e Conjunto Independente
Este repositório contém a implementação de três algoritmos fundamentais em teoria dos grafos e lógica booleana: Satisfatibilidade (SAT), Clique e Conjunto Independente. Cada um desses problemas é resolvido utilizando diferentes técnicas de otimização e busca.
Dada uma fórmula booleana na forma normal conjuntiva (CNF), o objetivo é encontrar uma atribuição de valores-verdade que torne a fórmula verdadeira. Se não existir tal atribuição, o programa deverá informar que a fórmula é insatisfatível.
Método de Solução: Backtracking.
Dado um grafo, o objetivo é encontrar o maior subcconjunto de vértices tal que todas as arestas entre eles estejam presentes, formando um clique máximo.
Método de Solução: Branch and Bound.
Dado um grafo, o objetivo é encontrar o maior conjunto de vértices independentes, ou seja, um conjunto em que não exista aresta entre nenhum par de vértices.
Método de Solução: Resolução por redução polinomial ao problema do Clique.
Linguagem: Python
Estruturas de dados: Matrizes de adjacência e fórmulas booleanas