En el post anterior hemos discretizado un sistema de ecuaciones donde únicamente aparecen primeras derivadas.

Para que quede claro lo que queremos decir, vamos a trabajar con la ecuación genérica

\frac{d}{dx}u = f(u,x)

Ya en el punto de la discretización necesitamos comentar dos cosas. Por una parte, dado que queremos escribir el método iterativamente, necesitamos que en la discretización aparezca un término con el punto actual. En caso contrario, no podemos despejar la variable en el punto actual. De esta manera, para la discretización de la primera derivada a orden uno hacia atrás, tenemos:

\frac{u_{i} - u_{i-1}}{h} = f(u,x) \Leftrightarrow u_i = h f(u,x) + u_{i-1}

Y en diferencias hacia adelante, nos encontramos con:

\frac{u_{i+1} - u_i}{h} = f(u,x) \Leftrightarrow u_i = u_{i+1} - h f(u,x)

Sin embargo, si utilizamos la aproximación a orden dos centrada, tenemos

\frac{u_{i+1} - u_{i-1}}{2h} = f(u,x)

nos encontramos con que no podemos despejar u_i para implementar la iteración ya que este termino no aparece en la ecuación.

Pero no solo eso. Además, la discretización que utilicemos debería dar lugar a una matriz con todos los autovalores con el mismo signo, para que una iteración tipo Jacobi pueda aplicarse. La primera discretización y la segunda cumplen esta propiedad (dan lugar a una matriz con 1 en la diagonal y -1 arriba o abajo de la diagonal en función de la discretización escogida). La última, sin embargo, da lugar a una matriz con todos los autovalores complejos (0 en la diagonal, 1 y -1 arriba y abajo de esta).

 

Asumiendo una estrella con simetría esférica y en complete equilibrium (hydrostatic equilibrium + thermally adjusted), las ecuaciones diferenciales básicas que nos darán su estructura son:

\frac{\partial}{\partial m}r = \frac{1}{4 \pi r^2 \rho}

\frac{\partial}{\partial m}P = - \frac{G m}{4 \pi r^4}

\frac{\partial}{\partial m}l = \varepsilon_n + \varepsilon_\nu

\frac{\partial}{\partial m}T = - \frac{G m T}{4 \pi r^4 P} \nabla

donde \nabla = \frac{d \ln T}{d \ln P}. Queremos encontrar funciones solución para la distancia radial r(m), para la presión P(m), para la energía l(m) y para la temperatura T(m) donde 0 \leq m \leq M, siendo M la masa total de la estrella. Necesitamos conocer los valores en la frontera de las funciones incógnita, esto es, r(0), P(0), l(0), T(0),  r(M), P(M), l(M), T(M). A través de la relación de operadores

\frac{\partial}{\partial m} = \frac{1}{4 \pi r^2 \rho} \frac{\partial}{\partial r}

deberíamos de recuperar las ecuaciones de la hidrodinámica en steady-state expresadas en su forma habitual.

Podemos discretizarlas a primer orden:

\frac{r_{i} - r_{i-1}}{\Delta m} = \frac{1}{4 \pi r_{i/2}^2 \rho_i}

\frac{P_{i} - P_{i-1}}{\Delta m} = - \frac{G m_i}{4 \pi r_{i/2}^4}

\frac{l_{i} - l_{i-1}}{\Delta m} = (\varepsilon_n)_i + (\varepsilon_\nu)_i

\frac{T_{i} - T_{i-1}}{\Delta m} = - \frac{G m_{i} T_{i/2}}{4 \pi r_{i/2}^4 P_{i/2}} \nabla_{i/2}

Si despejamos las variables en el punto i de la discretización, obtenemos:

r_{i}^{*} = \Delta m \frac{1}{4 \pi r_{i/2}^2 \rho_i} + r_{i-1}

P_{i}^{*} = - \Delta m \frac{ G m_i}{4 \pi r_{i/2}^4} + P_{i-1}

l_{i}^{*} = \Delta m [ (\varepsilon_n)_i + (\varepsilon_\nu)_i] + l_{i-1}

