Matemática Discreta - Introdução

Material didático da disciplina Matemática Discreta

1. • Apresentação da disciplina
•UNIVERSIDADE FEDERAL DE CAMPINA GRANDE
•CENTRO DE ENGENHARIA ELÉTRICA E INFORMÁTICA
•DEPARTAMENTO DE SISTEMAS E COMPUTAÇÃO
•Professor Ulrich Schiel

2. • Matemática – uma definição:
É uma ciência que analisa estruturas
abstratas segundo suas propriedades
e Modelos
• Ramos da matemática:
•Geometria
•Álgebra

3. • Uma estrutura fundamental:
O CONJUNTO
É uma coleção de objetos a serem
estudados.

4. • Tipos de conjuntos
Finitos
Enumeráveis ou contáveis (N, Z, Q)
Recursivamente enumerável
Não contáveis (P(X), para X infinito)
Contínuos ( R)
Hipótese do contínuo – não existe
nada entre |N| e |R|

5. • MATEMÁTICA
Dependendo do tipo de conjuntos das
estruturas abstratas - distinguimos:
• MATEMÁTICA CONTÍNUA
• MATEMÁTICA DISCRETA

6. • Matemática contínua
-Conjuntos e Funções contínuas,
-Análise, cálculo, Geometria, Topologia
-R, R
2
, .., R
n
,.., R
¥

7. • Matemática discreta
•É o ramo da matemática que estuda
estruturas discretas, enumeráveis ou finitas.

8. • Matemática discreta ou finita ou
concreta
– Lógica matemática
– Técnicas de prova
– Teoria dos conjuntos
– Relações e Funções
– Teoria dos números, combinatória
– Teoria dos jogos
– Estruturas discretas: Grafos, reticulados, Árvores
– Álgebra. Álgebra de Boole

9. • Matemática discreta ou finita ou
concreta
–Algoritmos e recursão
– Complexidade e computabilidade
– Teoria da informação, criptografia
–Estatística
–Teoria das probabilidades, possibilidades,
Cadeias de Markov
– Linguagens formais e Autômatas finitos

10. • BIBLIOGRAFIA
-J. Gersting “Fundamentos
Matemáticos para a Ciência da
Computação – 5ª edição”, LTC
(2004)
-Paulo Blauth “Matemática Discreta para
Computação e Informática”, Sagra-Luzzato
(2004)
-R.L. Graham, D.E. Knuth e O. Patashnik,
“Matemática Concreta – Fundamentos para
a Ciência da Computação”. LTC, 1995.

11. • Aulas expositivas
• Exercícios (bônus na média)
• Minitestes (0,2)
•Provas (0,8)

12. • Lógica simbólica (outra disciplina)
• Técnicas de Demonstração
• Definições indutivas
• Teoria dos Conjuntos
• Relações
• Funções
• Estruturas discretas: Grafos e Árvores (outra
disciplina)
• Estruturas matemáticas (Ordem, Álgebra e Topologia)
• Álgebra de Boole

13. http://www.dsc.ufcg.edu.br/~ulrich/disciplinas/MaDi.html
http://groups.google.com.br/group/md-l?pli=1

14. TURMA-1: Prof. Leandro Balby
http://www.dsc.ufcg.edu.br/~lbmarinho/md_apres_2012.2.html
https://groups.google.com/forum/?hl=pt&fromgroups#!
forum/matematica_discreta_ufcg_2012_2

15. Motivação – Lógica e
demontração

16. Motivação – Lógica e
demonstração

17. Motivação – Lógica e
demonstração
Principais lógicas:
• Cálculo proposicional
•(p & q) v (~p & q) ® q
•Tabelas verdade
•Cálculo dos predicados
•"x(P(x) ®Q(x)) & P(a) ® $x (Q(x))

18. Motivação – Teoria dos conjuntos
• Os alunos de Cálculo I têm algo a ver
Com os alunos do curso de Ciência da
Computação?
• É possível enumerar todos conjuntos
finitos de números inteiros?

19. Motivação – relações
• Dado o conjunto de todos usuários do
Facebook, como modelar todos amigos
registrados?
• Como um algoritmo sugere novos
amigos?

20. Motivação – funções
• é possível definir uma função que
associa a cada número racional um
número inteiro?
• Como é possível combinar duas
funções?

21. Motivação – Álgebras e Álgebras
de Boole
• Existe uma relação entre a lógica
proposicional a teoria dos conjuntos e a
matemática computacional?
• Como resolver cálculos de números
digitais com números binários?
• O que é uma combinação entre
conjuntos, relações e funções?