BCM0505-15 - Processamento da Informação

Feb 10, 2020

Laboratório 01 – 11/02

Toda programação será feita em Python 3 (a versão 2 foi oficialmente descontinuada em 01/01/2020). Vamos utilizar o site repl.it que mantém os pacotes atualizados, pode ser acessado à partir de qualquer dispositivo com acesso http à www e oferece 100 MB de espaço gratuito para armazenar seus códigos.

Crie sua conta no repl.it e interaja com o ambiente: o editor de código (à esquerda) e o interpretador (à direita).

Exercícios

(01) Dada uma temperatura em Celsius, determine sua equivalente em Fahrenheit.

Explicação e solução:
Sabemos que os pontos de liquefação da água são $0^\circ\mathrm{C}$ (Celsius) e $32^\circ\mathrm{F}$ (Fahrenheit) e que a ebulição ocorre a $100^\circ\mathrm{C}$ e a $212^\circ\mathrm{F}$. Denotando as temperaturas em Celsius e Fahrenheit por $c$ e $f$, respectivamente, obtemos a relação: $$f = \frac{9}{5}c + 32. \qquad\qquad (1)$$ Podemos utilizar o interpretador Python como calculadora, substituindo $c$ pelo valor desejado, por exemplo, $36.5$:
```
> 9/5 * 36.5 + 32
97.7
```
Se desejarmos fazer a avaliação uma única vez (i.é, para um único valor $c$), tal solução é adequada. Em caso contrário, é melhor criarmos um programa que lê um valor para $c$ e imprime o correspondente valor de $f$.
```
print ("Entre com uma temperatura c em Celsius: ")
c = float (input())
print ("Temperatura em Fahrenheit: f = ", 9/5 * c + 32)
```
O código acima, apesar de correto e funcional, apresenta baixa reusabilidade. Por exemplo, se quisermos construir uma tabela para os valores $10, 20, 30, 40$ de Celsius para Fahrenheit, devemos executar o código acima 4 vezes ou programar algo do tipo:
```
print (10, "C -> ", 9/5 * 10 + 32, "F")
print (20, "C -> ", 9/5 * 20 + 32, "F")
print (30, "C -> ", 9/5 * 30 + 32, "F")
print (40, "C -> ", 9/5 * 40 + 32, "F")
```
Observe que programamos a fórmula de conversão 4 vezes: algo tedioso e pior, sujeito a erros; imagine se em vez de 4, fossem 40 valores! Uma forma de contornar tal repetição manual consiste na utilização de mecanismos que permitem a expressão de repetições automáticas. Um deles é o laço for.
```
for c in range (10, 41, 10):
  print (c, "C -> ", 9/5 * c + 32, "F")
```
A execução do código acima produz como saída:
```
10 C ->  50.0 F
20 C ->  68.0 F
30 C ->  86.0 F
40 C ->  104.0 F
```
A função range (<inicio>, <final>, <passo>) gera uma progressão aritmética inteira (uma lista)

<inicio>, <inicio>+<passo>, <inicio>+2*<passo>, e assim sucessivamente, enquanto <inicio>+k*<passo> é menor que <final>,

para algum inteiro k. Note que este último valor, <inicio>+k*<passo>, não pertence à progressão.

O laço for <var> in <lista>: <comando> atribui, um a um, os valores da <lista> à variável <var> e executa o <comando> após cada atribuição. Nota: <comando> pode ser simples, como no código acima, ou uma sequência de declarações válidas de mesma indentação; mais sobre isso em breve.

O código envolvendo laço é, certamente, uma melhoria. Sua reusabilidade, no entanto, ainda é limitada: se desejarmos utilizar a conversão de temperaturas para outro fim, teremos de reprogramá-la. Apesar de simples (neste caso), é conveniente dispor de um mecanismo que isole a computação de $(1)$ e permita reutilizá-la em diferentes cenários. Isto é alcançado com o conceito de função.
```
def cels_to_fahr (c):
  return 9/5 * c + 32
```
A declaração def <fun> (<pars>): <comando> especifica uma função de nome <fun> que recebe uma lista de parâmetros <pars> e executa <comando> com os parâmetros disponíveis. No código acima, declaramos uma função chamada cels_to_fahr que recebe um parâmetro c, calcula 9/5 * c + 32 e devolve (return) o valor resultante à quem chamou a função.

