Matemática Discreta A
| Curso/semestre | Licenciatura em Matemática / Quinto |
| Disciplina | Matemática Discreta A |
| Caráter | Obrigatório |
| Pré-requisito | – |
| Código | 0100233 |
| Depto. | DME |
| CHT | 68 horas |
| Créditos | 04 |
| Natureza | 34 teóricas / 34 práticas |
| Prof. Resp. | |
| Objetivos |
Ensinar as técnicas básicas de contagem e noções sobre teoria de grafos.
|
| Ementa | Combinatória clássica enumeração de permutações e arranjos simples e com repetição, e de distribuições. Binômio de Newton, propriedades e relações dos coeficientes binomiais. Polinômio de Leibniz. Combinatória moderna enumeração via recorrência, funções, geratrizes e princípio da inclusão-exclusão. Noções de grafos e dígrafos. Caminhos Eulerianos e Hamiltonianos. |
| Programa |
Combinatória e Conjuntos O que é Combinatória? Aspectos históricos Conjuntos notação Somatório e Produtório Princípio de indução matemática
Métodos de contagem Princípio da Adição Princípio da Multiplicação (ou Fundamental da enumeração) Permutação simples Arranjos simples Combinações simples Combinações complementares Permutações com repetição Arranjos com repetição Combinação com repetição Permutações circulares Soluções inteiras de equações lineares com coeficientes unitários
Números binomiais O Triângulo de Pascal O Binômio de Newton Propriedades dos coeficientes binomiais O Polinômio de Leibniz
Outros Métodos de Contagem Princípio da inclusão e exclusão Cardinalidade da união finita de conjuntos A função phi de Euler Permutações caóticas O Princípio da reflexão O Princípio da casa dos pombos (ou princípio de Dirichlet)
Funções geratrizes Definição e exemplos Cálculo de coeficientes Partições de um inteiro
Relações de Recorrência Definição e exemplos Resolução de relações de recorrência Relações lineares homogêneas Relações lineares não-homogêneas Relações baseadas em função geratrizes.
Noções sobre grafos Definições Representações de grafos Caminhos Grafos Eulerianos Ciclos e caminhos Hamiltonianos Problema do menor caminho.
|
| Bibliografia |
Básica SANTOS, J. Plínio et alii. Introdução á Análise combinatória. Campinas, SP. Editora da UNICAMP, 1995. BARBOSA, R. M. Combinatória e Grafos. São Paulo. Nobel, 1974. LUCCHESI, C. L. Introdução à Teoria dos Grafos. Rio de Janeiro. Instituto de Matemática Pura e Aplicada (IMPA), 1979.
Complementar MORGADO, A. C. O. et alii. Análise combinatória e Probabilidade. Rio de Janeiro. IMPA, 1991. POLYA, G. et alii. Introduction to Combinatorics. Boston. Birkhauser, 1983. GRIMALDI, R. P. Discrete and Combinatorial Mathematics. Massachusetts. Addison-Wesley, 1986.
|