matemáticas - Tienda de ultramarinos
logo Tienda de Ultramarinos
Etiquetas: matemáticas

Máximo número de aristas en digrafo de diametro D

Breve introducción o repaso

Un grafo es una estructura compuesta por nodos unidos por aristas (edges, en inglés). En teoría de grafos, se denomina grafo completo K_n a aquel que cada uno de sus n nodos tiene una conexión con cada uno de los otros n-1 nodos.

El número de aristas en estos grafos es siempre E(K_n) = \frac{n (n-1)}{2}, que coincide con la suma de enteros de 1 hasta n. Esto se ve claramente dibujando un K_n en una hoja de papel. Primero pones los n nodos, luego tomas cada uno y dibujas todas las aristas que lo unen con el resto, n-1. Cuando lo hagas con el siguiente sólo podrás pintar n-2, con el siguiente n-3, etc.

En un grafo normal, las aristas son bidireccionales, pero hoy vamos a trabajar los grafos dirigidos o digrafos, donde cada arista va acompañada de una flecha que indica la única dirección posible que se puede tomar. Así, el número de aristas en un digrafo dirigido será el doble que en el mismo normal, por lo que:

 E(k) = n^2 - n = n(n-1)

Para simplificar los siguientes dibujos (todos de digrafos), asumiremos que las aristas sin flecha son bidireccionales, valen por dos, y las dibujadas con flecha indicarán la única dirección posible. De ese modo, los dos siguientes grafos dirigidos son equivalentes.

El número de nodos que hay que atravesar para ir de uno a otro se llama distancia. Si medimos la distancia de cada nodo a todos los demás y tomamos el valor máximo, tenemos el diámetro del grafo. En un grafo completo, el diámetro siempre es 1. En el las imágenes de encima, el diámetro es 2.

¿Cuál es el número máximo de aristas que puede tener un digrafo de diámetro D?

A estos grafos les llamaremos K_n^d, donde n es el número de nodos y d el diámetro. Así K_6^3 es el grafo de diámetro 3 y 6 nodos con el mayor número de aristas posibles entre ellos. Además, utilizaremos la función E(G) para contar el número de aristas en el grafo G.

\exists i,j \in K_n^d\Rightarrow distance(i,j)

Voy a poner los ejemplos con K_5^d, pero para seguir mejor los resultados, estaría bien que antes de continuar cogieras papel y lápiz y tratases de solucionar los grafos con 3 y 4 nodos, que son muy sencillos: K_3^2, K_4^2 K_4^3

D=1, es el caso trivial, K_n^1 = K_n por lo que E(K_n^1)=n^2 - n.

Para K_n^2, simplemente tenemos que tomar K_n^1, y eliminar cualquier arista en una dirección, dejándola en la otra. En la siguiente imagen se puede ver que para ir de A a E hemos de pasar obligatoriamente por otro nodo, teniendo así el diametro igual a dos que necesitábamos. Así pues, E(K_n^2)=n^2 - n - 1.

La estrategia a partir de ahora es clara, “aislar” dos nodos de forma que en una dirección siempre sea necesario recorrer los suficientes como para justificar el diámetro. La otra dirección no hay que “cerrarla”, ya que únicamente hacen falta un par de nodos con distancia igual a diametro, y el resto son aristas extra que se suman a la cuenta.

Con K_5^2, hemos visto que los recorridos posibles para llegar de A a E eran pasando por B, C ó D, sin embargo ahora necesitamos un salto más. Para ello, “cerramos” todas las entradas a E, salvo por D. Ahora simplemente prohibimos a A moverse directamente a D, teniendo que ir a través de B ó C. Así, al total de aristas E(K_5^1) =  n^2 - n le hemos quitado cuatro, quedando: E(K_5^3) = 5^2 - 5 - 4 = 16. También podemos decir que a K_5^2 le quitamos tres aristas.

Repetimos el mismo proceso para K_5^4=, que es el último para cinco nodos y donde lo que finalmente hemos conseguido es que de A a E sólo se pueda ir por el camino ABCDE. Para ello simplemente hemos tenido que quitarle dos aristas a E(K_5^3) E(K_5^4)= 16 -2 = 14.

K_5^d termina aquí, pero si hacemos esto con grafos mayores veremos claramente un patrón que se repite: (los paréntesis no son necesarios, sólo para visualizarlo más claro).

 E(K_n^1) = n^2 - n
 E(K_n^2) = (n^2 - n)  -1
 E(K_n^3) = (n^2 - n) - (n - 2) -1 = n^2 - 2n + 1
 E(K_n^4) = (n^2 - n) - (n - 2) - (n - 3) - 1 = n^2 - 3n + 4
 E(K_n^5) = (n^2 - n) - (n - 2) - (n - 3) - (n -4) - 1 = n^2 - 4n + 8
 E(K_n^d) = E(K_n^{d-1}) - (n - ( d - 1))
 E(K_n^d) = n^2 - (d-1) \cdot n + \frac{d\cdot (d-1)}{2} -2

En realidad, K_n^1 es K_n y no se puede tratar con la misma ecuación genérica que el resto, por lo que K_n^d sólo funciona para d\ge2.

Por otro lado, el caso específico K_n^{n-1} se puede solucionar mediante otra aproximación, de igual forma para todos los grafos. Primero, sabemos que la solución constará de un único camino bidireccional que recorra todos los nodos (lo cual es además un camino hamiltoniano). Esto es 2(n-1). El número de aristas es n-1, que valen doble porque son bidireccionales. Veamos el ejemplo con cinco y seis nodos.

