miércoles, 7 de octubre de 2015

Memoria y Materialización

Gran parte de mi día a día es ocupado por un trabajo totalmente aburrido en una empresa de software. Bueno; "empresa de software" que en realidad se parece más a una consultora. Si bien se trata de una labor que no requiere mucha imaginación o creatividad, y con pocos objetivos de progreso a largo plazo (hacia un estado de mayor felicidad), de vez en cuando uno aprende técnicas de programación que hacen a un tipo curioso irse por las ramas... ¡de la metafísica! Increíble o incluso hilarante que parezca para muchos desarrolladores de software, esos momentos de mi vida existen, y yo los valoro mucho.

Fenómenos y realidad


Esta es otra entrada que tiene que ver con los fenómenos. Los fenómenos son las manifestaciones, todo lo que se puede experimentar. O por qué no, las experiencias en sí, o las apariencias. Desde un punto de vista científico, un fenómeno es algo que se puede medir.

Supongo que la mayoría de nosotros tenemos una inclinación por intuir que existen cosas reales y otras irreales. O quizá, sentimos a algunas cosas "más reales" que otras (bueno; todo aquello que es sensible debe ser real, ¿o no? Lo recíproco puede no ser verdadero). Pero, ¿qué hace que ciertas cosas se sientan más reales que otras? En este momento, en el que estoy escribiendo este artículo, siento al teclado muy real; es porque puedo tocarlo. Lo mismo con la pantalla, la cual tengo frente a mis ojos. Son la una de la mañana de un miércoles, es obviamente de noche. Acabo de darle play a una lista de reproducción de Bossa Nova (adoro esta música); la música es tan real como cualquier elemento de la habitación. Acabo de fumar un cigarrillo.

¿Qué tal el sueño que tuve anoche? Hacer un viaje en el tiempo a un año 2067 retrofuturista decadente y luego escapar de vuelta al pasado ascendiendo por la entrada de una alcantarilla... bueno, no me parece tan real en este momento (¿será porque no lo recuerdo en detalle?), pero sí lo era anoche, mientras lo soñaba, mientras lo vivía.

Cachés


Hace unos días, cuando me hice la pregunta, recordé que ya me la había hecho hace unos años atrás. Pero ayudó haber estado trabajando con memorias caché unas horas antes; esa conjunción fue inspiradora. Pero, antes de seguir con la explicación, debo dar una mínima idea de lo que es una caché. Sin entrar en detalles, una caché es un tipo de memoria de acceso rápido y de tamaño reducido, que almacena datos temporales (volátiles). Se utiliza en diversos tipos de dispositivos o software que requieran leer con facilidad datos que, en un principio, no son sencillos de construir u obtener. Su pequeño tamaño es compensado con velocidad de acceso. El uso de una memoria caché no suele ser imprescindible para el acceso a la información, sino más bien una técnica de utilidad.

Una analogía podría llegar a dilucidarlo (creo que la estoy tomando prestada de cierta bibliografía de sistemas operativos): en mi facultad tenemos una biblioteca, y adyacente a ella su sala de lectura. Uno entra a la biblioteca, se dirige hacia la computadora, busca los libros A, B y C en el índice para luego ir hacia lugares específicos del almacén de libros y recogerlos. Este proceso toma algo de tiempo; quién haya vivido una vida de estudiante podría saberlo. Una vez que tiene los libros A, B y C que necesita, se dirige hacia la sala de lectura con ellos. Se sienta en alguno de los escritorios y coloca los libros sobre la mesa. Toma el cuaderno que lleva en su mochila y comienza a escribir sus notas. Al principio, podría llegar a hacerlo sin consultar ninguno de los tres libros. Pero, seguramente, llegará un momento en que deba hacer una consulta al libro A. Por suerte, uno no necesita volver al almacén en busca del libro A (lo que sería una tarea tediosa) ya que lo tiene al alcance de la mano. Lo mismo ocurre con los libros B y C: seguramente los necesitará pronto, y por eso los tiene sobre la mesa.

En definitiva, este escritorio es un buen ejemplo de caché. Notar que es pequeño y no puede albergar muchos libros, pero sí permite tenerlos a mano. También funciona como depósito temporal ya que una vez que el estudiante lo abandona, debe retornar los libros a la biblioteca (si es educado, claro).

Una rutina para calcular factoriales


