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)
Avatar
Aritanan Gruber
Assistant Professor

“See, if y’all haven’t the same feeling for this, I really don’t give a damn. If you ain’t feeling it, then dammit this ain’t for you!"
(desconheço a autoria; agradeço a indicação)