Ahora simplemente tenemos que rellenar los huecos del grafo con aristas en la dirección correcta. ¿Cuántas son? Pues fácil, el total de aristas de Kn menos n-1, que son las que acabamos de pintar.

 E(K_n) - (n-1) = \frac{n\cdot (n-1)}{2}-(n-1)

Lo cual, se lo sumamos a lo que ya teníamos y queda:

 E(K_n^{n-1}) = 2\cdot (n-1) +  \frac{n\cdot (n-1)}{2}-(n-1) = \frac{n^2+n-2}{2}

Si tomamos el caso general E(K_n^d) y sustituimos d=n-1, veremos que llegamos exactamente a la función E(K_n^{n-1}). Si bien dije previamente que K_n^d no funciona para d=1, esta nueva ecuación sí que respeta ese caso. Si despejamos n en E(K_n^1) = n^2 - n = \frac{n^2+n-2}{2} = E(K_n^{n-1}) sale una ecuación de segundo grado con raíces en 1 y 2; nos nos interesa la segunda puesto que estábamos considerando d=n-1 y demuestra que la igualdad es correcta. También es mucho más sencillo directamente sustituir n=2 en ambas fórmulas y ver que el resultado es el mismo, 2. El cual es exactamente el número de aristas en un digrafo de dos nodos y diámetro uno.

También podemos tomar valores específicos y comprobar que obtenemos el mismo resultado, por ejemplo:

 E(K_n^4) =  n^2 - 3n + 4
 E(K_5^4) = 5^2 - 3\cdot 5 + 4 = 25 - 15 + 4 =14
 E(K_n^{n-1}) = \frac{n^2+n-2}{2}
 E(K_5^{4}) = \frac{5^2+5-2}{2} = \frac{25 + 5 - 2}{2} = 14

¿Aplicaciones prácticas de este resultado?

En la asignatura Distributed System estamos estudiando algoritmos para seleccionar el nodo líder de una red, figura necesaria en muchas ocasiones para coordinar algoritmos distribuidos. Cada nodo tiene un identificador distinto del resto, así que la selección del líder se puede hacer bien con el que tenga el mayor ID o el que tenga el menor (para lo cual éste ha de pasar por todos los nodos).

Existen muy diversos algoritmos para comunicar el ID entre los participantes, difiriendo todos ellos en el número de rondas necesarias y de mensajes enviados. Es una asignatura a nivel teórico en la que tenemos que analizar la complejidad temporal y computacional (número de mensajes), distinguiendo mejor caso, peor, y comportamiento medio.

Un algoritmo muy simple es FloodMax, en el cual la complejidad es linear. Dura tantas rondas como el diámetro de la red, y en cada ronda cada nodo envía a todos sus vecinos el máximo valor ID que ha recibido hasta entonces. Así pues, el número de mensajes es simplemente el número de aristas por el diámetro.

Un par de clases después de esto, estaba lo suficientemente aburrido como para pensar en el peor caso de una red de tamaño N, para lo cual el primer paso era saber el máximo número de aristas posibles con cada diámetro existente.

Entonces, para saber el número de mensajes en una red de n nodos con diametro d, se hace msg = d \cdot E(K_n^d) y listo. He hecho un pequeño programita para calcular y mostrar estos valores (Graph.java y Graph.class). Ejecutando “java Graph -v N” imprime información detallada de cada diámetro, y con “java Graph N” escribe sólo los resultados para los cuales el número de mensajes es el mayor.

En realidad, la guinda del pastel sería resolver el problema de optimización para maximizar el valor msg = d \cdot E(K_n^d) \quad \forall d, 1 \le d < n[/latex] pero hasta ahí ya no llego. Consulté ayer a un amigo matemático que finalmente demostró que el máximo valor es siempre en [latex]E(K_n^{n-1})[/latex] y pese a que me indicó algunos de los pasos, no he sido capaz de reproducirlos. Si alguien se anima, [latex]\LaTeX[/latex] está activado también en los comentarios, utilizando $ latex fórmula $ , sin espacio entre “$” y “latex“.

Curso de Astrofísica la semana que viene

Un año más la Agrupación Astronómica de Huesca nos ameniza el verano con una nueva edición de su genial curso de Astrofísica. Bien se vale que se me ha ocurrido mirarlo esta mañana, porque es ya la semana que viene ¡por poco nos lo perdemos!

Lunes, 19 julio: “Astronomía en la Huesca del siglo XVII” por Carlos Garcés.

Martes, 20 julio: “El quinto estado de la materia” por Francisco Palacín.

Jueves, 22 julio: “Las formas de la naturaleza” por Iosu Redín.

Este año hay menos charlas que el pasado, pero seguro que es igual de interesante que anteriores sesiones.

Si no has estado nunca lee mi resumen del curso de astrofísica de 2009, del curso de 2008 y de una de las charlas del de 2007.

Como otros años, nos veremos la semana que viene a las 20 horas en el local de la agrupación en Travesía Ballesteros.

Jornadas R-Project finalizadas

ACTUALIZADO: Están disponibles en internet los videos de todas las charlas.


Como advertía hace un mes, la semana pasada se celebró la I Conferencia Hispana R-Project, unas jornadas que nacieron con la pretensión de reunir y afianzar el grupo de usuarios de R de la comunidad hispanoparlante, objetivos que creo han logrado.

