La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Archive for 30 junio 2007

Transformaciones de Möbius en vídeo

Posted by Carlos en junio 30, 2007

Las transfomaciones de Möbius son una familia de correspondencias geométricas con numerosas aplicaciones prácticas. Básicamente, la idea de las transformaciones es asociar cada punto de un cierto objeto bidimensional con otro cierto punto del plano. Esto se consigue mediante una función del tipo

f(z) = \frac{az+b}{cz+d}

donde z, a, b, c, d son números complejos, y ad-bc ≠ 0. Ajustando los valores de los coeficientes se pueden realizar traslaciones, rotaciones, dilataciones, o inversiones. Estas transformaciones nos pueden ser útiles por ejemplo a la hora de confeccionar un modelo de malla de la superficie de un objeto complejo: se encuentra la transformación de dicha superficie a un área cuadrada, se realiza una malla regular sobre la misma, y se transforma de manera inversa dicha malla. Relacionado con esto, también hay aplicaciones en neurología, realizando transformaciones de la superficie cerebral al plano, y analizando las unidades funcionales del cerebro sobre dicha proyección.

Este tipo de transformaciones pueden parecer complejas, pero como otros tantos conceptos matemáticos tienen una profunda simplicidad cuando se las estudia desde el punto de vista adecuado. Esto es lo que nos ilustra visualmente este magistral video, al que he llegado a través de Good Math, Bad Math. Todas las transformaciones de Möbius puede caracterizarse mediante operaciones simples sobre una esfera. Pasen y vean.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Matemáticas | Etiquetado: , | 5 Comments »

Turing en una cáscara de nuez: Complejidad de Kolmogorov

Posted by Carlos en junio 28, 2007

Aprovechando unos minutos de inusual relax para la época del año en la que nos encontramos, vamos a continuar la serie sobre computabilidad. En el último apunte al respecto vimos el problema del castor afanoso que -entre otras cosas- es especialmente interesante porque proporciona un primer nexo entre calculabilidad y complejidad descriptiva. Hay que recordar que la función castor afanoso se define como el mayor valor generable por un programa de cierta longitud, y que tal como vimos no es computable. Vamos ver hoy una noción más general y realmente interesante: la complejidad de Kolmogorov.

Imaginemos que tenemos una secuencia s de símbolos tomados de un cierto alfabeto Σ. Por simplicidad, y sin pérdida de generalidad, vamos a suponer que Σ={0,1}, y que por lo tanto estamos hablando de cadenas binarias. Supongamos ahora que queremos describir esta secuencia, donde por describir nos referimos a proporcionar información suficiente para poder reproducir dicha secuencia. Informalmente hablando, si la secuencia es simple, la cantidad de información necesaria para esta descripción será pequeña (por ejemplo, una cadena formada exclusivamente por ceros puede ser descrita simplemente dando su longitud, y aclarando que todos los símbolos son ceros). Por otra parte, es posible que no seamos capaces de discernir ningún patrón en los símbolos, y no nos quede otro remedio que usar la misma secuencia como su propia descripción.

De una manera más formal, imaginemos un cierto lenguaje L que usaremos para describir las cadenas de símbolos. Puesto que queremos evitar la ambigüedad del lenguaje natural, vamos a emplear un lenguaje puramente computacional. Por ejemplo, podemos considerar que L es nuestro lenguaje de programación favorito: haskell, perl, smalltalk, … Entonces, una descripción de una cadena de símbolos será un programa que la genera, e.g., la imprime en pantalla. Hecho esto, definimos la complejidad de Kolmogorov K(s) de una cierta cadena de símbolos s como el tamaño (definido de alguna manera razonable) del programa más pequeño que la genera.

