Portal InstitucionalUFPEL

Objetivo Geral:

Objetivo(s) geral(ais):
● Ensinar as técnicas básicas de contagem e noções sobre teoria de grafos.

Objetivo(s) específico(s):
● Estudar os Métodos de Contagem Simples e com Repetições;
● Estudar os Métodos de Contagem via Relações de Recorrência;
● Estudar os Métodos de Contagem via Funções Geradoras e Princípio de Inclusão-exclusão;
● Noções sobre Grafos.

Unidade 1 - Combinatória e Conjuntos
1.1. O que é Combinatória? Aspectos históricos;
1.2. Conjuntos notação;
1.3. Somatório e Produtório;
1.4. Princípio de indução matemática.

Unidade 2 - Métodos de contagem
2.1. Princípio da Adição;
2.2. Princípio da Multiplicação (ou Fundamental da enumeração);
2.3. Permutação simples;
2.4. Arranjos simples;
2.5. Combinações simples;
2.6. Combinações complementares;
2.7. Permutações com repetição;
2.8. Arranjos com repetição;
2.9. Combinação com repetição;
2.10. Permutações circulares;
2.11. Soluções inteiras de equações lineares com coeficientes unitários.

Unidade 3 - Números binomiais
3.1. O Triângulo de Pascal;
3.2. O Binômio de Newton;
3.3. Propriedades dos coeficientes binomiais;
3.4. O Polinômio de Leibniz.

Unidade 4 - Outros Métodos de Contagem
4.1. Princípio da inclusão e exclusão;
4.2. Cardinalidade da união finita de conjuntos;
4.3. A função phi de Euler ;
4.4. Permutações caóticas;
4.5. O Princípio da reflexão;
4.6. O Princípio da casa dos pombos (ou princípio de Dirichlet).

Unidade 5 - Funções geratrizes
5.1. Definição e exemplos;
5.2. Cálculo de coeficientes;
5.3. Partições de um inteiro.

Unidade 6 - Relações de Recorrência
6.1. Definição e exemplos;
6.2. Resolução de relações de recorrência;
6.3. Relações lineares homogêneas;
6.4. Relações lineares não-homogêneas;
6.5. Relações baseadas em função geratrizes.

Unidade 7 - Noções sobre grafos
7.1. Definições;
7.2. Representações de grafos;
7.3. Caminhos;
7.4. Grafos Eulerianos;
7.5. Ciclos e caminhos Hamiltonianos;
7.6. Problema do menor caminho.

Bibliografia Básica:

• ROSEN, K. H. Matemática discreta e suas aplicações. Porto Alegre: ArtMed, 2010. ISBN 9788563308399. E-book.
• GERSTING, J.L. Fundamentos Matemáticos para a Ciência da Computação. Rio de Janeiro: LTC, 2016. ISBN 9788521633303. E-book.
• SCHEINERMAN, E. R. Matemática Discreta: Uma introdução. São Paulo: Cengage Learning, 2016. ISBN 9788522125388. E-book.

Bibliografia Complementar:

• LIPSCHUTZ, S.; Lipson, M. Matemática discreta. Porto Alegre: Bookman (Schaum) 2013. ISBN 9788565837781. E-book.
• HUNTER, D. J. Fundamentos da matemática discreta. Rio de Janeiro LTC, 2011.
• SANTOS, J. P. O.; Mello, M. P; Murari, I.T.C. Introdução à Análise Combinatória. Rio de Janeiro: Ciência Moderna, 2007.
• BALAKRISHNAN, V.K. Introductory Discrete Mathematics. Dover Books, 2010.
• SUSANNA, S. E. Discrete Mathematics with Applications. Cengage learning, 2010.