T_{i}^{*} = - \Delta m \frac{G m_{i} T_{i/2}}{4 \pi r_{i/2}^4 P_{i/2}} \nabla_{i/2} + T_{i-1}

y con esto, podemos obtener esquemas con factor de relajación:

r_{i}^{k} = (1 - \omega) r_{i}^{k-1} + \omega r_{i}^{*}

P_{i}^{k} = (1 - \omega) P_{i}^{k-1} + \omega P_{i}^{*}

l_{i}^{k} = (1 - \omega) l_{i}^{k-1} + \omega l_{i}^{*}

T_{i}^{k} = (1 - \omega) T_{i}^{k-1} + \omega T_{i}^{*}

 

Este es el título de mi tesis para optar al grado de Doctor en Física. La defensa será el próximo día 19 de Julio a las 12h en el Salón de Grados “Manuel Valdivia” de la Facultat de Ciències Matemàtiques de la Universitat de València. Estáis todos invitados 😉

Cuando estudiaba en la universidad había toda una secuencia de asignaturas (Introducción a los Computadores, Estructura de Computadores I, Estructura de Computadores II, Arquitectura de Computadores, Multiprocesadores, Arquitecturas Vectoriales…) en las que nos enseñaban a “diseñar” un ordenador desde cero, llegando a ser tan complejo como podamos imaginar. Empezamos con circuitos combinacionales (puertas lógicas, comparadores, (semi)sumadores, (de)multiplexores, (de)codificadores, ROMs, PAL, PLA, PLDs, etc.) que se caracterizaban porque su salida solo dependía de la entrada en ese momento y que nos permitían construir, entre otras cosas, Unidades de Proceso, de las que forman parte las  Unidades Aritmético Lógicas o las Unidades de Coma Flotante (es en estas donde se ejecutan las instrucciones del lenguaje máquina de nuestro ordenador);  seguíamos con circuitos secuenciales (biestables, contadores síncronos y asíncronos, registros serie/paralelo, RAMs, etc.) cuya salida dependía además del estado en el que se encontraba un sistema cuando le llegaba la entrada (una máquina de estados) y que nos permitía saber hacer, entre otras cosas, la Unidad de Control y las memorias; y de aquí a diseño de procesadores (cableados o microprogramados), buses, memorias cache, lenguajes máquina, procesadores aritméticos, segmentación de procesadores…

Cuando diseñas lenguajes máquina, estos deben contener conjuntos de instrucciones para manejar diferentes tipos de datos, y uno de los tipos indispensables en infinidad de campos son los reales. Por una parte, esos reales van a tener que operarse en procesadores aritméticos, y por otra, los compiladores deben traducir instrucciones de lenguajes de mas alto nivel que contengan reales a instrucciones del LM. Es por toda esta interrelación entre diferentes niveles de abstracción que se hizo necesaria la especificación de un estándar (algo que todo el mundo va a cumplir si quiere continuar en el juego): el estándar IEEE 754.

Está claro que en unas aplicaciones, por ejemplo a nivel de átomos, vamos a necesitar números reales muy pequeños, mientras que en otras, si trabajamos con estrella o con galaxias, lo que necesitaremos son reales extremadamente grandes. Es por este motivo que se adopta una representación en coma flotante (notación científica donde tenemos una mantisa, una base y un exponente) frente a una representación de punto fijo mucho mas intuitiva al principio.

Si solo utilizáramos naturales, con el binario nos apañaríamos, pero en el cuanto que aparecen los enteros, necesitamos representar el signo mas y el signo menos también con ceros y unos. Ésto nos lleva a tener que reservar un bit para el signo, puesto que el número total de bits siempre va a estar determinado de antemano, y a los conceptos de representación explícita y valor representado.