No voy a hacer un resumen del programa, pues de eso ya se encargó Carlos Gil Bellosta hace un par de días con bastante precisión y todo lo que yo dijera sería redundante. De modo que me limito a citarlo (a modo de trabajo colaborativo, como bromeó Francesc Carmona en su blog).

Yo no utilizo habitualmente R, de hecho mi contacto con él se limitó a las prácticas de Estadística en la universidad y al desarrollo de mi PFC; al cual precisamente se debía mi presencia en estas jornadas, pues está hecho de tal forma que cualquiera puede ampliarlo con poco esfuerzo para que distribuya el código que necesite a través de una mini-red de computadores que se cree personalmente.

La verdad es que estaba bastante nervioso (¡nunca había hablado en un congreso!) y no sabía cómo iba a calar la aplicación entre los asistentes, pero parece ser que a algunos les pareció interesante y así me lo hicieron saber; lo cual no deja de ser reconfortante. Dejo enlace al pdf con mi presentación.

Debo decir, que pese a mi escasa relación con R-project, he disfrutado bastante de las charlas. Había gente de todas las áreas, tanto estadísticos puros salidos de matemáticas, como físicos, biólogos, informáticos… La inmensa mayoría pertenecían al ámbito universitario, pero también había una pequeña representación de gente venida de empresas.

El caso es que siempre hay conocimientos transversales, útiles para todos, y como informático también me ha resultado interesante desde el punto de vista de cómo se organiza una comunidad en torno al software libre.

Muchos hablaron de sus comienzos utilizando R, en los que se encontraban prácticamente solos en su entorno —robinsones como alguien definió muy acertadamente— aprendiendo poco a poco con lo que podían encontrar en internet —en inglés, claro— y sintiéndose los bichos raros de su comunidad. Más tarde llegó la lista de R-es y todo empezó a cambiar, hasta la semana pasada en la que empezaron a ponerse caras tras dos o tres años intercambiando mensajes y comenzaron a hablar de proyectos más serios para intercambiar material y conocimientos entre todos.

Casualmente esta tarde leyendo el libro Máquinas que piensan, de Pamela McCorduck he llegado al capítulo en el que relata de forma bastante detallada la que ahora se conoce como Conferencia de Dartmouth, que en 1956 sentó las bases de la investigación en Inteligencia Artificial durante las siguientes dos décadas, y que vertebró, en cierto modo, toda esta disciplina. Digo casualmente, porque esa reunión de miembros aislados de diversas áreas que fueron las jornadas de R, me ha recordado de alguna manera a lo que Pamela relata sobre aquel verano del 56 en el Darmouth College —salvando las distancias, claro—. Dice:

«[…] la Conferencia de Darmouth fue también una confluencia de diversas corrientes intelectuales del siglo XX. Ellos mismos provenían de otras corrientes, del trabajo de individuos aislados en los campos de las matemáticas, la estadística, la psicología, la ingeniería, la biología, la lingüística, y las emergentes disciplinas de la ciencia empresarial. Si algunos científicos no estuvieron presentes en la conferencia, su espíritu estuvo representado por su trabajo y algunas veces por sus colegas y alumnos.»

De algún modo, al leer estas líneas hoy en el autobús hacia la universidad, he sentido que acababa de participar en algo parecido.

El Problema de la Mezcla de Cartas

El verano trae consigo irremediablemente jugar a las cartas más a menudo que de costumbre. Bien sean las noches sentados en el césped, como los descansos del estudio en la biblioteca para el café.

Y si hay algo común a todos los juegos de cartas es barajarlas para poder repartirlas de la forma más aleatoria posible. Me gusta hacer la clásica mezcla que hacen croupiers y magos, tomando dos mitades y dejando caer las cartas intercaladas. A falta de un nombre mejor, la denominaba Mezcla Americana, pero Googleando un poco, parece ser que le llaman Riffle Shuffle.

Un día pensé ¿Y si se hace la mezcla perfecta? Imaginemos que tenemos un dominio tal de la baraja que somos capaces de partir exactamente por la mitad y luego soltarlas una a una, quedando perfectamente intercaladas, una de cada mazo. Entonces me planteé qué ocurriría si se repetía ese proceso varias veces ¿Se volvería a la posición inicial? Y de ser así ¿En cuántas veces?

Quiero que quede claro ya desde aquí que no es una cuestión estadística. No estamos haciendo una mezcla normal, en la que las cartas quedan de forma aleatoria cada vez, sino una totalmente definida y que está claro que siempre será igual. Lo digo ya porque mucha gente a la que se lo he planteado fue la respuesta que me dieron al principio, y es evidente que aquí la probabilidad está fuera de lugar.

Al principio no pasó de un simple pensamiento veraniego, pero dos o tres días después lo recordé estando con mis amigos en un bar y les comenté el problema, así que tras pensarlo un poco empezamos a escribir en una servilleta cómo iba evolucionando el conjunto de cartas. Lo hicimos muy resumido, sólo las primeras y últimas cartas de cada mitad, con puntos suspensivos por en medio, para tratar de imaginar cómo se iba comportando. En que llegamos a la tercera iteración nos dimos cuenta de que era una tarea tediosa y puramente mecánica, así que decidí hacer un programa al día siguiente que lo ejecutase.