Juntando os três exemplos iniciais:
```
def cels_to_fahr (c):
  return 9/5 * c + 32

print ("36.5 C = ", cels_to_fahr (36.5), "F")

c = float (input ("Entre com uma temperatura c em Celsius: "))
print ("Temperatura em Fahrenheit: f = ", cels_to_fahr (c))

for c in range (10, 41, 10):
  print (c, "C -> ", cels_to_fahr (c), "F")
```
Observe que a função cels_to_fahr pode ser utilizada quantas vezes for desejado. Mais do que isso, qualquer modificação que venha a ser necessária em seu código é feita uma única vez, em um único local — algo relativamente comum durante o desenvolvimento de funções mais complexas que a deste exercício.

Como nota final, esperamos que a função cels_to_fahr receba um valor ponto flutuante (float) e devolva outro. Apesar de Python ser uma linguagem de tipagem dinâmica — e fazer as conversões devidas entre tipos, quando necessário — é conveniente anotarmos os tipos que uma função recebe e devolve:
```
def cels_to_fahr (c: float) -> float:
  return 9/5 * c + 32
```
Tal prática aumenta a legibilidade do código, fornece informação extra ao interpretador e pode detectar erros em tempo de execução que, de outra forma, passariam despercebidos. $\qquad\square$
(02) Dada uma temperatura em Fahrenheit, determine sua equivalente em Celsius.
(Isto é, escreva uma função que recebe uma temperatura em Fahrenheit e devolva sua equivalente em Celsius.)
Solução:
```
def fahr_to_cels (f: float) -> float:
  return 5/9 * (f - 32)
```
$\square$
(03) Dadas uma temperatura $t$ em Fahrenheit e uma velocidade de vento $v$ em milhas por hora, o National Weather Service (serviço atmosférico americano) define a temperatura efetiva (sensação térmica) em Fahrenheit por: $$w = 35.74 + 0.6215t + (0.4275t - 35.75)v^{0.16}. \qquad\qquad (2)$$ Escreva uma função que recebe dois floats — uma temperatura $t$ em Celsius e uma velocidade $v$ em kilômetros por hora — e devolve a temperatura efetiva $w$ em Celsius. Escreva funções auxiliares se necessário.

Nota: a fórmula $(2)$ é válida somente para valores $t\leq 50$ e $3\leq v\leq 120$; você pode assumir que os parâmetros estarão sempre nestes intervalos.

Solução:
```
# em Fahrenheit e milhas por hora
def fmh_wind_chill (t: float, v: float) -> float:
  return 35.74 + 0.6215*t + (0.4275*t - 35.75) * v**0.16

# em Celsius e kilômetros por hora
def ckh_wind_chill (t: float, v: float) -> float:
  return fahr_to_cels (fmh_wind_chill (cels_to_fahr (t), v*0.621371))
```
Podemos fornecer agora um código para utilização da função pedida:
```
c = float (input ("Temperatura em Calsius: "))
v = float (input ("Velocidade do vento em Km/h: "))
print ("Sensação térmica (wind chill): ", ckh_wind_chill (c, v))
```
$\square$
(04) Escreva funções que:
- recebe floats $b$ e $h$ e devolve a área de um triângulo de base $b$ e altura $h$;
- recebe um float $r$ e devolve a área de um círculo de raio $r$; use import math e math.pi.
Solução:
```
import math

def area_triang (b: float, h: float) -> float:
  return b*h/2

def area_circ (r: float) -> float:
  return math.pi * r*r
```
$\square$
(05) Escreva uma função que recebe uma quantia inicial $p$, uma taxa de juros anual $r$ e um período (em anos) $t$ e devolve o montante que você teria se investisse $p$ reais a uma taxa $r$ continuamente por $t$ anos. A resposta é dada por: $pe^{rt}.$

Solução:
```
import math
def investment (p: float, r: float, t: int) -> float:
  return p*math.exp(r*t)
```
$\square$
(06) Escreva uma função que recebe três valores, $x$, $y$ e $z$, e devolve os valores mínimo e máximo de $\{x,y,z\}$.

Explicação e solução:
Python tem funções min() e max() para este propósito. Estas funções estão disponíveis por serem operações comuns, corriqueiras e de alto uso. Exatamente por isso, é útil saber como construí-las à partir dos princípios básicos da linguagem. Para tanto, precisamos de um mecanismo que permita uma tomada de decisão, isto é, a escolha de uma dentre múltiplas opções. Isto é feito via comando:

if <expr1>: <comando1> elif <expr2>: <comando2> elif <expr3>: <comando3> ... else: <comando>.

Nota: as partes envolvendo elifs e else são opcionais e devem ser usadas somente quando necessário.

Por exemplo, o código abaixo implementa a tricotomia numérica clássica, classificando um valor $x$ como negativo, neutro ou positivo.
```
x = float (input())
if x < 0:
  print ("negativo")
elif x > 0:
  print ("positivo")
else:
  print ("igual a zero")
```
Observe que um e somente um print é executado para cada valor de $x$. Note também a indentação dos prints.