Para concretar ideas, supongamos el caso sencillo de que tenemos tres bits. Los números binarios representados, los valores explícitos del sistema de representación, son del 0 al 7. Sin embargo, si estamos reservando el primer bit para el signo, donde un 0 significará + y un 1 significará -, los valores que representan esos valores explícitos son, en realidad, del +0 al +3 los cuatro primeros binarios (hasta aquí todo normal), pero ahora el valor explícito 4 representa al número entero -0, el valor explícito 5 representa al -1, el 6 se corresponde con el -2 y el 7 con el -3. Esta representación de los enteros se llama de signo y magnitud. El mayor problema que tiene, además de la duplicidad del 0, es que el algoritmo de suma es diferente del de los naturales (si hemos diseñado el sumador completo de 3 bits para naturales y ahora queremos utilizarlo para enteros, este no funciona: (+1) + (-1) tienen valores explícitos 001 y 101, que son los que vamos a meter al sumador, cuya suma da 110. Pero resulta que este valor explicito representa al -2 y no al 0…)

Existen otras representaciones de enteros, en donde lo que va a cambiar es la relación entre el valor explicito y el valor representado, que intentan resolver los diferentes problemas que nos encontramos: duplicidades del cero, algoritmos aritméticos o lógicos diferentes, rangos asimétricos, etc. Las mas conocidas son el complemento a 1 (donde el algoritmo de suma si es igual para naturales y para enteros), el complemento a 2 (donde conseguimos un solo cero a costa de perder la simetría de los rangos) y las representaciones en exceso, bias en inglés (donde los negativos tendrán un 0 delante y los positivos un 1, lo cual nos permitirá comparar enteros en comparadores binarios diseñados para naturales).

Y por fin, con todo esto, ya podemos entender las especificaciones de doble precisión del estándar IEEE 754. El estándar IEEE 754 define como representar números reales en simple y doble precisión. Como siempre se ha dicho, en un ordenador todo se almacena como ceros y unos, y el caso de los reales no podía ser menos. En simple precisión dedicaremos 32 bits (del bit 0 al bit 31) al almacenamiento del real, mientras que en doble precisión lo que tendremos serán 64 bits (bits 0, 1, …, 63). Ni uno mas. Ni uno menos… Y por cuestiones de espacio y no duplicidad, nos centraremos a partir de ahora en la doble precisión.

Para empezar, el bit 63 nos especificará el signo del número real que estamos representando.

A continuación, se reservan 11 bits para el exponente: del bit 62 al bit 52. Este exponente está en representación por exceso. Se consiguen buenas propiedades cuando este exceso es 2^{n-1}-1, que es lo que precisamente hace el estándar, de manera que 2^{11-1}-1 = 1023. Para obtener el valor explícito del valor que queremos representar, se le suma a éste el bias. Restaremos el bias para obtener el valor representado a partir del valor explicito. Con 11 bits, el rango de valores explícitos es del 0 al 2047. Por tanto, al restar el 1023 obtenemos el rango de valores representados que va de -1023 al 1024 (observar que, además, los exponentes negativos son mas pequeño que los positivos, algo bueno para utilizar comparadores binarios para comparar exponentes a la hora de hacer operaciones con números en coma flotante). Sin embargo, como el exponente mas pequeño (00000000000 que representa el -1023) y el mas grande (11111111111 que representa 1024) se reservan para casos especiales (representación del 0,  números denormalizados, mas y menos infinito y los Not a Number (NaN)), el rango de valores validos para los exponentes en el caso de números normalizados es de -1022 a 1023.

Finalmente, los últimos 52 bits, del bit 51 al 0, representan la mantisa. Recordemos que, al disponer de un exponente que varia al desplazar la coma (de ahí lo de coma flotante), la representación de un número, de entrada, no es única. Para conseguir esta unicidad, imponemos lo que se llama normalización, que quiere decir que la coma va a estar a la izquierda o la derecha de la primera cifra significativa. Esto en binario quiere decir que, dado cualquier número, siempre vamos a modificar el exponente de manera que la mantisa quede representada como 1. lo que sea o 0.1 lo que sea. Aunque la normalización a nivel general se puede hacer tanto por la izquierda como por la derecha, solo una de estas es la utilizada por el estándar, y es 1.xxx, con el primer uno a la izquierda de la coma. Además, como siempre vamos a tener este bit a 1, no lo vamos a almacenar de manera explicita y vamos a tener lo que se llama representación con bit oculto (aunque no hemos mencionado nada al respecto, lo mismo pasa con la base, que como ya sabemos que es dos, también queda almacenada de manera implícita). Con todo esto, dada una secuencia de 52 bits

