Ejercicios

1.

La conjetura de Goldbach afirma que todo número par se puede expresar como suma de dos primos.

El código de abajo pretende verificar la conjetura de Goldbach hasta un cierto número par K.

Tu objetivo es mejorar este código siguiendo las siguientes directrices:

• Identifica, de entre las tres funciones de abajo, la que más tiempo de cómputo consume, y por tanto la que más necesita nuestra atención. Justifica tu respuesta.
• Usando la hipótesis (trivial de demostrar, por otro lado), de que la criba de Eratóstenes tiene complejidad en O(N^2) (observa que decimos O, luego hablamos sólo de una cota superior), estima la complejidad del código presentado.
• Mejora el código de arriba modificando el algoritmo hasta que su complejidad sea O(N^2). Trabaja únicamente en mejorar la función que has identificado antes.

sage: ##Criba
sage: def criba(ls):
...       '''Se queda con los elementos irreducibles de una lista de enteros'''
...       primos = []
...       while ls:
...           p = ls[0]
...           primos.append(p)
...           ls = [k for k in ls if k%p]
...       return primos
sage: def lista_primos(K):
...       'genera los numeros primos menores que K'
...       return criba(range(2,K))
sage: def goldbach(N):
...       for t in range(4,N,2):
...           comprobado = False
...           for x in lista_primos(N):
...               for y in lista_primos(N):
...                   if t == x+y:
...                       comprobado = True
...           if not comprobado:
...               return False #t es un contraejemplo
...       return True

sage: time goldbach(200)

2.

El objetivo de este ejercicio es calcular el tiempo de parada de la sucesión de Collatz comenzando por cada numero menor que M. El código de abajo calcula la longitud de la secuencia de Collatz partiendo de cada número entre 1 y M. Tus objetivos son:

• Modificar el algoritmo para recordar los valores ya calculados. Por ejemplo, si sabes que la longitud de la sucesión que comienza por 3 es 8, entonces la longitud de la sucesión que empieza por 6 es 9(=8+1), ya que el número siguiente a 6 es, y a partir de ese punto las sucesiones son iguales.

6->3->10->5->16->8->4->2->1

• Compila el código usando cython y declarando los tipos de las variables para acelerar el cálculo.

sage: def collatz(k):
...       if k%2:
...           return 3*k+1
...       else:
...           return k/2
sage: def tiempos_collatz(M):
...       tiempos = []
...       for j in range(1,M):
...           l = 1
...           k = j
...           while k!=1:
...               k = collatz(k)
...               l+=1
...           tiempos.append(l)
...       return tiempos

sage: time ts = tiempos_collatz(1000)
Time: CPU 0.39 s, Wall: 0.38 s

sage: point2d([(j,ts[j]) for j in range(len(ts))])

3.

http://es.wikipedia.org/wiki/Juego_de_la_vida

El “juego de la vida” se desarrolla en una malla formada por cuadrados (“células”) que se extiende por el infinito en todas las direcciones. Cada célula tiene 8 células vecinas, que son las que están próximas a ella, incluyendo las diagonales. Las células tienen dos estados: están “vivas” o “muertas” (o “encendidas” y “apagadas”). El estado de la malla evoluciona a lo largo de unidades de tiempo discretas (se podría decir que por turnos). El estado de todas las células se tiene en cuenta para calcular el estado de las mismas al turno siguiente. Todas las células se actualizan simultáneamente.

Las transiciones dependen del número de células vecinas vivas:

• Una célula muerta con exactamente 3 células vecinas vivas “nace” (al turno siguiente estará viva).
• Una célula viva con 2 ó 3 células vecinas vivas sigue viva, en otro caso muere o permanece muerta (por “soledad” o “superpoblación”).

El código de debajo calcula la evolución de una matriz NxN con unos para las células vivas y ceros para las muertas. Tu objetivo es compilar el código en cython indicando los tipos de las variables y haciendo alguna otra optimización sencilla que se te ocurra para mejorar el código. Anota las mejora obtenidas contra un ejemplo tipo de tamaño respetable para observar qué cambios son más importantes.

sage: def cuenta_vecinos(m, j, k):
...       '''Cuenta el número de vecinos vivos de la casilla (j,k)'''
...       cuenta = 0
...       for j0, k0 in [(j - 1,k - 1), (j - 1,k), (j - 1,k + 1), (j,k - 1), (j,k + 1), (j
sage: + 1,k - 1), (j + 1,k), (j + 1,k + 1)]:
...          if 0<=j0<m.nrows() and 0<=k0<m.ncols():
...              cuenta += m[j0,k0]
...       return cuenta
sage: def paso(m):
...       F = m.nrows()
...       C = m.ncols()
...       nueva = matrix(F,C)
...       for j in range(F):
...           for k in range(C):
...               vecinos = cuenta_vecinos(m, j, k)
...               if vecinos == 3 or (m[j,k] and vecinos == 2):
...                   nueva[j,k] = 1
...               else:
...                   nueva[j,k] = 0
...       return nueva
sage: def gameoflife(matriz, generaciones):
...       for g in range(generaciones):
...           matriz = paso(matriz)
...       return matriz

sage: m=matrix(8,8)
sage: m[3,4]=1
sage: m[4,4]=1
sage: m[2,4]=1
sage: m[4,3]=1
sage: m[2,2]=1
sage: matrix_plot(m).show()
sage: m = gameoflife(m,1)
sage: matrix_plot(m).show()

sage: %time
sage: m=matrix(8,8)
sage: m[3,4]=1
sage: m[4,4]=1
sage: m[2,4]=1
sage: m[4,3]=1
sage: m[2,2]=1
sage: a = animate([matrix_plot(gameoflife(m,j)) for j in range(1,10)])