La tarde posterior programé lo necesario para hacer las iteraciones, y 56 líneas después empecé a probar resultados. El problema no hubiera pasado de ahí, de no ser porque las soluciones se escapaban de lo predecible. ¿Quién iba a pensar que las veces que hay que barajar no aumentan con el número de cartas? ¿Cómo iba a imaginar que con 40 naipes hacen falta 12 mezclas y con 64 solo 6? Cuantos más conjuntos de cartas probaba, más sorprendido me quedaba.

Así que fui envenenando a diferentes amigos con el problema, picando la curiosidad de todos, hasta que me descubrí buscando las ecuaciones que definen el problema. Desgraciadamente sólo uno se lo está “tomando en serio” y nos estamos quedando sin ideas. Necesitamos un soplo de aire fresco de alguien con nuevas ideas, pues las que teníamos las hemos explotado bastante.

Yo conseguí una ecuación recursiva definida en dos trozos que explicaba a dónde iba la carta, y que aplicándola iterativamente hasta que la posición volvía a ser la original, daba el número de mezclas. Él, matemático, lo analizó como una matriz, aplicando transformaciones y obteniendo la solución como la matriz unidad, con vectores propios y diagonalización. Yo ahora estoy empezando con grafos y me he dado cuenta de que me equivoqué en una premisa inicial, por lo que la fórmula que tenía no es esencialmente correcta. Ahora pongo algunos conjuntos de ejemplo, por si a alguien no le ha quedado claro cómo se mezcla.

Conjunto de 8 cartas. [1, 2, 3, 4, 5, 6, 7, 8]
Vuelta número 1
Primera mitad: [1, 2, 3, 4]
Segunda mitad: [5, 6, 7, 8]
Mazo mezclado: [1, 5, 2, 6, 3, 7, 4, 8]

Vuelta número 2
Primera mitad: [1, 5, 2, 6]
Segunda mitad: [3, 7, 4, 8]
Mazo mezclado: [1, 3, 5, 7, 2, 4, 6, 8]

Vuelta número 3
Primera mitad: [1, 3, 5, 7]
Segunda mitad: [2, 4, 6, 8]
Mazo mezclado: [1, 2, 3, 4, 5, 6, 7, 8]

Así se puede ver como, para 8 cartas, con mezlcar 3 veces, volvemos a la posición de partida.
Copio, ahora, la solución para 52 naipes, la baraja francesa.

Conjunto de 52 cartas.
Vuelta número 1
Primera mitad: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]
Segunda mitad: [27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52]
Mazo mezclado: [1, 27, 2, 28, 3, 29, 4, 30, 5, 31, 6, 32, 7, 33, 8, 34, 9, 35, 10, 36, 11, 37, 12, 38, 13, 39, 14, 40, 15, 41, 16, 42, 17, 43, 18, 44, 19, 45, 20, 46, 21, 47, 22, 48, 23, 49, 24, 50, 25, 51, 26, 52]

Vuelta número 2
Primera mitad: [1, 27, 2, 28, 3, 29, 4, 30, 5, 31, 6, 32, 7, 33, 8, 34, 9, 35, 10, 36, 11, 37, 12, 38, 13, 39]
Segunda mitad: [14, 40, 15, 41, 16, 42, 17, 43, 18, 44, 19, 45, 20, 46, 21, 47, 22, 48, 23, 49, 24, 50, 25, 51, 26, 52]
Mazo mezclado: [1, 14, 27, 40, 2, 15, 28, 41, 3, 16, 29, 42, 4, 17, 30, 43, 5, 18, 31, 44, 6, 19, 32, 45, 7, 20, 33, 46, 8, 21, 34, 47, 9, 22, 35, 48, 10, 23, 36, 49, 11, 24, 37, 50, 12, 25, 38, 51, 13, 26, 39, 52]

Vuelta número 3
Primera mitad: [1, 14, 27, 40, 2, 15, 28, 41, 3, 16, 29, 42, 4, 17, 30, 43, 5, 18, 31, 44, 6, 19, 32, 45, 7, 20]
Segunda mitad: [33, 46, 8, 21, 34, 47, 9, 22, 35, 48, 10, 23, 36, 49, 11, 24, 37, 50, 12, 25, 38, 51, 13, 26, 39, 52]
Mazo mezclado: [1, 33, 14, 46, 27, 8, 40, 21, 2, 34, 15, 47, 28, 9, 41, 22, 3, 35, 16, 48, 29, 10, 42, 23, 4, 36, 17, 49, 30, 11, 43, 24, 5, 37, 18, 50, 31, 12, 44, 25, 6, 38, 19, 51, 32, 13, 45, 26, 7, 39, 20, 52]

Vuelta número 4
Primera mitad: [1, 33, 14, 46, 27, 8, 40, 21, 2, 34, 15, 47, 28, 9, 41, 22, 3, 35, 16, 48, 29, 10, 42, 23, 4, 36]
Segunda mitad: [17, 49, 30, 11, 43, 24, 5, 37, 18, 50, 31, 12, 44, 25, 6, 38, 19, 51, 32, 13, 45, 26, 7, 39, 20, 52]
Mazo mezclado: [1, 17, 33, 49, 14, 30, 46, 11, 27, 43, 8, 24, 40, 5, 21, 37, 2, 18, 34, 50, 15, 31, 47, 12, 28, 44, 9, 25, 41, 6, 22, 38, 3, 19, 35, 51, 16, 32, 48, 13, 29, 45, 10, 26, 42, 7, 23, 39, 4, 20, 36, 52]