Llegados a este punto, ¿para que sirven los exponentes que nos hemos reservado? Pues para tratar casos especiales. El primero es la representación del 0. Si todo número representado se tiene que interpretar como 1.xxx, esta claro que nunca vamos a conseguir, si no hacemos nada al respecto, una representación explicita del cero. Lo que hacemos es que, cuando todos los bits del exponente están a 0 (exponente -1023) y toda la mantisa también está a 0, entonces este número se interpreta como el 0. Para el mismo exponente pero mantisas diferentes de 0, tenemos los números denormalizados (se van a interpretar con bit oculto a 0, es decir, su valor sera 0.xxx con xxx siendo el valor de la mantisa en lugar de interpretarse como 1.xxx). El matlab, por ejemplo, soporta algo de esto, pues realmin nos da el mínimo numero representable en coma flotante, 2.225073858507201e-308, pero si hacemos 0.0000001/(10^308), obtenemos 9.999999984816838e-316, que es mas pequeño. La explicación es que el primero solo es el mas pequeño de los normalizados, mientras que el segundo es un denormalizado. El mas pequeño posible de los denormalizados nos lo da el comando matlab con eps(0.0). Lo mismo ocurre con el exponente mayor, que es 1024: se utiliza para representar + \infty o -\infty cuando toda la mantisa esta a cero y en función del signo; y para los NaN cuando la mantisa es diferente de 0.

Con todo esto, sea s el bit de signo, e los bits de exponente y m los de mantisa. El valor real es -(1)^s (2^{e-1023})(1.m) si e \in (0,2047). Si e=0 y m \neq 0 entonces el valor es -(1)^s (2^{e-1023})(0.m). Si e=0 y m=0 entonces el valor es 0. Todo lo demás, e = 2047, son casos que no representan números sino casos especiales (infinitos, NaN…). Y fuera de aquí tenemos overflows i underflows.

Y ya para acabar. En general , y a la luz del estándar, para que un sistema en coma flotante en un computador quede determinado, necesitamos especificar, como mínimo, el número total de bits que se utilizarán (uno será el signo), cuantos serán para la mantisa, cuantos se utilizarán para el exponente y cual será el exceso de su representación, como representaremos el cero y cual es el criterio de normalización.

 

Antes que nada, a ver si retomamos este blog, que está abandonadísimo.

No he podido evitar la tentación de poner esta entrada, no sea que esta tarde en nasatv anuncien que han podido estudiar la atmósfera con Spitzer de un exoplaneta potencialmente habitable y haya sorpresas 😉

 

Después de muchísimo tiempo sin escribir, vuelvo con este post que resume todo el trabajo que hemos realizado durante este último año.

En julio del año pasado nos enteramos de un artículo publicado por X. Yang and R. Mittal, de la Johns Hopkins University, en el que aceleraban de manera espectacular el algoritmo de Jacobi y lo utilizaban para resolver ecuaciones en derivadas parciales de tipo elíptico.

A pesar del relativo eco mediático que tuvo, y aunque aceleraba muchísimo Jacobi, seguía sin ser competitivo con los métodos utilizados actualmente para solucionar este tipo de ecuaciones. Sin embargo, como prometía en cuanto a su sencillez desde el punto de vista tanto de implementación como de paralelización, decidimos trabajar un tiempo sobre el mismo.

Finalmente, en junio presentamos unos proceedings en el CEDYA 2015 (pag. 733) y hace tres semanas enviamos un paper a JCP, donde presentamos una serie de mejoras realizadas que permiten, tal y como allí comentamos, que el SRJ sea prácticamente competitivos en ejecución secuencial con los algoritmos utilizados actualmente.

Por un lado, su inmediata implementación (todos tenemos un Jacobi implementado de nuestro curso de métodos numéricos, y es trivial convertirlo en un SRJ 🙂 ) hace pensar que mucha gente que no tenga y necesite un resolvedor elíptico eficiente sin invertir mucho esfuerzo en su implementación quiera utilizarlo. Por otro, su trivial paralelización, por ejemplo en entornos GPU, nos hace pensar en su extraordinario potencial en el ámbito de la supercomputación.

