miércoles, 22 de octubre de 2014

Unión e intersección de conjuntos con Excel


De cuando en cuando publicamos en este blog entradas sobre el funcionamiento de las hojas de cálculo, y en concreto sobre la programación en su Basic. La de hoy es una de ellas, así que si no te interesa el tema no sigas, que no vas a encontrar cuestiones sobre números.

Nos vamos a proponer la obtención de la unión y la intersección de dos conjuntos escritos en la hoja como dos columnas paralelas. Lo desarrollaremos en Excel sólo, para no duplicar las explicaciones, pero el contenido se puede adaptar a OpenOffice o LibreOffice. No se busca aquí la utilidad, sino la posibilidad de superar un reto. Lo que construyamos puede que aparentemente no sirva para nada.

Hemos preparado un esquema en el que a partir de la fila 7 se van escribiendo los conjuntos A y B con lo que deseamos operar. Después, con una simple pulsación de un botón, realizaremos las operaciones deseadas.



Intentamos en primer lugar resolver la cuestión sin el uso de macros, pero resultó un proceso tan complejo y artificioso que renunciamos a ello. Así, todo lo que sigue se basará en el lenguaje VBA de Excel. Como se observa en la imagen, se pueden usar números y también letras y palabras. Sólo hay que tener en cuenta que un espacio en blanco cuenta como un elemento, por lo que el borrado se debe realizar con el botón correspondiente o con la tecla Supr, sin escribir nada.

Otro detalle interesante es que en las operaciones se eliminan los elementos repetidos, logrando con ello una gran limpieza en la presentación. En un segundo paso puedes ordenar los resultados sin son más extensos.



Procedimientos necesarios

Recorrido por un conjunto 

Para obtener la unión e intersección de dos conjuntos se requiere, en primer lugar, el poder recorrer un conjunto del que no se sabe en principio cuántos elementos contiene. Para ello usaremos la idea de celda vacía. El recorrido se basará entonces en “avanzo mientras la celda no esté vacía”. Esta condición se puede verificar en VBA con la función IsEmpty, que nos devuelve True si la celda no contiene ningún dato. Con ella es fácil programar un recorrido:

fila = 7
While Not IsEmpty(Cells(fila, columna)) And … (cualquier otra condición)
‘ Aquí las operaciones que deseemos realizar con el elemento.
fila = fila + 1
Wend

Este sencillo esquema se repetirá cada vez que realicemos una operación elemento a elemento: ver si un dato pertenece o no al conjunto, buscar repetidos, incorporar elementos nuevos y otros. Comenzamos por la fila 7, que es donde comienzan nuestros conjuntos y después se va bajando de fila hasta que no queden elementos.

Por ejemplo, la siguiente función ESTA nos devuelve True si un valor n pertenece al conjunto situado en la cierta columna

Public Function esta(n, columna) As Boolean
Dim fila
Dim est As Boolean

est = False
fila = 7
While Not IsEmpty(Cells(fila, columna)) And Not est
If n = Cells(fila, columna).Value Then est = True
fila = fila + 1
Wend
esta = est
End Function

Es fácil identificar la estructura del recorrido por el conjunto. Esta función ESTA nos servirá para saber si podemos agregar un elemento nuevo a un conjunto mediante el procedimiento  AGREGA, que servirá para ir incorporando términos a la unión y a la intersección.

Sub agrega(n, columna)
Dim i

i = 7
While Not IsEmpty(Cells(i, columna))
i = i + 1
Wend
If Not esta(n, columna) Then Cells(i, columna).Value = n
End Sub

Recorre el conjunto, y si no encuentra el elemento dado, baja una fila y lo incorpora.
Con los procedimientos de recorrido y agregación y la función ESTA podemos ya planificar nuestra tarea:


  • Se elige el primer conjunto
  • Se recorre, y para cada elemento:
  • (A) Si no está en la unión, se agrega (así evitamos repetidos)
  • (B) Se compara con todos los elementos del segundo (mediante un recorrido por el mismo) y si está repetido, se incorpora a la intersección si todavía no está.
  • Se repite la tarea con el segundo conjunto, pero esta vez no se busca la intersección, que ya estará resuelta.

Para entender el listado que sigue recuerda que los conjuntos están escritos en las columnas  tercera y cuarta, que la unión se escribe en la quinta y la intersección en la sexta.

Así quedaría:

Option Explicit  ‘Evita el uso de variables no dimensionadas

Public Function esta(n, columna) As Boolean ‘ Ya explicada. Determina si un elemento pertenece a un conjunto
Dim fila
Dim est As Boolean

est = False
fila = 7

While Not IsEmpty(Cells(fila, columna)) And Not est
If n = Cells(fila, columna).Value Then est = True
fila = fila + 1
Wend
esta = est
End Function

Sub agrega(n, columna) ‘También explicada: añade un elemento si aún no está
Dim i

i = 7
While Not IsEmpty(Cells(i, columna))
i = i + 1
Wend
If Not esta(n, columna) Then Cells(i, columna).Value = n
End Sub


Sub union() ‘Esquema general de trabajo. Se inicia al pulsar el botón “Operación”
Dim i, j, n1, n2
Dim esinter As Boolean

i = 7
Call borrar ‘Macro grabada aparte
While Not IsEmpty(Cells(i, 3)) ‘Recorre el primer conjunto


