BCM0505-15 - Processamento da Informação

Laboratório 03 – 03/03

Exercícios

• (01) Ashley ficou interessada no resultado de Diane do laboratório anterior e decidiu generalizá-lo. Ela pretende distribuir $n\geq 0$ doces a $m\geq 0$ crianças, mas agora há a possibilidade de que algumas crianças não recebam doces. Escreva uma função que recebe $n$ e $m$ e devolve o número de formas que ela pode fazer a distribuição.

  Solução:
  Uma ideia simples é reduzirmos o problema de Ashley ao de Diane: transformamos uma entrada ao problema de Ashley em uma entrada que seja consistente com o de Diane; aplicamos a solução obtida para o problema de Diane à entrada transformada; reinterpretarmos a resposta obtida no contexto original de Ashley. Se você ainda não estudou a solução apresentada ao problema de Diane, sugiro que o faça antes de prosseguir.

  Assuma que Ashley empresta um doce de cada criança antes de começar a distribuição. Ashley tem, então, $n+m$ doces para distribuir a $m$ crianças com a restrição de que cada criança recebe ao menos um doce, uma situação semelhante à de Diane. Após esta distribuição, se uma criança que recebeu somente um doce, é porque ela não recebeu nenhum dos $n$ doces; recebeu somente uma devolução ao doce que havia emprestado.

  Logo, a resposta ao problema de Ashley é obtida avaliando-se $$\binom{n+m-1}{m-1}.$$

  # recebe : n >= 0 e m >= 0 
  # devolve: $\binom{n}{m}$
  def binomial (n: int, m: int) -> int:
    if n < m: return 0
    a = b = 1
    for i in range (n-m+1, n+1): a *= i
    for j in range (2, m): b *= j      
    return a//b
  
  def ashley (n: int, m: int) -> int:
    return binomial (n+m-1, m-1)
  

  $\square$

• (02) Brenda está estudando como dispor rainhas – e somente rainhas – em um tabuleiro de xadrez de forma estável, sem que haja a possibilidade de ataques mútuos. Duas rainhas podem se atacar mutuamente se compartilharem uma mesma linha horizontal, vertical, ou diagonal no tabuleiro. Como primeiro passo, Brenda quer resolver o seguinte problema: em um tabuleiro $4\times 4$, cujas casas são numeradas de $(1,1)$ a $(4,4)$, dadas as posições $(x,y)$, $(z,w)$, $(u,v)$ e $(s,t)$ ocupadas por $4$ rainhas, determinar se este posicionamento é estável. Escreva uma função que resolva este problema.

  Solução:
  Se mais de uma rainha ocupar uma mesma linha, coluna, ou diagonal o posicionamento não é estável. Construímos uma função attack() para auxiliar na tarefa. A detecção de linhas ou colunas comuns é trivial. Para diagonais, observe que as principais são numeradas por $j-i$ e as secundárias por $n-j-i$, em que $n=4$ e $(i,j)\in\{(x,y),(z,w),(u,v),(s,t)\}.$

  # devolve True se ao menos dois dos valores a, b, c, d forem iguais, ou False em caso contrário
  def attack (a: int, b: int, c: int, d: int) -> bool:
    return a in (b,c,d) or b in (c,d) or c == d
  
  # devolve True se o posicionamento é estável, ou False em caso contrário
  def stable_queens (x: int, y: int, z: int, w: int, u: int, v: int, s: int, t: int) -> bool:
    return not (attack (x,z,u,s) 
             or attack (y,w,v,t) 
             or attack (y-x,w-z,v-u,t-s) 
             or attack (4-y-x,4-w-z,4-v-u,4-t-s))
  

  $\square$

