View
161
Download
17
Category
Preview:
Citation preview
INE5381 - Fundamentos Matemáticos INE5381 - Fundamentos Matemáticos da Computaçãoda Computação
Parte I - Elementos básicos:Parte I - Elementos básicos:
1. Lógica Matemática1. Lógica Matemática 2. Conjuntos e subconjuntos2. Conjuntos e subconjuntos - Operações sobre conjuntos- Operações sobre conjuntos 3. Indução e recursão3. Indução e recursão 4. Números inteiros4. Números inteiros - Divisão nos inteiros, inteiros módulo n- Divisão nos inteiros, inteiros módulo n 5. Matrizes5. Matrizes 6. Seqüêncas e somas6. Seqüêncas e somas
MatrizesMatrizes
• Matrizes são usadas para representar Matrizes são usadas para representar relações entre relações entre elementoselementos de conjuntos. de conjuntos.
• Exemplo: redes de comunicaçõesExemplo: redes de comunicações
• DefiniçãoDefinição: uma matriz é uma : uma matriz é uma tabela numéricatabela numérica arranjada em arranjada em um número m de linhas e um número n de colunas.um número m de linhas e um número n de colunas.
mn2m1m
n22221
n11211
a...aa
::::
a...aa
a...aa
A
MatrizesMatrizes
• A i-ésima linha de A é:A i-ésima linha de A é:
miaaa inii 121
• A j-ésima coluna de A é:A j-ésima coluna de A é:
nj
a
a
a
mj
j
j
12
1
Matrizes – Notações e terminologiaMatrizes – Notações e terminologia
AAmxnmxn: matriz A com m linhas e n colunas: matriz A com m linhas e n colunas
AAnxnnxn: matriz : matriz quadradaquadrada de tamanho n de tamanho n
: diagonal principal de A: diagonal principal de A
aaijij: : elementoelemento da i-ésima linha e da j-ésima coluna da matriz A da i-ésima linha e da j-ésima coluna da matriz A
[a[aijij]: denota uma ]: denota uma matrizmatriz A onde a dimensão está definida A onde a dimensão está definida
nnaaa 2211
MatrizesMatrizes
DefiniçãoDefinição: Uma matriz : Uma matriz quadradaquadrada A=[a A=[aijij] em que todos ] em que todos elementos fora da diagonal são iguais a zero, isto é, elementos fora da diagonal são iguais a zero, isto é, aaijij=0 para i=0 para ij, é chamada de j, é chamada de matriz diagonalmatriz diagonal. .
30
04F
ExemplosExemplos::
500
030
002
G
MatrizesMatrizes
DefiniçãoDefinição: Duas matrizes mxn A=[a: Duas matrizes mxn A=[aijij] e B=[b] e B=[bijij] são ditas ] são ditas iguaisiguais se a se aijij=b=bijij para 1 para 1iim e 1m e 1jjn.n.
644
250
132
A
ExemploExemplo::
• A=B se e somente se x=-3, y=0, e z=6.A=B se e somente se x=-3, y=0, e z=6.
z
y
x
B
44
25
12
Aritmética de matrizesAritmética de matrizes
Def.Def.: Se A=[a: Se A=[aijij] e B=[b] e B=[bijij] são duas matrizes mxn, ] são duas matrizes mxn, então a então a soma de A e Bsoma de A e B é a matriz C=[c é a matriz C=[cijij], de ], de ordem mxn, definida por:ordem mxn, definida por:
205
143A
ExemploExemplo::
ccijij = a = aijij + b + bijij (1 (1iim , 1m , 1jjn)n)
230
354B
035
297
22)3(005
315443BAC
Aritmética de matrizesAritmética de matrizes
DefiniçãoDefinição: Uma matriz cujos elementos são todos : Uma matriz cujos elementos são todos nulos é chamada de nulos é chamada de matriz nulamatriz nula e é denotada por e é denotada por 00..
000
00032O
ExemplosExemplos::
000
000
000
33O
Propriedades da soma de matrizesPropriedades da soma de matrizes
TeoremaTeorema::
a) A + B = B + Aa) A + B = B + A
b) (A + B) + C = A+ (B + C)b) (A + B) + C = A+ (B + C)
c) A + c) A + 00 = = 00 + A = A + A = A
mn2m1m
ij
n22221
n11211
pnpj2p1p
n2j22221
n1j11211
mp2m1m
ip2i1i
p22221
p11211
ccc
c
ccc
ccc
bbbb
bbbb
bbbb
aaa
aaa
aaa
aaa
Aritmética de matrizesAritmética de matrizes
Def.Def.: Se A=[a: Se A=[aijij] é uma matriz mxp e B=[b] é uma matriz mxp e B=[bijij] é uma matriz ] é uma matriz pxn, então o pxn, então o produtoproduto de A e B (AxB) é a matriz C=[c de A e B (AxB) é a matriz C=[cijij], de ], de ordem mxn, definida por: ordem mxn, definida por:
p
kkjikpjipjijiij babababac
12211 njmi 1,1
Produto de matrizesProduto de matrizes
321
432A 32
35
22
13
B 23
??
??C 22
ExemploExemplo::
332211532231
342312542332C
414
2020C
Propriedades do produto de matrizesPropriedades do produto de matrizes
• As propriedades básicas do produto de matrizes As propriedades básicas do produto de matrizes são dadas pelo seguinte teorema:são dadas pelo seguinte teorema:
• TeoremaTeorema::
a) A(BC) = (AB)Ca) A(BC) = (AB)C
b) A(B + C) = AB + ACb) A(B + C) = AB + AC
c) (A + B)C = AC + BCc) (A + B)C = AC + BC
• Note que, dadas duas matrizes ANote que, dadas duas matrizes Amxpmxp e B e Bpxnpxn, então A.B , então A.B pode ser calculada (mxn). Quanto a B.A pode ocorrer:pode ser calculada (mxn). Quanto a B.A pode ocorrer:
1. o produto B.A pode não ser definido1. o produto B.A pode não ser definido2. (m=n) e B.A é definida 2. (m=n) e B.A é definida mas A.B mas A.B B.A (tamanho) B.A (tamanho)
3. A.B e B.A podem ter o mesmo tamanho mas A.B 3. A.B e B.A podem ter o mesmo tamanho mas A.B B.A B.A
4. A.B = B.A4. A.B = B.A
Propriedades do produto de matrizesPropriedades do produto de matrizes
ExemplosExemplos: :
23
12A 22
32
11B 22
321
432A 32
5243
2851
2914
B 43
21
12A 22
51
15B 22
Multiplicação de matrizesMultiplicação de matrizes
QuestãoQuestão: quantas operações são necessárias para : quantas operações são necessárias para calcular o produto Ccalcular o produto Cmxnmxn de duas matrizes A de duas matrizes Amxpmxp e B e Bpxnpxn??
Resp.Resp.:: - Há mxn elementos no produto de A- Há mxn elementos no produto de Amxpmxp e B e Bpxnpxn
QuestãoQuestão: Em que ordem as matrizes A: Em que ordem as matrizes A11(30x20), A(30x20), A22(20x40) (20x40) e Ae A33(40x10) devem ser multiplicadas (matrizes de (40x10) devem ser multiplicadas (matrizes de inteiros) para usar o menor ninteiros) para usar o menor noo possível de operações? possível de operações?
• AA11(A(A22AA33) ) 20.40.10 para obter a matriz 20x10 A 20.40.10 para obter a matriz 20x10 A22AA33 + 30.20.10 para multiplicar por A+ 30.20.10 para multiplicar por A11 = 14000 = 14000
- Para encontrar cada elemento são necessárias p (x) e p (+)- Para encontrar cada elemento são necessárias p (x) e p (+)
- Logo, um total de m.n.p (x) e m.n.p (+) são usadas.- Logo, um total de m.n.p (x) e m.n.p (+) são usadas.
• (A(A11AA22)) AA33 30.20.40 + 30.40.10 = 36000 (!) 30.20.40 + 30.40.10 = 36000 (!)
Matriz identidadeMatriz identidade
• DefiniçãoDefinição: a matriz diagonal n: a matriz diagonal nn na qual todos os n na qual todos os elementos da diagonal são 1’s é chamado de elementos da diagonal são 1’s é chamado de matriz matriz identidadeidentidade de ordem n e é denotada por de ordem n e é denotada por IInn..
• NotaNota: se A é uma matriz m: se A é uma matriz mn, vale:n, vale:
IImm.A = A..A = A.IInn = A = A
1...000
:::::
0...100
0...010
0...001
I
Potências de matrizesPotências de matrizes
• Pode-se definir Pode-se definir potênciaspotências de matrizes quadradas. de matrizes quadradas.
• Se A é uma matriz quadrada nxn, temos:Se A é uma matriz quadrada nxn, temos:
AApp = A.A...A = A.A...A
p vezesp vezes
onde: Aonde: A00 = I = Inn
• Também se pode provar as leis de Também se pode provar as leis de exponenciaçãoexponenciação::
AAppAAqq = A = Ap+qp+q
(A(App))qq = A = Ap.qp.q
Matrizes transpostasMatrizes transpostas
DefiniçãoDefinição: Se A é uma matriz mxn, então a matriz : Se A é uma matriz mxn, então a matriz nxm:nxm:
tijt aA onde:onde:
é chamada de é chamada de transpostatransposta da matriz A. da matriz A.
ExemplosExemplos::
jitij aa nj1emi1
261
012
543
A
205
614
123
A t
0
3
1
B 031Bt
Propriedades de matrizes transpostasPropriedades de matrizes transpostas
TeoremaTeorema: Se A e B são matrizes, então:: Se A e B são matrizes, então:
ExemploExemplo::
a) (Aa) (Att))tt = A = A
b) (A+B)b) (A+B)tt = A = Att + B + Btt
c) (A.B)c) (A.B)tt = B = Btt.A.Att
DefiniçãoDefinição: Uma matriz A=[a: Uma matriz A=[aijij] é chamada simétrica se A] é chamada simétrica se Att=A=A
• se A é simétrica, A se A é simétrica, A deve serdeve ser uma matriz uma matriz quadrada.quadrada.
205
014
543
A
Matrizes booleanasMatrizes booleanas
• Matrizes constituídas Matrizes constituídas apenas de zeros e 1’sapenas de zeros e 1’s são são frequentemente utilizadas para representar frequentemente utilizadas para representar estruturas discretas (como as relações - parte II).estruturas discretas (como as relações - parte II).
DefiniçãoDefinição: Uma : Uma matriz booleanamatriz booleana é uma matriz mxn é uma matriz mxn em que os elementos são zeros ou uns.em que os elementos são zeros ou uns.
ExemploExemplo::
00100
10101
00110
B
Operações com matrizes booleanasOperações com matrizes booleanas
Def.Def.: sejam A=[a: sejam A=[aijij] e B=[b] e B=[bijij] duas matrizes booleanas,] duas matrizes booleanas,
0be0ase0
1bou1ase1c
ijij
ijijij
1) A1) AB=C=[cB=C=[cijij] é a ] é a junçãojunção de A e B, dada por: de A e B, dada por:
2) A2) AB=D=[dB=D=[dijij] é o ] é o encontroencontro de A e B, dado por: de A e B, dado por:
Note que A e B Note que A e B devem ter o devem ter o mesmo tamanhomesmo tamanho
0bou0ase0
1be1ase1d
ijij
ijijij
Operações com matrizes booleanasOperações com matrizes booleanas
ExemploExemplo: Calcule a junção e o encontro de:: Calcule a junção e o encontro de:
010
101A
SoluçãoSolução::
011
010B
011
111
001110
011001BA
010
000
001110
011001BA
Operações com matrizes booleanasOperações com matrizes booleanas
Def.Def.: Sejam as matrizes booleanas A=[a: Sejam as matrizes booleanas A=[a ijij] (mxp) e B=[b] (mxp) e B=[bijij] ] (pxn). O (pxn). O produto booleanoproduto booleano de A e B é a matriz C mxn cujos de A e B é a matriz C mxn cujos elementos são dados por:elementos são dados por:
ccijij = (a = (ai1i1bb1j1j) ) (a (ai2i2bb2j2j) ) ... ... (a(aipipbbpjpj))
• Denota-se este produto por ADenota-se este produto por ABB
• Note que esta operação é idêntica à multiplicação Note que esta operação é idêntica à multiplicação matricial ordinária em que:matricial ordinária em que:
- a adição é substituída por - a adição é substituída por
- a multiplicação é substituída por - a multiplicação é substituída por
Produto booleanoProduto booleano
ExemploExemplo: Encontre o produto booleano de A e B, onde:: Encontre o produto booleano de A e B, onde:
01
10
01
A
Note que #-Note que #-colunas de A deve colunas de A deve ser = ser = #-linhas de B#-linhas de B
110
011B
100110110011
110011100110
100110110011
BA
011
110
011
000101
101000
000101
BA
Operações com matrizes booleanasOperações com matrizes booleanas
TeoremaTeorema: Se A, B e C são matrizes booleanas, então:: Se A, B e C são matrizes booleanas, então:
1)1) a) A a) A B = B B = B A Ab) A b) A B = B B = B A A
2)2) a) (A a) (A B) B) C = A C = A (B (B C) C) b) (A b) (A B) B) C = A C = A (B (B C) C)
3)3) a) A a) A (B (B C) = (A C) = (A B) B) (A (A C) C) b) A b) A (B (B C) = (A C) = (A B) B) (A (A C) C)
4)4) A A (B (B C) = (A C) = (A B) B) C C
Recommended