Una primera consideración que nos puede venir a la mente de manera inmediata es que dicho tamaño es muy dependiente del lenguaje descriptivo que empleemos. La dependencia es cierta, pero no es muy preocupante ya que se reduce a una cierta constante, esto es, dados dos lenguajes L1 y L2, y cualquier cadena de símbolos s, |K2(s)-K2(s)| < c. Esto puede parecer sorprendente, pero no lo es, ya que lo único que necesitamos para pasar de una descripción en L1 a otra en L2 es un programa intérprete de L1 escrito en L2. Dicho intérprete podrá ser más o menos largo, pero es fijo, por lo que su tamaño es una constante (y el tamaño del programa correspondiente en L2 es el tamaño del programa en L1 más el del intérprete). Otro resultado interesante pero menos sorprendente es que existe una constante c (dependiente del lenguaje) tal que para cualquier cadena s, K(s) < |s| + c. Esto es fácil de ver, si pensamos que en el peor caso basta con confeccionar un programa que contenga la propia cadena como constante interna.

Dicho lo anterior, uno de los aspectos más interesantes de la complejidad de Kolmogorov es el que hace referencia a la noción de compresibilidad. Si tenemos una cadena s y un programa P más pequeño que s que la describe, entonces dicho programa puede interpretarse como una compresión (sin pérdida de información) de s. Por lo tanto, si K(s)<|s| diremos que s es compresible. Es fácil ver que no todas las cadenas son compresibles, esto es, hay cadenas s que son incompresibles: K(s) >= |s|. Por ejemplo, si P es el programa más pequeño que describe a s (i.e., K(s) = |P|), y pudiéramos comprimir al propio P usando el mismo lenguaje en el que está escrito, tendríamos una descripción Q más corta de s, lo que suponíamos que no existía. Siendo estrictos, en realidad una vez que ejecutáramos Q, tendríamos que dar la orden de ejecutar la salida que ha producido -P- para obtener s, por lo que incluyendo el tamaño de dicha orden llegamos a que K(s) >= |s|-c (y decimos entonces que s es c-incompresible). En cualquier caso, existen (|Σ|n-1)/(|Σ|-1) cadenas de menos de n símbolos, y |Σ|n cadenas de n símbolos, esto es, más que la primera cantidad por lo que no se puede hacer una correspondencia biyectiva entre ellas, y por lo tanto existen cadenas 1-incompresibles.

El próximo día exploraremos más en detalle las propiedades algorítmicas de la complejidad de Kolmogorov, y veremos que no sólo no es computable, sino que a través de ella llegamos una vez más a los teoremas de incompletitud de Gödel.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Calculabilidad, Matemáticas | Etiquetado: , , | 10 Comments »

Música para el domingo – Wild Boys (Duran Duran)

Posted by Carlos en junio 24, 2007

El domingo es día de asueto, y nada mejor que un poco de música para amenizarlo. Por ejemplo, este gran éxito de Duran Duran de 1984 titulado “Wild Boys“. Aunque Duran Duran fueron coetáneos del movimiento New Romantic (del que bandas como Spandau Ballet eran estandartes) y a veces se les encuadra dentro del mismo, la verdad es que su estilo musical difería bastante del de otras bandas de la época. Precisamente este tema en concreto se aleja mucho del pop romanticón que se estilaba. De hecho la historia de esta canción es interesante, ya que surgió a partir de un proyecto cinematográfico que finalmente no se llevó a cabo. Se trataba de adaptar para el cine la novela de ficción apocalíptica “The Wild Boys: A Book of the Dead“, de William Burroughs. El vídeo evoca en ese sentido el ambiente post-apocalíptico de películas como por ejemplo Mad Max, y fue muy costoso de producir debido a la cantidad de extras y efectos especiales (punteros para la época).

La versión del vídeo que puede verse es una extendida, y poco conocida. Todo un espectáculo visual, con grandes momentos como la cabeza robótica, o el alien acuático. ¡Que lo disfruten!

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Música, Post-Apocalyptic | 2 Comments »

Equilibrios de poder en la Unión Europea: El método de Penrose

Posted by Carlos en junio 21, 2007

