MC358 - Fundamentos Matemáticos da Computação

A partir de 2016

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

http://www.ic.unicamp.br/~anamaria/.

• 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).