Introdução à Teoria da Computação. Notações Matemáticas. Linguagens Regulares. Autômatos Finitos Determinísticos e Não-determinísticos. Expressões Regulares. Lema do Bombeamento. Linguagens Livres do Contexto. Gramáticas. Autômatos de Pilha. Máquinas de Turing Dterminísticas e Não-determinísticas. Problema da Parada. Decidibilidade.
Conceito de algoritmo. Papel dos algoritmos em computação. Corretude e eficiência. Complexidade assintótica no pior e melhor casos e no caso médio. Padrões de algoritmos: força bruta, gulosos (greedy), retrocesso (backtrack), divisão e conquista. Programação dinâmica. Grafos. Problemas geométricos. Problemas intratáveis.
Corretude e eficiência de algoritmos. Análise combinatória. Espaço de busca:
crescimento exponencial e poda da árvore de busca. Teoria dos números. Resolução de problemas e implementação computacional de algoritmos. Treinamento para participação em competições de programação.
Representação de dados. Estruturas lineares: vetor, lista, pilha e fila. Recursão. Árvores binárias. Árvores de busca. Árvores balanceadas. Algoritmos para manipulação de estruturas: inserção, remoção, busca e percurso. Ordenação de dados. Heaps. Filas com prioridades. Noções de complexidade dos algoritmos utilizados.