Tras el fiasco del proyecto de constitución europea, durante los últimos días está habiendo cierta discusión en los medios de comunicación sobre el relanzamiento de las conversaciones entre los países de la UE para alcanzar un nuevo acuerdo de mínimos que sustituya al vigente Tratado de Niza. Una vez abierto el melón de las discusiones, una de las cuestiones que se ha puesto sobre la mesa es el sistema de toma de decisiones. Mientras países como Alemania o Francia dan por sentado que se mantendrá el que figuraba en el fracasado proyecto de constitución, Polonia está haciendo una defensa numantina de un sistema basado en la raíz cuadrada de las poblaciones de cada país. Merece la pena detenernos en esto, ya que en algunos medios se ha llegado a tratar esta propuesta como una “martingala”, y poco más o menos se ha venido a sostener que Polonia propone la raíz cuadrada como podría proponer el coseno hiperbólico si le conviniera más. Dejando de lado que obviamente cada país defiende sus intereses (y que en este caso los de Polonia y España son teóricamente parejos por tratarse de países con casi la misma población), el método de la raíz cuadrada no es una boutade ni muchísimo menos. Es de hecho el denominado método de Penrose, y tiene su justificación matemática.

Empecemos por considerar algunas de las afirmaciones que de manera más o menos explícita suelen hacerse al discutir un sistema de toma de decisiones:

  1. La influencia de un país es proporcional a su número de votos.
  2. Si se aumenta el número de votos de un país, su influencia siempre aumentará.
  3. Si el número de votos de un país es proporcional a su población, el poder decisorio de cualquier ciudadano de la Unión es el mismo.
  4. Es muy difícil definir un sistema de toma de decisiones que sea objetivo, simple, representativo y eficiente.

De todo lo anterior surge el mecanismo que se proponía en el proyecto de constitución europea, con su sistema de doble mayoría (55% de países, 65% de población), y que se presentaba como representativo. Sin embargo, es fácil ver que las anteriores hipótesis de partida son falsas:

  1. La influencia de un país no es proporcional a su número de votos. Por poner un ejemplo, en una situación en la que hubiera cuatro países A, B, C y D, donde A tiene 7 votos, B tiene 6, C tiene 5, y D tiene 2 votos, este último no tiene influencia en absoluto. Cualquier coalición entre dos de los países grandes (A, B y C) tiene mayoría. Incluso si se pide una cierta mayoría cualificada puede producirse una situación de este tipo (y de hecho era el caso de Luxemburgo en la Comunidad Económica Europea, de 1958 a 1972).
  2. Un país puede aumentar su número de votos, pero disminuir su influencia. Por ejemplo, si en la situación anterior se le quitan 5 votos a B, y se le dan 4 a A y 1 a C, este último tiene más votos (pasa de 5 a 6), pero dado que A tiene mayoría absoluta, la influencia de C no ha aumentado, sino todo lo contrario.

Los dos primeros puntos hacían referencia a cuestiones cualitativas y eran relativamente fáciles de refutar. Para ver por qué el punto 3 es falso, es preciso dar una medida cuantitativa de poder decisorio. Para ello se puede recurrir al denominado índice de poder de Banzhaf. Este índice captura lo que intuitivamente entendemos por influencia o capacidad decisoria: ¿qué capacidad tiene uno de los participantes en la votación de determinar el sentido de la misma? Esto depende obviamente del número de votos que tenga, pero también del de los demás participantes. Podemos entonces considerar todas las coaliciones posibles (si hay n participantes, hay 2n coaliciones), ver cuántas de ellas son ganadoras, comprobar en cuántas de las mismas participa un cierto país X, y ver qué fracción de estas coaliciones ganadoras serían perdedoras si X se pasase al otro bando. Este sería el índice de Banzhaf β del país X. Se puede calcular un índice normalizado para cada país, dividiendo el índice de Banzhaf por la suma de todos los índices de los demás países. Si queremos obtener un índice del poder de un ciudadano de un país cualquiera, tenemos que volver a dividir este índice normalizado por el poder decisorio que dicho ciudadano tiene a la hora de elegir el gobierno de su país (y por lo tanto, de dirigir el sentido del voto del país en la UE). Si N es el número de participantes en una votación (suponiendo circunscripción única, claro), el poder decisorio de cada uno es proporcional a N1/2. Dividiendo entonces el índice de poder de un país por la raíz cuadrada de su población (se asume que la composición demográfica de todos los países es similar, y que por lo tanto la diferencia entre ‘ciudadano’ y ‘votante’ se resume en una constante de proporcionalidad fija), se obtiene el poder relativo de cada ciudadano en la UE.