• (03) Claire deseja calcular uma aproximação para $\sin x$ via série de Taylor-Maclaurin $$\sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \cdots + (-1)^k\frac{x^{2k+1}}{(2k+1)!} + \cdots$$ com precisão $0<\varepsilon\ll 1$. Isto é, ela deseja somar todos os termos da série acima até que a diferença absoluta entre dois termos consecutivos seja menor que $\varepsilon$: $$\left|\frac{x^{2k+1}}{(2k+1)!} - \frac{x^{2k-1}}{(2k-1)!}\right| < \varepsilon.$$ Escreva uma função que recebe floats $x$ e $\varepsilon$ e devolve a aproximação desejada.

  Solução:
  Uma codificação direta consiste em calcular cada termo da série de forma independente e somá-los até que a diferença absoluta de dois termos consecutivos seja menor que $\varepsilon$. Para isso, é conveniente utilizarmos a função fact(), que calcula o fatorial de um interiro não negativo, que implementamos em sala. Por questões de clareza, ela é repetida abaixo.

  # calcula o fatorial de n >= 0
  def fact (n: int) -> int:
    f = 1
    while n > 1: f, n = f*n, n-1
    return f
  
  # aproxima sin(x) via Taylor-Maclaurin com precisão 0 <= eps < 1
  def sen_x_squander (x: float, eps: float) -> float:
    fj, fk = x, -x*x*x/6
    k, s = 2, fj + fk
    while abs (fj - fk) >= eps:
      fj, fk = fk, (-1)**k * x**(2*k+1)/fact(2*k+1)
      s += fk
      k += 1
    return s
  

  Como já sabemos, inúmeros cálculos são feitos repetidamente no código acima. Para uma versão mais econômica, observe que $$(-1)^k\frac{x^{2k+1}}{(2k+1)!} \bigg/ (-1)^{k-1}\frac{x^{2k-1}}{(2k-1)!} = \frac{(-1)^k x^{2k+1}}{(2k+1)!} \cdot \frac{(2k-1)!}{(-1)^{k-1} x^{2k-1}} = \frac{-x^2}{2k(2k+1)}.$$ Logo, aproveitando o termo anterior para gerarmos o corrente, obtemos:

  # aproxima sin(x) via Taylor-Maclaurin com precisão 0 <= eps < 1
  def sen_x (x: float, eps: float) -> float:
    fj, fk = x, -x*x*x/6
    k, s = 2, fj + fk
    while abs (fj - fk) >= eps:
      fj, fk = fk, fk * -x*x/(2*k*(2*k+1))
      s += fk
      k += 1
    return s
  

  Nota: Python disponibiliza a função math.sin(). $\qquad\square$

• (04) Danielle está trabalhando na conjectura de Collatz, que diz que dado um inteiro $n_0>0$ e definindo-se $$n_i = \begin{cases} \displaystyle\frac{n_{i-1}}{2} & \text{se $n_{i-1}$ é par,} \\ 3n_{i-1}+1 & \text{se $n_{i-1}$ é ímpar.} \end{cases}$$ para $i\geq 1$, existe um valor para $i$ tal que $n_i=1$. Apesar de ainda não conhecermos uma prova formal, a conjectura já foi testada como positiva para inúmeros valores $n_0$. Escreva uma função que recebe um int $n_0>0$ e devolva o menor $i\geq 0$ tal que $n_i=1$.

  Solução:
  

  def collatz (n: int) -> int:
    i = 0
    while n != 1: i, n = i+1, n//2 if n % 2 == 0 else 3*n+1
    return i
  

  $\square$

• (05) Ellen deseja resolver um problema de busca de padrões: dados um texto $t$ e um padrão $p$, armazenados como strings, ela quer determinar quantas vezes $p$ ocorre em $t$. Por exemplo, se $t=$"ana e mariana gostam de banana" e $p=$"ana", temos que $$\mathsf{\underline{ana}~e~mari\underline{ana}~gostam~de~b\underline{an}\underline{\underline{a}na}}$$ e, portanto, $p$ ocorre $4$ vezes em $t$. Escreva uma função que recebe strings $t$ e $p$ e devolve o número de ocorrências de $p$ em $t$.
  Nota: Uma string é indexada como uma lista. No exemplo acima, t[0] == p[0] == 'a', t[1] == p[1] == 'n', e assim sucessivamente.

  Solução:
  Apresentamos um algoritmo ingênuo (força bruta) que faz $O(mn)$ comparações no pior caso, em que $m=\,$len(p) e $n=\,$len(t).

  def search (t: str, p: str) -> int:
    k, m, n = 0, len (p), len (t)
    for i in range (n - m + 1):
      if t[i] == p[0]:
        j = 1
        while j < m and t[i+j] == p[j]: j += 1
        if j == m: k += 1
    return k
  

  Uma variação, utilizando fatiamento de strings — igualmente ingênuo; mesmo consumo de tempo no pior caso.

  def search_alt (t: str, p: str) -> int:
    k, m, n = 0, len (p), len (t)
    for i in range (n - m + 1):
      if t[i:i+m] == p: k += 1
    return k
  

  $\square$

