El Fractal Definitivo

Matemáticos del mundo, dejad de buscar fractales. Hete aquí el fractal definitivo:

(Vía Useful Zero)

Las 20 Ecuaciones Más Importantes

En physicsworld realizaron hace tres años una encuesta para hacer una lista con las 20 ecuaciones más importantes de la historia. Sí, lo veo a estas alturas :-)

Las ganadoras fueron:

1. 4 ecuaciones de Maxwel:
   1. ∇·D=ρ
   2. ∇·B=0
   3. ∇xE=-∂B/∂t
   4. ∇xH=-∂D/∂t+J
2. Identidad de Euler: e^iπ+1=0
3. Segunda Ley de Newton: F=m·a
4. Teorema de Pitágoras: a²=b²+c²
5. Ecuación de Schrödinger: HΨ=EΨ
6. 1+1=2
7. Equivalencia masa-energía: E=mc²
8. Constante de Boltzmann: S=k·ln(W)
9. Principio de mínima acción: δS=0
10. Hipótesis de De Broglie: p=h/λ
11. Transformada de Fourier: F(ξ)=(2π)^-1/2∫f(x)e^-iξxdx
12. Ecuación de campo de Einstein: G_μv=8πGT_μv
13. Longitud de circunferencia: C=2πr
14. Ecuación de Dirac: iγ·∂ψ=mψ
15. Producto de Euler: ζ(s)=∏[p^s/(p^s-1)]
16. Ley de Hubble: v=H₀d
17. Regla de tres: a/b=c/d
18. Ley de los gases ideales: PV=nRT
19. Líneas de Balmer: 1/λ=R(1/n₁²-1/n₂²)
20. Ley de Plank: E=hv

Me ha hecho gracia que aparezca 1+1=2, porque aunque pueda parecer una tontería, es fundamental. ¿Echáis en falta alguna? Yo creo que habría puesto la ecuación ara el área de un rectángulo: S=b·h.

El Teorema de los 4 Colores Aplicado a los Compiladores

El Teorema de los 4 Colores establece que cualquier plano dividido en regiones contiguas puede ser coloreado usando 4 colores, de forma que dos regiones adyacentes cualesquiera (que tengan un borde en común, no sólo un punto) tienen colores distintos. Por ejemplo, el siguiente plano dividido puede colorearse con sólo 4 colores:

Aunque hay casos en que es posible colorear un plano de forma válida usando menos colores, el teorema se sigue cumpliendo, ya que dice que hacen falta como mucho 4. Una aplicación directa de este teorema se encuentra en la cartografía y el coloreado de mapas políticos. Sin embargo, este teorema es bastante más importante que sólo eso, y es que además se mantuvo sin demostrar desde 1852 hasta que en 1976 se convirtió en el primer gran teorema demostrado por computador, si bien hay quien se mostraba reacio a ello por aquello de suponer la correción del programa, compilador y hardware.

Enunciado Formal en Teoría de Grafos

En teoría de grafos, el problema se puede formular convirtiendo el mapa en un grafo plano tal que cada región es un vértice y las aristas van desde los vértices que se corresponden con regiones adyacentes. La solución sería aquella en la que cada vértice tiene un color, de forma que dos vértices adyacentes no tengan el mismo color.

La demostración, que en 1976 llevaron a cabo Kenneth Appel y Wolfgang Haken se basó en demostrar que no existía ningún vértice adicional para ningún grafo tal que fueran necesarios 5 colores. Por ello, se dice que un grafo plano correspondiente a un mapa es, como mucho, un grafo 4-coloreable.

En general, un grafo es k-coloreable si necesita k colores como mínimo para ser coloreado. A este número se le llama número cromático del grafo, y se representa con la letra χ. El problema de calcular el número cromático de un grafo es NP-duro, aunque existen distintos algoritmos de clase P que se basan en ciertas asunciones para tipos concretos de grafo.

Coloreado de Grafos en Compiladores

La aplicación de la coloración de grafos en compiladores es una de las cosas que me dejó sorprendido cuando lo estudié, por el ingenio del que se hace gala. Cuando un compilador ha calculado ya la serie de instrucciones para máquina abstracta, el siguiente paso es asignar los registros de la CPU a cada variable, teniendo en cuenta cuando se necesita cada una y cuando deja de utilizarse, para optimizar la ejecución al máximo y acceder a memoria el menor número de veces posible, agilizando así la ejecución.