En la página de nuestro grupo de investigación tenemos disponibles todos los esquemas SRJ presentados en el paper.

¡Disfrutenlo!

¡Cómo pasa el tiempo! Ya hace meses que no escribo en mi blog…

A continuación dos enlaces a dos blogs que creamos, a ver si se animan las visitas :-), uno para mi hijo mayor de siete años y otro para mi hija mediana de cinco (la pequeña aun es demasiado pequeña 🙂 ), donde suben fotos de construcciones que hacen con Lego: la mayoria inventadas por ellos o con la ayuda de sus padres 🙂 y unas pocas oficiales a partir de instrucciones.

¡Qué los disfruten!

Hoy tiene lugar la investidura como Doctor honoris causa del físico Juan Ignacio Cirac por parte de la Universitat de València. Aprovechando su presencia en la universidad, ayer impartió la conferencia “Simuladores cuánticos” como invitado principal en el Encuentro de Excelencia en Física que tuvo lugar.

El problema de estudiar sistemas cuánticos con los supercomputadores actuales es que estamos intentando simular sistemas cuánticos mediante uno que es clásico, por lo que se intuyen muchas limitaciones.

La idea fundamental de la conferencia, o por lo menos lo que entendí yo, fue la de utilizar sistemas cuánticos sencillos controlables para simular estos otros mucho mas complicados. De este sistema bajo control, el simulador, conocemos su Hamiltoniano, su energía, y lo que vamos a hacer es que, como tenemos control absoluto sobre todos sus parámetros, modificarlos para conseguir que dicho Hamiltoniano sea equivalente al del sistema en estudio, con lo que, una vez hecho esto, se deja evolucionar el sistema y a partir de ésta podremos sacar nuestras conclusiones.

¿Y como son físicamente estos simuladores? Pues comentó que se trata de atrapar átomos a partir de sus propiedades ópticas o magnéticas y enfriarlos mediante láser o por evaporación. Comentó la realización concreta de un sistema cuántico sencillo, del  que de hecho si se conocía su comportamiento por otras técnicas y que sirvió de test de los simuladores, y finalmente comentó como utilizar simuladores cuánticos para simular física de partículas.

Todo muy interesante 🙂

 

En el artículo técnico What would a binary black hole merger look like?  se simula, mediante técnicas de ray tracing, como vería un observador externo el merge de dos agujeros negros (del artículo y del sitio web de los autores están sacadas prácticamente todas las imágenes).

Si estamos mirando hacia algún sitio, digamos:

ClockTower-400x300

y pasa un agujero negro frente a nosotros, lo primero que se nos viene a la cabeza es la siguiente imagen:

ClockTower-400x300b

ya que como de un agujero negro no puede escapar nada, ni la luz, pensamos que veríamos una simple esfera negra tapando un trozo de nuestra visión. Sin embargo, una imagen mas realista de lo que veríamos es:

ClockTower_BH-400x300debido a la curvatura que experimentan los rayos de luz por la curvatura del espacio-tiempo que genera el agujero negro: efecto de lente gravitacional.

Colocando una imagen de fondo más métrica, así es como se verían los espacios de Minkowski, Schwarzschild y Kerr.

analyticSpacetimesSi en lugar de un agujero negro tenemos un sistema binario de agujeros negros de igual masa, entonces tendríamos:

bbhSystem

Finalmente, una animación del merge:

El viernes 13 de noviembre de 2014 murió Alexander Grothendieck, un genio matemático a la altura de los mas grandes, capaz de reformular el solo toda una área de las matemáticas desde sus mismos cimientos: la geometría algebraica. Sobre el escribí lo siguiente en esta entrada que dediqué al premio Abel del año pasado:

Alexander Grothendieck es el siguiente personaje importante en el área, pues reescribió la geometría algebraica subsumiendo el concepto de variedad algebraica en el de esquema, entendiendo que cualquier anillo conmutativo puede ser un objeto geométrico, dotando de esta manera, de un nuevo lenguaje y una fundamentación, mucho mas potente que la de Weil, para la geometría algebraica.

