Curso de Matemática Discreta

Aula 1 • Notação e Símbolos Matemáticos

Aborda símbolos padrão, quantificadores e notação de somatório usados em matemática discreta. Desenvolve fluência na leitura e escrita de enunciados matemáticos formais.

Aula 2 • Introdução à Lógica e Proposições

Define proposições, conectivos lógicos e valores-verdade. Conecta o raciocínio lógico à redação de demonstrações e à análise de algoritmos.

Aula 3 • Conjuntos e Operações com Conjuntos

Apresenta conjuntos, pertinência e operações como união, interseção e complemento. Fornece a linguagem fundamental para todos os tópicos subsequentes.

Aula 1 • Números Primos e Fatoração

Examina a distribuição de números primos, testes de primalidade e a fatoração única. Dá suporte à compreensão da criptografia RSA e de algoritmos de teoria dos números.

Aula 2 • Aritmética Modular

Apresenta congruências, operações modulares e classes de resíduos. Fornece a base aritmética para aplicações criptográficas e de hashing.

Aula 3 • Divisibilidade e Propriedades dos Inteiros

Define divisibilidade, fatores e múltiplos para inteiros. Estabelece propriedades usadas no cálculo de MDC e na aritmética modular.

Aula 1 • Formas Normais e Simplificação

Aborda as formas normais conjuntiva e disjuntiva e a simplificação booleana. Conecta a simplificação lógica ao projeto de circuitos e ao raciocínio automatizado.

Aula 2 • Lógica Proposicional e Inferência

Formaliza a lógica proposicional com regras de inferência e leis lógicas. Desenvolve a capacidade de derivar conclusões a partir de premissas dadas de forma sistemática.

Aula 3 • Lógica em Algoritmos e Programas

Aplica o raciocínio lógico à correção de programas, invariantes de laço e especificações. Conecta a lógica formal à verificação de software e à análise de algoritmos.

Aula 1 • Definições e Estruturas Recursivas

Define sequências, conjuntos e funções recursivamente. Conecta definições recursivas a estruturas de dados como listas e árvores.

Aula 2 • Indução Forte e Princípio da Boa Ordenação

Estende a indução para a forma forte e a conecta ao princípio da boa ordenação. Permite demonstrações em que vários casos anteriores são necessários simultaneamente.

Aula 3 • Resolução de Relações de Recorrência

Aborda métodos para encontrar soluções em forma fechada para recorrências lineares. Auxilia na análise de complexidade de algoritmos por meio da resolução de recorrências.

Aula 1 • Princípio da Casa dos Pombos e Aplicações

Enuncia o princípio da casa dos pombos e o aplica a demonstrações de existência. Demonstra como argumentos de contagem garantem propriedades estruturais em sistemas discretos.

Aula 2 • Introdução às Funções Geradoras

Apresenta as funções geradoras ordinárias como ferramenta de contagem. Conecta a álgebra polinomial à enumeração combinatória e à resolução de recorrências.

Aula 3 • Permutações e Combinações

Distingue seleções ordenadas e não ordenadas e deriva fórmulas baseadas em fatorial. Aplica esses conceitos a problemas de agendamento, arranjo e seleção.

Aula 4 • Teorema Binomial e Identidades

Demonstra o teorema binomial e deriva identidades combinatórias. Conecta a expansão algébrica a argumentos de contagem e ao triângulo de Pascal.

Aula 1 • Relações de Equivalência e Partições

Conecta relações de equivalência a partições de um conjunto em classes disjuntas. Aplica classes de equivalência à aritmética modular e a sistemas de tipos.

Aula 2 • Funções: Tipos e Propriedades

Classifica funções como injetoras, sobrejetoras e bijetoras e analisa inversas. Auxilia na compreensão de codificação de dados, hashing e transformações criptográficas.

Aula 3 • Relações Binárias e Propriedades

Define relações binárias e suas propriedades: reflexividade, simetria e transitividade. Fornece a estrutura para relações de equivalência e de ordem.

Aula 1 • Árvores e Árvores Geradoras

Define árvores, árvores enraizadas e árvores geradoras e demonstra propriedades-chave. Conecta estruturas de árvore a dados hierárquicos e algoritmos de árvore geradora mínima.

Aula 2 • Propriedades de Grafos e Grafos Especiais

Examina sequências de graus, conectividade e famílias especiais de grafos. Conecta propriedades estruturais ao projeto de algoritmos e à análise de redes.

Aula 3 • Caminhos e Ciclos Eulerianos e Hamiltonianos

Enuncia condições para caminhos e circuitos eulerianos e hamiltonianos. Aplica esses conceitos a problemas de roteamento, agendamento e projeto de redes.

Aula 4 • Definições e Representações de Grafos

Define vértices, arestas, grafos direcionados e não direcionados e representações comuns. Estabelece vocabulário e estruturas de dados para todos os algoritmos em grafos.

Aula 1 • Fluxo em Redes e Teorema do Fluxo Máximo e Corte Mínimo

Apresenta redes de fluxo, fluxos viáveis e o teorema do fluxo máximo e corte mínimo. Conecta fluxo em redes a transporte, roteamento e alocação de recursos.

Aula 2 • Emparelhamento e Grafos Bipartidos

Aborda emparelhamentos perfeitos, teorema de Hall e algoritmos de caminho aumentante. Aplica a teoria de emparelhamento à otimização de atribuição e agendamento.

Aula 3 • Algoritmos de Caminho Mínimo

Aborda os algoritmos de Dijkstra e Bellman-Ford para caminhos mínimos em grafos ponderados. Aplica esses conceitos a protocolos de roteamento e sistemas de navegação geográfica.

Aula 4 • Grafos Planares e Isomorfismo de Grafos

Demonstra a fórmula de Euler para grafos planares e introduz testes de isomorfismo. Conecta planaridade a layout de circuitos e consultas em bancos de dados de grafos.