Suponga que quiero escribir un programa de ordenador que le permita a un usuario calcular factoriales. El factorial de un número natural n es el producto de todos los números naturales entre 1 y n, ambos incluidos. Se denota con n!. Por ejemplo, 4! = 1×2×3×4 = 24.

Ahora, suponga que el usuario desea usar mi programa para calcular los factoriales 5! y 10!, en ese orden. Yo, como programador, sería un poco ingenuo si escribiera un programa que primero calcule 1×2×3×4×5, y luego 1×2×3×4×5×6×7×8×9×10. ¿Por qué? Pues porque no hay necesidad de multiplicar los números desde 1 hasta 5 la segunda vez, ya que la máquina los multiplica la primera vez para obtener 5!. En vez de repetir los cálculos, podría indicar a la computadora que guarde el resultado 5! en su memoria, que es 120, para luego computar 120×6×7×8×9×10. Esto reduce la cantidad de operaciones a 5 productos en vez de 9.

Esta técnica se denomina "programación dinámica". En algunas ocasiones se vuelve práctica la combinación de esta técnica y el uso de memorias caché para almacenar resultados de cálculos complejos. 

Materialización de factoriales 


Hemos de notar en el ejemplo anterior que si bien guardar 5! en la caché no es necesario para calcular 10!, sí es muy práctico. Lo mismo podría hacerse con cualquier n! para reducir cálculos de factoriales más grandes. Pero para ello es necesario un espacio donde materializar esos valores. Ese espacio es la memoria.

Dicho de otra manera, el resultado 120 almacenado en la memoria es de alguna forma más concreto que la receta (implícita y abstracta) que se utiliza para definir 5!, la cual es 1×2×3×4×5. En definitiva: podemos pensar que los factoriales se manifiestan (o materializan) cuando se guardan en la memoria, porque luego de ser memorizados pasan a formar parte de un espacio muy palpable, que es la memoria misma.

Materializar Mandelbrot


Puede ser una buena idea retornar (¡una vez más!) a los fractales, pero esta vez para analizar programas capaces de calcularlos... o medirlos... o como queramos pensarlo, ya que después de todo es más o menos lo mismo. Los conjuntos que más me interesan son el de Mandelbrot, el de Julia, o similares, en cuyos gráficos abundan formas similares a las que se encuentran en la naturaleza, como árboles, ríos, plantas, insectos, etc.


Las implementaciones de representación gráfica de estos conjuntos (por lo menos las más populares) pueden llegar a requerir una cantidad importante de cálculos, incluso al momento de colorear un solo píxel. Estos algoritmos toman algunos datos de entrada, como coordenadas, y a partir de ellos dibujan alguna sección en particular. En general, los programas de computadora que funcionan de esta manera disponen de herramientas para hacer zoom hacia dentro y hacia afuera, o moverse en diferentes direcciones. Esto permite al usuario explorar diferentes partes del fractal a diversas escalas.

Pensemos un poco en una posible implementación. Un programador podría utilizar una caché para almacenar los colores de los últimos píxeles visitados por el usuario. La finalidad práctica sería que los colores de los píxeles recientes no fueran recalculados cada vez que el usuario decidiera hacer un pequeño zoom o movimiento. Pero, además, si pensamos en el cacheo como materialización, entonces podemos concluir que memorizar el color de un píxel es lo mismo que hacerlo manifiesto. Observamos un fractal cuando lo calculamos, y lo hacemos "tangible" cuando lo memorizamos.

Los Fenómenos como Materialización de las Ideas


Permitámonos soñar que observar la naturaleza o el mundo físico (o el universo en un estado de vigilia) no es diferente a realizar un cálculo complejo. No me refiero justamente a que el cerebro requiera de cálculos complejos para interpretar la realidad; podemos dar eso por sentado. En vez de eso, sugiero "soñar", ya que pido que pensemos que todo lo que medimos en el mundo físico es el resultado de hacer cálculos y almacenar datos en nuestra memoria; que medir el mundo y memorizarlo es materializarlo.

¿Qué tal si no hubiera mucha "estructura" allá afuera? ¿Qué tal si el mundo fuera simplemente una receta de ideas ejecutada por los sujetos? ¿Algún concepto nos impide ver al mundo de esa forma? ¿Sería esa receta pequeña, extensa, o ininteligible? Podríamos tener una receta parecida a la órbita de un fractal. Podría incluso ser comprensible pero caótica también. Los sujetos serían meras implementaciones de materialización de ideas en el espacio y el tiempo.


