Aulas 01 Matematica Discreta Unip Computação

Prévia do material em texto

MATEMÁTICA DISCRETA
Prof. Waterloo F. da Silva
MBA em Gestão de Projetos
Fundação Getúlio Vargas 
Bach. Em Ciências da Computação 
UFMA - Universidade Federal do Maranhão
Contatos:
EMAIL:waterloof@gmail.com
Skype: waterloof 
Prof. Wateloo Ferreira da Silva
Mestrando em Engenharia Elétrica
UFPA Universidade Federal do Pará 
PLANO DE ENSINO
I – EMENTA
 Combinatória: Princípios da adição e da
multiplicação, permutações e
combinações.
 Primeiro e Segundo Princípios da
Indução Matemática.
 Recursão: Relações de Recorrência,
Sequências recursivas e algoritmos
recursivos.
 Comparação entre algoritmos recursivos
e iterativos.
PLANO DE ENSINO
II – OBJETIVOS GERAIS
Desenvolver o raciocínio em matemática
discreta com o estudo de combinatória,
indução matemática e recursão. Fazer
contagens, desenvolver demonstrações por
indução, compreender relações de
recorrências e algoritmos recursivos.
Diferenciar algoritmos recursivos de
algoritmos iterativos.
PLANO DE ENSINO
III - OBJETIVOS ESPECÍFICOS
 Utilizar os métodos para fazer
contagens;
 Compreender a diferença entre
combinações e permutações;
 Fazer demonstrações de conjecturas
usando as técnicas de demonstração por
indução matemática;
 Compreender definições recorrentes de
seqüências, coleções de objetos e
operações sobre objetos.
 Escrever definições recorrentes para
determinadas seqüências, coleções de
objetos e operações sobre objetos.
PLANO DE ENSINO
IV – CONTEÚDO PROGRAMÁTICO
Módulo 01: 
 Princípio da multiplicação
 Princípio da adição
Módulo 02: 
 Arranjos e Permutações
PLANO DE ENSINO
IV – CONTEÚDO PROGRAMÁTICO
Módulo 03: 
 Combinações.
Módulo 04: 
 Combinações com elementos repetidos e 
Permutações circulares.
Módulo 05: 
 Princípio de Inclusão-exclusão 
 Princípio da Casa dos Pombos.
PLANO DE ENSINO
IV – CONTEÚDO PROGRAMÁTICO
Módulo 06: 
 Primeiro Princípio de Indução 
Matemática
Módulo 07: 
 Segundo Princípio de Indução 
Matemática
Módulo 08: 
 O Princípio de Indução Matemática e o 
Princípio da Boa-Ordem.
PLANO DE ENSINO
IV – CONTEÚDO PROGRAMÁTICO
Módulo 09: 
 Funções Recursivas e Sequências 
recursivas
Módulo 10: 
 Relações de recorrência e conjuntos 
recursivos.
PLANO DE ENSINO
IV – CONTEÚDO PROGRAMÁTICO
Módulo 11: 
 Alfabetos e conjuntos recursivos.
Módulo 12: 
 Comparação entre algoritmos recursivos 
e iterativos
PLANO DE ENSINO
V – ESTRATÉGIA DE TRABALHO
 Aulas teóricas expositivas. 
 Aulas de exercícios com a participação 
dos alunos e com a orientação dos 
professores. 
 Recursos audiovisuais. 
VI – AVALIAÇÃO
 Duas provas bimestrais. 
 Entrega de trabalhos, individuais ou em 
grupos, e/ou resolução de listas de 
exercícios.
PLANO DE ENSINO
VII – BIBLIOGRAFIA
Básica:
 GERSTING, J. L. - Fundamentos 
Matemáticos para a Ciência de 
Computação Rio de Janeiro. – Ed. LTC. -
2004.
 LOPES, L. - Manual da indução 
matemática. - Ed. Interciência - 1999.
 SCHEINERMAN, E. R. - Matemática 
