VERSION ACTUAL :

Inicio de sesión

Raulito el Friki

Raulito El Friki

COMENTARIOS

EN LINEA

Hay actualmente 0 usuarios conectados.

NUEVOS

  • Gilberto Morales
  • mr.popo
  • marcef
  • Ing Edward
  • Miguelon_85

Agregador de canales de noticias

La sorprendente constante de Khinchin

Gaussianos - Lun, 10/20/2014 - 10:00

Las matemáticas nunca dejarán de sorprenderme. En cualquier lugar puedes encontrarte una cuestión interesante, una relación curiosa o una propiedad inesperada de algún número, alguna función o alguna figura. Particularmente conozco un buen número de ejemplos de este tipo (muchos de ellos os los he comentado en este blog), y en este post vamos a añadir uno más a la lista: la constante de Khinchin.

Vamos a comenzar presentando esta constante de Khinchin. Es la siguiente:

K_0=2.685452001065306445309714835481795693820382293994462 \ldots

Para poder explicar de dónde sale dicho número y hablar sobre sus propiedades necesitamos antes recordar algunas cosas sobre fracciones continuas. Una fracción continua es una expresión del tipo siguiente:

a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{ \ddots + \cfrac{1}{a_n} }}}

donde a_0 es un número entero y a_1, \ldots , a_n, \ldots son números enteros positivos. Suele abreviarse de la forma [a_0;a_1, \ldots , a_n, \ldots ] (la expresión podría ser finita o infinita).

Como podéis ver, en la expresión anterior todos los numeradores son 1, pero seguro que en alguna ocasión habéis visto una fracción continua con otros números en el numerador. Bien, cuando todos son 1 la fracción continua se llama regular, y cuando permitimos otros números se denomina generalizada. En este post podéis encontrar más información sobre ellas, en este otro tenéis fracciones continuas de números muy conocidos y aquí una interpretación combinatoria de las mismas.

Una de las principales propiedades de las fracciones continuas es que todo número real puede expresarse como una fracción continua regular. Es decir, podemos expresar todo número real de la forma [a_0;a_1, \ldots, a_n, \ldots ]. Olvidémonos de a_0 y quedémonos con los a_i desde i=1 hasta i=n. Ahora calculemos la media geométrica de esos términos, es decir:

(a_1 \cdot \ldots \cdot a_n)^{1/n}

y después el límite de esa expresión cuando n a infinito. Entonces, casi siempre ocurre lo siguiente:

\displaystyle{\lim_{n \to \infty} (a_1 \cdot \ldots \cdot a_n)^{1/n}=K_0}

Es decir, el límite de la media geométrica de los a_i desde i=1 hasta i=n casi siempre (esto es, para casi todos los números reales) vale K_0, la constante de Khinchin. Tremendo, ¿verdad?

Aleksandr Khinchin

Este resultado lo demostró Aleksandr Khinchin (en ocasiones escrito Khintchine), matemático soviético de la primera mitad del siglo XX (nació en 1894 y murió en 1959) que trabajó en múltiples áreas de las matemáticas y la física: análisis real, teoría de la probabilidad, teoría de números o física estadística. Podéis encontrar más información sobre él aquí y aquí (web de la que he tomado la foto de Khinchin).

Bien, posiblemente la primera pregunta que os ha surgido a la mayoría de los que habéis leído hasta aquí es ésta: ¿qué significa eso de casi siempre? Pues significa, como comenté antes, para casi todos los números reales. Y ese casi lo que nos dice es que el conjunto de números para los cuales no se cumple la propiedad anterior es un conjunto de medida nula, que viene a ser un conjunto que aunque puede ser infinito (como veremos que ocurre en este caso) tiene muy pocos elementos.

Es interesante destacar que aunque esta propiedad la cumplen casi todos los números reales no se ha probado para ningún número en concreto (¡¿?!). Lo que sí se conocen son excepciones, es decir, números de los que se sabe que no la cumplen. Por ejemplo, los racionales no cumplen dicha propiedad. Y tampoco algunos números irracionales como el número \sqrt{2}, el número áureo \phi o el número e.

Por otra parte, se conjetura que otros números irracionales (o que se sospecha que lo son) también muy conocidos sí que la cumplen, aunque no se sabe con certeza (recordad que hemos dicho que no se ha demostrado esta propiedad explícitamente para ningún número concreto). Por ejemplo, se cree que el número \pi (que sí se sabe que es irracional) cumple esta propiedad, y también la constante de Euler-Mascheroni \gamma (aunque no se sabe si este número es irracional).