De hecho, Immanuel Kant afirma en su Crítica de la Razón pura que "todo lo intuido en el espacio y el tiempo, y con ello todos los objetos de nuestra experiencia posible, no es más que fenómenos, esto es, meras representaciones, que del modo en que se representan, como sustancia extensa o series de alteraciones, no tienen existencia propia e independiente aparte de nuestro pensamiento". Además, para Kant existe un nivel de conocimiento, la sensibilidad, que se encarga de ordenar en el espacio y el tiempo (los cuales son parte de este mismo nivel de sensibilidad) las impresiones que tiene el sujeto. Entonces, ¿qué tal pensar en el espacio-tiempo como la caché de nuestra realidad lúcida, o como gran parte de ella? Nuestra realidad lúcida es construida a partir de una fórmula para luego ser plasmada en el espacio-tiempo.

En el artículo Del porqué de la existencia comparo la galaxia de Andrómeda con el conjunto de Mandelbrot, y remarco la pobre excusa de recurrir a una variable espacial para determinar la existencia de las cosas. Por alguna razón decidimos creer que un objeto es "más real" que otro. Quizá ese juicio tenga que ver más con nuestra cultura (¿occidental?) que con nuestra naturaleza humana. O quizá tenga que ver una mente habituada a la vigilia. Sea como sea, valdrá la pena dejar de programar un poco y tomarse unas horas del trabajo para analizarlo.

Especulaciones y Nada Más


Me gusta especular, y como me siento libre de hacerlo, voy a hacerlo. Si el espacio-tiempo es caché, entonces puede que sea pequeño en comparación al mundo potencialmente mensurable. Quizá nunca haya existido y nunca existirá un unicornio en nuestra verdad lúcida. Sin embargo, los fenómenos están al alcance de la mano. Son volátiles, a diferencia de la receta, la cual es inmutable y trascendental. Las cosas que vemos están ahí porque es conveniente tenerlas ahí, pero no fundamental. Materializar es una ardua tarea. La sensibilidad es (muy) útil, pero prescindible.



Más info:http://www.wordreference.com/es/en/frames.aspx?es=materializar
https://es.wikipedia.org/wiki/Fen%C3%B3meno
https://es.wikipedia.org/wiki/Cach%C3%A9_%28inform%C3%A1tica%29
https://es.wikipedia.org/wiki/Programaci%C3%B3n_din%C3%A1mica
https://es.wikipedia.org/wiki/Factorial
https://es.wikipedia.org/wiki/Conjunto_de_Mandelbrot
https://es.wikipedia.org/wiki/Conjunto_de_Julia
http://www-reynal.ensea.fr/docs/iq/PrinciplesOfQuantumComputation1.pdf (Introduction to Classical Computation, deterministic chaos)
https://es.wikipedia.org/wiki/Idealismo
https://es.wikipedia.org/wiki/Idealismo_trascendental
https://es.wikipedia.org/wiki/Cr%C3%ADtica_de_la_raz%C3%B3n_pura
https://es.wikipedia.org/wiki/Immanuel_Kant
https://en.wikipedia.org/wiki/Orbit_(dynamics)
https://es.wikipedia.org/wiki/Galaxia_de_Andr%C3%B3meda

lunes, 5 de enero de 2015

Del porqué de la existencia (de Mandelbrot)

Lo primero que diré es que cuando me refiera a "Mandelbrot" no voy a estar haciendo referencia a Benoit, sino a su conjunto. Lo segundo es que "Andrómeda" será la galaxia, no la diosa.

¿Por qué diríamos que Mandelbrot no existe y que Andrómeda sí? Quizás, el simple hecho de que no podamos apuntar con el dedo para ubicar ese conjunto en algún punto del espacio nos hace concluir que no existe. Podemos usar esta técnica con la galaxia de Andrómeda, aún considerando que la mayoría de nosotros no tiene telescopio para poder observarla en detalle. De hecho, muchos dirían que Benoit tampoco existe; y pensarían que sería mejor decir que existió, ya que murió en 2010.