A pesar de su abstracción, o precisamente por ella, esta última visión es la que ha permanecido, pues permite conectar dos mundos, el de la geometría algebraica y el de la álgebra conmutativa.

Una anécdota que he leído en estos días, que muestran el despertar de su genialidad es la siguiente. Cuando empezó a trabajar en su tesis doctoral bajo la supervisión de Laurent Schwartz y Jean Dieudonné, dos de los mejores matemáticos de la época, le entregaron una lista con 14 problemas para que escogiera uno en el que trabajar los tres o cuatro años siguientes. A los pocos meses los había resuelto todos.

Cosechas y Siembras. Reflexiones y testimonios sobre un pasado de matemático, obra de su puño y letra y, según sus propias palabras:

…una reflexión sobre mí mismo y mi vida. Por eso mismo también es un testimonio…

da una visión de la profundidad e inmensidad de su pensamiento. Algunos extractos de la misma:

.Sus doce “grandes ideas” (su aportación a las matemáticas):

  1. Productos tensoriales topológicos y espacios nucleares.
  2. Dualidad “continua” y “discreta” (categorías derivadas, “seis operaciones”).
  3. Yoga Riemann-Roch-Grothendieck (teoría K, relación con la teoría de intersecciones).
  4. Esquemas.
  5. Topos.
  6. Cohomología étal y l-ádica.
  7. Motivos y grupo de Galois motívico (\otimes-categorías de Grothendieck).
  8. Cristales y cohomología cristalina, yoga “coeficientes de De Rham”, “coeficientes de Hodge”…
  9. “Algebra topológica”:\infty-campos, derivadores; formalismo cohomológico en los topos, como inspiración para una nueva álgebra homotópica.
  10. Topología moderada.
  11. Yoga de geometría algebraica anabeliana, teoría de Galois-Teichmüller.
  12. Punto de vista “esquemático” o “aritmético” en los poliedros regulares y las configuraciones regulares de todo tipo.

.Metaforas:

“Habló sobre dos tipos de matemáticos, el que abriría una nuez con martillo y cincel y el que, pacientemente, la sumerge en agua y espera, con el paso de los meses, a que el líquido penetre y se pueda partir cerrando la mano sin más”.

“Lo ignoto que quiere ser conocido se me presentaba como una porción de tierra, o una dura magra, resistiéndose a la penetración… El océano avanza insensible en silencio, nada parece suceder, nada se mueve, el agua está tan lejos que apenas puedes escucharlo… Y sin embargo finalmente rodea la sustancia resistente”.

.Importancia de las preguntas, nociones y puntos de vista frente a las respuestas propiamente dichas:

Es realmente por el descubrimiento sobre todo de preguntas nuevas, de nociones nuevas, o aún de puntos de vista nuevos, o de nuevos “mundos”, que mi obra matemática ha resultado ser fecunda, más que por las “soluciones” que he aportado a preguntas ya planteadas. Esta pulsión muy fuerte que me lleva hacia el descubrimiento de las buenas preguntas, más que hacia el de las respuestas, y hacia el descubrimiento de buenas nociones y enunciados, mucho más que hacia el de las demostraciones, son otros trazos “yin” fuertemente marcados en mi aproximación a las matemáticas

.Sensibilidad en el manejo del lenguaje e invención de nueva terminología:

Desde un punto de vista cuantitativo, a lo largo de mis años de productividad intensa, mi trabajo se ha concretado sobre todo en unas doce mil páginas de publicaciones, bajo la forma de artículos, monografías o seminarios, y por medio de centenares, si no miles, de nociones nuevas que han entrado en el patrimonio común, con los nombres mismos que les había dado al despejarlas [dégagées]. En la historia de las matemáticas, creo ser aquel que ha introducido en nuestra ciencia el mayor número de nociones nuevas y, a la vez, ser aquel que se ha visto llevado a inventar el mayor número de nombres nuevos, para expresar esas nociones con delicadeza y de la manera más sugestiva posible.

