Temas de TCC de Teoria da Computação
Equipe editorial TCC Pronto · atualizado em
Teoria da Computação investiga o que pode ser computado, a que custo e com quais garantias. Autômatos, linguagens formais, computabilidade, complexidade e verificação formal formam o núcleo da área. Esta página reúne temas de TCC de Teoria da Computação, desde estudos experimentais de algoritmos até provas assistidas por computador, com orientações para cada etapa.
Temas de TCC: 12 ideias em Teoria da Computação
Ideias de temas para TCC e monografia em Teoria da Computação, cada uma já delimitada: problema de pesquisa, objetivo e metodologia para levar ao orientador.
1. Minimização de autômatos finitos determinísticos: comparação experimental dos algoritmos de Hopcroft, Moore e Brzozowski
- Problema:
- Em quais famílias de autômatos o algoritmo de Brzozowski, de pior caso exponencial, é competitivo com os de Hopcroft e Moore?
- Objetivo:
- Implementar os três algoritmos e comparar seu tempo de execução em autômatos aleatórios e em famílias estruturadas.
- Metodologia:
- Geração de autômatos aleatórios com tamanhos crescentes, famílias conhecidas da literatura, várias repetições e análise de tendência.
2. Formalização em Lean da correção de um algoritmo de ordenação e de seu limite inferior por comparações
- Problema:
- É viável, numa graduação, formalizar a correção do merge sort e o limite inferior de comparações em um assistente de provas?
- Objetivo:
- Formalizar a especificação e a prova de correção do merge sort e discutir o esforço de formalização do limite inferior.
- Metodologia:
- Desenvolvimento em Lean com a biblioteca matemática da comunidade, registro do número de lemas e das dificuldades encontradas.
3. Transição de fase em instâncias aleatórias de 3-SAT e o desempenho de solucionadores modernos
- Problema:
- O pico de dificuldade de solucionadores SAT atuais ainda ocorre perto da razão crítica entre cláusulas e variáveis em 3-SAT aleatório?
- Objetivo:
- Medir a fração de instâncias satisfatíveis e o tempo de solução em função da razão entre cláusulas e variáveis.
- Metodologia:
- Geração de instâncias aleatórias com tamanhos variados, execução de solucionadores abertos com limite de tempo e análise das curvas.
4. Algoritmos de aproximação para o problema da cobertura de vértices: garantias teóricas e desempenho prático
- Problema:
- A razão de aproximação observada em grafos reais é muito menor que o limite teórico de 2 para os algoritmos clássicos?
- Objetivo:
- Comparar a qualidade das soluções de algoritmos de aproximação com a solução ótima obtida por programação inteira.
- Metodologia:
- Grafos de repositórios públicos e grafos sintéticos, solução exata por solucionador de programação inteira e cálculo das razões observadas.
5. Ferramenta didática para simulação de máquinas de Turing e avaliação com estudantes de Linguagens Formais
- Problema:
- Um simulador visual de máquinas de Turing com execução passo a passo melhora o desempenho de estudantes em exercícios de construção de máquinas?
- Objetivo:
- Desenvolver um simulador didático e avaliar seu efeito sobre o desempenho de estudantes da disciplina.
- Metodologia:
- Estudo com turmas da disciplina, pré e pós-teste, grupo de comparação e aprovação prévia do CEP via Plataforma Brasil.
6. Algoritmos parametrizados para o problema do conjunto dominante em grafos de largura de árvore limitada
- Problema:
- Programação dinâmica sobre decomposições em árvore resolve o conjunto dominante em grafos reais de largura pequena mais rápido que a busca exaustiva?
- Objetivo:
- Implementar o algoritmo parametrizado por largura de árvore e comparar com abordagens exatas gerais.
- Metodologia:
- Cálculo de decomposições com heurísticas abertas, implementação da programação dinâmica e testes em grafos de redes viárias e sociais.
7. Verificação de modelos de um protocolo de exclusão mútua com lógica temporal
- Problema:
- O algoritmo de Peterson para n processos satisfaz exclusão mútua e ausência de inanição em um verificador de modelos?
- Objetivo:
- Especificar o algoritmo e as propriedades em lógica temporal e verificá-las automaticamente para diferentes números de processos.
- Metodologia:
- Modelagem em verificador de modelos aberto, propriedades em LTL, análise do crescimento do espaço de estados por número de processos.
8. Expressões regulares com retrocesso e o risco de tempo exponencial em validadores de entrada
- Problema:
- Quantas expressões regulares em projetos de código aberto apresentam comportamento de tempo exponencial com entradas maliciosas?
- Objetivo:
- Identificar expressões vulneráveis a retrocesso catastrófico e relacioná-las à teoria de autômatos finitos não determinísticos.
- Metodologia:
- Coleta de expressões de repositórios públicos, análise com ferramenta aberta de detecção, confirmação experimental e classificação dos padrões.
9. Reduções polinomiais entre jogos de quebra-cabeça e problemas NP-completos clássicos
- Problema:
- Um quebra-cabeça popular de lógica, em sua versão generalizada, é NP-completo por redução a partir de 3-SAT?
- Objetivo:
- Demonstrar a pertinência a NP e construir uma redução polinomial de um problema NP-completo conhecido para o quebra-cabeça.
- Metodologia:
- Estudo teórico com construção de gadgets, prova de correção da redução e implementação ilustrativa da transformação.
10. Análise amortizada de estruturas de dados: verificação experimental do custo de heaps de Fibonacci e de pareamento
- Problema:
- Os custos amortizados teóricos dos heaps de Fibonacci se traduzem em vantagem prática sobre heaps de pareamento no algoritmo de Dijkstra?
- Objetivo:
- Comparar o tempo de execução de Dijkstra com diferentes heaps em grafos de redes viárias reais.
- Metodologia:
- Implementação própria das estruturas, grafos viários públicos, contagem de operações e de tempo e relação com a análise teórica.
11. Gramáticas livres de contexto ambíguas: detecção automática em gramáticas de linguagens de programação
- Problema:
- Ferramentas de detecção de ambiguidade, limitadas pela indecidibilidade do problema, encontram ambiguidades em gramáticas reais em tempo útil?
- Objetivo:
- Avaliar ferramentas de detecção de ambiguidade em gramáticas de linguagens de programação e discutir seus limites teóricos.
- Metodologia:
- Coleção de gramáticas públicas, inserção controlada de ambiguidades, execução com limite de tempo e relação com a indecidibilidade.
12. Algoritmos quânticos em simulador: implementação do algoritmo de Grover e análise da probabilidade de sucesso
- Problema:
- Como o número de iterações e o ruído simulado afetam a probabilidade de sucesso do algoritmo de Grover em poucos qubits?
- Objetivo:
- Implementar o algoritmo de Grover em simulador e comparar resultados ideais e com modelos de ruído.
- Metodologia:
- Simulação com biblioteca aberta de computação quântica, variação de qubits e iterações e comparação com a análise teórica.
Do tema ao TCC: próximos passos
Escolhido o tema, transforme-o em estrutura: o gerador de sumário de TCC monta os capítulos a partir do problema e do objetivo. O passo a passo de como fazer monografia mostra cada etapa até a defesa, e as referências ABNT saem formatadas a partir das obras com DOI. Para entender o que a IA faz e o que continua sendo seu, veja TCC com IA.
Como escolher um tema de TCC em Teoria da Computação
Decida o tipo de contribuição. Pode ser uma demonstração nova de algo simples, uma formalização em assistente de provas, um estudo experimental que confronte teoria e prática, ou uma ferramenta didática. Cada formato exige habilidades diferentes, e todos são aceitos em Ciência da Computação.
Leia com atenção a bibliografia das disciplinas de Linguagens Formais, Teoria dos Grafos, Complexidade e Projeto de Algoritmos. Exercícios avançados e problemas em aberto citados nos livros são fontes de ideias. Converse com o orientador sobre o que é factível: provar um resultado inédito é difícil, mas reproduzir e formalizar um resultado conhecido já é valioso.
Por fim, avalie seu gosto por escrita matemática. A teoria pede definições precisas, notação consistente e muitas revisões. Se isso agrada, a área recompensa com trabalhos elegantes e boa preparação para o mestrado.
Linhas de pesquisa em alta em Teoria da Computação
A teoria se aproximou da prática com os assistentes de prova e com o uso de solucionadores SAT e SMT na indústria. No Brasil, eventos como o SBMF e o LSFA reúnem pesquisas em métodos formais e lógica.
- Formalização de matemática e algoritmos em assistentes de prova
- Solucionadores SAT e SMT e suas aplicações
- Complexidade parametrizada e algoritmos exatos
- Algoritmos de aproximação e otimização combinatória
- Verificação de modelos e lógica temporal
- Teoria de autômatos aplicada a expressões regulares e analisadores
- Computação quântica e seus algoritmos
- Ensino de teoria da computação com ferramentas interativas
Metodologias mais usadas em Teoria da Computação
O método clássico é a demonstração: definir o problema formalmente, enunciar o resultado e prová-lo. Reduções, indução e argumentos combinatórios são as ferramentas principais. A formalização em assistente de provas acrescenta verificação mecânica e deixa o trabalho reprodutível.
A algoritmia experimental é a outra grande vertente. Você implementa algoritmos, gera instâncias com propriedades controladas e compara o comportamento observado com o previsto pela análise. Trabalhos sobre ensino usam métodos de pesquisa educacional, com pré e pós-teste e grupos de comparação.
Como fazer o TCC de Teoria da Computação: passo a passo
A revisão começa pelos livros-texto da área, que estabelecem notação e resultados clássicos. Depois, use o dblp para localizar artigos por autor e evento, a ACM Digital Library, o arXiv na seção de ciência da computação e o Portal de Periódicos da CAPES. Os anais do SBMF estão na SBC OpenLib.
Escreva as definições antes de tudo. Uma seção de preliminares bem feita, com notação fixada, evita confusões nos capítulos seguintes. Em trabalhos experimentais, descreva os geradores de instâncias e os limites de tempo; em formalizações, informe a versão do assistente de provas e das bibliotecas usadas.
Entre os temas de TCC de Teoria da Computação, os que avaliam ferramentas didáticas com estudantes envolvem pessoas. Nesse caso, o projeto passa pelo Comitê de Ética em Pesquisa via Plataforma Brasil, conforme as Resoluções CNS 466/2012 e 510/2016, antes de qualquer aplicação.
O sumário costuma ter introdução, preliminares, trabalhos relacionados, desenvolvimento teórico ou formalização, experimentos quando houver, discussão e conclusão. Apêndices podem trazer provas longas e código.
- Escolha o formato: prova, formalização, estudo experimental ou ferramenta didática.
- Leia os capítulos de referência em livros-texto e fixe a notação.
- Localize artigos no dblp, na ACM, no arXiv e na SBC OpenLib.
- Escreva definições e enunciados antes de tentar as demonstrações.
- Implemente ou formalize, registrando versões e limites de tempo.
- Se houver estudantes participando, submeta o projeto ao CEP.
- Peça ao orientador revisão cuidadosa de cada prova antes da defesa.
Erros comuns no TCC de Teoria da Computação
Os problemas abaixo aparecem com frequência em monografias teóricas e costumam ser os primeiros apontados pela banca.
- Usar notação diferente em cada capítulo. Fixe a notação nas preliminares e mantenha-a.
- Fazer a redução na direção errada. Para provar dificuldade, reduza do problema conhecido para o novo.
- Esquecer de provar que o problema está em NP. Mostre o certificado e o verificador polinomial.
- Confundir pior caso com caso médio. Diga qual análise está sendo feita.
- Concluir complexidade a partir de poucos experimentos. Use a análise teórica e trate o experimento como ilustração.
- Deixar passos das provas como evidentes. Justifique cada passo não trivial.
Perguntas frequentes
Dá para fazer TCC de teoria da computação sem programar?
Dá. Trabalhos de demonstração, como reduções de complexidade ou provas sobre linguagens formais, podem ser inteiramente teóricos. Ainda assim, uma implementação ilustrativa costuma ajudar a banca a visualizar o resultado.
O que é um assistente de provas e por que usar no TCC?
É um software que verifica demonstrações matemáticas passo a passo, como Coq, Lean e Isabelle. Usá-lo garante que a prova não tem lacunas e gera um artefato reutilizável. A curva de aprendizado é grande, por isso combine o escopo com o orientador.
Posso tentar provar P diferente de NP no TCC?
Não é recomendável. É um dos maiores problemas em aberto da matemática e da computação. Um bom TCC pode, por outro lado, estudar resultados que explicam por que certas técnicas de prova não resolvem a questão, ou classificar a complexidade de problemas específicos.
Teoria da computação ajuda a entrar no mestrado?
Ajuda, porque desenvolve escrita matemática, leitura de artigos e rigor, que são cobrados em qualquer pós-graduação em computação. Um trabalho de conclusão teórico bem feito também mostra autonomia para pesquisa.
Como montamos esta página
Os temas foram redigidos pela equipe do TCC Pronto como ponto de partida e precisam da aprovação do seu orientador. As obras vêm de bases acadêmicas abertas (OpenAlex e Crossref) e o DOI de cada uma foi conferido antes da publicação. Leia a obra antes de citá-la no seu trabalho.