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.

Objetivos

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.

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.

Página gerada em 14/11/2024 20:39:52 (consulta levou 0,072028s)