¿No es una excusa bastante pobre la de utilizar exclusivamente una variable espacial para juzgar la existencia de las cosas? Bueno, otros dirían que es válido afirmar que Mandelbrot existe, pero que "no tiene existencia física". O sea, no se puede tocar, oler, observar, y otras cualidades empíricas (cualidades de los sentidos). Sin embargo, tampoco podemos tocar ni oler a Andrómeda, y tampoco pueden observarla en detalle aquellos que no tienen al alcance un telescopio. Pero tranquilamente podría decir que sí es posible observar a Mandelbrot si tengo acceso a una computadora (si está conectada a la internet, mejor).

Yo creo que no hay mucha diferencia entre un telescopio y una computadora. Más allá de lo que decía Edsger Dijkstra acerca de la computación y la astronomía *, podemos analizar el asunto desde dos perspectivas:

* "La ciencia de la computación no trata sobre las computadoras más de lo que la astronomía trata sobre los telescopios".
  1. Reduccionista: telescopios y computadoras son instrumentos de medición. Toman datos de entrada y los transforman en datos de salida para que el operador los pueda interpretar. Hay diversos mundos por descubrir, y aparatos de toda clase para estudiarlos. Desde este punto de vista, una computadora recibe un algoritmo de generación del fractal de Mandelbrot y muestra un dibujo en la pantalla. En definitiva, Mandelbrot existe, está en "alguna parte" de la realidad (no necesariamente en algún lugar), y puede ser medido por un ordenador. Después de todo, supongo que consideramos que Benoit no inventó al conjunto, sino que lo descubrió... ¿o me equivoco?
  2. Holista: todo es creado por los instrumentos de medición, por lo que es obvio que llamarlos "instrumentos de medición" no es una buena idea. En particular, telescopios y computadoras generan por su cuenta toda la información que observa el operador. De esta manera, un telescopio puede generar la imagen de Andrómeda para luego proyectarla por el ocular o en una pantalla. Sólo depende de que los parámetros de entrada para generar la galaxia sean correctos. Estos parámetros son, entre otros, la posición espacial del instrumento y el ángulo del cañón. Claro que si quisiéramos ser aún "más holistas", no notaríamos la diferencia entre un telescopio y su operador... ¿dónde termina uno y empieza el otro?

Al momento de escribir este artículo, siento ganas de pensar que el fractal existe; que es un inmenso mundo que, paradójicamente, cabe en un puñado de líneas de código. Parece que me estuviera inclinando por la versión reduccionista. Y sin embargo podría imaginar que Mandelbrot existe porque, ¡yo soy Mandelbrot!. xD


Info relacionada:
http://en.wikipedia.org/wiki/Benoit_Mandelbrot
http://en.wikipedia.org/wiki/Mandelbrot_set
http://en.wikipedia.org/wiki/Andromeda_Galaxy
http://en.wikipedia.org/wiki/Empiricism
http://en.wikipedia.org/wiki/Reductionism
http://en.wikipedia.org/wiki/Holism
http://es.wikiquote.org/wiki/Edsger_Dijkstra

jueves, 7 de marzo de 2013

Ser cuadrado es divertido.

Cómo construir un cubo.

Me refiero a la figura. De hecho, en general, al politopo que generaliza al segmento, al cuadrado, al cubo, al hipercubo, y a todos los n-cubos, con n natural (me faltó nombrar al punto, de dimensión 0?). En general, todos conocemos a los primeros tres... pero, qué es un hipercubo? Cómo definimos a un cubo de más de tres dimensiones? Si los consideramos meros grafos (vértices unidos por aristas, sin considerar la posición de cada vértice), es muy sencillo; veamos que hay un patrón para construirlos:

* Un segmento es la unión de dos puntos por una arista.

* Para tener un cuadrado, debemos tomar dos segmentos A y B. Suponiendo que a1 y a2 son los vértices de A, y b1 y b2 son los vértices de B, al unir por aristas a1 con b1 y a2 con b2 tenemos un cuadrado.

* Para construir un cubo, debemos tener dos cuadrados A y B. Sean a1,a2,a3,a4 los vértices de A y b1,b2,b3,b4 los de B, al unir por aristas a1 con b1, a2 con b2, a3 con b3, a4 con b4 tenemos un cubo.


El patrón es notable en las dimensiones más bajas; podemos generalizarlo y aplicarlo a dimensiones más altas:

* Para construir un (n+1)-cubo ("cubo de dimensión n+1"), tomamos dos n-cubos A y B (dos cubos de una dimensión inmediatamente más baja). Sean a1,a2,...,a2^n los vértices de A y b1,b2,...,b2^n los vértices de B, al unir por aristas a1 con b1, a2 con b2, ... , a2^n con b2^n tenemos un (n+1)-cubo. Para quienes no conozcan la notación, "2^n" significa "dos elevado a la n-ésima potencia"; 2 multiplicado n veces. Simplificado: tomo dos cubos A y B de una dimensión inmediatamente más baja, y ligo con aristas cada vértice de A con exactamente un vértice de B.

Lo que para algunos puede no ser muy claro es que este método asume que un n-cubo tiene 2^n vértices. Pero esta cuestión es muy sencilla de demostrar:

* Claramente, un segmento tiene 2 = 2^1 vértices.
* Un cuadrado está formado por dos segmentos unidos por sus vértices. Cada segmento tiene dos vértices, por lo que tenemos 2 + 2 = 4 = 2^2 vértices.
* Un cuadrado está formado por dos cuadrados unidos por sus vértices. Cada cuadrado tiene cuatro vértices, por lo que tenemos 4 + 4 = 8 = 2^3 vértices.
* Etcétera, para dimensiones más altas.

De hecho, un punto consta de un solo vértice y su dimensión es 0; 1 = 2^0.

La lógica y los cubos.

Alguno diría "qué nexo puede llegar a haber entre un politopo, que es un elemento geométrico, y la lógica?". Otros afirmarían "pfff, por suerte todo se relaciona con la lógica, los cubos no son la excepción". Si bien no estoy seguro de la segunda afirmación (:P) sé que la primera es incorrecta. Inclusive, la correlación puede llegar a ser tan obvia (para nuestras mentes) que pocas veces la notamos.

Una proposición es una declaración que puede ser verdadera o falsa, pero no ambas al mismo tiempo (pues claro). Si es verdadera, se dice que su valor de verdad es verdadero; de lo contrario su valor de verdad es falso. Por ejemplo, "el sol es una estrella" es una proposición cuyo valor de verdad es verdadero, "dos y dos son cinco" es otra cuyo valor es falso. La declaración "qué bonito día!" NO es una proposición. Además, diremos que dos proposiciones son "independientes" si el valor de verdad de una no afecta al de la otra. Por ejemplo, podemos asumir que "yo tengo un gato" y "yo tengo un perro" son independientes, ya que podría no tener ninguno, podría tener uno de ellos, o incluso ambos (poco tiene que ver la propia rivalidad entre perros y gatos). Sin embargo, "hoy es lunes" y "mañana es martes" NO son independientes ya que si la primera es verdadera, la segunda también lo es.

Vamos a imaginar que tenemos una clase de mundo (algo así como una "plantilla") formada por una cantidad n de proposiciones independientes. Cada proposición será p1, p2, p3, ..., pn. Llamaremos a n el grado de la clase. Un mundo será una instancia de esta clase, donde cada proposición toma algún valor de verdad. Para ejemplificar, supongamos que nuestra clase está formada por n = 2 proposiciones, que son las siguientes:

p1: "Javier tiene un gato".
p2: "Javier tiene un perro".

Entonces, pregunto: cuántos mundos de esta clase podría haber? Respuesta: cuatro mundos.

Mundo número 1: p1 y p2 son falsos; o sea, Javier no tiene ni gato ni perro.
Mundo número 2: p1 es verdadero y p2 es falso; o sea, Javier tiene gato pero no tiene perro.
Mundo número 3: p1 es falso pero p2 es verdadero; Javier no tiene gato pero sí perro.
Mundo número 4: p1 y p2 son verdaderos; Javier tiene ambos.

En definitiva, es muy fácil enumerar los mundos para cada clase. Simplemente probamos todas las posibilidades, asignando verdadero o falso a las proposiciones. Entonces, en general, si tenemos una clase de mundo de grado n (con n proposiciones), cuántas instancias habrá? La respuesta es 2^n y el razonamiento es sencillo:

* Si n = 1, nuestra clase sólo está formada por una proposición; sea p1. Por ende, hay 2 = 2^1 mundos: en uno p1 es falso, en el otro p1 es verdadero.

