MC358-Fundamentos-Matematicos-da-COMPUTACAO-INSTITUTO-DE-COMPUTACAO

Prévia do material em texto

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).
http://www.ic.unicamp.br/~anamaria/