Nome da Atividade
MATEMÁTICA DISCRETA A
CÓDIGO
0100233
Carga Horária
68 horas
Tipo de Atividade
DISCIPLINA
Periodicidade
Semestral
Unidade responsável
CRÉDITOS
4
CARGA HORÁRIA TEÓRICA
2
CARGA HORÁRIA PRÁTICA
2
CARGA HORÁRIA OBRIGATÓRIA
4
FREQUÊNCIA APROVAÇÃO
75%
NOTA MÉDIA APROVAÇÃO
7
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.
Objectives
Objetivo Geral:
Ensinar as técnicas básicas de contagem e noções sobre teoria de grafos.Conteúdo Programático
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.
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
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.
Bibliografia 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.