Pero quizás lo más llamativo de todo este tema es que se cree (no está probado, pero los indicios apuntan a ello) que el propio K_0 cumple esta propiedad. Es decir, que si expresamos K_0 como una fracción continua y calculamos el límite de la media geométrica de los correspondiente valores a_i el resultado sería de nuevo el propio K_0. No sé a vosotros, pero a mí estoy me parecería absolutamente maravilloso.

Por otra parte, tampoco se sabe si K_0 es un número racional, un número irracional algebraico o un número trascendente. Y, por tanto, tampoco si es o no un número normal, aunque también en este caso los indicios apuntan a ello. En la siguiente tabla podéis ver el número de apariciones de los números 0, 1,…,9 en los primeros 10^n decimales, para n de 1 a 5:

Como podéis ver, parece que conforme n va siendo mayor la frecuencia de cada uno de los números de una cifra se va pareciendo bastante. Pero lo dicho, no hay ni demostración ni refutación sobre la normalidad de K_0.

El límite antes mencionado no es ni mucho menos la única manera de representar K_0 que se conoce. Hay muchas otras que involucran a series infinitas, como ésta:

K_0=\displaystyle{\prod_{n=1}^{\infty} \left [ 1+ \cfrac{1}{n(n+2)} \right ] ^{\frac{log(n)}{log(2)}}}

Y también se conocen algunas relacionadas con integrales, como ésta:

