MC358 - Fundamentos Matemáticos da Computação

Créditos: 4
Horas semanais de atividades teóricas: 4
Oferecimento: Ambos os períodos letivos
 
Ementa

Conceitos básicos de matemática discreta e de lógica para computação. Técnicas de provas, indução matemática. Relações e conceitos de teoria de grafos. Modelagem de problemas usando grafos.

Programa

1. Conjuntos

 

2. Discurso matemático: leitura e escrita matemática

 

3. Elementos de lógica:

- proposições, conetivos lógicos e quantificadores.

 

4. Estratégias de prova

 

5. Indução matemática

 

6. Relações

- restrição, composição e inversa

- relações de ordem e elementos extremos

- relações e classes de equivalência

 

7. Funções

- funções injetoras, sobrejetora e bijetoras

- inversas

- sequências

- funções piso e teto

 

8. Somatórios e produtórios

- manipulação de índices e troca de ordem

- majoração e minoração de somatórias.

 

9. Recorrências

- aditivas e multiplicativas simples

- recorrências lineares, polinômio característico

- majoração e minoração de recorrências

 

10. Contagem

- princípios básicos da contagem (aditivo e multiplicativo)

- permutações, arranjos e combinações

- identidades binomiais

Bibliografia
A. Gomide e J. Stolfi, Elementos de Matemática Discreta para a Computação
D. J. Velleman, How to prove it - A structured approach (2a. edição), Cambridge (2006).
K. H. Rosen, Discrete Mathematics and its applications (7a. edição), McGraw-Hill (2011).
J. L. Gersting, Fundamentos Matemáticos para a Ciência da Computação (5a. edição), LTC Editora (2004).
M. Ben-Ari, Mathematical Logic for Computer Science (3a. edição), Springer (2012).