Curso de Matemática Discreta

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

Aborda os símbolos padrão, quantificadores e notação de somatório usados na matemática discreta. Desenvolve a fluência na leitura e escrita de afirmações matemáticas formais.

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

Define proposições, conectivos lógicos e valores de verdade. Relaciona o raciocínio lógico com a escrita de demonstrações e a análise de algoritmos.

Aula 3 • Conjuntos e Operações sobre Conjuntos

Introduz conjuntos, pertença 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 Fatorização

Examina a distribuição de primos, testes de primalidade e fatorização única. Suporta a compreensão da criptografia RSA e de algoritmos de teoria dos números.

Aula 2 • Aritmética Modular

Introduz congruências, operações modulares e classes de resto. 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 do 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. Relaciona a simplificação lógica com o design de circuitos e o 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 ciclo e especificações. Estabelece uma ponte entre a lógica formal e a verificação de software e a análise de algoritmos.

Aula 1 • Definições e Estruturas Recursivas

Define sucessões, conjuntos e funções recursivamente. Relaciona definições recursivas com estruturas de dados como listas e árvores.

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

Estende a indução à forma forte e relaciona-a com o 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 fechadas para recorrências lineares. Suporta a análise de complexidade de algoritmos através da resolução de recorrências.

Aula 1 • Princípio do Pombal e Aplicações

Enuncia o princípio do pombal e aplica-o a demonstrações de existência. Demonstra como os argumentos de contagem garantem propriedades estruturais em sistemas discretos.

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

Introduz as funções geradoras ordinárias como ferramenta de contagem. Relaciona a álgebra de polinómios com a enumeração combinatória e a resolução de recorrências.

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

Diferencia seleções ordenadas e não ordenadas e deriva fórmulas baseadas em fatoriais. Aplica estas a problemas de escalonamento, disposição e seleção.

Aula 4 • Teorema Binomial e Identidades

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

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

Relaciona relações de equivalência com 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 injetivas, sobrejetivas e bijetivas e analisa inversas. Suporta a compreensão de codificação de dados, hashing e mapeamentos criptográficos.

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

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

Aula 1 • Árvores e Árvores Abrangentes

Define árvores, árvores enraizadas e árvores abrangentes e demonstra propriedades-chave. Relaciona estruturas de árvore com dados hierárquicos e algoritmos de árvore abrangente mínima.

Aula 2 • Propriedades de Grafos e Grafos Especiais

Examina sucessões de grau, conectividade e famílias especiais de grafos. Relaciona propriedades estruturais com o design de algoritmos e a análise de redes.

Aula 3 • Caminhos Eulerianos e Hamiltonianos

Enuncia condições para caminhos e circuitos eulerianos e hamiltonianos. Aplica estes conceitos a problemas de encaminhamento, escalonamento e design de redes.

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

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

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

Introduz redes de fluxo, fluxos admissíveis e o teorema do fluxo máximo-corte mínimo. Relaciona o fluxo em redes com transporte, encaminhamento 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ções e escalonamentos.

Aula 3 • Algoritmos de Caminho Mais Curto

Aborda os algoritmos de Dijkstra e Bellman-Ford para caminhos mais curtos em grafos ponderados. Aplica estes a protocolos de encaminhamento 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. Relaciona a planaridade com o design de circuitos e as consultas em bases de dados de grafos.