En la figura inferior se muestran estos valores para los diez países más poblados, tanto para el vigente tratado de Niza, como para lo que se proponía en el proyecto de constitución europea (y que los grandes países más España pretenden mantener). Los valores están normalizados de manera que el poder de un ciudadano alemán sea 1.0.

Poder relativo de cada ciudadano de la UE

Como puede verse, aunque con el modelo de Niza los alemanes están penalizados y tanto españoles como polacos tienen una ventaja comparativa, por lo demás el poder de los ciudadanos de los diferentes países es más o menos similar. Por el contrario, con el modelo que se pretende implantar, un alemán tiene mucho más poder que el resto de los ciudadanos europeos, y esta diferencia se va acrecentando para los ciudadanos de países pequeños (para más inri, la tendencia se invierte para los países diminutos, y un chipriota o un maltés tendrían más influencia que un alemán, y mucho más del doble que un español).

Por la propia definición de la medida de poder individual, está claro que el sistema en el que la influencia de cada ciudadano es la misma sea cual sea su nacionalidad es aquél en el que el peso del país es proporcional a la raíz cuadrada de su población. No es por lo tanto nada descabellado proponer este reparto de poder, que tiene la ventaja adicional de desmentir la consideración inicial número 4 (por ejemplo, si hubiera nuevos miembros admitidos en la Unión, el peso de cada uno sería fácil y objetivamente computable). No es previsible en cualquier caso que este método sea el finalmente adoptado. Parafraseando un célebre adagio, la política tiene razones que la razón no entiende.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Matemáticas, Política | 7 Comments »

La vida social secreta de las plantas: La familia es lo que importa

Posted by Carlos en junio 18, 2007

Cakile edentulaQue las plantas tienen algo similar a una “vida social” es un hecho conocido por los biólogos: son capaces de detectar la presencia de plantas vecinas a través de cambios en los niveles de agua o nutrientes, o por la aparición de señales químicas en el terreno. Sin embargo, un comportamiento mucho más interesante acaba de ser descubierto por Susan A. Dudley y Amanda L. File, del Departamento de Biología de la McMaster University (Canadá): hay plantas que son capaces de distinguir a parientes genéticos dentro de su propia especie. De este hallazgo dan cuenta en un artículo (de acceso libre) titulado

publicado en Biology Letters. Básicamente, cuando las plantas se hallan en una situación de gran competición por los recursos con sus vecinos “optan” por invertir más energía en la expansión de sus raíces, para de esta manera conseguir un mejor acceso a los mismos. El matiz interesante se produce cuando se observa que esta competición no es tan agresiva cuando los vecinos están genéticamente relacionados dentro de la especie (esto es, no se trata de que la planta reconozca a otros ejemplares de la misma especie, sino a otros ejemplares que son “primos” cercanos). El experimento de Dudley y File se ha realizado con ejemplares de la variedad lacustre de los ‘cohetes de mar’ (Cakile edentula, ver imagen superior). Cuando se plantan en maceteros separados, los ejemplares de la planta producen la misma cantidad de raíces. Sin embargo, se observa una variación significativa en la masa de las raíces cuando se hace competir en el mismo macetero a ejemplares de diferentes estirpes, en relación a los grupos de plantas de la misma estirpe.