La forma usual de resolver este problema empieza con un análisis de flujo, del que se calcula el llamado grafo de interferencia. Por ejemplo, dado el siguiente código que empieza con las variables k y j, y termina con las variables d, k y j:

1. k, j
2. g = mem[ j + 12 ]
3. h = k -1
4. f = g * h
5. e = mem[ j + 8 ]
6. m = mem[ j + 16 ]
7. b = mem[ f ]
8. c = e + 8
9. d = c
10. k = m * 4
11. j = b
12. d, k, j

la cosa consiste en ir desde el final hasta el principio, marcando por cada variable cuales son las transiciones en las que es necesario guardar su valor. Por ejemplo, d es necesaria en la transición 11→12, ya que su valor debe ser devuelto en el estado 12. Paso a paso hacia atrás, se ve que en el estado 9 se le asigna un valor, por lo que ha de mantenerse hasta el estado 12. Si continuamos hacia atrás, se ve que no es usada anteriormente, por lo que se concluye que d debe mantenerse en las transiciones 9→10→11→12. De forma parecida, j debe mantenerse en 11→12, ya que es en 11 donde se le asigna un valor. Sin embargo, retrocediento puede verse que desde el estado 1 es usada hasta el estado 6, a partir de donde su valor puede desecharse hasta el estado 11. Así pues, j debe mantenerse en las transiciones 1→2→3→4→5→6 y 11→12. Continuando con cada variable, construimos la siguiente matriz de interferencia:

Matriz que, a su vez, se corresponde con el siguiente grafo de interferencia, en donde cada vértice es una variable y las aristas unen las variables que están vivas al mismo tiempo y, por tanto, deben estar en registros distintos de la CPU:

Como se ve, el grafo puede colorearse de forma válida con 4 colores. La idea detrás de este grafo es que dos vértices adyacentes contienen variables que deben guardarse en registros distintos. Así, el color asignado a cada vértice se corresponde con un registro de la CPU, y por ello ambos vértices deben tener colores distintos.

De esta forma, 4 registros son válidos para el anterior programa, asignando cada variable al registro de color correspondiente. En general, si la CPU tiene n registros y el número cromático del grafo de interferencia es m, no será necesario llevar variables a la memoria RAM si m es menor o igual que n. Sin embargo, una parte que nos hemos saltado es la de optimización del código. Dejando de lado aquello de que hay operaciones no necesarias (la verdad es que las instrucciones del ejemplo son bastante enrevesadas), un punto a tener en cuenta es que j actúa como dos variables distintas: j₁ entre 1→2→3→4→5→6 y j₂ entre 10→11→12, ocurriendo lo mismo con k. Tomando ventaja de ello, la matriz de interferencia (y el correspondiente grafo) puede colorearse de la siguiente forma:

Como se ve, ahora son necesarios sólo 3 registros. En particular, el grafo optimizado con j₁, j₂, k₁ y k₂ es 3-coloreable, mientras que el que usa j y k es 4-coloreable. De hecho, puede apreciarse que j usa colores distintos en la matriz de interferencia optimizada, debido a que se consideran 2 variables distintas (ocurriendo lo mismo con k). El problema de calcular el número cromático en estos casos es más sencillo, porque es el mayor número de variables que estén vivas en una misma transición (número de variables vivas en una misma columna de la matriz de interferencia). En el ejemplo podemos ver que cada columna tiene como máximo 3 variables vivas, así que 3 registros son suficientes para el programa.

Día de Pi

Hoy 14 de Marzo es el día de π, porque en el mundo anglosajón se escribe primero el mes y luego día (y no sabéis lo que cuesta acostumbrarse a ello). Así que nada, feliz día de pi.

En Gaussianos se pueden encontrar unas cuantas curiosidades al respecto.

Actualización (22 de Julio de 2007): En TotumRevolutum proponen el 22 de Julio como día de π para los no anglosajones, ya que el 22 del 7 es 22/7, que es 3.1428… una buena aproximación de π.

Avances en Escritura de Números

Pues resulta que en el foro de softoniqueros me encuentro una foto de un cheque:

y la verdad es que le manda narices la gente. Pero lo curioso es que esto recuerda mucho a la Identidad de Euler de la que ya hablamos en su día:

