e-Aula02

Prévia do material em texto

Matemática
Computacional
Profº. Luis GONZAGA de Paulo
2
34
Matemática Computacional
Revisão do conteúdo:
• Aula 03 – Erros, Conjuntos, Vetores e 
Matrizes
• Aula 04 – Grafos, Árvores Binárias e 
Máquinas de Estado
... e as questões encaminhadas para a 
Tutoria por meio do UNIVIRTUS
3
34
Modelagem matemática
Levantamento 
de dados
Construção do 
modelo 
matemático
Escolha do 
método 
adequado
Implementação 
computacional
Análise dos 
resultados 
obtidos
E se 
falhar?
Programas 
prontos...
4
34
Erros
Computadores podem apresentar 
cálculos com resultados incorretos?
– Podem. E isto é até mais comum do 
que acreditamos.
– Dos processos que compõem a 
modelagem matemática, a 
implementação computacional é a 
mais exposta a erros.
Cálculo de PI
5
34
Erros
Todos os cálculos computacionais são 
absolutamente confiáveis?
– Não, pois não existe verdade absoluta 
ou resposta definitiva na ciência em 
geral;
– Na matemática existem respostas ou 
soluções que fogem à nossa 
capacidade de validação;
– Bjørn Lomborg, “o ambientalista 
cético”: o perigo da matemática como 
religião.
6
34
Erros
Podemos validar os resultados obtidos? 
– Sim, isto é o objetivo da Análise 
Numérica.
– Na maioria das vezes usando os 
computadores também...
7
34
Erros
Podemos evitar, identificar ou corrigir 
os erros?
– Sim, principalmente por meio de 
métodos confiáveis;
– Usando métodos de resolução com 
menor número de operações 
aritméticas envolvidas;
8
34
Erros
– Escolhendo algoritmos com o menor 
número de recursividade;
– Escolhendo, para implementar o 
algoritmo, uma linguagem e um 
compilador que represente as 
variáveis envolvidas com precisão 
suficiente;
9
34
Exercício: 
Considerando F(10, 2, -5, 5):
Calcular 4,32 + 0,064
0,43.101 + 0,64.10-1 �
0,43 x101
+ 0,0064 x101
= 0,4364 x101
�0,44.101
Ou seja, 4,4 ao invés de 4,384!
10
34
Exercício: 
Considerando F(10, 2, -5, 5):
Calcular 372 - 371
0,37.103 - 0,37.103 �
0,37 x103
- 0,37 x103
= 0,00 x103
�0,00.100
Ou seja, 0 ao invés de 1!
11
34
Exercício: 
Considerando F(10, 2, -5, 5):
Calcular 691 + 2,71
0,69.103 - 0,27.101 �
0,69 x103
+ 0,0027 x103
= 0,6927 x103
�0,69.103
Ou seja, 690 ao invés de 693,71!
12
34
Exercício: 
Considerando F(10, 2, -5, 5):
Calcular 1234 x 0,016
0,12.104 - 0,16.10-1 �
0,12 x104
x 0,16 x10-1
= 0,0192 x103
�0,19.102
Ou seja, 19 ao invés de 19,744!
13
34
Exercício: 
Considerando F(10, 2, -5, 5):
Calcular 875 x 3172
0,88.103 x 0,32.104 �
0,88 x103
x 0,32 x104
= 0,2816 x107
�Overflow!
Ou seja, número maior que a 
capacidade de representação.
14
34
Exercício: 
Considerando F(10, 2, -5, 5):
Calcular 0,0064 / 7312
0,64.10-2 / 0,73.104 �
0,64 x10-2
÷ 0,73 x104
= 0,8767 x10-6
�Underflow!
Ou seja, número menor que a 
mínima capacidade de representação.
15
34
Exercício: 
Considerando F(10, 6, -99, 99):
Representar o valor 
�
�
0,333333333333333333...100 �
0,333333.100
Ou seja, perde-se uma parcela 
significativa devido à limitação da
representação.
16
34
Exercício: 
Considerando F(2,10,-15,+15): dízima
Representar 
�
��
(10) periódica
≅(0,1100110011)2.2-3
Ou seja, devido à limitação da
representação, não é possível 
representar o valor correto.
17
34
Norma IEEE 754
Propriedade
Precisão
Simples Dupla Estendida
Total de bits 32 64 80
Bits na mantissa 23 52 64
Bits no expoente 8 11 15
Base 2 2 2
Exp. Máximo 127 1023 16383
Exp. Mínimo -126 -1022 -16382
Maior nº ≅ 3,40x1038 ≅ 1,80x10308 ≅ 1,19x104932
Menor nº ≅ 1,18x1038 ≅ 2,23x10-308 ≅ 3,36x104932
Decimais 7 16 20
18
34
Épsilon da máquina
• É o menor número que, somado a 1, 
resulta em um número diferente de 
1 (não é arredondado);
• Representa a precisão aritmética 
relativa da máquina;
• Consequência da precisão finita da 
aritmética de ponto flutuante.
19
34
Épsilon da máquina
Algoritmo em pseudocódigo:
eps = 1
Enquanto (eps + 1) >1
eps = eps / 2
Fim
eps = eps * 2
20
34
•Cancelamento catastrófico é o 
nome que se dá ao efeito que ocorre 
quando se atinge o ε da máquina;
• Resulta em um aumento expressivo 
e abrupto do erro relativo.
21
34
Grafos
• Estrutura matemática gráfica;
• Relações entre os objetos ou 
elementos de um determinado 
conjunto
• Equação G(V,A):
• Os vértices - V, ou objetos;
• As arestas - A, ligações, dependências ou 
caminhos entre os vértices;
22
34
Grafos
• Exemplo:
23
34
Exercício: construção de uma casa.
Atividade Premissa Duração
1. Preparar o terreno Nenhuma 4 dias
2. Construir a fundação 1 3 dias
3. Erguer as paredes 2 7 dias
4. Colocar o telhado 3 6 dias
5. Rebocar as paredes 3 4 dias
6. Elétrica & Hidráulica 4, 5 6 dias
7. Assentar caixilhos 3 5 dias
8. Instalar portas e janelas 7 5 dias
9. Pintar paredes 4, 6, 8 5 dias
10. Entrega 9 0 dias
• Quanto tempo demora?
• Quais são os passos mais críticos?
24
34
1 2
4
3
3
5
4
7
7
6
8
5
9
4 6
10
5
Quanto tempo demora?
• A = {1, 2, 3, 4, 9, 10} = 4+3+7+6+5 = 25 dias
• B = {1, 2, 3, 4, 6, 9, 10} = 4+3+7+6+6+5 = 31 dias
• C = {1, 2, 3, 5, 6, 9, 10} = 4+3+7+4+6+5 = 29 dias
• D = {1, 2, 3, 7, 8, 9, 10} = 4+3+7+5+5+5 = 29 dias
Caminho crítico:
• B = {1, 2, 3, 4, 6, 9, 10} = 4+3+7+6+6+5 = 31 dias
Solução: Grafo!
25
34
• Conjunto finito de elementos – arestas
(T) e vértices, tal que:
• Se T = 0, a árvore é dita vazia;
• Existe um nó especial r, chamado raiz de
T;
• Os restantes podem ser divididos em
dois subconjuntos disjuntos: TrE e TrD;
• TrE e TrD formam a sub-árvore à
esquerda e à direita de r,
respectivamente, e são também árvores
binárias.
Árvores Binárias
26
34
• A raiz da sub-árvore esquerda (direita)
de um nó v, é denominada filho
esquerdo (direito) de v, e pode existir
sem o direito e vice-versa;
• Se r é a raiz de T, TrE e TrD são as sub-
árvores esquerda e direita de T,
respectivamente;
• Uma árvore binária pode ter duas sub-
árvores vazias (a esquerda e a direita);
• Toda árvore binária com n nós possui
exatamente n + 1 sub-árvores vazias
entre suas sub-árvores esquerdas e
direitas.
Árvores Binárias
27
34
•Uma árvore binária é uma árvore
cujos nós têm 0, 1 ou 2 filhos;
• Cada filho é designado como filho à
esquerda ou filho à direita (Grau 2);
•O número de nós (folhas) é uma
importante característica das árvores
binárias para mensurar a eficiência
esperada de algoritmos.
Árvores Binárias
28
34
Caminhos em Árvores Binárias
• Em profundidade (altura): os nós da
sub-árvore atual têm prioridade na
ordem de acesso;
• Em amplitude (largura): os nós de
menor nível têm prioridade na
ordem de acesso.
29
34
Caminhos em Árvores Binárias
• Em profundidade - três tipos
“canônicos”:
• Pré-ordem
• Pós-ordem
• Em-ordem
• Em amplitude:
• Em nível
30
34
Caminho em Pré-ordem
• Visitar a raiz
• Percorrer a sub-árvore esquerda em pré-ordem
• Percorrer a sub-árvore direita em pré-ordem
Percurso: 4, 2, 1, 3, 6, 5, 7
44
22 66
3311 7755
31
34
Caminho em Pós-ordem
• Percorrer a sub-árvore esquerda em pós-ordem
• Percorrer a sub-árvore direita em pós-ordem
• Visitar a raiz
Percurso: 1, 3, 2, 5, 7, 6, 4
44
22 66
3311 7755
32
34
Caminho Em-ordem
• Percorrer a sub-árvore esquerda em pré-
ordem
• Visitar a raiz
• Percorrer a sub-árvore direita em pré-ordem
Percurso:1, 2, 3, 4, 5, 6, 7
44
22 66
3311 7755
33
34
Caminho Em Nível
• Percorre-se a árvore em nível de cima 
para baixo e da esquerda para a direita.
Percurso: 4, 2, 6, 1, 3, 5, 7
44
22 66
3311 7755
34
34
Estrutura de dados
44
22 66
3311 7755
4
2 6
1 3 5 7
null
Referência à sub-árvore da esquerda ou null
quando não há filhos
Referência à sub-árvore da direita ou 
null quando não há filhos
Chave
Muitas implementações
referenciam o pai no nó
Muitas implementações
referenciam o pai no nó