DC-UFRPE/Bacharelado em Ciência da Computação/Matemática Discreta II

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/.