Un resumen en  http://finiterank.com/docs/grothendieck-zalamea.pdf:

Una sitio web dedicado a Grothendieck: http://www.grothendieckcircle.org/

Hoy, por primera vez en la historia, una sonda espacial aterrizará en un cometa. El cometa en cuestión es 67P/Churyumov-Gerasimenko, Chury para los amigos, la sonda espacial es Rosetta, de la ESA, y el módulo de aterrizaje es Philae.

En directo desde los medios de la ESA: http://rosetta.esa.int/

Podríamos decir que somos nuestras proteínas y que nuestro DNA codifica, entre otras cosas, la manera de construirlas.

Como breve introducción a la genética molecular, diremos que las proteínas son largas cadenas de aminoácidos, de los que existen únicamente 22 diferentes en éstas, sintetizadas por los ribosomas, los cuales son capaces de leer el mRNA, una copia de una sola hebra y con una base diferente al DNA (los cuatro nucleótidos del DNA son Citosina(C), Timina(T), Guanina(G) y Adenina (A) mientras que en el RNA en lugar de timina tenemos Uracilo(U)), por tripletes de nucleótidos.

En resumen, para sintetizar una proteína primero se copia su codificación en la doble hélice de DNA en una hebra de mRNA la cual es leída por un ribosoma y sintetiza una cadena peptidica traduciendo cada triplete de nucleótidos en el aminoácido que codifica éste.

Una proteína funciona porque adquiere una estructura tridimensional, en la que suelen repetirse dos estructuras secundarias características: hélices \alpha  y láminas \beta, durante el proceso de plegamiento. Aunque este plegamiento ocurre de manera relativamente rápida en la naturaleza, simularla computacionalmente se ha demostrado que es un problema NP-difícil.

Un problema puede ser más o menos difícil de resolver. La complejidad computacional pretende clasificar los problemas computacionales desde el punto de vista de cuanto cuesta resolverlos. Y para cuantificar esta dificultad de una manera teórica y objetiva, lo que se hace es ver como varia el tiempo de resolución con el tamaño de la entrada.

De esta manera, un problema perteneciente a la clase P, un problema resoluble en tiempo polinómico, es un problema cuyo tiempo de resolución es una función polinómica del tamaño de la entrada (si crece poco el tamaño de la entrada, crece poco el tiempo que tardamos en resolverlo, lo cual hace que estos problemas sean tratables).

¿Y qué quiere decir que un problema es de clase NP? Son aquellos problemas para los que es difícil encontrar una solución pero fácil verificarla, es decir, no se conoce ningún algoritmo polinómico que nos encuentre una solución pero si lo existe para comprobar que efectivamente lo es.

Para aclarar la definición anterior, pongamos un ejemplo: el problema del viajante de comercio. Dado un conjunto de ciudades, encontrar una ruta para un comerciante de manera que pase por TODAS las ciudades UNA ÚNICA vez. Este problema se traduce en encontrar un ciclo Hamiltoniano en un grafo. Un crecimiento moderado en el número de ciudades implicadas hace que el problema se vuelva prácticamente intratable. Sin embargo, si nos dan ya una solución, una ruta, es prácticamente trivial comprobar si es un ciclo hamiltoniano o no.

El problema P vs NP pretende demostrar si estos dos conjuntos son o no el mismo.

Dos definiciones complementarias para terminar.

  • Un problema es NP-completo si es un problema NP de los mas difíciles, dejémoslo ahí. El problema anterior es un problema de esta clase. Una propiedad que tienen estos problemas es que son todos equivalentes, desde el punto de vista de complejidad computacional, entre si, es decir, existe un algoritmo que traduce cualquier problema NP-completo en cualquier otro en tiempo polinómico. De manera que, si lográramos un algoritmo en P que resolviera uno de ellos, tendríamos un algoritmo en P para todos ellos (traducimos el otro problema al primero en tiempo polinómico, lo resolvemos en tiempo polinómico y traducimos la solución a una solución del original en tiempo polinómico).
  • Un problema es NP-duro si es, al menos, tan difícil como NP.

 

 

