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$

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)