Lo que aún queda por despejar es el procedimiento mediante el cual se produce la identificación de los familiares. Puede tratarse muy probablemente de algún proceso bioquímico, pero está por ver cuáles son las moléculas mensajeras, y cómo funciona el ciclo de detección-promoción del crecimiento de las raíces. Es en cualquier caso asombrosa la riqueza del comportamiento de estos seres, y cómo nuestro “animalocentrismo” nos hace en muchas ocasiones percibir a las plantas casi como mero attrezzo de la Naturaleza.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Botánica | 5 Comments »

Música para el domingo – You Might Think (The Cars)

Posted by Carlos en junio 17, 2007

El domingo es día de asueto, y nada mejor que un poco de música para amenizarlo. Por ejemplo, este magnífico tema de The Cars the 1984 titulado “You Might Think“. Además de un peculiar estilo de pop-rock, The Cars es un grupo que tuvo un cierto toque “gamberro” en algunos de sus vídeos, algo que casa muy bien con sus influencias originarias del punk, y con Ric Ocasek que siempre me ha parecido un tipo divertido. Esta canción es un buen ejemplo de ello, con un vídeo que en su momento causó sensación por su uso de efectos generados por ordenador (fue de los primeros en este sentido), y con algunas escenas -como la de Ocasek convertido en mosca- que han pasado a ser icónicas. !Que lo disfruten!

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Música | 3 Comments »

Bloggin’ bout my generation

Posted by Carlos en junio 16, 2007

Simplemente g-g-genial.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Comic, Internet, Meta-Blogging, Nanoposts | Etiquetado: | 3 Comments »

Proyecto Avogadro: La Esfera Perfecta

Posted by Carlos en junio 14, 2007

A diferencia de otras magnitudes físicas como la longitud o el tiempo, la unidad de masa (el kilogramo) se define en términos de una medida-patrón. Concretamente, la referencia es un cilindro compuesto de una aleación de iridio y platino que se conserva en la Oficina Internacional de Pesos y Medidas (ubicada en Sèvres, cerca de París). Además de este patrón primario, hay copias que periódicamente se recalibran con el original. Evidentemente, sería ideal poder disponer de una definición de kilogramo que permitiera su reproducción sin necesidad de recurrir al patrón. Éste es el objetivo del Proyecto Avogadro.

El Proyecto Avogadro debe su nombre a Amedeo Avogadro, el físico y químico italiano que enunció la ahora conocida como Ley de Avogadro, y que puede enunciarse entre otras maneras como sigue:

“Volúmenes de gases diferentes medidos en las mismas condiciones de presión, volumen y temperatura, contienen igual número de moléculas”

En otras palabras, el volumen de un gas es proporcional al número de moléculas que contiene. Si consideramos un volumen tal que la masa del gas (en gramos) sea igual a la masa atómica de las moléculas que lo componen, encontramos que el número de moléculas es una constante, el número de Avogadro NA (o el número de Loschmidt en la literatura científica alemana), cuyo valor es de 6.022·1023 moléculas. A la cantidad de una sustancia (gaseosa o no) que contiene este número de moléculas se le denomina mol. Consideremos entonces un mol de carbono-12. Por su propia definición, su masa sería de 12 gramos, por lo que podría definirse un kilogramo como la masa de 1000NA/12 moléculas de carbono-12. El problema es que esta definición no es útil por cuestiones prácticas: no es fácil ser capaces de determinar si tenemos ese número de moléculas de ese elemento en concreto. Sin embargo, la idea es buena, y en ella se centra el Proyecto Avogadro.

En lugar de carbono, el objeto del proyecto es el silicio, un elemento barato, fácil de conseguir y de purificar, y cuya estructura cristalina es sumamente regular. Esto es una gran ventaja, ya que es fácil hacer crecer un cristal de silicio, y si se puede determinar su volumen con la suficiente precisión, entonces se conocerá con gran exactitud el número de moléculas que contiene. Dado que NA se conoce con una precisión de 0.1 ppm (partes por millón), es necesario ser capaces de determinar el volumen con una precisión análoga. Para ser precisos se está intentando confeccionar esferas de silicio de 9.63 cm de diámetro, con una precisión de 0.6 nm.