e^iπ+1=0

Y es que el sumatorio del cheque, si no me equivoco, es igual a 1. Así pues, la suculenta cantidad a pagar sería:

0.002+e^iπ+1=0.002

Por cierto, la pregunta que hace mejor no la traduzco :-) Curioso cuanto menos, oiga.

Actualización (14 de Marzo de 2007): El mundo es un pañuelo. Tanto que el dueño de Softoniqueros estudia en mi antigua Universidad :-)

Nuevo Récord Guinness de Decimales de π

El mes pasado hablábamos de Akira Haraguchi, que batió el récord mundial de recitar decimales del número pi de memoria: llegó a 100.000. La cosa es que hoy, leyendo La Flecha, he visto que se ha batido el Récord Guinness con 67.890 decimales, y claro, me ha extrañado.

Y aquí es donde viene la explicación. Resulta que ni la vez que Haraguchi recitó 100.000 decimales ni la vez que recitó 83.431 (Julio de 2005) fueron registradas por la Guinness World Records, con lo que el Guinness lo seguía teniendo Hiroyuki Goto con 42.195 decimales en 1995.

Así que el chino Lu Chao aprovechó para batir el Record Guinness el pasado 19 de noviembre de 2005 con un total de 67.890 decimales. El resultado se ha terminado de comprobar ahora —que son 67.890 números, oiga— y le ha sido concedido el Guinness finalmente. La pregunta es: ¿A qué aspira Akira Haraguchi?

Degeneramos.

La Circunferencia de Feuerbach

Una de esas cosas que seguramente nunca nos contaron en el colegio: la Circunferencia de Feuerbach. Para decirlo rápidamente, es una circunferencia que se obtiene a partir de un triángulo cualquiera. Para por el punto medio de sus lados, por la intersección de cada altura del triángulo con sus lados opuestos y además por el punto medio de cada segmento que une el ortocentro del triángulo y sus vértices. Y además, para más inri, su centro es el punto medio del segmento que une el ortocentro y el circuncentro del triángulo.

Curioso, oiga.

(Vía Gaussianos)

La Identidad de Euler

e^iπ+1=0

Sin duda, una de las fórmulas más bellas, especialmente por su demostración y porque

Relaciona los que podríamos considerar como los cinco números más importantes de las matemáticas: e, π, i, 0 y 1.

La demostración se puede encontrar en Gaussianos.

(Vía Gaussianos)

Euler

Sacado de la entrada de la Wikipedia sobre Euler:

Euler ya empleaba las series de Fourier antes de que el mismo Fourier las descubriera [...]

Esto no nos lo contaban en clase, además de otras tantas cosas curiosas sobre Euler.

(Vía Gaussianos)

¿Resuelto otro Problema del Milenio?

Si hace poco se montó mucho revuelo por la demostración de la conjetura de Poincaré (ahora teorema de Poincaré-Perelman), el rechazo de la medalla Fields por parte de Grigori Perelman y el supuesto plagio de otros, ahora le toca el turno a las ecuaciones de Navier-Stokes.

Y puede que a más de uno le dé igual, pero se trata de otro de los siete problemas del milenio, considerados como los más difíciles porque algunos de ellos llevan siglos sin haber podido ser demostrados o refutados. Además, aparte del reconocimiento de la comunidad matemática que resultaría de resolver alguno de ellos, el Clay Mathematics Institute premia con un millón de dólares por cada uno de ellos. Y además, esta vez la solución no viene de un, sino de una matemática: Penny Dorothy Smith, que ha publicado su trabajo en el arXiv.

Como dice ^DiAmOnD^ en Gaussianos:

Parece ser que las grandes barreras científicas siguen cayendo.

(Vía Gaussianos)

100000 Dígitos del Número π

La gente se aburre…y Akira Haraguchi se aburre aun más. Este japonés tenía el récord de decimales del número pi recitados de memoria: 83.431. Pues ahora ha vuelto a aumentar la cifra a 100.000 decimales, para lo que ha necesitado más de 16 horas.

<sarcasmo type="soy el más guay">

Si todavía estuviesen la Obregón y Ramón García en el Qué Apostamos, bueno… ¡la que se iba a armar! Ríete tú de aquél que se dedicaba a multiplicar chorizos de números.

</sarcasmo>

Degeneramos.

(Vía Gaussianos)