Vuelta número 5
Primera mitad: [1, 17, 33, 49, 14, 30, 46, 11, 27, 43, 8, 24, 40, 5, 21, 37, 2, 18, 34, 50, 15, 31, 47, 12, 28, 44]
Segunda mitad: [9, 25, 41, 6, 22, 38, 3, 19, 35, 51, 16, 32, 48, 13, 29, 45, 10, 26, 42, 7, 23, 39, 4, 20, 36, 52]
Mazo mezclado: [1, 9, 17, 25, 33, 41, 49, 6, 14, 22, 30, 38, 46, 3, 11, 19, 27, 35, 43, 51, 8, 16, 24, 32, 40, 48, 5, 13, 21, 29, 37, 45, 2, 10, 18, 26, 34, 42, 50, 7, 15, 23, 31, 39, 47, 4, 12, 20, 28, 36, 44, 52]

Vuelta número 6
Primera mitad: [1, 9, 17, 25, 33, 41, 49, 6, 14, 22, 30, 38, 46, 3, 11, 19, 27, 35, 43, 51, 8, 16, 24, 32, 40, 48]
Segunda mitad: [5, 13, 21, 29, 37, 45, 2, 10, 18, 26, 34, 42, 50, 7, 15, 23, 31, 39, 47, 4, 12, 20, 28, 36, 44, 52]
Mazo mezclado: [1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52]

Vuelta número 7
Primera mitad: [1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50]
Segunda mitad: [3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52]
Mazo mezclado: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52]

Vuelta número 8
Primera mitad: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51]
Segunda mitad: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52]
Mazo mezclado: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52]

De todas las personas con las que he hablado, ninguno había escuchado jamás este problema, así que si ya existe formulado como tal, quizás no sea muy famoso. Aunque este blog no lo lee mucha gente espero que alguien se anime, o se lo contéis a alguien que pueda interesarle, a mí por lo menos me tiene atrapado.

Dentro de un par de semanas o así publicaré todo lo que hemos averiguado hasta ahora, que tampoco es mucho, pero tenemos el problema más o menos cogido por algunos puntos.

Asumo que todos tenéis la máquina Java instalada en vuestro ordenador. Para utilizar el programa que hice tenéis que ir al Símbolo del Sistema (Inicio > ejecutar > cmd > Aceptar), acudir a la carpeta donde lo hayáis descargado y escribir, respetando las mayúsculas javac Mezcla.java con lo que lo compilaréis. Luego, cada vez que queráis ejecutarlo, basta con poner java Mezcla N siendo N=”Número par de cartas a mezclar“. Por ahora suponemos una baraja que se pueda dividir en dos mitades iguales, por lo que ha de ser múltiplo de dos. Si estáis bajo un sistema GNU/Linux (imagino que cualquiera basado UNIX también) podéis redirigir la salida estándar a un fichero de texto, para guardar los datos que saca haciendo:

java Mezcla N >> mezclaN.txt

El arte de la lógica

Al finales de curso, los fines de semana que volvía a casa, iba a la biblioteca pública de Huesca a estudiar —al igual que en verano, navidades y esas fechas preexámenes—. Siempre miro la sección de novedades que cambia constantemente, y descubrí un libro con el título de la entrada, de Carmen García Trevijano. Me pareció interesante así que le eché un vistazo, que me convenció para sacarlo. Ya ha pasado un tiempo desde que lo leí, pero tomé un par de notas para escribir aquí la reseña, así que no dejaré que se me olvide del todo.

Para empezar he de decir que yo no había tenido más contacto con la lógica que la booleana de la que hacemos gran uso los informáticos —y electrónicos— vista en un par de asignaturas (Sistemas Lógicos y Electrónica Digital), y un poco de borrosa en Autómatas. Se supone que formaba parte del temario de Filosofía en 1º de Bachillerato, pero el profesor que tuvimos prefirió enseñarnos a pensar y leer en lugar de limitarse al libro “oficial”.

Tener unos conocimientos básicos de lógica me parecía importante no sólo como informático, sino también como persona racional; y éste libro me ha parecido ideal para aprender desde cero. El libro empieza con la simbología para pasar al Análisis de argumentos y la lógica de predicados, cerrando con un artículo de Louis Couturat, Argumentación silogística; y dos de Stuart Mill, Síntesis lógica tradicional y Cuatro métodos de indagación experimental.

Una de las curiosidades que más me llamó la atención fue de la que se percató Duns Scoto sobre una propiedad de las disyuntivas que afirma que: «Es formalmente correcto inferirla unión disyuntiva de una proposición con cualquier otra que se nos antoje». Con lo cual:

«Si contamos con una disyunción y, por otro lado, con la contradictoria de una de sus partes, es formalmente correcto concluir afirmando la parte que resta de esa disyunción.»

Esto se ejemplifica con la frase: «Sócrates corre y no corre, luego tú estás en Roma».
Que formalmente se representa, para A=”Sócrates corre” y B=”Tú estás en Roma”, así:

1:
2: ; (Regla de simplificación sobre 1) Si A y no A es cierto, entonces A es cierto.
3: ; (Regla de adición a 2) Si A es cierto, también A o B es cierto.
4: ; (Regla de simplificación en 1) Si A y no A es cierto, entonces no A es verdad.
5: ; (Silogismo disyuntivo con 3 y 4) Si A o B es verdad, pero A no lo es (no A es cierto), entonces necesariamente, B ha de ser cierto.