Esferas perfectas de silicio

Esto es una tarea de gran dificultad, ya que una variación de temperatura de únicamente 2 mK hace que la dilatación exceda esta tolerancia. Además, por efecto de oxidación pueden formarse capas de monóxido y dióxido de silicio de 3-4 nm de espesor. Las mediciones han de hacerse pues en entornos sumamente controlados, y se debe prestar gran atención a la pureza del material. Así, el trabajo en equipo del proyecto comprende a un grupo en Rusia que está produciendo silicio-28 con una pureza del 99.99%. Un grupo en Alemania se encarga de fundir y hacer crecer cilindros de silicio, que son enviados a Australia para que a partir de los mismo se confeccionen esferas casi-perfectas (hasta ahora, la mínima desviación conseguida ha sido de 35 nm). Simultáneamente, científicos en Bélgica estudian la pureza del silicio-28, científicos italianos miden el espacio entre átomos, en los EE.UU. se estudia por qué surgen a veces huecos en la estructura cristalina, y en Alemania, Reino Unido y Japón se estudian métodos para medir el peso que eliminen el empuje de Arquímedes efectuado por el aire. Todo un complejo trabajo en equipo que hará posible que en el futuro cercano se pueda reproducir el patrón de masa por todo aquel que lo desee (y tenga los medios, claro).

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Física, Nanotecnología, Química | 4 Comments »

La clase PP, computación democrática, y la cota de Chernoff

Posted by Carlos en junio 12, 2007

Hace tiempo hablamos de las clases de complejidad P y NP a cuento de la computación cuántica, y aunque sin duda estas dos clases son las más conocidas (incluso fuera del ámbito de la informática teórica) no son ni muchísimo menos las únicas. Hay todo un universo de diferentes clases que habitan tanto en el interior de P o de NP, como en su exterior, englobando a estas dos en parte, o totalmente. Esto último es precisamente el caso de la clase que nos ocupa: PP (Probabilistic Polynomial-Time). Antes de definirla, recapitulemos brevemente el significado de P y NP. Estamos considerando problemas de decisión, para los que la respuesta es SÍ o NO. Si tenemos un algoritmo que en un número polinómico de pasos (esto es, un número p(n) -donde n es el tamaño del problema- tal que asintóticamente p(n) < anc, donde a y c son dos constantes) es capaz de solucionar correctamente el problema, entonces dicho problema está en la clase P. Por otra parte, consideremos un programa no-determinista que en ciertos momentos lanza monedas al aire y toma decisiones al azar. Si dado un problema, siempre que la respuesta es SÍ existe al menos una secuencia de decisiones tales que el algoritmo anterior responde SÍ en tiempo polinómico, y siempre que la respuesta es NO, todas las secuencias de decisiones resultan en un NO, entonces el problema está en la clase NP. Análogamente, si siempre que la respuesta es NO, existe al menos una secuencia de decisiones tales que el algoritmo responde NO en tiempo polinómico, y siempre que la respuesta es SÍ, todas las secuencias de decisiones resultan en un SÍ, entonces el problema está en la clase co-NP. Un ejemplo de problema en NP (y de hecho, NP-completo) es el de la satisfacibilidad (SAT): dada una fórmula lógica, ¿existe una asignación de valores de verdad a las variables que la componen, tal que la fórmula sea cierta? Si en lugar de SAT consideramos VALIDITY (dada una formula lógica, ¿es cierta para todas las asignaciones de valores de verdad a las variables que la componen?), tenemos un problema en co-NP (y de hecho, co-NP-completo). Se sabe que P está contenido en NP ∩ co-NP, y se cree que la inclusión es estricta, y que NP ≠ co-NP.