Podemos construir uma função min_max como:
```
def min_max (x: float, y: float, z: float) -> (float, float):
  # primeiro, comparamos x e y
  if x <= y:
    v_min, v_max = x, y
  else:
    v_min, v_max = y, x
  # agora, tratamos de z
  if z <= v_min:
    v_min = z
  if z >= v_max:
    v_max = z    
  return v_min, v_max
```
Observe que min_max funciona corretamente inclusive no caso em que $x=y=z$. $\qquad\square$
(07) Dados floats $a$, $b$ e $c$, calcule as raízes reais (caso existam) do polinômio quadrático $P(x)=ax^2+bx+c$. Utilize a fórmula de Bháskara: $$x = \frac{-b\pm\sqrt{\Delta}}{2a} \qquad \textrm{em que} \qquad \Delta = b^2-4ac.$$ Lembre-se que:
- se $\Delta > 0$, $P(x)$ tem duas raízes reais distintas,
- se $\Delta = 0$, $P(x)$ tem uma raiz real dupla,
- se $\Delta < 0$, $P(x)$ não possui raízes reais.
Sua função deve tratar todos os casos. (O que deve ser devolvido?)

Solução:
Seguindo as boas práticas de programação, qualquer função deve devolver o mesmo número de parâmetros quando chamada. Uma solução é sempre devolver uma tripla $(n, x_1, x_2)$, em que $n$ é o número de raízes reais; caso $n=0$, $x_1$ e $x_2$ não representam valores úteis e devolvemos math.nan (not a number); caso $n=1$, devolvemos $x_1 = x_2 = -b/2a$; e caso $n=2$, devolvemos $x_1=(-b-\sqrt{\Delta})/2a$ e $x_2=(-b+\sqrt{\Delta})/2a$.
```
import math
def bhaskara (a: float, b: float, c: float) -> (int, float, float):
  delta = b*b - 4*a*c
  if delta < 0:
    return (0, math.nan, math.nan)
  elif delta == 0:
    z = -b/(2*a)
    return (1, z, z)
  else:
    return (2, (-b - math.sqrt(delta))/(2*a), (-b + math.sqrt(delta))/(2*a))
```
Podemos fornecer agora um código para utilização da função pedida:
```
a = float (input ("a = "))
b = float (input ("b = "))
c = float (input ("c = "))
n, x1, x2 = bhaskara (a, b, c)

if n == 0:
  print ("não tem raízes reais")  
elif n == 1:
  print ("raíz dupla: ", x1)
else:
  print ("raízes: ", x1, " e ", x2)
```
$\square$
(08) Escreva uma função que recebe cinco valores em $\{0,1\}$ e devolve verdadeiro (True) se o número de uns é maior que o de zeros, ou falso (False) em caso contrário.

Solução:
Observe que à medida em que o número de uns aumenta, o número de zeros diminui – pois ambos devem somar $5$. Logo,
```
def majority (a: int, b: int, c: int, d: int, e: int) -> bool:
  return a + b + c + d + e >= 3
```
$\square$

(09) Escreva uma função que recebe cinco valores em $\{$True,False$\}$ e devolve verdadeiro (True) se a quantidade de verdadeiros recebidos é ímpar, ou falso (False) em caso contrário.

Solução:
Sejam $a,b,c,d$ e $e$ os parâmetros da função parity. Como cada parâmetro pode receber True ou False, temos $32$ combinações distintas. Utilizando somente operadores lógicos, podemos testar cada uma das $16$ possibilidades válidas. Isso, no entanto, resulta em um código de difícil leitura e fácil de cometer erros durante sua confecção.

def parity_dnf (a: bool, b: bool, c: bool, d: bool, e: bool) -> bool:
  if ( (a and not b and not c and not d and not e) 
    or (not a and b and not c and not d and not e) 
    or (not a and not b and c and not d and not e) 
    or (not a and not b and not c and d and not e) 
    or (not a and not b and not c and not d and e) 
    or (a and b and c and not d and not e) 
    or (a and b and not c and d and not e) 
    or (a and b and not c and not d and e) 
    or (a and not b and c and d and not e) 
    or (a and not b and c and not d and e) 
    or (a and not b and not c and d and e) 
    or (not a and b and c and d and not e) 
    or (not a and b and c and not d and e) 
    or (not a and b and not c and d and e)
    or (not a and not b and c and d and e)
    or (a and b and c and d and e) ):
    return True
  else:
    return False

