01 Introducao MTMD

Prévia do material em texto

Introdução à
Matemática Discreta
Matemática Discreta
Prof. Vilson Heck Junior
vilson.junior@ifsc.edu.br
Condução da disciplina
• Aulas:
– Quartas: 10:10 – 12:00
– Sextas: 08:00 – 09:50
• Haverá troca de professores:
– Cada professor realizará avaliações;
– A nota final será uma média das diferentes avaliações;
• MUITOS EXERCÍCIOS!
• Diferentes livros na biblioteca!
• Haverá reposição das aulas de Administração e Introdução à
Programação!
Conteúdos - MTMD
Conteúdos Docente (ch)
1. Introdução;
2. Lógica proposicional e de primeira ordem;
Vilson (18h)
3. Conjuntos;
4. Relações;
(16h)
5. Sequências e somas (10h)
6. Indução e recursão (8h)
7. Análise combinatória (12h)
8. Elementos da teoria dos números (8h)
Livro Principal
(Primeira parte - Vilson)
O que é MTMD?
• A matemática discreta é o estudo de estruturas
matemáticas que são fundamentalmente discretas, ao
invés de contínuas;
• Alguns pontos importantes:
– A importância do pensamento lógico;
– O poder da notação matemática;
– A utilidade de abstrações matemáticas;
Contínuo
• Se pensarmos nos números reais, temos um exemplo do que é
contínuo. Não há transições abruptas entre os valores, na
verdade há infinitos valores entre cada par de números:
0
0,5
1
1,5
2
2,5
3
3,5
4
0 1 2 3 4
Contínuo
Reais
Discreto
• Ao compararmos com os números inteiros, temos um exemplo do
que é discreto. Há transições abruptas entre os valores:
0
0,5
1
1,5
2
2,5
3
3,5
4
0 1 2 3 4
Discreto
Inteiros
Outros exemplos
• Ainda, além dos números inteiros, declarações lógicas
e grafos são outros exemplos de estruturas discretas.
• Em geral, estes problemas matemáticos não são
equacionados através de fórmulas algébricas
tradicionais.
Exemplo de grafo
EXEMPLOS:
CONTÍNUO VS DISCRETO
Introdução à Matemática Discreta
Dados - Velocidade de uma 
Ferrari 430 Scuderia 2008
No mundo real - Contínuos Na computação - Discretos
Fonte da imagem à esquerda: 
http://www.motortrend.com/roadtests/exotic/112_0808_2008_ferrari_430_scuderia_test/photo_17.html
Imagens Digitais
No mundo real - Contínuas Na computação - Discretas
Fonte da imagem à esquerda: 
http://en.wikipedia.org/wiki/Lenna
Mapas
No mundo real - Contínuos Na computação - Discretos
Fonte da imagem à esquerda: 
http://www.brasil-turismo.com/santa-catarina/mapas/transportes.htm
Quando estudaremos 
Matemática Contínua?
1. Álgebra Linear e Geometria Analítica – Fase 2
– A geometria cuida de questões de forma, tamanho e posição
relativa de figuras, formas e com as propriedades do espaço;
– Álgebra linear é um ramo da matemática que estuda sistemas
de equações lineares, muito utilizados na geometria;
2. Cálculo (diferencial e integral) – Fase 3
– Estuda principalmente variações e acúmulos de grandezas,
com aplicações em diversas áreas de geometria e otimização
de problemas;
3. Cálculo Numérico (computacional) – Fase 4
– Quantificação de Erros, solução de sistemas lineares e não
lineares, interpolação, ajuste de curvas e integração
numérica.
MTMD – Pra que?
• Aritmética Básica em Computadores;
• Programação, principalmente a lógica;
• Estruturas de Dados;
• Grafos;
• Inteligência Artificial;
• Teoria da Computação;
• Cálculo Numérico;
• Computação Gráfica;
• Modelagem e Simulação;
• Estatística e Probabilidade;
• Fundamentos de Banco de Dados;
ENGENHEIROS E ADVOGADOS
Introdução à Matemática Discreta
Problema
• Cenário hipotético:
– Em uma empresa sitiada pela Polícia Federal, estão sendo
investigadas irregularidades jurídicas. Todas as informações da
empresa foram destruídas, uma queima de arquivos.
– Nesta empresa há N funcionários investigados, sendo:
• N um número ímpar;
• No mínimo
𝑁
2
são da classe de engenheiros;
• No máximo
𝑁
2
são da classe de advogados;
– A dificuldade está em identificar, dentre os funcionários, quais são
engenheiros e quais seriam advogados. A PF sabe que:
• Cada funcionário sabe qual é a classe de todos os outros;
• Os engenheiros não mentem, pois estão isentos de culpa;
• Os advogados podem faltar com a verdade, para tentarem
escapar, pois são muito inteligentes e estão conspirando para
confundir os investigadores;
• Problema: Formule um roteiro de interrogação para o agente da PF que,
realizando perguntas para um funcionário i de qual classe é outro
funcionário j, aponte ao menos um engenheiro.
Problema v2.0
• Agora, iremos adicionar uma nova restrição ao problema:
– O agente poderá fazer no máximo (N – 1) perguntas para encontrar
o engenheiro.
• Como fica a solução deste problema?
MTMD e o Problema
• O grupo N é um Conjunto;
• Os advogados e os engenheiros são Subconjuntos;
• As perguntas são feitas de forma Combinatória;
• As respostas são relacionadas através de Lógica Formal;
• Resultados são calculados com base em Somas e números;
• Para saber se o algoritmo está certo, temos que Provar;
Conclusão
• Para resolver um simples exemplo, foi necessário o
emprego empírico de diversos tipos de
conhecimentos:
– Até agora, aprendemos tudo isto de diversas formas
separadas: escola, dia-a-dia, em atividades cotidianas, entre
outros.
• A formalização e o aprofundamento no uso destes
conhecimentos trarão diversos benefícios ao
profissional da Ciência da Computação.