discreta. Uma introdução. – Ed. Pioneira 
Thomson -2003.
PLANO DE ENSINO
VII – BIBLIOGRAFIA
Complementar :
 ALENCAR FILHO, E. - Iniciação à Lógica 
Matemática. – Ed. Nobel - 2002.
 ROSS, K. A.; WRIGHT, C. R. B.- Discrete 
mathematics. 3. ed. Englewood Ciffs, N. 
J.: Prentice-Hall - 2003.
 GRAHAM, R. L., KNUTH, D. E. e 
PATASHNIK, O. - Concrete Mathematics. 
A foundation for computer science. New 
York. Addison Wesley.- 1994.
PLANO DE ENSINO
VII – BIBLIOGRAFIA
Complementar :
 GARCIA LOPEZ, Javier. TOSCANI, Laira
Vieira. MENEZES, Paulo Blauth. 
Aprendendo Matemática Discreta com 
Exercícios. Livros Didáticos Informática 
UFRGS, V.19. Bookman Companhia Ed., 
2009.
 MENEZES, Paulo Blauth. Matemática 
Discreta para Computação e Informática. 
Bookman Companhia Ed., 2010.
Símbolos da Lógica
Símbolo Lê-se
não
ou
e
Se...então
....se e
somente se....
Para todo
Existe







Símbolos da Álgebra
Símbolo Lê-se
pertence
está contido ou é igual
união
intersecção
Produto cartesiano
Conjunto das partes
Conjunto vazio






  ou 
Inclusão de Conjuntos
Observação:
)( BxAxBA 
ABBABA 
União de Conjuntos
 Bx ouA xxBA  :
BxAxBAx 
BA
Intersecção de Conjuntos
 Bx eA xxBA  :
BxAxBAx 
BA
Diferença entre Conjuntos
 Bx eA xxBA  :
BA 
Partes de um Conjunto
Exemplo:
Se , então
 indica o número de elementos de

AX se )AX  (
 dcbaA ,,,
       ,,,,,,,,,,,, dcbdcadbacba
           ,,,,,,,,,,,, dcdbcbdacaba
       ,,,,,{)( dcbaA 
 },,, dcba
A2A  )(
A A
Produto Cartesiano
Exemplo:

 Bb eA abaBA  :),(
 21A ,
 432B ,,
 ),(),,(),,(),,(),,(),,( 423222413121BA 
BABA .
Interatividade
Considerando o conjunto , 
indique a alternativa falsa :
a) 
b) 
c) 
d) 
e)
 4321A ,,,
A3
)(A3 
  A3 
  )(A3   A3 
Resposta
Alternativa d): 
Justificativa:
é um subconjunto de A e não um 
elemento de A.
  A3 
 3
Princípio da Inclusão-Exclusão 
(para dois conjuntos)
 BABA
A B
Princípio da Inclusão-Exclusão 
(para dois conjuntos)
BABABA 
BA
Princípio da Inclusão-Exclusão 
(para dois conjuntos)
Exemplo
Entre 50 frequentadores de uma
academia 40 praticam musculação, 25
praticam natação e 20 praticam ambas as
modalidades. Qual é o número de
frequentadores que não praticam
nenhuma das duas modalidades?
Princípio da Inclusão-Exclusão 
(para dois conjuntos)
Solução:
Número total de frequentadores: 50
A = conjunto formado pelos que praticam
musculação;
B= conjunto formado pelos que praticam
natação;
, e 
Portanto,
R: 5 frequentadores não praticam nem 
musculação, nem natação;
40A  25B  20BA 
45202540BA 
Princípio da Inclusão-Exclusão 
(para três conjuntos)
 CBA  CBA
A B
C
Princípio da Inclusão-Exclusão 
(para três conjuntos)
 CBA CB A
 CBCABA
CB
Princípio da Inclusão-Exclusão 
(para três conjuntos)
 CBA CB A
CBCA  BA
CBA 
CBA 