• (06) Florence precisa de uma extensão da função que você proveu no item anterior. Especificamente, ela deseja substituir todas as ocorrências de um padrão $p$ por outro $q$ num texto $t$ – do início para o final. Alerta à possibilidade de superposições, ela deseja ter o controle de qual variante utilizar. Por exemplo, caso $t=$"ana e mariana gostam de banana", $p=$"ana" e $q=$"olga", a substituição com superposições é $$\mathsf{olga~e~mariolga~gostam~de~bolgolga}$$ já a sem superposições é $$\mathsf{olga~e~mariolga~gostam~de~bolgana}$$ Escreva uma função que recebe três strings $t$, $p$ e $q$ e um bool $s$ e substitui todas as ocorrências de $p$ em $t$ por $q$ com superposições se s == True, e sem superposições caso s == False. Nota: as substituições devem ser feitas no próprio texto $t$; para isso, use separações ([a:b]) e concatenação (+).

  Solução:
  A substituição sem superposições é simples e não apresenta problemas: basta controlarmos um laço em que o parâmetro de término muda ao longo do processamento (um dos objetivos do exercício).

  A com superposições é ligeiramente mais delicada: se $p\neq q$ e $p$ ocorre em $q$ não somente como prefixo, o processo não tem fim! Você percebeu isso? Logo, é necessário supor que tal situação não ocorre – isto pode ser facilmente verificado à priori com a função do item anterior. Por exemplo, para $p=$"ana",

  • se $q=p+r$, em que $r$ é uma string — potencialmente vazia — que não começa com "na" e não contém $p$, a substituição deve funcionar sem problemas;
  • se $q=u+p+v$, em que $u$ e $v$ são strings com $u$ não vazia e $v$ qualquer (inclusive vazia), o processo de substituição com superposições é infinito!

  O objetivo desta variação era mostrar que potenciais laços infinitos podem estar escondidos atrás da falta de hipóteses precisas.

  def replace (t: str, p: str, q: str, s: bool) -> str:
    i, n, m, l = 0, len (t), len (p), len (q)
    while i < n - m + 1:
      if t[i:i+m] == p:
        t = t[:i] + q + t[i+m:]
        n = n - m + l
        i += 1 if s else l
      else
        i += 1
    return t
  

  $\square$

• (07) Gaia deseja calcular os coeficientes de Bézout de dois inteiros positivos $m$ e $n$, isto é, inteiros $a$ e $b$ relativamente primos tais que $$am + bn = \mathsf{mdc}(m,n).$$ Escreva uma função que recebe ints $m>0$ e $n>0$ e devolve o par $(a,b)$.

  Solução:
  Para explicação de como calcular $a$ e $b$, veja dedução na Solução da lista 1, exercício 3.

  def bezout (m: int, n: int) -> (int, int, int):
    ri, rj = max(m,n), min(m,n)
    ai, aj = 1, 0
    bi, bj = 0, 1
    while True:
      qj, rk = ri//rj, ri%rj
      ai, aj = aj, ai - aj*qj
      bi, bj = bj, bi - bj*qj
      if rk == 0: return rj, aj, bj
      ri, rj = rj, rk
  

  $\square$

• (08) Hannah tem sequências de $n\geq 3$ inteiros $A$ e deseja determinar o terceiro menor elemento em $A$. Ajude-a construindo uma função que resolve tal problema. Nota: não use nenhuma função que ordene os elementos de $A$.

  Solução:
  Vamos oferecer uma solução mais geral, que funciona para um $A$ com qualquer número de elementos.
  Se len(A) < 3, o valor devolvido é $\infty.$

  from math import inf as oo  
  
  def trd_min (A: [int]) -> int:
    x = y = z = oo # menor, segundo e terceiro menores em A, respectivamente
    for a in A:
      if   x > a: x, y, z = a, x, y
      elif y > a: y, z = a, y
      elif z > a: z = a
    return z        
  

  $\square$

• (09) Isabella tem um inteiro $x$ e quer determinar se uma dada sequência de $n\geq 0$ inteiros $A$ possui dois elementos distintos cuja soma é igual a $x$. Em outras palavras, ela quer determinar se existem índices $0\leq i\neq j< n$ tais que $A[i]+A[j]=x$. Escreva uma função que recebe $A$ e $x$ e devolve o par $(i,j)$ em caso afirmativo, ou $(n,n)$ em caso contrário.

  Solução:
  Apresentamos primeiro uma solução cujo consumo de tempo é $O(n^2)$, em que $n$ é o número de elementos em $A$.

  def pair_sum_nn (A: [int], x: int) -> (int, int):
    n = len (A)
    for i in range (n-1):
      for j in range (i+1, n):
        if A[i] + A[j] == x: return (i,j)
    return (n,n)
  

  Se ordenarmos $A$, é possível resolver o problema em tempo $O(n\log n)$.

  def pair_sum_nlogn (A: [int], x: int) -> (int, int):
    n = len (A)
    A.sort()
    i, j = 0, n-1
    while i < j:
      if   A[i] + A[j] < x: i += 1
      elif A[i] + A[j] > x: j -= 1
      else: return (i,j)
    return (n,n)
  

  Pergunta: por que o código acima funciona?
  $\square$

