Institutional PortalUFPEL

Objetivo Geral:

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

Objetivos específicos:
– 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:

• SCHEINERMAN, E.R. Matemática Discreta: uma introdução. São Paulo: Cengage Learning. ISBN 9788522125388 [Livro eletrônico]
• SANTOS, J.P.O.; MELLO, M.P.; MURARI, I.T.C. Introdução à Análise Combinatória. Rio de Janeiro: Ciência Moderna. ISBN 9788573936346
• GERSTING, J.L. Fundamentos Matemáticos para a Ciência da Computação. Rio de Janeiro: LTC. ISBN 9788521633303 [Livro eletrônico]

Bibliografia Complementar:

• ROSEN, K.H. Matemática Discreta e suas Aplicações. Porto Alegre: ArtMed. ISBN 9788563308399 [Livro eletrônico]
• LIPSCHUTZ, S. Matemática Discreta. Porto Alegre: Bookman (Schaum). ISBN 9788565837781 [Livro eletrônico]