log(K_0)=\displaystyle{\int_0^1 \cfrac{log(\lfloor x^{-1} \rfloor}{(x+1) log(2)} \, dx}

Y para terminar vamos a responder a una pregunta que posiblemente os habéis hecho muchos de vosotros: ¿por qué se llama a esta constante K_0? Bueno, la K es, como cabía esperar, por ser la inicial de Khinchin. ¿Y el subíndice 0? Pues muy sencillo: porque K_0 es simplemente un caso particular de una clase de medias de ese tipo, K_p, definidas de la siguiente forma:

\displaystyle{\lim_{n \to \infty} \left ( \cfrac{ a_1^p+a_2^p+ \ldots +a_n^p}{n} \right )^{1/p}}

Se puede demostrar que para p \rightarrow 0 (que sería el caso de la constante de Khinchin) obtenemos K_0 tal cual lo hemos definido al principio de este artículo. Otro valor destacable de esta clase de medias es el que se obtiene para p=-1, y que se denomina media armónica de Khinchin:

K_{-1}=\displaystyle{\lim_{n \to \infty} \cfrac{n}{a_1^{-1}+a_2^{-1}+ \ldots +a_n^{-1}}}=1.7454056624073468634 \ldots

Con este artículo sobre la constante de Khinchin espero haberos descubierto algo nuevo, tanto a los que no tenéis muchos conocimientos matemáticos como a los que estáis más metidos en el tema. Para todos, en los enlaces que aparecen debajo de este párrafo podréis encontrar más información sobre esta sorprendente constante.

Fuentes y más información:

Esta es la primera contribución de Gaussianos a la Edición 5.7: Alan Turing del Carnaval de Matemáticas, que en esta ocasión tiene como anfitrión a @cuantozombi en su blog El zombi de Schrödinger.

Entra en Gaussianos si quieres hacer algún comentario sobre este artículo, consultar entradas anteriores o enviarnos un mensaje.

Construye tú también el poliedro de Császár.

Conoce tu mercado

Jose Salgado - Lun, 10/20/2014 - 08:14

Conoce tu mercado

Somos casi siete billones de personas en el planeta tierra, es una cifra considerable a tener en cuenta. Siete billones de personas, de seres individuales, cada cual con sus preferencias, sus pasiones y sus necesidades, ahora es tu trabajo intentar detectar cual es el grupo de referencia para tu producto.

Hay tantas personas que es casi imposible cubrir específicamente las necesidades de todos, siempre quedarán flecos que no se cubrirán con otros productos. Es aquí donde has de investigar si tienes sitio, si puedes hacerte

Esto es un resumen del artículo Conoce tu mercado escrito para Exelisis. Visita la web para más información y compártelo si crees que es interesante.

Urgente o importante o simple pérdida de tiempo

Jose Salgado - Vie, 10/17/2014 - 12:28

jobs

Hoy ha sido un día básicamente improductivo por una sencilla razón, he sido incapaz de distinguir entre importante, urgente o perder el tiempo. Tenía la agenda llena de tareas a cumplimentar, pero había salido la última versión de Mac OSx, y por supuesto he picado miserablemente.

Me he tirado toda la mañana haciendo copias de seguridad, bajándome la imagen, preparando el USB, instalando, reinstalando, recuperando los documentos, y todavía a estas horas todavía estoy a medias del proceso.

Esto es un resumen del artículo Urgente o importante o simple pérdida de tiempo escrito para Exelisis. Visita la web para más información y compártelo si crees que es interesante.

Segundas Clasificaciones Parciales de los Premios Bitacoras 2014

Gaussianos - Vie, 10/17/2014 - 09:30

Ya han salido las segundas clasificaciones parciales de los Premios Bitácoras 2014, en los que Gaussianos participa en la categoría Mejor Blog de Ciencia.

En dicha categoría Gaussianos ha bajado de la tercera a la quinta posición. Los cinco primeros puestos son los siguientes:

  1. Dimetilsulfuro
  2. Ciencia de sofá
  3. Ese Punto Azul Pálido
  4. La pizarra de Yuri
  5. Gaussianos

Hemos bajado un par de puestos, pero eso no puede significar que el ánimo decaiga. Quedan todavía unas semanas para votar y todavía hay posibilidades de quedar entre los tres primeros, que son los que al finalizar las votaciones serán los finalistas de esta categoría y, por tanto, los que optarán a ganar el premio final. Si quieres votar a Gaussianos identifícate en http://bitacoras.com y después haz click en la imagen siguiente:

Si no sabes cómo identificarte en este post te explico cómo hacerlo. Puedes hacerlo a través de la propia web http://bitacoras.com (si tienes cuenta en ella) o mediante tu cuenta de Twitter o Facebook. Y si tienes algún problema al intentar votar comenta en esta entrada (o en cualquier otra de las que hemos publicado relacionadas con los premios) y te ayudaré. Son solamente unos minutos, y tu voto puede ayudar a que Gaussianos sea finalista de estos premios. Muchas gracias por adelantado.

Entra en Gaussianos si quieres hacer algún comentario sobre este artículo, consultar entradas anteriores o enviarnos un mensaje.

Construye tú también el poliedro de Császár.

FUDCon and Fedora on TV

Fedora Nicaragua - Jue, 10/16/2014 - 14:05

Thursday 16th, there were two interviews about FUDCon on TV. Two different channels with variety mornig talk shows. One one apart from each other, have to run from one TV station to the other. Almost out of air we cover one and a half block.

The talks were about the University as a co-organizator of the convention, their role in activities for technology and those related to freesoftware. The came the turn for Fedora and FUDCon. People coming from different parts, FUDCon as a moving event but one of the most important in LATAM, the topics, web registration and it is all free.

Valentin Basel is now on the spot as his project was mentioned as freehardware, educational, built from scratch 100% with fedora.

Sadly, there is no web archive of the shows. Those channels only have archive for news.

Monday we will have another interview on TV. We hope that one of the people that arrived early for FUDCon step forward to face the camera. There is another TV interview pending to be confirmed.

Paper media has been harder, there will be one before the event and one covering the event. This has been a valuable help from the Public Relation office of the University to make all this press contacts.

Un juego que te hará terminar bizco

eliasbrasa - Jue, 10/16/2014 - 12:03

Pues eso, os dejo un enlace a un juego on-line en el que has de ir señalando cuál es la baldosa de diferente color, al principio es fácil, pero luego te vas quedando bizco para poder averiguar el correcto, solo tenéis que hacer clic en la imagen:

Juego CuadrosVisto en: FinoFilipino (y es también fuente de la imagen)

 


Poniendo los puntos sobre las íes

Gaussianos - Jue, 10/16/2014 - 09:30

Relacionar el talento matemático con la cantinela de la tabla de multiplicar, o con la facultad de recordar los números premiados de la lotería, es una ligereza equivalente a la de afirmar la falta de dotes literarias de una persona, no por ser incapaz de escribir poemas como Juan Ramón Jiménez o novelas como Gabriel García Márquez, sino por no poder recitar de memoria las conjunciones del castellano o por no recordar los nombres y apellidos del listín telefónico.

Antonio Córdoba, en su libro La vida entre teoremas.


Estas palabras de Antonio Córdoba son una especie de contestación a unas líneas escritas por el escritor Francisco Ayala que forman parte de un artículo que él mismo publicó en El País allá por diciembre de 1999. El artículo en cuestión se titula El ordenador novelista y las palabras a las que “contesta” Antonio Córdoba son las siguientes:

Debo reconocer en efecto que entre las cualidades innatas de que carezco se encuentra en lugar preeminente el talento matemático. Nunca en la escuela primaria, donde se nos hacía recitar la tabla de multiplicar, logré retener en la memoria sino los primeros versículos de la cantinela [...] Sin osar envidiarlos, uno admiraba aquellos casos asombrosos del señor que se sabía de memoria los números premiados en la lotería desde quién sabe cuánto tiempo atrás; y, aparte de tan singulares proezas, solía estimarse en general, y se cotizaba, la habilidad de los contables profesionales que con una rápida ojeada solían repasar sin falla columnas aterradoras de guarismos.

Pues eso, que parece que algunos, como Francisco Ayala, no se han enterado de la película.

Por cierto, estaría bien que en los comentarios dejarais más casos como éste. Es decir, artículos de prensa, blogs, etc., en los que se pretenda identificar las matemáticas solamente con cuestiones como éstas. Seguro que, por desgracia, hay muchísimos.

Entra en Gaussianos si quieres hacer algún comentario sobre este artículo, consultar entradas anteriores o enviarnos un mensaje.

Construye tú también el poliedro de Császár.

Gestión del error

Jose Salgado - Jue, 10/16/2014 - 08:43

errores

Por muy bueno que seas, por mucha formación que tengas, y por muchas horas que pongas encima de la mesa, ten por seguro que te vas a equivocar. Es ley de vida, nadie es perfecto durante toda su vida de forma constante y vas a cometer errores. Pueden ser pequeños, grandes o de proporciones bíblicas, pero los vas a cometer y lo más importante, muchas veces no te vas a dar cuenta hasta que sea demasiado tarde o peor todavía, que tu jefe o tu cliente se de cuenta antes.

Si tu jefe, ya sea directo o simplemente que esté por

Esto es un resumen del artículo Gestión del error escrito para Exelisis. Visita la web para más información y compártelo si crees que es interesante.

Small computers will be big at FUDCon

Fedora Nicaragua - Mié, 10/15/2014 - 12:59

There is no way to get experimental devices in Nicaragua. Just for FUDCon local team pitch in to get 5 Raspberry Pi +B and 5 Arduino UNO R3. This will not be all, there are sonic distance sensors, temperature sensors, infrared movement sensors, light sensor among other cool stuff.

We hope that those get across customs before Fedora collaborators start arriving to Nicaragua. Most likely there will be some custom duties to pay for. But that will be small thing with the success that this will bring to the event. Other parts and tools have been coordinated with other collaborators coming to Nicaragua.

Combined with bread boards, buzzers, RGB leds the GPIO of the raspberry pi will have plenty to do using Pidora.

We also expect that Arduino will be a success. There has been a lot of talk about arduinos in Nicaragua, even some demonstrations. Never have been a hands on hacking. This will be all running fedora. The link with fedora and experimental electronics will be ever lasting.

Best of all, all components and sensors can be shared among Icaro, Arduino and Rasperry Pi. Small things will be the greatest.

Inscripciones para Fudcon Latam abiertas

Fedora Nicaragua - Mié, 10/15/2014 - 11:29

Estamos a poco mas de una semana para la Fudcon Managua, ya pueden inscribirse e ir votando por su charla favorita en http://fudconlatam.org/

Talento o formación

Jose Salgado - Mié, 10/15/2014 - 09:30

talento

Hoy he tenido una conversación sobre que es lo más importante cuando estás buscando a un profesional para cubrir una vacante o para trabajar como freelance. La cuestión estaba en si era más importante la formación que podía acreditar el individuo o era más relevante el talento que podía demostrar.

Está claro que ambas son necesarias, pero si nos pusieran ante el dilema de escoger un perfil u otro, ¿por cual nos decantaríamos?. No creo que haya una respuesta fácil ni única, porque ambas dos opciones presentan sus

Esto es un resumen del artículo Talento o formación escrito para Exelisis. Visita la web para más información y compártelo si crees que es interesante.

XI Edición del ciclo de talleres divulgativos “Matemáticas en Acción” en la Universidad de Cantabria

Gaussianos - Mié, 10/15/2014 - 06:00

En este curso 2014-2015 se cumple el undécimo aniversario del ciclo de talleres divulgativos Matemáticas en Acción que se imparten desde el curso 2004-2005 en la Universidad de Cantabria. Organizados por Luis Alberto Fernández y Fernando Etayo, estos talleres tienen los siguientes objetivos:

  • Difundir el papel esencial desempeñado por las Matemáticas en campos muy variados del conocimiento científico y técnico.

  • Mostrar la aplicación de las Matemáticas a problemas reales y enseñar cómo se construyen modelos matemáticos para estudiar un problema real.

  • Completar la visión de las Matemáticas ofrecidas en las enseñanzas regladas con una visión interdisciplinar.

  • Servir como punto de encuentro de personas provenientes de diferentes ámbitos que utilizan las Matemáticas como base o herramienta fundamental en su trabajo o estudio.


La edición de este año constará de diez conferencias desde hoy 15 de octubre de 2014 hasta el 6 de mayo de 2014. Sí, la primera de las conferencias comenzará hoy mismo a las 18:00 horas. Su título es Emergencias por riesgos naturales: el deslizamiento de Sebrango de 2013 y la impartirá Alberto González, del departamento de Ciencias de la Tierra y Física de la Materia Condensada de la Universidad de Cantabria. Podéis ver toda la información relativa a esas diez charlas en el cartel del ciclo:

En este enlace podéis ver el programa completo algo más detallado y aquí encontraréis información sobre las charlas de las ediciones anteriores. Entre ellas, concretamente en el curso 2010-2011, tenéis el taller Blogs y matemáticas: una interesante comunión que tuve el placer de impartir en enero de 2011. Aquélla fue mi primera conferencia en universidades y eventos de divulgación, y estoy muy agradecido a Luis Alberto y a Fernando que tuvieran el detalle de invitarme. Ojalá iniciativas de este tipo nunca dejen de existir, son tan necesarias como interesantes.

Entra en Gaussianos si quieres hacer algún comentario sobre este artículo, consultar entradas anteriores o enviarnos un mensaje.

Construye tú también el poliedro de Császár.

Robotic will rock FUDCon

Fedora Nicaragua - Mar, 10/14/2014 - 22:12

The electronic start of FUDCon will be Icaro, an educationl robotics project from Argentina. Valentin Basel has set hardware start from scratch session. Local team has enable him  as good a we could.

ferric

Getting drill bits as thing as 1/32″, copper boards and etching solution will bring electronic circuits to life together with a household iron and a laser printer. The project itself aims to enable robotics as an educational tool to teach programming with a low cost.

Other items were also gathered for Icaro boards like terminals, usb ports type b, leds and capacitors.

usbterminal

ledscapacitor

Icaro is developed in Fedora, with electronic design software, chip programming software and a beautiful block interface for children.

As parts are difficult to acquire in Nicaragua, Valentin will bring more. We expect that people that never have been close to build hardware will link this experience forever with Fedora.

Y volvemos con los problemas de vigilancia en la red

eliasbrasa - Mar, 10/14/2014 - 11:18

Ya no somos ignorantes de la vigilancia a la que nos tienen sometidos ciertas agencias de espionaje, así que cada vez somos más culpables de utilizar ciertos programas de mensajería que no respetan nuestra privacidad. El pasado 6 de Octubre leo esta noticia en la que explican que los habitantes de Corea del Sur se han enterado de que su gobierno espía sus conexiones a una red social de ese país y, ni cortos ni perezosos, han comenzado a utilizar programas de mensajería encriptada, como Telegram.

vigilancia_internet

Y es que la privacidad es un derecho y los gobiernos no están ya abusando solo de hurgar en nuestros asuntos privados sino que, además, si las redes sociales son un problema, pues cortamos Internet…

Pero todo son malas noticias, hay una aplicación que no está muy difundida en España pero que sí están usando en la “revolución de los paraguas” de Hong Kong que no necesita ni siquiera de Internet, esa aplicación es FireChat. Al parecer esta aplicación se puede conectar a través de Internet (como todas) pero también solo a través de puntos Wifi o Bluetooth, con lo que es más difícil de cortar las comunicaciones. Con esta herramienta los manifestantes de Hong Kong están burlando la censura china. Y es que ese país no puede controlar las comunicaciones a través de esta aplicación como sí lo hace con otras (bien cortando Internet o bien porque tenga acceso a ellas).

¿Por qué es importante que usemos este tipo de aplicaciones? El problema no es “es que a mi me da igual que me vean las conversaciones, no tengo nada que ocultar“, el problema es que renunciamos a un derecho sin recibir nada a cambio, el problema de estas agencias de espionaje no es que usen la información para coger a “los malos” sino que usan la información para intereses más oscuros y, desde luego, a nadie le importa lo que yo lo diga a mis amistades o conocidos a través de mi teléfono, si quisiera vivir en 1984 no estaría escribiendo estas líneas.

De todos modos me pregunto cuanto tardarán los gobiernos en presionar a Google y Apple para que quiten esas aplicaciones de sus tiendas, no sería la primera vez que una empresa cierra porque el gobierno de un país presiona para hacer desaparecer un servicio al ciudadano.

Si queréis descargaros Firechat, aquí os dejo un par de enlaces para Android y para iPhone.

Fuentes: The Verge,  y Ubuntizando.

Fuente de la imagen: Noticias de trabajo.


Probar que es un cuadrado perfecto

Gaussianos - Mar, 10/14/2014 - 09:15

Os dejo el problema de esta semana. Ahí va:

Sea n > 1 un número natural y p un número primo. Probar que si p|n^3-1 y n|p-1, entonces 4p-3 es un cuadrado perfecto.

A por él.

Entra en Gaussianos si quieres hacer algún comentario sobre este artículo, consultar entradas anteriores o enviarnos un mensaje.

Construye tú también el poliedro de Császár.

Si queremos profesionales, seamos profesionales

Jose Salgado - Mar, 10/14/2014 - 07:36

profesionales

Existe una especie de Marianismo en el mundo de la empresa, un pasar sin manchar pero tampoco sin limpiar. Falta de implicación, dejadez, poca seriedad con la calidad de los proyectos y las fechas, en resumen, una auténtica implementación de la metodología del avestruz: yo escondo la cabeza y que pasen los marrones de largo.

El problema de este sistema de gestión es precisamente que cuanto más alto en la escala de mando se ejecuta, peores son sus consecuencias. Si un directivo se dedica a desaparecer durante las crisis,

Esto es un resumen del artículo Si queremos profesionales, seamos profesionales escrito para Exelisis. Visita la web para más información y compártelo si crees que es interesante.

http://fiee.nitcom.com

Gino Alania - Lun, 10/13/2014 - 12:57

He querido hoy aperturar un espacio donde se pueda divulgar al mundo los avances , ocurrencias , coherencias y sobre todo .. el impetu de un estudiante de la FIEE , la idea inicial es pilotear el proyecto, pero en el tiempo esto poco a poco irá avanzando ...

Bueno , pasen la voz a sus amigos que pronto se verán mas novedades ::

http://fiee.nitcom.com

Tags: 

Siguiendo el protocolo

Jose Salgado - Lun, 10/13/2014 - 08:55

protocolo

Los protocolos y los procesos se han diseñado para minimizar los riesgos, ya sea en las operaciones diarias como en momentos de crisis. Se asume que se definen y se corrigen cada vez que es necesario para que la probabilidad de error se acerque lo más posible a cero.

Ahora bien, a veces no se sabe diseñar protocolos, o directamente, no sabemos aplicarlos cuando nos llega el momento. Puede que sean complejos o quizás que no estén correctamente delimitados, dejando vacíos que solemos aprovechar los seres humanos para

Esto es un resumen del artículo Siguiendo el protocolo escrito para Exelisis. Visita la web para más información y compártelo si crees que es interesante.

Las tortitas de Gates

Gaussianos - Lun, 10/13/2014 - 04:30

Bill GatesBill Gates es mundialmente conocido por, entre otras cosas, ser uno de los fundadores de Microsoft (y, por tanto, uno de los responsables de Windows) y por las donaciones millonarias que ha realizado a través de la Fundación Bill y Melinda Gates, que comparte con su esposa Melinda. Estas cuestiones y otras muchas de su vida relacionadas con la informática son de dominio público, y se puede encontrar información sobre ellas muy fácilmente a través de internet. Lo que posiblemente no sea muy conocido es su faceta investigadora en lo que se refiere a publicaciones científicas. Y es normal, ya que solamente hay una publicación de este tipo en la que Bill Gates aparezca como autor (coautor en este caso, junto con Christos H. Papadimitriou). Curiosamente, el contenido de dicho artículo tiene como temática central las matemáticas, y en esta entrada vamos a contar la historia del mismo. Matemáticas, tortitas y Bill Gates…ahhh, y Los Simpson, que parece que están en todos sitios. ¿Se puede pedir más?

Comencemos con el origen del problema que trata la publicación científica de Gates y Papadimitriou. En 1975, el matemático estadounidense Jacob E. Goodman se encontraba colocando toallas en su casa. Al ver que la pila de toallas que había quedado estaba algo desordenada decidió recolocarlas en orden según su tamaño: la más grande abajo y la más pequeña arriba. Y fue durante estos cambios de posición de las toallas cuando le vino a la cabeza la siguiente cuestión: ¿Cuál sería el número de cambios que tendría que hacer?

Goodman pensó que el problema era suficientemente interesante como para enviarlo a American Mathematical Monthly, pero lo de las toallas no le convencía. Pensó que cambiando las toallas por tortitas (“pancakes” en inglés) la cosa quedaría mejor, y con este cambio nació el problema conocido como pancake sorting problem.

Por otra parte, parece que no tenía muy claro eso de que se le asociara con esa pregunta (quizás por si el tema acababa siendo demasiado trivial y le acababa perjudicando). Por ello no quiso arriesgar y utilizó un seudónimo, concretamente Harry Dweighter, que pronunciado en inglés como harried waiter significa camarero agobiado. Vamos con el enunciado que creó Goodman para ilustrar este problema:

El chef de nuestro negocio es descuidado, y cuando prepara una pila de tortitas, todas son de distintos tamaños. Por tanto, cuando las servimos a los clientes, de camino a la mesa las ordeno un poco, de modo que las más pequeñas queden encima, las de mayor tamaño debajo de todo cogiendo varias de encima e intercalándolas, y lo repito (variando el número de las que cambio) tantas veces como sea necesario. Si hay n tortitas, ¿cuál es el máximo número de cambios (como una función de n) que tendré que hacer para ordenarlas?

Bueno, pues parece que el problema que planteó Goodman sí que despertó el interés de cierta cantidad de matemáticos, tanto por enfrentarse al problema en sí como por las aplicaciones que podría tener (por ejemplo, en informática).

Vamos a analizar un poco el problema para cantidades pequeñas de tortitas, y vamos a llamar T_n al número de cambios que tendríamos que hacer para reordenar de la forma comentada nuestra torre de tortitas en el peor de los casos:

\bullet Supongamos que tenemos una tortita nada más. En este caso es evidente que la torre ya está ordenada, por lo que no hay que hacer ningún cambio. Por tanto, T_1=0.

\bullet Supongamos ahora que tenemos dos tortitas. Aquí podría ocurrir que la más grande estuviera abajo y la más pequeña arriba, por lo que no habría que cambiar nada (la torre ya viene ordenada). Pero puede ocurrir lo contrario, que la más grande venga arriba y la más pequeña abajo, por lo que habría que hacer un único cambio para ordenar la torre: dar la vuelta a las dos tortitas a la vez para que queden en el orden correcto. Por tanto, en este caso tenemos que T_2=1.

\bullet ¿Qué ocurre si tenemos tres tortitas? Aquí la cosa se complica un poco. La torre nos puede llegar de seis formas distintas, y analizando cada una de ellas vemos que el máximo número de cambios necesarios son tres. Aquí tenéis las seis opciones y el número de cambios que harían falta para ordenar cada una de ellas:

En este punto vamos a pararnos un momento para explicar más detenidamente cómo se realizan estos cambios. El camarero estará agobiado, pero es limpio, y realiza los cambios con una espátula, por lo que la forma de hacer cada cambio es meter la espátula por una zona concreta de la pila y dar la vuelta a todas las que en ese momento están encima de la espátula, cambiando totalmente la posición de éstas. En la siguiente imagen podéis ver los tres cambios que habría que hacer para ordenar la torre que aparece en la imagen anterior abajo a la izquierda:

Sería un ejercicio interesante que intentarais ordenar el resto de situaciones que se nos pueden presentar con esas tres tortitas.

Como podéis imaginar, conforme aumenta el número de tortitas de la pila inicial el problema es cada vez más complicado. El número de disposiciones iniciales posibles aumenta considerablemente, y en consecuencia es mucho más difícil encontrar el número de cambios necesarios para ordenarlas todas. Y por si fuera poco parece que los valores de T_n no siguen un patrón determinado, por lo que en principio ni siquiera se podría estimar una expresión para ese número de cambios analizando los valores conocidos. En la siguiente tabla podéis ver el valor de T_n para n de 1 a 19:

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 T_n 0 1 3 4 5 7 8 9 10 11 13 14 15 16 17 18 19 20 22 ¿?

Y en 19 tortitas nos quedamos. No se sabe el valor de T_n para n=20. Ni siquiera mediante el uso de ordenadores se ha podido calcular dicho número, dada la gran cantidad de combinaciones posibles. Posiblemente el principal problema es el comentado anteriormente: no se ha podido encontrar una expresión que calcule exactamente el valor de T_n en función de n, por lo que se puede decir que lo único que tenemos para realizar este cálculo es la fuerza bruta. Y, por desgracia, hasta los ordenadores tienen un límite.

Bueno, ¿y qué tiene que ver Bill Gates con todo esto? Muy sencillo. Hemos dicho que para cantidades de tortitas mayores o iguales que 20 no sabemos cuántos cambios son necesarios, ni parece que tengamos forma de calcular dicho número. En esta situación, calcular una cota superior de dicho valor sí que podría ser interesante. Pues precisamente eso es lo que hicieron Bill Gates y Christos Papadimitriou en su artículo Bounds for sorting by prefix reversal (pdf), publicado en Discrete Mathematics en 1979: establecer una cota superior para T_n. Concretamente la siguiente:

T_n \leq \cfrac{5n+5}{3}

Por ejemplo, si tuviéramos una pila de 200 tortitas (con la que es casi seguro que el camarero estaría realmente agobiado), la peor colocación posible de las mismas se podría reordenar de la manera comentada con, a lo sumo, 335 cambios:

\cfrac{5 \cdot 200 +5}{3}=335

Bueno, en realidad en el artículo, además de dar esa cota superior, plantean una variación del problema y dan también cotas para él. Dicha variación consiste en suponer que cada tortita está algo quemada por uno de sus lados, por lo que es interesante que al presentarlas al cliente cada una de las tortita muestre su “lado bueno” (vamos, que el quemado quede abajo). Por tanto, ahora no solamente hay que ordenar la pila por tamaño, sino que también hay que conseguir que todas ellas estén con su parte quemada mirando hacia abajo. Por ello este problema se denomina burnt pancake problem, y Gates y Papadimitriou establecieron que el número de cambios en este caso estaría entre (3n/2)-1 y 2n+3.

Pero más adelante esas cotas se mejoraron, y uno de los responsables fue David S. Cohen. ¿Os suena? Exacto, uno de los guionistas de Los Simpson (ya lo habíamos citado aquí) y uno de los creadores de Futurama, donde aparece como David X. Cohen. Cohen y el informático venezolano Manuel Blum publicaban en 1995 el artículo On the problem of sorting burnt pancakes (pdf) en Discrete Applied Mathematics. En él mejoraban las cotas encontradas por Gates y Papadimitriou, dejando la inferior en 3n/2 y la superior en 2n-2. Por ejemplo, para las 200 tortitas que tomamos antes, en este caso necesitaríamos, en el peor de los casos, 398 cambios.

Y parece ser que ahí estamos hasta ahora. Hasta donde yo sé no se han mejorado ninguna de las cotas (si alguien tiene más información al respecto que la deje en un comentario), por lo que podríamos decir que estos dos problemas siguen parados desde que Gates y Papadimitriou por un lado y Cohen y Blum por otro publicaron sus artículos. Y, como decía antes, parece que estos temas tienen interés práctico. En informática, como comentaba más arriba, por el tema de la reordenación de datos que están desordenados. Pero parece ser que también podría tener cierto interés en Biología, en lo que se refiere a cómo se ordenan los genes (algo así como que dos organismos pueden tener los mismos genes pero en distinto orden, y podría haber interés en saber cuántos cambios fueron necesarios para pasar de uno a otro). Si conocéis algún otro campo en el que este problema de las tortitas pueda ser interesante no dudéis en comentarlo.

Fuentes y más información:

La foto de Bill Gates está tomada de aquí, la primera foto de las tortitas de aquí y la segunda de las tortitas de aquí.

Entra en Gaussianos si quieres hacer algún comentario sobre este artículo, consultar entradas anteriores o enviarnos un mensaje.

Construye tú también el poliedro de Császár.

Linux: Un WINEPREFIX para cada aplicación Wine instalada

Xenode - Vie, 10/10/2014 - 19:46

Como todos los Linuxeros sabemos, cuando se requiere usar alguna aplicación Windows en nuestro Linux siempre podemos contar con Wine, la capa de compatibilidad directa para programas de ésta plataforma. Sin embargo lo que pocos saben (hasta que lo viven) es que las dependencias de algunas aplicaciones pueden romper y/o dejar inutilizables otras, es por esto que es recomendable instalar c/u de las aplicaciones Windows que vayas a usar dentro de tu Linux bajo un prefijo Wine distinto. Para hacer esto, necesitaremos seguir el siguiente proceso (en la línea de comandos):

1. WINEPREFIX=$HOME/.wine-app/ winecfg
2. WINEPREFIX=$HOME/.wine-app/ winetricks libs01 libs02 libs03
3. WINEPREFIX=$HOME/.wine-app/ wine setup.exe

NOTA: Recuerda reemplazar app por el nombre de la aplicación que estés instalando, (por ejemplo "evernote") en los comandos de arriba.

Básicamente lo que estamos haciendo aquí es primero inicializar un prefijo vacío con la configuración predeterminada de Wine, abriendo la ventana de configuración después de manera automática para editar cuestiones como la versión de Windows a usar, el nombre de usuario y la organización a nuestro gusto (comando #1).

Luego, instalamos las dependencias de la aplicación Windows que queremos usar vía winetricks, (comando #2) para finalmente correr el instalador de la aplicación a instalar forzando a que la ruta final de destino sea el prefijo que creamos previamente (comando #3). Instalar apps Wine de esta manera te permite tener un control más completo sobre los entornos de c/u de tus programas "emulados" (recuerden que Wine no es un emulador, so eso está mal dicho jeje) y así te evitarás conflictos de dependencias cruzadas.

P.D. Este es más o menos el mismo proceso que siguen programas/scripts como PlayOnLinux al instalar programas Windows en sus llamadas "botellas" sin embargo, (aunque separar las aplicaciones wine en entornos isolados es lo mejor que puedes hacer); Para todo lo que no son juegos generalmente es mejor seguir un enfoque más orgánico y usar Wine por sí solo como estoy recomendando aquí.

Páginas

Suscribirse a Fedora-es sindicador