Todo esto entre paréntesis son las reglas y tautologías que se aplican en la Lógica formal para realizar el razonamiento a partir de unas premisas. Si tenéis interés en conocerlas, en ésta página las he recordado y está muy bien explicado. Os la recomiendo si queréis un buen punto con el que comenzar o recordar conceptos olvidados.

De este modo hemos demostrado que si Sócrates corre (A) y Sócrates no corre (no A), es cierto que Tú estás en Roma (B). Obviamente es una conclusión absurda, pero es un ejemplo de a lo que se puede llegar partiendo de premisas falsas, todo sin violar las leyes de la lógica.

(Maldita sea, creo que tendré que poner el filtro para el WordPress, es la única forma decente cada vez que necesito poner fórmulas . No obstante, me he valido de la URL que utiliza el plugin para poner las imágenes directamente.)

También, a raíz de la paradoja de Aquiles y la tortuga de Zenón se sirve para hablar sobre el infinito y diversas soluciones a la misma que se han dado a lo largo de la historia. Os recuerdo que es la de que Aquiles, el mejor corredor de Grecia, jamás podrá alcanzar a una tortuga moviéndose delante de él puesto que ha de recorrer la mitad del camino, y luego la mitad de la mitad y la mitad de lo restante, y… por lo que siempre habrá espacio entre él y la tortuga por más rápido que vaya; y nunca la alcanzará.

Es obvio que no ocurre así, y a muchos matemáticos y filósofos se han devanados los sesos para explicar formalmente porqué. Matemáticamente se puede modelar como la infinita suma de la mitad, y la mitad de la mitad…

Con los conocimientos actuales sobre series y sucesiones sabemos que ésta es convergente y tiende a 1, lo cual significa que la infinita suma de mitades de algo da ese algo, de modo que Aquiles sí que termina por recorrer la distancia inicial.

Otra explicación, a mi juicio muy buena, que dió el filósofo británico Thomas Hobbes en su obra De Corpore fue:

«Dividir infinitas partes no es sino ser dividido en tantas partes como se desee. Pero no es necesario que una línea tenga infinitas partes, ni que sea infinita, porque puedo subdividirla tanto como quiera, y por muchas partes que haga, su número será finito.»

Otra reflexión sobre el concepto de infinito es que antes se creía que un conjunto infinito tenía que tener al menos uno de ambos extremos abiertos, imposibilitando así que tuviera un primer y últimos elementos. Sin embargo, podemos ver que no es así con los reales comprendidos en, por ejemplo, el intervalo [1, 2], los cuales son infinitos pero, obviamente, tiene un principio y un final.

Un libro en fin, interesante, que toca varios temas, y que me gustó y me hizo aprender un poco sobre la formalización de la lógica. Lo recomiendo sólo para quién esté realmente interesado. Además, al final de cada capítulo incluye una extensa lista de problemas con sus soluciones para practicar en el tema.

Sobre la autora, decir que Carmen García Trevijano aparte de escribir sus propias obras, se dedica principalmente a la traducción del inglés, francés y alemán al español, contando en sus trabajos con autores como David Hume, Karl Popper, Arthur Schopenhauer o Bertrand Russell entre otros.

Como casualidad, empecé a escribir esto hace dos días, y justo ayer apareció en el recién estrenado El Cedazo una Introducción a la lógica.Que continúa hoy con una explicación a los axiomas de Peano para la construcción de Los números naturales. El Cedazo es un blog comunitario creado por Pedro, de El Tamiz —genial blog sobre cienca que creo que aún no había recomendado por aquí pese a seguirlo ya hace unos meses—, con la idea de que sean los propios lectores los que envíen sus artículos explicando temas de su especialidad que quizás escapan un poco de la temática de El Tamiz, pero con la misma filosofía de tratar de explicar ciencia sin fórmulas y para que cualquiera, como yo, pueda entenderla. Recomiendo ambos. Además, El Cedazo parece haber tenido un gran éxito inicial, pues en sus seis primeros días ya lleva ocho artículos.

Espiritismo

  1. Desde un punto de vista intelectual, las almas de los muertos entran en una condición que, si hemos de juzgar por las producciones que consignan en las pizarras de los médiums, debe ser calificada de muy lamentable. Estas escrituras pertenecen por completo a la categoría de la imbecilidad; carecen de todo contenido.
  2. Lo más favorecido, por lo visto, es la condición moral del alma. De acuerdo con el testimonio que poseemos, de su carácter sólo puede decirse que es inofensivo. Los espíritus, de la manera más educada, se abstienen de comportamientos bárbaros, tales, por ejemplo, como destruir los doseles de las camas.
  3. Desde un punto de vista físico, las almas de los muertos caen bajo servidumbre de algunos seres vivos que se llaman médiums. Estos médiums constituyen, al menos hasta el presente, una clase no demasiado extendida y parecen ser casi exclusivamente norteamericanos. Bajo sus órdenes, las almas de los difuntos realizan hazañas mecánicas que poseen en todo respecto el carácter de la más absoluta inutilidad. Dan golpes, levantan mesas y sillas, mueven camas, tocan la armónica y hacen otras cosas similares.

Wilhelm Wund, Espiritismo, una cuestión llamada científica, 1889.

