Programa da Disciplina

Nome:	MATEMÁTICA DISCRETA II
Código:	14203
Departamento:	Departamento de Computação (DC)
Área:	Computação
Carga-horária total:	60 horas
Créditos:	4
Pré-requisitos:	14203 - MATEMÁTICA DISCRETA I

Ementa

Combinatória Básica: Permutações, Combinações, binômios, ocupância, inclusão/exclusão, recorrências. Inversão de Moebius, Ações de grupos e semigrupos.
Teoria dos Grafos: propriedades e teoremas fundamentais.
Algoritmos em Grafos. Indução e Iteração, Órbitas e pontos fixos, Automato Celulares (AC), AC e Automatos Finitos, AC e Álgebra, AC e Computação.

Objetivos

Fornecer aos alunos os conhecimentos básicos dos principais tópicos da Matemática Discreta:

Combinatória;

Álgebra abstrata;
Teoria dos grafos;
Visualizar algumas aplicações práticas dessas teorias e técnicas na área de Ciência da Computação.

Equivalências

14086 - LÓGICA APLICADA À COMPUTAÇÃO

Conteúdo

• Coeficientes binominais

• Teorema Binominal e Triangulo de Pascal

• Permutações e combinações

• Estruturas algébricas: semigrupos, monoides, grupos (definição e exemplos)

• Grupos: propriedades

• Geradores e grafos de grupos; Grupos de permutação.

• Anéis e Corpos

• Grafos: Introdução, Definição e Terminologia.

• Grafos: Representação, isomorfismos, conectividade, grafos com pesos.

• Grafos: conectividade, caminho, circuito euleriano e hamiltoniano

• Grafos: planaridde e coloração

• Aritmética Modular

• Teoria de codificação algébrica

• Técnicas de verificação de erros

• Aplicações de matemática discreta

• ~~Criptografia~~ conteúdo obsoleto

Conteúdo do período letivo 2019.1

Contagem
- Princípios básicos (Regra da soma e do produto, PCP...);
- Permutação e Combinação;
- Coeficientes Binomiais;
- Relações de Recorrência;
Grafos
- Tipos de grafos;
- Isomorfismo de grafos;
- Coloração e planaridade;
- Árvores;
Estrutura Algébricas
- Grupos;
- Anéis e Corpos

Validação do período letivo 2019.1

1ª V.A.: Teste + Prova
- Contagem
- Grafos e Árvores
2ª V.A.: Teste + Prova
- Grupos
- Anéis e Corpos
3ª V.A.: Prova escrita
Final: Prova escrita

Estilos de provas

Definições: Definições e conceitos vistos
Probleminhas: Problemas práticos dos assuntos abordados
Problemas: Demonstrações de proposições e teoremas

Bibliografia Básica

SCHEINERMAN, E. R. Matemática Discreta: Uma Introdução. Segunda edição. São Paulo: Cengage

Learning, 2011.

GERSTING, J. L. Fundamentos Matemáticos para a Ciência da Computação. Quinta Edição. Rio de

Janeiro: LTC, 2004.

PATASHNIK, O.; GRAHAM, R. L.; KNUTH, D. E. Matemática Concreta: Fundamentos para a Ciência

da Computação. Segunda edição. Rio de Janeiro: LTC, 1995.

Bibliografia Complementar

HARRIS, J.; HIRST, J. L.; MOSSINGHOFF, M. Combinatorics and Graph Theory. 2nd ed. Springer,

2008.

ROSEN, K. H. Matemática Discreta e suas Aplicações. Sexta edição. São Paulo: McGraw-Hill, 2009.

PEMMARAJU, S.; SKIENG, S.: Computational Discrete Mathematics: Combinatorics and Graph

Theory with Mathematica®. Cambridge University Press, 1 Reissue edition, 2009.

SUTNER, K.: Computational Discrete Mathematics (notas de aulas). Disponível eletronicamente em

http://www.cs.cmu.edu/~cdm/.

GALLIAN, J. A.; Contemporary Abstract Algebra, Seventh Edition.2010.

JUDSON, T.W.; Abstract Algebra: Theory and Applications. 2012. Disponível eletronicamente em:

http://abstract.ups.edu/.