A linearidade inerente da fórmula DNF (disjunções de conjunções de variáreis ou de suas negações) implica que certas variáveis são avaliadas várias vezes no pior caso. Explorando a ausência de ciclos da fórmula, podemos reestruturar o código como uma árvore de decisão.

def parity_dtree (a: bool, b: bool, c: bool, d: bool, e: bool) -> bool:
  if a:
    if b:
      if c:
        if d:
          if e: return True
          else: return False
        else:
          if e: return False
          else: return True
      else:
        if d:
          if e: return False
          else: return True
        else:
          if e: return True
          else: return False
    else:
      if c:
        if d:
          if e: return False
          else: return True
        else:
          if e: return True
          else: return False
      else:
        if d:
          if e: return True
          else: return False
        else:
          if e: return False
          else: return True
  else:
    if b:
      if c:
        if d:
          if e: return False
          else: return True
        else:
          if e: return True
          else: return False
      else:
        if d:
          if e: return True
          else: return False
        else:
          if e: return False
          else: return True
    else:
      if c:
        if d:
          if e: return True
          else: return False
        else:
          if e: return False
          else: return True
      else:
        if d:
          if e: return False
          else: return True
        else:
          if e: return True
          else: return False

Neste caso, cada variável é avaliada uma única vez e, assim, este código apresenta claras vantagens sobre o primeiro. Apesar disto, ele é longo e tedioso – e também apresenta múltiplas possibilidades para introdução de erros. Uma alternativa melhor é a aritmetização dos valores lógicos, com False igual a $0$ e True igual a $1$.

def parity_arith (a: bool, b: bool, c: bool, d: bool, e: bool) -> bool:
  n = 0
  if a: n += 1
  if b: n += 1
  if c: n += 1
  if d: n += 1
  if e: n += 1
  return n % 2 == 1

O mecanismo de conversão entre tipos de Python segue as regras que estabelecemos acima, e pode ser utilizado para um código muito mais enxuto – e, portanto, o nosso preferido.

def parity (a: bool, b: bool, c: bool, d: bool, e: bool) -> bool:
  return (int(a) + int(b) + int(c) + int(d) + int(e)) % 2 == 1

$\square$

(10) Mini Quadra é uma simplificação da Mega Sena, na qual o apostador deve escolher quatro números inteiros distintos entre $1$ e $20$, inclusive.
- Escreva um programa que gere todos os jogos possíveis (i.é, todas as quádruplas). Você deve imprimir um jogo por linha.
- Modifique seu programa para que receba um inteiro não negativo $n$ e gere todos os jogos com valores entre $1$ e $n$, inclusive (em vez de $1$ e $20$).
Solução:
Podemos fornecer um único código, fazendo uso de parâmetros padrão na declaração da função.
```
def mini_quadra (n: int = 20):
  for i in range (1, n-2):
    for j in range (i+1, n-1):
      for k in range (j+1, n):
        for l in range (k+1, n+1):
          print (i, j, k, l)
```
Se invocarmos mini_quadra(), a variável n recebe o valor $20$ automaticamente; uma chamada mini_quadra (6) atribui o valor $6$ a n.

$\square$
(11) Escreva funções que:
- recebe um inteiro $n\geq 0$ e devolve $n!$, o fatorial de $n$, definido por $0!=1$ e $$n! = n(n-1)! \qquad \textrm{se} \qquad n > 0.$$
- recebe inteiros $n,m\geq 0$ e devolve $\binom{n}{m}$, o coeficiente binomial de $n$ e $m$, dado por $$\binom{n}{m} := \frac{n!}{m!(n-m)!}.$$ Observe que $\binom{n}{m}$ é o número de subconjuntos com $m$ elementos que podem ser tomados de um conjunto com $n$ elementos. Por exemplo, $\binom{20}{4}$ é o número de jogos que seu programa (10) deve ter impresso na saída.
Solução:
Da definição de fatorial, temos que $0! = 1$ e, para $n > 0$, $$n! = 1 * 2 * 3 * \cdots * (n-1) * n.$$
```
def fatorial (n: int) -> int:
  fat = 1
  for i in range (1, n+1):
    fat = fat * i
  return fat
```
Simplificando a expressão do coeficiente binomial, obtemos $$\binom{n}{m} = \frac{(n-m+1) * (n-m+2) * \cdots (n-1) * n}{m!}.$$
```
def binomial (n: int, m: int) -> int:
  if n < m: return 0
  num = 1
  for i in range (n-m+1, n+1):
    num = num * i
  return num//fatorial (m)  
```
Nos dois códigos, fat e num são inicializados com $1$ por ele ser o elemento neutro da multiplicação. $\qquad\square$

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)