BCM0505-15 - Processamento da Informação
Aula 05 – 06/03
Norma e Produto Interno
Problema 5.1: Dados dois vetores (listas) $x=[x_0,x_1,\ldots,x_{n-1}]$ e $y=[y_0,y_1,\ldots,y_{n-1}]$ em $\mathbb{R}^n$, determine o produto interno $$\langle x,y\rangle := \sum_{i=0}^n x_i y_i.$$
# recebe : x,y em R^n
# devolve: produto interno <x,y>
def inner_product (x: [float], y: [float]) -> float:
s = 0.0
for i in range (len (x)):
s += x[i] * y[i]
return s
Uma versão, utilizando sum()
.
# recebe : x,y em R^n
# devolve: produto interno <x,y>
def inner_product_s (x: [float], y: [float]) -> float:
return sum (x[i]*y[i] for i in range (len (x)))
E outra com sum()
e zip()
.
# recebe : x,y em R^n
# devolve: produto interno <x,y>
def inner_product_z (x: [float], y: [float]) -> float:
return sum (xi*yi for xi, yi in zip (x, y))
Nota: a função zip()
recebe iteráveis (list
, set
, string
, etc.), intercala-os e devolve um iterável que permite percorrer os iteráveis originais em paralelo. No caso dos iteráveis fornecidos serem listas
$$A_0=[a_{0,0},a_{0,1},\ldots,a_{0,n-1}],~A_1=[a_{1,0},a_{1,1},\ldots,a_{1,n-1}],~\ldots,~A_k=[a_{k,0},a_{k,1},\ldots,a_{k,n-1}],$$
o iterável devolvido é uma representação implícita da lista
$$zA = [a_{0,0},a_{1,0},\ldots,a_{k,0},a_{0,1},a_{1,1},\ldots,a_{k,1},\ldots a_{0,n-1},a_{1,n-1},\ldots,a_{k,n-1}].$$
O laço
for i0, i1, ..., ik in zip (A0, A1, ..., Ak): # as elipses devem ser substituídas corretamente por variáveis e listas
<código que usa i0, i1, ..., ik>
equivale a
for i in range (len (A0)):
i0, i1, ..., ik = A0[i], A1[i], ..., Ak[i] # o mesmo aqui
<código que usa i0, i1, ..., ik>
A norma euclidiana (ou norma $\ell_2$) de um vetor $x=[x_0,x_1,\ldots,x_{n-1}]\in\mathbb{R}^n$ é dada por $$\|x\| = \|x\|_2 := (\langle x,x\rangle)^{1/2}$$ e corresponde comprimento de $x$. Claramente, $\|x\|\geq 0$ para todo $x$, com igualdade se e somente se $x=0$.
Problema 5.2: Dado $x\in\mathbb{R}^n$, determine $\|x\|_2$.
import math
# recebe : x em R^n
# devolve: norma euclidiana ||x||_2
def norm_2 (x: [float]) -> float:
return math.sqrt (inner_product (x, x))
Dois vetores $x$ e $y$ são ortogonais se $\langle x,y\rangle = 0$. Isto sugere que produtos internos podem ser usados para medir o ângulo $\theta$ entre $x$ e $y$. De fato, temos que $$\theta(x,y) = \mathsf{arccos} \left(\frac{\langle x,y\rangle}{\|x\|\cdot\|y\|}\right).$$
Problema 5.3: Dados $x,y\in\mathbb{R}^n$, determine $\theta(x,y)$.
# recebe : x,y em R^n
# devolve: angulo \theta formado por x e y
def angle (x: [float], y: [float]) -> float:
return math.arccos (inner_product (x, y)/(norm_2 (x) * norm_2 (y)))
A norma $\|\cdot\|_2$ induz uma distância entre pontos em $\mathbb{R}^n$. Especificamente, para $x,y\in\mathbb{R}^n$, $$\mathsf{dist}(x,y) := \|x-y\|_2.$$
Problema 5.4: Dados $x,y\in\mathbb{R}^n$, determine $\mathsf{dist}(x,y)$.
# recebe : x,y em R^n
# devolve: distância entre x e y
def distance (x: [float], y: [float]) -> float:
return norm_2 ([(xi-yi)*(xi-yi) for xi, yi in zip (x, y)])
Nota: Python disponibiliza a função math.dist()
para cálculo de distâncias.
Mínimos e Máximos
Problema 5.5: Dado uma lista $A=[0\,..n-1]$ de inteiros, determine um elemento mínimo em $A$.
Se $A$ é vazia, o valor correto a ser devolvido é $\infty$.
from math import inf as oo
# recebe : uma lista A = [0..n-1] de inteiros
# devolve: um elemento mínimo em A ou oo caso A == []
def minimum (A: [int]) -> int:
x = oo
for y in A:
if x > y: x = y
return x
Nota: Python disponibiliza a função mim()
que equivale à função acima.
Problema 5.6: Dado uma lista $A$ de inteiros, determine um índice $j$ tal que $A[j]$ é um mínimo em $A$. Se $A$ é vazia, devolva $0$.
# recebe : uma lista A de inteiros
# devolve: um índice j tal que A[j] é um mínimo em A ou 0 caso A == []
def minimum (A: [int]) -> int:
j = 0
for i in range (1, len (A)):
if A[j] > A[i]: j = i
return j
Uma versão utilizando enumerate()
.
# recebe : uma lista A de inteiros
# devolve: um índice j tal que A[j] é um mínimo em A ou 0 caso A == []
def minimum_with_enumerate (A: [int]) -> int:
j, aj = 0, oo
for i, ai in enumerate (A):
if aj > ai: j = i
return j
Nota: Para uma lista $A=[a_0,a_1,\ldots,a_{n-1}]$, enumerate (A)
equivale a zip (I, A)
, em que $I=[0,1,\ldots,n-1]$.
Problema 5.7: Dado uma lista $A=[0\,..n-1]$ de inteiros, determine um índice $j$ tal que $A[j]$ é um segundo menor elemento em $A$. Se $n < 2$, devolva $-1$.
# recebe : uma lista A = [0..n-1] de inteiros
# devolve: um índice k tal que A[j] é um segundo mínimo em A ou -1 caso len(A) < 2
def second_minimum (A: [int]) -> int:
if len (A) < 2: return -1
j, k = 0, 1 if A[0] < A[1] else 1, 0
for i in range (2, len (A)):
if A[j] >= A[i]:
j, k = i, j
return j
Uma versão utilizando enumerate()
.
# recebe : uma lista A = [0..n-1] de inteiros
# devolve: um índice j tal que A[j] é um segundo mínimo em A ou -1 caso len(A) < 2
def second_minimum_with_enumerate (A: [int]) -> int:
j = k = -1
aj = ak = oo
for i, ai in enumerate (A):
if aj >= ai:
j, k = i, j
aj, ak = ai, aj
return j if k != -1 else -1
Média e Desvio Padrão
Problema 5.8: Dado uma lista $A$ de reais, determine a média (simples) dos elementos em $A$.
# recebe : uma lista A de reais
# devolve: a média (simples) dos elementos em A
def average (A: [float]) -> float:
n, s = len (A), 0.0
for i in range (n):
s += A[i]
return math.nan if n == 0 else s/n
Uma versão com sum()
.
# recebe : uma lista A de reais
# devolve: a média (simples) dos elementos em A
def average_with_sum (A: [float]) -> float:
return math.nan if len(A) == 0 else sum(A)/len(A)
Problema 5.9: Dadas uma lista $A[0\,..n-1]$ de reais e uma lista $W[0\,..n-1]$ de pesos entre $0$ e $1$ tal que $\sum_{i=0}^{n-1} W[i]=1$, determine a média ponderada dos elementos em $A$: $$\sum_{i=0}^{n-1} W[i]\cdot A[i].$$
# recebe : uma lista A de reais e uma lista W de pesos entre 0 e 1 tal que `sum (W) == 1`
# devolve: a média ponderada (de acordo com W) dos elementos em A
def weighted_average (A: [float], W: [float]) -> float:
s = 0.0
for i in range (len (A)):
s += W[i] * A[i]
return s
Versão com sum()
e zip()
.
# recebe : uma lista A de reais e uma lista W de pesos entre 0 e 1 tal que `sum (W) == 1`
# devolve: a média ponderada (de acordo com W) dos elementos em A
def weighted_average_with_zip (A: [float], W: [float]) -> float:
return sum (wi*ai for ai, wi in zip (A, W))
Problema 5.10: Dadas uma lista $A[0\,..n-1]$ de reais e uma lista $W[0\,..n-1]$ de pesos entre $0$ e $1$ tal que $\sum_{i=0}^{n-1} W[i]=1$, determine o desvio padrão de $A$ com relação a $W$: $$\sigma = \left(\sum_{i=0}^{n-1} W[i]\cdot A[i]^2 - \left(\sum_{i=0}^{n-1} W[i]\cdot A[i]\right)^2\right)^{1/2}.$$
# recebe : uma lista A de reais e uma lista W de pesos entre 0 e 1 tal que `sum (W) == 1`
# devolve: o desvio padrão dos elementos em A de acordo com W
def std_deviation (A: [float], W: [float]) -> float:
a = b = 0.0
for i in range (len (A)):
b += W[i] * A[i]
a += b * A[i]
return math.sqrt (a - b*b)
Versão com sum()
e zip()
.
# recebe : uma lista A de reais e uma lista W de pesos entre 0 e 1 tal que `sum (W) == 1`
# devolve: o desvio padrão dos elementos em A de acordo com W
def std_deviation_sumzip (A: [float], W: [float]) -> float:
a = sum (wi*ai*ai for ai, wi in zip (A, W))
b = sum (wi*ai for ai, wi in zip (A, W))
return math.sqrt (a - b*b)