¿Cuantas veces necesito doblar un papel por la mitad para conseguir la altura de la Estatua de la Libertad (93m) o de la Torre Eiffel (324m)? Pues, aunque parezca increíble, superaríamos estas alturas con doblar un folio (supongamos 0.1mm) 20 veces o 22 veces respectivamente. Es más, con doblarlo 32 veces y ponernos encima, la Estación Espacial Internacional (ISS) orbitaría por debajo de nuestra posición. Y ésto es debido al vertiginoso crecimiento de la función exponencial: cada vez que doblamos el papel, doblamos la altura anterior.

A continuación, un ejemplo práctico de 13 dobleces llevado a cabo en el MIT:

Como puede verse, no resulta sencillo doblar un papel sobre si mismo tantas veces :-). Sin embargo, a efectos de la altura conseguida, pensemos simplemente en cortar y apilar…

Un número es perfecto si es la suma de sus divisores propios. Un divisor a de un número b es un divisor propio si a divide a b (a|b) pero b no divide a a (b \nmid a). Dicho de otra manera, son todos los divisores de un número excepto el mismo.

De esta manera, 6 = 1 + 2 + 3 es el primer número perfecto, ya que 1, 2, 3 son sus divisores propios. El siguiente número perfecto es el 28.

Dos cuestiones abiertas sobre estos números: ¿Existen infinitos números perfectos? ¿Existen números perfectos impares?

En el segundo libro de Paenza, se explica una manera de multiplicar cualquier par de números conociendo únicamente la tabla del dos. Necesitamos adicionalmente saber dividir por dos y saber sumar. Es es método ruso: vamos dividiendo el primer número por dos olvidándonos de los restos hasta llegar a 1, escribiéndolos en columna. En otra columna hacemos lo contrario con otro número: lo multiplicamos por dos hasta tener tantos elementos como en la columna anterior. Finalmente, sumamos los elementos de la segunda columna cuyo compañero en la primera sea un número impar y ¡voilà!

Este método, junto con el método egipcio, son métodos de multiplicación por duplicación.

¿Por qué funcionan? Básicamente estamos escribiendo  uno de los número en binario y aprovechando que la suma es distributiva 🙂

¡Cuánto tiempo sin escribir nada! Estoy bastante liado con el trabajo y he dejado abandonado el blog. Para que no se diga, una entrada breve: premio Leelavati.

En el penúltimo ICM en Hyderabad, la India, se estableció el premio Leelavati destinado a premiar la divulgación de las matemáticas. Ese año recibió el premio Simon Singh (leí su libro “El enigma de Fermat” en su día y vi el documental “El último teorema de Fermat” que dirigió y fue emitido en la BBC, ambos fantásticos).

En el ICM de este verano el galardonado fue el argentino Adrián Paenza. Aquí su memorable charla pública para la clausura del evento, y aquí sus libros, gratuitos para el disfrute personal, repletos de maravillosa matemática lúdica.

Acabo de descubrir, en esta entrada de Tao, unos vídeos sobre los medallistas Fields del 2014.

Añado también una imagen curiosa sobre los medallistas de la IMO del 1995, donde lograron medalla de oro tanto Mirzakhani (7) como Avila (24). También aparece con medalla de plata Ben J. Green (46):

imo1995

Finalmente, un software creado por Hairer para Mac.

El operador Laplaciano en dos dimensiones y en coordenadas polares queda:

\Delta := \partial_{rr} + \frac{1}{r} \partial_r + \frac{1}{r^2} \partial_{\theta \theta},

por lo que la ecuación de Laplace \Delta u = 0 en un sector circular [r_1,r_2] \times [0,2\pi] se escribe:

\partial_{rr} + \frac{1}{r} \partial_r + \frac{1}{r^2} \partial_{\theta \theta} = 0.

Aplicando el método de separación de variables, podemos plantear ahora una solución

u(r,\theta) = R(r)\Theta(\theta),

que es producto de dos funciones dependientes cada una de una sola de las variables. Sustituyendo la solución en la ecuación de Laplace, llegamos a:

agosto 2017
L M X J V S D
« Jul    
 123456
78910111213
14151617181920
21222324252627
28293031