Matemática Discreta para Computação

Tópicos Abordados

A disciplina é divida em 2 unidades, como visto abaixo, visando facilitar a organização do conhecimento e o aprendizado.

Primeira Unidade

• Provas e Proposições
• Noções básicas sobre conjuntos
• Noções básicas sobre funções e relações.
• Sequências
• Cardinalidade e Enumerabilidade
• Racionais
• Crescimento de função
• Métodos de Prova e Indução Matemática
• Definições Recursivas
• Fibonacci
• Teorema binomial
• Triângulo de Pascal
• O Princípio da Casa de Pombo
• Números Primos e Divisibilidade
• Algoritmo de Euclides
• Aritmética Modular
• Teorema Chinês do Resto
• O pequeno teorema de Fermat e teste de primalidade

Segunda Unidade

• Relações
• Fechos de uma relação
• Relações de equivalência
• Ordenações parciais
• Ordem Lexicográfica
• Diagrama de Hasse
• Reticulados
• Grafos: definições e terminologia
• Grafos: representação e isomorfismo
• Grafos com pesos
• Grafos: caminho e circuito euleriano e hamiltoniano
• Planaridade
• Coloração
• Árvores: definições, terminologia, propriedades
• Árvores binárias de busca
• Caminhamento em árvores
• Árvores Geradoras

Condução da Disciplina

• O curso está dividido em duas unidades. Cada unidade se encerra com uma avaliação que inclui todos os assuntos da respectiva unidade.

• Cada unidade possui 2 mini-provas. Cada uma vale 2,0 (dois) pontos. Cada avaliação vale 7,0 (sete) pontos.

• Não haverá segunda chamada de todas as mini-provas. Caso o aluno falte apenas uma mini-prova, poderá fazer uma questão extra na avaliação da unidade, valendo como segunda chamada da mini-prova.

Objetivos

Diferentemente de Cálculo, que estuda as chamadas estruturas matemáticas contínuas, este curso aborda a matemática que envolve apenas estruturas matemáticas discretas e/ou finitas: números inteiros, recorrências, grafos, árvores. A idéia é prover ferramentas básicas para o projeto e a análise de algoritmos.

Referências

• Discrete Mathematics and its Applications, Kenneth Rosen, McGraw-Hill Higher Education. ISBN: 0-07-289905-0, 4th edition, 1998.