Aparece como nota del autor en el libro La cuarta dimensión, de Rudy Rucker, que me estoy leyendo ahora. Parece ser que a finales del siglo XIX se puso muy de moda la idea de que los fantasmas pudiesen ser seres del hiperespacio. Me ha gustado esta pequeña crítica a los médiums.

Curso de Astrofísica en Huesca 2008

El año pasado descubrí que la Asociación Astronómica de Huesca llevaba desde hace doce años haciendo cada verano unos minicursos de astrofísica en forma de pequeñas charlas. Acudí a las tres, disfrutando en todas ellas. De la primera, sobre matemáticas, escribí una reseña.

Al principio de este verano recordé que debía estar atento en estas fechas para volver a acudir, pero me despisté y casi se me pasa. Bien se vale que a RJ no se le ha escapado y ha publicado la noticia en Pirineos7.

En el curso de este año hacen una charla más que el año pasado, quedando un total de cuatro.Repiten dos de los ponentes de la anterior ocasión: Julio Bernués, profesor de matemáticas que dio la amena charla de Experimentos Matemáticos, este año dará una sobre Curvas el jueves 31; y Francisco Palacín, que reflexionó sobre ¿Por qué es oscuro el universo?, que responderá a la pregunta ¿Existen los agujeros negros?.

En la de esta tarde —recuerdo que son todas a las 20:00— Angel Biarge nos explicará los detalles de la Construcción de telescopios por aficionados y el viernes 1 Daniel hablará sobre Estrellas domésticas: fusión nuclear por confinamiento magnético.

Sobre la charla de Curvas, revisando lo que escribí el año pasado, ya nos habló sobre el cicloide, la parábola y la braquistocróna, así que a ver con qué nos sorprende este año. A los que les asusten las matemáticas que no hagan como uno que yo me sé y el curso de Jaca al que fui hace poco: son charlas de carácter divulgativo, y para nada formales; no hace falta apenas formación matemática.

La de Palacín, en cambio, fue algo más dura, abstrayéndose hasta las ecuaciones de campo de Einstein, el tiempo de Planck (primeros momentos del universo) y temas del estilo. Aún así logramos entender algunas cosas y siempre te quedas con algo. A ver qué nos cuenta esta vez sobre los agujeros negros.Este año cuento con la ventaja de haber leído recientemente Hawking y los agujeros negros, que siempre ayuda saber algo del tema.

En fin, os recomiendo a todos los que os interese el tema acercaros hoy a las 20:00 por el local de la Agrupación Astronómica en Travesía Ballesteros 6.

Matemáticas celestiales y terrenales

Hoy mismo he vuelto Ayer volví del curso de matemáticas con el mismo título de esta entrada y que comentaba en el último post. Y la verdad es que he salido bastante contento.

Para empezar, debo destacar el buen ambiente que se respiraba entre todo el mundo, tanto los ponentes como los alumnos. Entre estos últimos había una abrumadora mayoría de físicos y matemáticos, y algún bala perdida como yo (otro informático, una química, un par de economistas…). Los primeros eran muy cercanos, e incluso fuimos a tomar unas cervezas con algunos de ellos.

Como predije, en unas charlas con el caracter divulgativo y ameno con que se anunciaban, se han tocado muchos de los temas que leí en La poesía del Universo; así como los que se pueden encontrar en blogs como Gaussianos o Historias de la ciencia.

Las charlas del primer día, impartidas por Luis Floría Gimeno —profesor de Geodesia de la Facultad de Físicas de Zaragoza—, casi asustaban como primer contacto con el curso, pues es un físico teórico que preparó las charlas pensando en un público más especializado, pese a que bajó el nivel e intentó reconducirlas para respetar ese carácter entretenido y básico que se buscaba con el curso. Así pues, pese a ser un tema algo duro, lo fue explicando con gran detalle y detenimiento y creo que no hubo mayor problema en seguirle.

Dada su especialidad, sus charlas se centraron en los temas estudiados por la Geodesia, para determinar la forma y dimensiones de la Tierra, como pueden ser su estructura física y los campos gravitatorios y magnéticos a los que está sometida. También estudia su representación. La parte tan técnica de la que hablaba antes se debe a que explicó minuciosamente el método de los mínimos cuadrados —muy usado actualmente en estadísica— y reivindicando su origen en las Misiones Geodésicas enviadas por la Academia Francesa (y con colaboración española) en 1735 a dos puntos extremos del globo terráqueo para calcular su achatamiento (por entonces se sabía que existía, pero no en qué sentido: estirada o achatada por los polos). Más tarde Gauss se basó en este método para predecir la posición del asteroide Ceres con muy pocas observaciones, predicción que le llevó a la fama. Quizás se centró mucho en explicar el método —para una, dos, tres, n variables— dejando de lado otros temas, pero se le siguió bien y abordó cuestiones interesantes.

La siguiente exposición vino de la mano de Manuel Membrado explicando las diferentes curiosidades de los cuerpos del sistema solar y yéndose cada vez más lejos analizando las posiciones de las estrellas, galaxias, grupos y cúmulos más cercanos a nuestra posición. Esta charla servía de presentación a la posterior escapada ese mismo día para realizar una observación del cielo nocturno en la explanada del Monasterio de San Juan de la Peña (el nuevo). Disfruté mucho porque hace años que esperaba que alguien me explicase alguna constelación. Supongo que podría haber cogido algún mapa celeste en cualquier momento, pero me ha dado una tremenda pereza toda mi vida. Me gusta mucho mirar el cielo estrellado, y siempre se disfruta todo mucho más si sabes algo al respecto, como está organizado, etcétera. Además, gracias a su telescopio pudimos ver algunos cuerpos como galaxias, cúmulos, nebulosas y Júpiter. Con el planeta me quedé muy impresionado pues para la mayoría había que poner demasiada fé; pero en él, aparte de distinguir tres de sus satélites, se distinguían claramente varias franjas de diferentes tonalidades de azul verdoso, destacando especialmente el brillante central. Además, luego con los prismáticos conseguías diferenciar los satélites al saber dónde mirar.

