Saltar a contenido

Parcialito 1 - 2022b - Tema 1#

Ejercicio 1#

Implementar una función que dadas 2 secuencias recibidas como argumento retorne los índices de cada una de ellas a partir de los cuales se obtiene la subsecuencia en común de mayor longitud, y retorne también la longitud de dicha secuencia. Por ejemplo, las cadenas:

  • "TAGGTTAATGGGCCATTTTCGGCACCCTAGGTAGCTTATT", y
  • "ACCATACTATGGTTTTTCCTAAGCGATTGGCATTTTCTTG"

tienen un solapamiento máximo de 7 caracteres, como se muestra a continuación:

                 TAGGTTAATGGGCCATTTTCGGCACCCTAGGTAGCTTATT
ACCATACTATGGTTTTTCCTAAGCGATTGGCATTTTCTTG
                              ^^^^^^^

Mientras que las cadenas:

  • "TACCAGTCTATGTCATCCAGGGTAGCTGTTTGATTGTCCC", y
  • "CGAACGGAGAAAGTTAGCATTCCCAGTTGTCGGGTCTACG"

tienen un solapamiento máximo de 5 caracteres:

                    TACCAGTCTATGTCATCCAGGGTAGCTGTTTGATTGTCCC
CGAACGGAGAAAGTTAGCATTCCCAGTTGTCGGGTCTACG
                      ^^^^^

Por otro lado, las listas [0, 1, 2, 3, 4, 5] y [2, 3, 4] tienen un solapamiento de 3 elementos.

Ejercicio 2#

El algoritmo de Newton-Raphson es uno de los más utilizados para encontrar las raices de una ecuación. Para ello, necesitamos una función \(f(x)\) a la que le buscaremos la raíz, es decir, el \(x\) tal que \(f(x) = 0\). Una vez que tenemos \(f(x)\), necesitamos \(f'(x)\) y partir de un punto, llamado \(x_0\).

Dado un valor \(x_0\), \(f(x)\) y \(f'(x)\), podemos calcular un siguiente punto como:

\[ x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} \]

de manera genérica, dado un punto cualquiera para \(f(x_k)\), donde \(x_k\) es el valor de \(x\) en la iteración \(k\), podemos obtener \(x_{k+1}\) del siguiente modo:

\[ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} \]

Claramente, tenemos como condición que \(f(x_k) \neq 0\).

Dada \(f(x) = \cos(x) - 2 x^3\) y \(f'(x) = -\sin(x) - 6 x^2\):

  1. Implementar las funciones fx(x) y dfdx(x) con las definiciones de \(f(x)\) y \(f'(x)\), respectivamente.

  2. Implementar una función que implemente el algoritmo descripto anteriormente, considerando:

    • La función debe recibir un parámetro que indique el error máximo admitido (\(\delta\)) que indica qué tan cerca del cero podemos frenar (sin llegar al cero).
    • La función debe recibir un parámetro que indique la cantidad de iteraciones máximas (\(N\)).
    • La función debe retornar el valor de \(x\) y el número de iteración cuando \(|f(x)| \leq \delta\) o cuando se alcance el número de iteraciones.
    • En cada iteración, la función debe imprimir por pantalla: “Iteración k: x = valor de x, f(x) = valor de f(x)”, donde “k” es el número de iteración, “valor de x” es el valor de \(x\) en dicha iteración y “valor de f(x)” es el valor de \(f(x)\) en dicha iteración.