'Se recorre la primera columna
n1 = Cells(i, 3).Value
Call agrega(n1, 5) ‘Agrega el elemento a la unión

'se busca la intersección
j = 7
esinter = False
While Not IsEmpty(Cells(j, 4)) And Not esinter ‘Se recorre el segundo conjunto
n2 = Cells(j, 4).Value
If n1 = n2 Then esinter = True
j = j + 1
Wend
If esinter Then Call agrega(n1, 6) ‘Si está repetido se agrega a la intersección
i = i + 1
Wend
i = 7
While Not IsEmpty(Cells(i, 4))
'Se recorre la segunda columna y se repite el agregar a la unión.
n1 = Cells(i, 4).Value
Call agrega(n1, 5)
i = i + 1
Wend
End Sub

Si lo has entendido, intenta programar la diferencia entre dos conjuntos, los elementos que pertenecen a uno pero no al otro. Puedes repasar la hoja alojada en (http://www.hojamat.es/blog/union de conjuntos.xlsm) y modificarla libremente.

lunes, 13 de octubre de 2014

Propiedades de los restos cuadráticos


Usaremos en los desarrollos el símbolo de Legendre ya explicado en la entrada anterior, Recuerda que la actual entrada es parte de un ciclo de tres.

El criterio de Euler da lugar a propiedades interesantes de los restos cuadráticos respecto a ciertos tipos de primos. Los vemos:

 -1 es un resto para todos los primos del tipo 4N+1 y no resto para los del tipo 4n+3

Es una consecuencia del criterio de Euler, pues (p-1)/2 sería par en el primer caso, e impar en el segundo, luego al elevar -1 a esa cantidad producirá un 1 (ser resto) para p=4N+1 y -1 (no resto) en el otro caso.

Esto quiere decir que la ecuación x2 + 1 º 0 (mod p) tiene solución para p=4N+1 y no la tiene en el segundo caso. Podemos expresarlo también como que 1 posee una raíz cuadrada entre las clases de restos módulo p

Podemos diseñar un pequeño esquema con la hoja de cálculo que usamos en esta serie:


 En la celda del 11 hemos escrito =RESTOCUAD(-1;61). Como este módulo es del tipo 4N+1, obtenemos la solución 11, ya que 11*11 módulo 61 es igual a 60, es decir, la clase de restos -1
Si hubiéramos usado módulo 11, que es del tipo 4N+3. Obtendríamos un cero, que es la señal de que -1 no es resto cuadrático:


Esta propiedad se puede expresar así:

2 es resto cuadrático para todos los primos del tipo 8N+1 y 8N+7, y no resto para los demás

También podemos, en nuestra hoja de cálculo, crear un esquema para comprobar esta propiedad siguiendo la estructura que usamos en la anterior.


Vemos que 11 no pertenece al tipo 8N+1 ni al 8N+7, y para el 2 no devuelve raíz cuadrada (el cero es una señal)

Sin embargo, al usar el módulo 31, que es del tipo 8N+7, el 2 presenta raíz cuadrada 8, y es resto cuadrático.


No es sencilla la demostración. Tienes una en Fundamentos de la Teoría de los números de Vinogradov.

Encontrarás propiedades similares para el -3 y el 5 en el documento de Rafael Parra “Restos cuadráticos y Ley de reciprocidad cuadrática”(http://www.hojamat.es/parra/restocuad.pdf). Las puedes comprobar con el esquema propuesto, sustituyendo el 2 por otros valores.

Ley de reciprocidad cuadrática

La propiedad más importante de estos restos es la ley de reciprocidad cuadrática, enunciada y demostrada por Gauss en 1801 en su libro Disquisitones Arithmeticae. Con palabras la podemos expresar así:

Dados dos primos impares p y q, si ambos pertenecen al tipo 4k+3, entonces p es resto cuadrático módulo q si y sólo si q no lo es de p. Si alguno de los primos pertenece al tipo 4k+1 entonces o bien ambos son restos uno del otro, o bien ninguno lo es.

Expresada así o de forma similar la propiedad resulta oscura. Sin embargo su significado queda claro con el uso de los símbolos de Legendre. En ese caso la propiedad se reduce a esta identidad:

Así se explica mejor: Si uno de los dos, p o q, es del tipo 4k+1, el exponente del -1 será par y el segundo miembro valdrá 1, con los que los símbolos del primero serán ambos iguales a 1 (restos recíprocos) o bien -1 (ninguno es resto).

Si ambos son del tipo 4k+3 el exponente será impar, el segundo miembro -1 y los símbolos tendrán signo opuesto: Si uno de los primos es resto del otro, no se dará la reciprocidad.

En textos y documentos varios dispones de ejercicios sencillos que muestran la utilidad de esta propiedad. Nosotros la hemos incluido en nuestra hoja de cálculo (http://www.hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm#restocuad)

Al escribir los dos primos la hoja analiza si son del tipo 4N+3 o 4N+1, calcula después los restos y comprueba la propiedad.



Como se trabaja con valores 1 y -1, algunos manuales expresan esta propiedad mediante esta otra identidad equivalente:



Así se ve mejor cómo calcular un valor de (p/q) si se conoce el de (q/p). Como hemos afirmado más arriba, no entra dentro de los objetivos de esta entrada pasar a ese tipo de cálculos.