• (10) Julie está estudando platôs em sequências $A=[a_0,a_1,\ldots,a_{n-1}]$ de inteiros, isto é, segmentos $[i\,..j]$ de $A$ tais que $$a_i=a_{i+1}=\cdots=a_{j-1}=a_j,$$ com $i\leq j$. Escreva uma função que recebe uma lista de ints $A$ e devolve o início ($\,i\,$) e o final ($\,j\,$) do maior platô em $A$. Nota: o que deve ser devolvido caso $A$ seja vazia?

  Solução:
  Caso A = [], o maior platô tem comprimento zero e os índices devolvidos devem satisfazer $i>j$; vamos fixar $i=0$ e $j=-1$.

  def plateau (A: [int]) -> (int, int):
    if len (A) == 0: return (0,-1)
    i = j = k = 0; l, n = 1, len (A)
    while l < n:
      while l < n and A[l] == A[k]: l += 1
      if j - i < l-1 - k:
        i, j = k, l-1
      k = l
    return (i,j)
  

  $\square$

• (11) Kathrin tem uma lista de notas $A=[a_0,a_1,\ldots,a_{n-1}]$ e deseja normalizá-las. Escreva uma função que recebe uma lista de floats $A$ e determina:

  • a média de $A$ $$\mu = \frac{1}{n}\sum_{i=0}^{n-1} a_i,$$
  • o desvio padrão de $A$ $$\sigma = \left(\left(\frac{1}{n}\sum_{i=0}^{n-1} a_i^2\right) - \mu^2\right)^{\frac{1}{2}},$$
  • uma lista $B=[b_0,b_1,\ldots,b_{n-1}]$, de notas normalizadas, tal que $$b_i = \frac{a_i-\mu}{\sigma}.$$

  Devolva $\mu$, $\sigma$ e $B$.
  Nota: você pode usar B.append() para incluir novos elementos ao final de $B$, inicialmente vazia (B = []), o criar $B$ diretamente via um predicado adequado.

  Solução:
  

  def average (A: [float]) -> float:
    return 0 if len (A) == 0 else sum (A) / len (A)  
  
  def std_dev (A: [float], mu = None) -> float:
    if mu == None: mu = average (A)
    s2 = 0 if len (A) == 0 else sum ([a*a for a in A]) / len (A)
    return math.sqrt (s2 - mu*mu)
  
  def normalize (A: [float]) -> (float, float, [float]):
    mu = average (A)
    sigma = std_dev (A, mu)  
    return (mu, sigma, [(a-mu)/sigma for a in A])
  

  $\square$

• (12) Louise quer usar a função construída para Kathrin no item anterior para calcular conceitos de acordo com a tabela abaixo. $$\begin{array}{|c|c|} \hline \text{nota normalizada em} & \text{conceito} \\ \hline (3\sigma/2,+\infty] & A \\ \hline (\sigma,3\sigma/2] & B \\ \hline (\sigma/2,\sigma] & C \\ \hline (0,\sigma/2] & D \\ \hline (-\infty,0] & F \\ \hline \end{array}$$ Escreva uma função que recebe um desvio padrão $\sigma$ e uma lista $B$ de notas normalizadas e devolve uma lista $C$ de conceitos (como strings). Nota: $B$ e $C$ devem naturalmente seguir a mesma ordem.

  Solução:
  

  def grade (B: [float], sigma) -> [str]:
    C = []
    for b in B:
      if   b > 3*sigma/2: C += ["A"]
      elif b > sigma:     C += ["B"]
      elif b > sigma/2:   C += ["C"]
      elif b > 0:         C += ["D"]
      else:               C += ["F"]
    return C
  

  $\square$