* Si n = 2, la clase está hecha de dos proposiciones; sean p1 y p2. Notemos que si tomamos p1 podemos crear otra clase de grado 1; sea A. De la misma forma, podemos tomar p2 y crear otra clase de grado 1; sea B. Entonces, cualquier mundo de la clase está conformado por dos mundos, uno de A y otro de B. Cuántos mundos hay para A? Ya conocemos la respuesta por el punto anterior: 2. Y para B? Respuesta: también 2. Entonces cuántos mundos tenemos? 2*2 = 2^2 = 4.

* Si n = 3, la clase está hecha de tres proposiciones; sean p1,p2,p3. Con un razonamiento análogo al anterior, un mundo de nuestra clase está formado por tres mundos de clases de grado 1; sean A,B,C. Cuántos mundos hay para A? Ya conocemos la respuesta por el primer punto: 2. Lo mismo para B y C: 2 mundos. Entonces cuántos mundos tenemos? 2*2*2 = 2^3 = 8.

* Etcétera para grados más altos.

Se ve la relación entre clases y cubos? O entre mundos y vértices de un cubo? Notemos que dadas una clase de grado n y un n-cubo, podemos asignar un mundo a cada vértice del cubo... y viceversa: podemos asignar un vértice a cada mundo! Pero uno podría considerar esta correspondencia bastante trivial... más adelante mostraré que no es así.

Los conjuntos, la lógica y los cubos.


Pensemos en números naturales (son 0,1,2,3,4,5,... en adelante). De hecho, pensemos en conjuntos finitos de número naturales... son colecciones de números naturales, como por ejemplo {1,2,3}, o {1,3,5}, o {10}, o el conjunto vacío {} (es un conjunto con cero números naturales). Me gustan estos conjuntos ya que me gustan estos números... parecen ser "más reales que algunos reales"... esto me recuerda a una cita del matemático y lógico alemán Leopold Kronecker: "Dios sólo hizo a los naturales, todo lo demás es obra del hombre". En fin... Una "parte" de un conjunto X es un subconjunto de X. Por ejemplo, si X = {1,2,3}, entonces {2,3} es una parte de X, pero {3,5} NO es ya que 5 no está en la lista 1,2,3. Además, el conjunto vacío {} es parte de cualquier conjunto, y un conjunto siempre es parte de sí mismo. Representaremos a la colección de partes de un conjunto S como P(S). Pregunta: cuántas partes tiene X? O sea, cuántos elementos tiene P({1,2,3})? Contemos:

* Primero el conjunto vacío, 1.
* Contemos las partes de cardinal 1, {1}, {2}, {3}, son 3.
* Contemos las partes de cardinal 2, {1,2}, {1,3}, {2,3}, son 3.
* Contemos las partes de cardinal 3, {1,2, 3}, sólo 1.

En total: 1 + 3 + 3 + 1 = 2^3 = 8. Se observa la idea del planteo?

En general, supongamos que tenemos un conjunto finito S = {x1, x2, x3, ..., xn} cuyo cardinal es n (tiene n elementos). Cuántas partes tiene S? Respuesta: 2^n. La prueba es análoga a las anteriores, que demuestran que la cantidad de vértices de un cubo o la cantidad de mundos de una clase es una potencia de dos... se mantiene la naturaleza de recursividad, o de inducción...

Como existe una cantidad finita de partes, estas también pueden ser enumeradas. Vamos a usar una numeración bastante estándar, un algoritmo sencillo... para asignar un número a una parte T de S, empezamos asignando el valor 0 una variable r. Luego, recorremos todos los elementos de S, que son x1, ..., xn. Si i es tal que xi pertenece a T, le sumamos 2^i a r. Hago esto para todos los elementos xi de S. Finalmente, r será el número asignado a T. Por ejemplo, supongamos que S = {0,1,2} y T = {1,2}:

* Empezamos haciendo r = 0.
* x0 = 0 pertenece a S; pero está en T? NO, dejo r como está.
* x1 = 1 pertenece a S; pero está en T? SÍ, sumo 2^1 = 2 a r. r = 2.
* x2 = 2 pertenece a S; pero está en T? SÍ, sumo 2^2 = 4 a r. r = 6.

Resultado final: {2,3} tiene asignado el número r = 6. En general para este ejemplo tenemos 2^3 = 8 partes que se enumeran de la siguiente forma:

{} -> 0
{0} -> 1
{1} -> 2
{0, 1} -> 3
{2} -> 4
{0, 2} -> 5
{1, 2} -> 6
{0, 1, 2} -> 7

Se ve la relación entre conjuntos finitos de naturales, los cubos y las clases? Todo esto significa que dados un conjunto finito de cardinal n y un n-cubo, podemos asociar una parte a cada vértice del cubo... y podemos asociar un vértice a cada parte... y una parte a cada mundo... y un mundo a cada parte! Y aún más: podemos enumerar cada vértice, mundo o parte! En definitiva, existe la siguiente correlación:

Cubo........... Clase......... Conjunto finito
Vértice........ Mundo...... Parte (con su número natural asignado)
Dimensión... Grado....... Cardinal

Pero uno podría seguir creyendo que esta correspondencia es algo banal.

Vértices en el espacio.

No voy a profundizar en lo que es un espacio vectorial; sólo explicaré de forma sencilla qué es un vector: puede ser imaginado como un punto o vértice dentro de un espacio. En muchas ocasiones, quienes utilizamos el álgebra, nos enfrentamos a la tarea de trabajar con espacios de dimensión finita. Estos son, por ejemplo, los espacios unidimensionales, bidimensionales, tridimensionales (como lo es nuestro espacio físico), o tetradimensionales... en general, n-dimensionales, siendo n un número natural. En este artículo sólo mencionaremos espacios de dimensión finita.

Estos espacios son conjuntos de vectores (o vértices, o puntos); cada vector  ocupa un lugar distinto del espacio. Por lo tanto, si elegimos un punto de referencia, podemos concluir que cada vector tiene una posición. Esa posición puede ser representada mediante una lista (o tupla) de coordenadas, que son valores (en general numéricos) que codifican la posición del vector a lo largo de algún eje o dimensión.

Por ejemplo, supongamos que tenemos un espacio tridimensional V, formado por todos los vectores cuyas coordenadas son triplas de números enteros. Además, llamémosle "x" a la primera dimensión de V, "y" a la segunda, "z" a la tercera. Las siguientes son coordenadas de algunos vértices de V:

(1, 2, 3),
en este caso, la posición de nuestro punto a lo largo del eje x es 1, a lo largo del eje y es 2, para el eje z es 3.

(-1, 2, 3)
en este otro, la posición de nuestro punto a lo largo del eje x es -1, a lo largo del eje y es 2, para el eje z es 3. Notemos que este vector NO es el mismo que el anterior... su posición NO es la misma: que la coordenada x sea positiva o negativa significa que el punto está de un lado o del otro con respecto al plano formado por los ejes y, z.

(2, -3, 5)
este último caso representa al vector x=2, y=-3, z=5.

Notemos que, como NO puede haber dos puntos distintos en la misma posición, las coordenadas de un vector lo representan unívocamente. Por lo tanto, diremos que un vector es igual a su tupla de coordenadas. Por ejemplo, el vector (1,2,3) es el vector cuya posición es (1,2,3).

Para cerrar este apartado, observemos que un espacio de dimensión finita puede ser infinito. Por ejemplo, el espacio tridimensional conformado por "todas" las triplas de enteros es de dimensión finita (3); sin embargo hay una cantidad infinita de triplas de enteros. En los siguientes apartados, sólo nos concentraremos en espacios "totalmente" finitos.

Códigos lineales binarios.

Un código lineal binario (o para nosotros, simplemente "código") es un espacio vectorial finito (por ende, también de dimensión finita), constituido por tuplas de valores en {0, 1}. A cada vector se le llama palabra. Representaremos con Z(2,n) al código lineal binario de n dimensiones formado por todas las tuplas de valores {0, 1} y de longitud n.

Por ejemplo, las palabras (1,0,1), (0,0,1), (0,1,0), (0,0,0) pertenecen a Z(2,3), ya que son vectores de tres coordenadas {0, 1}. De hecho:

Z(2,3) = {(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}.

Pudimos enumerar las palabras de Z(2,3) ya que el espacio tiene una cantidad determinada de elementos. En general, cuántas palabras hay en un código Z(2,n)? Respuesta: como siempre, 2^n. La prueba es muy sencilla: ya que Z(2,n) tiene TODAS las palabras de longitud n, una palabra w de Z(2,n) podría contener 0 ó 1 en cualquiera de sus coordenadas. O sea, podemos asignarle a w el 0 en la primera posición, o tal vez el 1; el 0 en la segunda, o quizá el 1; etc. En definitiva: podemos asignar uno de dos valores a cada coordenada. Eso nos da una cantidad 2*2*2*...*2 [n veces] = 2^n de combinaciones... por ende, 2^n palabras.

Cuando hablamos de conjuntos finitos en un apartado anterior, aprendimos que el conjunto de las partes de {0, 1, 2} (P({0,1,2})) tiene 2^3 = 8 elementos. Existirá una correlación entre P({0,1,2}) y Z(2,3)? Claro que sí: podemos asignar exactamente una palabra de Z(2,3) a cada parte de P({0,1,2}), de la siguiente manera:

sea w = (w0, w1, w2) una palabra de Z(2,3). Elegimos una parte X de P({0,1,2}) tal que X contenga 0 si y sólo si w0 = 1, que contenga 1 siempre y cuando w1 = 1 y que tenga a 2 si y sólo si w2 = 1. A esa parte X le asignamos w. Para ilustrar, damos las asignaciones de cada parte:

{} -> (0, 0, 0)
{0} -> (1, 0, 0)
{1} -> (0, 1, 0)
{2} -> (0, 0, 1)
{0, 1} -> (1, 1, 0)
{0, 2} -> (1, 0, 1)
{1, 2} -> (0, 1, 1)
{1, 2, 3} -> (1, 1, 1)

Pero, como cada parte tiene un número natural asignado, podemos asociar un número natural con cada palabra!:

  {} <-> (0, 0, 0) <-> 0
{0} <-> (1, 0, 0) <-> 1
{1} <-> (0, 1, 0) <-> 2
{2} <-> (0, 0, 1) <-> 4
{0, 1} <-> (1, 1, 0) <-> 3
{0, 2} <-> (1, 0, 1) <-> 5
{1, 2} <-> (0, 1, 1) <-> 6
{1, 2, 3} <-> (1, 1, 1) <-> 7

De hecho, para quienes conocen de la materia, las palabras y su número asociado son representaciones del mismo valor, sólo que una en binario (base 2) y la otra en decimal (base 10), respectivamente.

Estas cualidades no sólo se cumplen para n = 3, sino que para cualquier n natural! Por ende, tenemos la siguiente correlación:

Cubo........... Clase......... Conjunto finito......... Código
Vértice........ Mundo...... Parte......................... Palabra
Dimensión... Grado....... Cardinal................... Dimensión (del código)

Finalizando este artículo...

En definitiva, la tabla anterior resume íntimos paralelismos entre estructuras aparentemente distintas. Quizá en diversos ambientes sea conveniente considerar que cubos, clases, conjuntos finitos y códigos son "la misma cosa".

Por otro lado, ya que este artículo se me ha hecho algo extenso, dejaré los temas de distancia de Hamming, coloreo de grafos y ciclos de Hamilton para el futuro. Hay mucho más por descubrir detrás de la inocente traza de un discreto cubo.

Más info:
http://es.wikipedia.org/wiki/Politopo
http://es.wikipedia.org/wiki/Hipercubo
http://es.wikipedia.org/wiki/Grafo
http://es.wikipedia.org/wiki/Proposici%C3%B3n
http://es.wikipedia.org/wiki/N%C3%BAmero_natural
http://es.wikipedia.org/wiki/Leopold_Kronecker
http://es.wikipedia.org/wiki/Conjunto_enumerable
http://es.wikipedia.org/wiki/Recursividad
http://es.wikipedia.org/wiki/Inducci%C3%B3n_matem%C3%A1tica
http://es.wikipedia.org/wiki/Algoritmo
http://es.wikipedia.org/wiki/Espacio_vectorial
http://es.wikipedia.org/wiki/V%C3%A9rtice_%28geometr%C3%ADa%29
http://en.wikipedia.org/wiki/Linear_code
http://es.wikipedia.org/wiki/Base_%28aritm%C3%A9tica%29

Mi música!

Algo de mi música (y con amigos). Lo seleccionado desde 2004 hasta 2010. ;)

Buscá...

Buscá y encontrá lo que quieras en alguno de mis espacios (La Mezcolanza, C^2 ó mi canal en Youtube) o en alguno de los sitios amigos.

Posts recientes

Contate algo...