Una vez definido lo anterior, podemos describir la clase PP como la colección de todos los problemas para los que si la respuesta es SÍ un algoritmo no-determinista da la solución correcta en tiempo polinómico y con probabilidad superior al 50%. Si nos imaginamos que el algoritmo no-determinista toma sus decisiones aleatorias de manera uniforme, esto quiere decir que la decisión mayoritaria de todas las ramas de computación es la correcta (motivo por el cual se ha propuesto también la denominación Majority-P). Por ejemplo, consideremos el problema MAJSAT: dada una fórmula lógica, ¿tiene más asignaciones de verdad que la hacen cierta que asignaciones que la hacen falsa? Un algoritmo que genere una asignación de verdad uniformemente al azar y compruebe si hace cierta o falsa la fórmula responderá SÍ con probabilidad mayor al 50% si y sólo si hay más asignaciones que hagan la fórmula cierta, que asignaciones que la hagan falsa.

En relación con las clases mencionadas anteriormente es fácil ver que NP está contenida en PP. Para ello, considérese el problema SAT y un algoritmo que genere una asignación al azar, y si hace cierta la fórmula responda SÍ, y si la hace falsa responda SÍ o NO al 50%. Si la formula no es satisfacible, el SÍ y el NO ocurrirán con el 50% de probabilidad, pero si es satisfacible, la probabilidad será superior. ¿Cuánto superior? Si las asignaciones de calculan al azar, y hay N asignaciones que hacen cierta la fórmula, la probabilidad del SÍ será p=1/2+N2-n, donde n es el número de variables lógicas. La utilidad de que la probabilidad sea estrictamente mayor al 50% radica en el hecho de que al repetir la ejecución del algoritmo múltiples veces, se amplifica la probabilidad de que salga SÍ (si la respuesta es efectivamente esa). Obviamente, cuanto menor sea el margen por el que se supera el 50%, serán necesarias más ejecuciones del algoritmo para aumentar la probabilidad de que la solución que ha salido más veces sea la correcta. La cota de Chernoff nos dice cuántas ejecuciones tenemos que hacer para que la probabilidad de que respuesta mayoritaria sea incorrecta esté por debajo de un cierto ε. Concretamente, dicho número k es

k \geq  -\left(\ln\sqrt{\varepsilon}\right)/{(p-1/2)^2}

En el ejemplo anterior de SAT, en el caso extremo en el que N=1, tendríamos que el número de ejecuciones para un cierto ε sería

k \geq  -\left(\ln\sqrt{\varepsilon}\right)2^{2n}

esto es, exponencial en el tamaño del problema. Esto hace que en el fondo un algoritmo de este tipo no sea práctico. Si el margen por el que se supera el 50% resulta sin embargo no ser exponencialmente pequeño en n, sino constante, tendríamos un algoritmo mucho más útil, y también una clase de complejidad diferente, de la que hablaremos otro día.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Complejidad, Matemáticas | Comentarios desactivados

Música para el domingo – Alles nur geklaut (Die Prinzen)

Posted by Carlos en junio 10, 2007

El domingo es día de asueto, y nada mejor que un poco de música para amenizarlo. Por ejemplo, este pegadizo tema de Die Prinzen de 1993 titulado “Alles nur geklaut“. Die Prinzen son un grupo alemán (originarios de la extinta RDA) no muy conocidos en el resto de países, pero que tienen temas muy interesantes. Varios de sus miembros fueron estudiantes de música en Leipzig, y participaron en el Thomanerchor (un coro de la iglesia de Santo Tomás en Leipzig, uno de los más antiguos e importantes del mundo). Esto trasluce en el estilo de la banda, un pop-rock en el que la vocalización es muy importante (y de hecho, han llegado a hacer muchos temas a capella).

Esta canción es uno de sus mayores éxitos. El título significa “todo es robado (plagiado)” y puede interpretarse como una crítica a la música en serie, y a la falta de creatividad. El vídeo es muy ameno, ya que es una sucesión de imitaciones de escenas de otros vídeos de grupos conocidos (a ver quién identifica más de ellos). ¡Que lo disfruten!

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Música | 4 Comments »