• (13) Melanie definiu uma sequência $A=[a_0,a_1,\ldots,a_{n-1}]$ de inteiros como par-piramidal se $a_0$ é par, $a_1$ e $a_2$ são ímpares, $a_3,a_4$ e $a_5$ são pares, $a_6,a_7,a_8$ e $a_9$ são ímpares, e assim sucessivamente. Escreva uma função que recebe uma lista $A$ de ints e determina se $A$ é par-piramidal.

  Solução:
  Observe, inicialmente, que o número $n$ de elementos em $A$ deve ser igual a $k(k+1)/2$, para algum inteiro $k\geq 1$. Resolvendo a equação em função de $k$, obtemos que $$k = \frac{-1+\sqrt{1+8n}}{2}.$$ Logo, $A$ tem um comprimento apropriado se, e somente se, a substituição de $n=\,$len (A) na expressão acima resulta em um valor inteiro — o que pode ser checado com k % 1 == 0. Em sendo o caso, devemos ter $k-1$ alternancias de paridade em $A$.

  def par_piramidal (A: [int]) -> bool:
    k = (-1 + math.sqrt (1 + 8*len(A)))/2
    if len(A) == 0 or k % 1 != 0: 
      return False
  
    m, parity = 0, 0
    for j in range (1, int (k) + 1):
      for i in range (j):
        if A[m] % 2 != parity: 
          return False
        m += 1
      parity = 1 if parity == 0 else 0 # parity = int (not bool (parity))
    return True
  

  $\square$

• (14) Nassim está estudando sequências de inteiros que possuem alternância de sinal. Uma sequência $A=[a_0,a_1,\ldots,a_{n-1}]$ de inteiros é $k$-alternante, para $k\geq 1$, se:

  • $A$ pode ser dividida em n // k blocos (de elementos contíguos) de mesmo comprimento,
  • os elementos de um bloco são todos positivos ($+$) ou negativos ($-$),
  • blocos adjacentes possuem sinais distintos ($+-+-\cdots$ ou $-+-+\cdots$).

  Por exemplo:

  • $[1,2,3,-8,-8,-8,1,1,5]$ é $3$-alternante,
  • $[-1,-2,3,4,-1,-2,5,6]$ é $2$-alternante,
  • $[1,2,3,4,5]$ é $5$-alternante,
  • $[1,2,-1,3]$ não é alternante; diremos neste caso que ela é $0$-alternante.

  Escreva uma função que recebe uma lista de ints $A$ e devolve um valor $k\geq 0$ tal que $A$ é $k$-alternante.

  Solução:
  Se $A$ for vazia ou possuir um zero (o único inteiro sem sinal), ela é $0$-alternante. Se $A$ for unitária, ela é $1$-alternante.

  def alternante (A: [int]) -> int:
    n = len (A)
    if n in (0,1): return n
  
    # determinação de k
    k = 1
    while k < n and A[k-1] * A[k] > 0: k += 1
    if k < n and A[k-1] == 0 or n % k != 0: 
      return 0
  
    # verificação do resto de A
    m = 1 if k > 1 else 0
    for i in range (1, n // k):
      for j in range (i*k, (i+1)*k - m):
        if A[j] * A[j+1] <= 0:
          return 0
    return k
  

  $\square$

• (15) Octavia aprendeu que uma lista $A[0\,..n-1]$ é unimodal se existe um índice $j\in\{-1,0,1,\ldots,n-1\}$ tal que os elementos da sub-lista $A[0\,..j]$ estão em ordem crescente e os da sub-lista $A[j+1\,..n-1]$ estão em ordem decrescente. Em outras palavras, $A$ é unimodal se $$ A[0] \leq A[1] \leq \cdots \leq A[j] > A[j+1] \geq A[j+2] \geq \cdots \geq A[n-1].$$ Escreva uma função que recebe uma lista $A$ e decide se $A$ é unimodal. Em caso afirmativo, devolva o valor $j$ determinado; em caso negativo, devolva $n$.

  Solução:
  Observe que se $A$ estiver em ordem crescente ou decrescente, ela é unimodal. Os valores corretos para $j$ nestes casos são $-1$ e $n-1$, respectivamente.

  def is_unimodal (A: [float]) -> int:
    n, i = len(A), 0
    while i < n-1 and A[i] <= A[i+1]: i += 1
    j = -1 if i == 0 else i    
    i += 1
    while i < n-1 and A[i] >= A[i+1]: i += 1
    if i == n-1: j = n
    return j
  

  $\square$

• (16) Phoebe precisa de uma função que recebe uma lista $A[0\,..n-1]$ de inteiros e devolve True se existem elementos repetidos em $A$, ou False em caso contrário. Ajude-a escrevendo tal função.

  Solução:
  Apresentamos, inicialmente, uma solução $O(n^2)$.

  def repetition_nn (A: [int]) -> bool:
    n = len (A)
    for i in range (n-1):
      for j in range (1, n):
        if A[i] == A[j]: return True
    return False
  

  Se ordenarmos $A$, é possível resolver o problema em tempo $O(n\log n)$.

  def repetition_nlogn (A: [int]) -> bool:
    A.sort()
    for i in range (1, len(A)):
      if A[i-1] == A[i]: return True
    return False
  

  $\square$