Pedro José Miana, como organizador, también nos dió varias conferencias (una de ellas en el Ayuntamiento con asistencia libre para todo el público). En ellas tocó varios temas más filosóficos en los que pedía nuestra colaboración para debatir: ¿Son las matemáticas un lenguaje universal? ¿Saben contar los animales? ¿Toda la naturaleza es número? Y también habló de curiosidades del número φ (la proporción áurea), la sucesión de Fibonacci, números primos, fractales, más Gauss, teselaciones, la conjetura de Kepler… y algún otro asunto similar.

El último de los ponentes fue Miguel Vallejo, subdirector del Real Instituto y Observatorio de la Armada en San Fernando (Cádiz). En las distintas charlas nos explicó la historia del mismo y los temas tan diversos que estudia el observatorio. Nació a mediados del siglo XVIII en cuyos años la astronomía era una importantísima ciencia para la navegación, pues dependían del buen conocimiento de los astros para conocer su posición. Desde entonces, tienen la obligación de elaborar el Almanaque Náutico que toda nave ha de poseer (es una publicación regular puesto que la posición de los astros cambia cada año). Dado que tenían que conseguir unas buenas observaciones nocturnas, tuvieron que desarrollar buenos conocimientos en meteorología para saber cuándo podían mirar el cielo y, lo que es más importante, saber cómo las partículas atmosféricas modificarían la correcta visualización de los astros por la refracción. Es por esto que, además de ser el primer observatorio español (y tercero o cuarto del mundo), fue también el primer observatorio meteorológico en España (aunque ya han dejado esa tarea). Además del Almanaque también están realizando un completo y amplio catálogo de cuerpos celestes de la franja de +60º a -60º, que es la que pueden observar gracias a sendos telescopios en Canarias y Argentina.

El principal problema de la situación en alta mar durante toda la historia fue determinar la longitud (la latitud, más trivial, estaba resuelta hace años) y estaba demostrado que para solucionarlo se requería de precisos relojes que funcionasen en alta mar, y que cuando llegaban al puerto debían poner en hora con los del Observatorio. Esto, aparte de conducir a la creación de los relojes mecánicos en una interesante historia que también nos contó, llevó a que en el ROA fuesen adquiriéndose relojes cada vez más precisos. Así, actualmente cuentan con seis relojes atómicos y son los encargados de dar el patrón de hora oficial en España. Es un tema interesante porque al estar “creando el tiempo” mediante impulsos atómicos, pueden tener pequeños errores, por lo que se hace la media de todos los relojes atómicos que poseen. Pero luego, una vez al año, todos los países comparan los tiempos medios de sus relojes entre sí, estableciendo el Tiempo Unificado Coordinado (UTC). Pero no cualquier país sirve para establecer el UTC, sino sólo los que posean los relojes más exactos que se aproximen más al UTC válido. Todo un mundo, vaya. Por cierto, estos errores en la medida del tiempo de los que hablo son de nanosegundos (10-9 segundos). Por todo esto, el ROA tiene un servidor UTC con el que cualquiera puede sincronizar su computadora (hora.roa.es). Y aquí podéis comprobar la diferencia entre su hora y la vuestra.

¿Y para qué se necesita tanta precisión? Para situar un barco en alta mar con la hora y los minutos es más que suficiente, sin embargo, en la cúpula del observatorio tienen desde mediados del último siglo una estación láser utilizada para calcular la posición de satélites artificiales geoestacionarios. Por ello fue también el primer lugar en España en realizar seguimiento de satélites. Se necesitan estas precisiones, decía, porque para determinar la posición del satélite se envía un haz que rebota en una placa el mismo y sabiendo el tiempo que tarda en volver, es trivial resolver la distancia que nos separa del mismo. Y claro, a esas distancias y velocidades, con precisiones de picosegundos se consiguen márgenes de error de unos pocos centímetros.

También se dedican a diversos temas geodésicos como estudio del magnetismo, movimientos sísmicos y de las placas tectónicas, para los cuales obtienen lugares idílicos para situar las estaciones en, por ejemplo, muchos de los peñones y pequeñas islas a los que sólo tiene acceso el Ejército de España.

Todas estas charlas han sido más o menos en el orden expuesto aquí, salvo porque las de cada ponente se dividían en varias partes y Pedro Miana intercalaba las suyas entre medio. Tras este tostón, sólo puedo resumir que fue una experiencia positiva en la que he aprendido muchas cosas, recordado y mejorado otras y que, sobre todo, he disfrutado y me lo he pasado bien.

Pedro ha asegurado que seguirá haciendo cursos de verano sobre matemáticas (obviamente) a los que os animo a todos los que os gusten a acudir, sin tener miedo por no ser demasiado buenos con ellas, pues el nivel es claramente divulgativo y no hay problemas para seguirlas. Además de que se enfocan de forma amena y entretenida y no academicista y formal.