23 julio, 2007

Aficiones secretas II: Origami

Bien, he aquí el segundo capítulo de las aficiones de Aitor Menta. Si la primera era el japonés, la segunda está muy relacionada. Se trata del Origami, o papiroflexia, en fin: el sutil arte de crear vida de la materia. Hacer papiroflexia genera una especie de sentimiento de omnipotencia, algo siempre reconfortante. Como siempre, aquí contaremos una:

Historieta del Origami

El papel procede de China, y fue transportado a Japón con los mojes budistas en torno al s. VI. (quienes, como ya sabemos, llevaron también la escritura y el budismo). Los chinos ya habían desarrollado diversas figuras de papel, muy sencillas si las comparamos con las actuales. Por supuesto fueron los japoneses, que deben ser un pueblo con unas increíbles ganas de aprender cualquier cosa chorra, quienes convirtieron el origami en toda una disciplina.


Se cree que el origami en este sentido desciende de una tradición (noshi) consistente en acompañar regalos de una sencilla figura doblada. No es de extrañar que poco a poco estos modelos fuesen complicándose llegando a constituir regalos en sí mismos. Cuando finalmente el coste del papel se hizo más asequible, se convirtió en un entretenimiento y ejercicio, con ciertas connotaciones espirituales.

Pero el papel no se quedó en China. Los árabes en su expansión del s. VII habían invadido zonas del país y de los prisioneros aprendieron cómo doblar papel. Por desgracia, los musulmanes tienen prohibida la representación de animales o humanos (quizá por aquello de la omnipotencia) y el arte musulmán consistió en la elaboración de figuras geométricas que sirvieron, al irse complicando, de modelo o inspiración en construcciones arquitectónicas. En Játiva, por cierto, los musulmanes construyeron la primera fábrica de papel de Europa.
Por otro lado, Marco Polo también trajo papel de sus extraños viajes en el s. XIII. El papel tardó en asentarse en Europa, pues el pergamino era más resistente... pero también más caro.

A través de los españoles, el papel cruzó el océano y fue a las américas. Y en cada zona del mundo el arte de crear figuras con él se desarrolló de distinto modo. En Japón se practicaba sobretodo una disciplina del origami llamada Kirigami 切り紙 (cortar y papel), donde se utilizaban cuchillas, pegamento y colores para componer muy complicadas figuras.

Las distintas tradiciones sólo pudieron confluir cuando el Shogun 将軍 japonés se vio obligado a abrir sus puertos comerciales al resto de países en 1854, presionado por los EE.UU. También como consecuencia directa de esta presión internacional se inició la restauración Meiji, que devolvió al poder al Emperador... pero eso no nos interesa tanto como la papiroflexia.

Encontradas las distintas tradiciones surgieron poco a poco las convenciones. En primer lugar el nombre: origami (折紙 doblar y papel), cuyo origen es más bien incierto y data de finales del s. XIX. Quizá proceda de una traducción del alemán, papierfalten. A los niños japoneses se les empezó a enseñar en la escuela desde pequeños. Quizá por ser sus caracteres más sencillos que otros que se referían al mismo arte (los japoneses aprenden kanjis escalonadamente) se impuso este nombre.

El origami que hoy más conocemos desciende de Akira Yoshizawa quien junto a Sam Randlett ideó en 1950 un método para describir los pliegues en secuencias. Éste código constituye un lenguaje universal y su uso permite que todos los plegadores de papel del universo que lo conozcan puedan distribuir y componer sus modelos de forma sencilla. Akira Yoshizawa ha creado más de 50000 figuras y es uno de los grandes genios de la papiroflexia. Según sus consejos, es necesario meditar y rezar antes de elaborar la figura. Tras ella, es necesario lavarse las manos. El origami es en ese sentido similar al arte de la caligrafía japonesa, o shodou, que también requiere de la introspección.

En el origami "moderno" el pegamento y las tijeras están prohibidos. Las figuras deben hacerse preferiblemente con un sólo trozo de papel, que se pliega formando bases. Además, si el papel es de dos colores, se busca que la figura quede con un color uniforme a su realización.

En la actualidad, el origami ha desembocado en muchas vertientes. Las nuevas técnicas de plegado permiten la realización de impresionantes figuras modulares. Además, se han desarrollado estudios que relacionan las matemáticas con el origami, en estudio de fractales, por ejemplo. El origami es algo muy informático, por cierto: se ha determinado que el problema de doblar un modelo desde su representación como patrón de doblado pertenece a la clase de problemas NP-completos, un concepto relacionado con la complejidad computacional (ya vimos algo de ello cuando ordenábamos longanizas).

Las técnicas más modernas de la papiroflexia, en especial el Origami Sekkei 折紙設計 se encomiendan a los ordenadores para desarrollar modelos impresionantes. El padre de esta disciplina el es profesor Robert Lang, que ha utilizado sus conocimientos matemáticos (y físicos) para crear esta langosta que ustedes están viendo... de un sólo trozo de papel sin cortar.

En la actualidad, Aitor Menta se encuentra retirado de la papiflexia de forma activa, aunque en pasado le dedicó muchas horas, con la intención de ligar, principalmente. Los resultados fueron funestos. Y es que no se puede asentar una relación sobre papel. Por cierto, en la primera imagen vemos un pegaso (autor: Eduardo Clemente) un águila (autor J. Wu) y un zorro (extraído de un libro de papiroflexia polaco, en polaco).

Origami en la wikipedia: un artículo muy completo.
Pajarita: asociación española de papiroflexia.
J. Wu: Otro genio de la papiroflexia. Comprobad, si no, su galería.
KameKameHa: Modelos de Origami sekkei y sus diagramas.

19 julio, 2007

Muy breve historia de la Cerveza (II)

De Carlos I al Frío Industrial

Esta entrada es una continuación de esta otra...

Pero puedo hacer un resumen rápido para vagos: la cultura de la cerveza se desarrolló simultáneamente en todos los lares de la tierra, si bien arraigó especialmente en las orillas del Eufrates y el Nilo. Más tarde los celtas hicieron de ella parte fundamental de su cultura gastronómica, de donde procede en cierta forma su fama de bebida "bárbara".

Nobles y especialmente monjes de distintas órdenes monásticas dignificaron la bebida mejorando el proceso de producción. Bajo el imperio de Carlos I se promulgó en Baviera la Ley de Pureza Alemana en 1516, de carácter proteccionista. Carlos I era tan aficionado a las cervezas de su país que aquí le llamaban quinto de Alemania (vale, es MUY malo, y qué, éste es MI blog).


En el periodo comprendido entre el siglo XVI y el XIX la cerveza alcanza su esplendor en las regiones de Flandes y Gante, que por otro lado vivían un gran momento como centros comerciales de Europa. La Ley de Pureza Alemana tuvo, por otro lado, consecuencias nefastas en lo que a cultura cervecera se refiere. A lo largo de los siglos siguientes se extendió lentamente a lo largo de la geografía alemana. La limitación en los ingredientes impidió que distintos tipos de cerveza proliferasen y sólo con suerte se pudieron salvar algunos estilos antiguos de fabricación tradicional en ciertas zonas (Como la Altbier, típica de Düsseldorf).

Y sin embargo, fue en estas regiones donde hicieron uno de los mayores descubrimientos de la historia de la cerveza. En Baviera, en torno a los siglos XV y XVI ya habían observado que, manteniendo la cerveza en grutas heladas, parte de la levadura se estabilizaba en el fondo de la misma (al modo tradicional quedaba flotando, por lo que se le conoce como levadura de alta fermentación). De este modo fabricaban la cerveza en invierno, dejándola reposar más tiempo en estas grutas. Sin saberlo, estaban inventando las cervezas Lager. Lager significa almacén en alemán.

Pasarían muchos más años hasta que un joven llamado Gabriel Sedlmayr se interesase por esta forma de producción. Gabriel, que era hijo de padre del mismo nombre y tenía una larga tradición cervecera a sus espaldas, emprendió un viaje por Europa donde aprendió todo lo que se podía saber en la elaboración de cerveza. Investigando (más bien probando) conseguiría refinar y mejorar el proceso de baja fermentación. A la muerte de Gabriel Sr., en 1839, sus hijos se encargarían de modernizar su cervecería, conocida mundialmente como Spaten-Franziskaner.

La nueva técnica se extendió a otras ciudades. En cada una de ellas, la distinta composición de las aguas y maltas daba lugar a un tipo de cerveza distinto... así la de Munich era más oscura y amarga, mientras que la de Viena tenía un color cobrizo.

Y de este modo llegó a Plzen, una ciudad situada en la zona de Bohemia, actual República Checa. En ella, un joven bávaro llamado Josef Groll fue contratado para elaborar cerveza. Experimentando con el lúpulo local, una malta muy pálida y agua de bohemia, inventó -para delicia de la variedad cervecera- lo que hoy llamamos Pilsener: una cerveza suave y aromática con un increíble color dorado. Era 1842. Las botellas de Pilsner Urquell todavía alardean de haber sido las primeras de la que hoy es la variedad de cerveza más extendida del mundo. Curiosamente, cuando expiró el contrato de Josef, no fue renovado.

Pero el siglo reservaba todavía la mejor de sus sorpresas. En 1857, un joven químico llamado Louis Pasteur realizó el descubrimiento más importante de la historia de la elaboración de cerveza y vino. Hay que hacer notar que, siendo estudiante, este joven sólo obtuvo notas mediocres en química hasta que encontró un buen profesor de la materia. Ténganlo en cuenta si por casualidad ustedes son profesores de química en u instituto.

Lo que Pasteur hizo fue demostrar que la fermentación era un proceso realizado por unos microorganismos, unos hongos llamados levaduras1. Además, estos no crecían por generación espontanea, una teoría bastante aceptada en la época. Con ello, Pasteur sentó las bases de la teoría de los gérmenes, que habría de cambiar profundamente la concepción de la vida. El control de los gérmenes y microorganismos fue crucial en muchos campos, como en la cirugía. Pero este no es un blog de cirugía...

El estudio de Pasteur pretendía conocer y controlar el proceso de producción del vino, pero igualmente podía ser aplicado a la cerveza. En 1976 Pasteur publicó sus estudios sobre la levadura de cerveza. La pasteurización se aplicó por primera vez a la cerveza en 1873, en la ciudad norteamericana de San Louis.

El resto es otra historia. En 1883 fue descubierta la levadura que hacía posible el tipo de fermentación a baja temperatura y en el fondo de la cuba. Lo descubrió Emil Christian Hansen, que trabajaba para Calsberg. En su honor (el del jefe, claro) ésta lleva su nombre: Saccharomyces carlsbergensis.

Las nuevas técnicas de frío industrial de finales del XIX (gracias a la aportación de Carl von Linde), cambiaron para siempre el mundo de las cervezas. Por lo pronto, las cervezas Lager se conservaban mucho mejor que las tradicionales y se adaptaban a gran variedad de gustos, lo que permitiría que desplazasen poco a poco a las Ales, las tradicionales cervezas de alta fermentación. Pero cada una de estas historias merece ser ser contada tranquilamente. En el siguiente post cervecero os contaré una historia (esa sí que será muy breve) de la cerveza en España.

Una historia en la que Aitor Menta, de algún modo u otro, pretende escribir un par de lineas.

1 En 1839 el biólogo Cagniard Latour ya se había dado cuenta de este hecho. Cómo se producía y los distintos tipos de fermentación fue estudio de Pasteur

La Cerveza, Manual de uso. Pedro Plasencia.
Moritz. Atlas Histórico de la cerveza.
¡Y todas la referencias del texto!


Posts relacionados

13 julio, 2007

Los "héroes" y el socorrista

Al ver ésta noticia, se me ocurrió publicar, a modo de opinión personal, lo que pienso acerca de estos "héroes". Al menos así han sido calificados por los agudos comentaristas de 20minutos. Con los comentarios del 20Minutos tengo un problema. Sé que su lectura me producirá una patada en el estómago y, sin embargo, no puedo evitar leerlos. Es un caso curioso de masoquismo.

Bien, de héroes nada. Arrojados sí, y también bastante inconscientes. Si una niña cae con problemas respiratorios y yo, sin conocimiento médico alguno, decido realizarle una traqueotomía, no seré un héroe. Seré más bien idiota. Para rescatar a alguien en el agua también es necesario saber salvar y en demasiados casos los improvisados rescatadores fallecen junto con la víctima. Al menos en este caso la niña se salvó, poniendo la nota irónica al asunto.

Nadar es un deporte cansadísimo. Y el rescate es unas 10 veces más cansado que la natación. Lo sabe Aitor Menta que fue socorrista acuático y ha visto a gente MUY fuerte vomitando la primera papilla en la segunda piscina. Así que ya lo saben. Si no han probado nunca a arrastrar a alguien 200 metros, mejor no intenten ser héroes. No es tan extraño: al igual que sucede con los accidentes de tráfico, si no se sabe qué hacer, lo mejor es no hacer nada.


Pero como no quería que el post quedase como una simple opinión, aprovecharé y contaré una:

Breve historia del salvamento acuático

Evidentemente, la historia del salvamento acuático se remonta a los orígenes de la humanidad. En cuanto el ser humano tuvo que cruzar ríos, lagos y mares, tuvo que aprender a nadar, de algún modo u otro. El ser humano siempre ha permanecido cerca de ríos y aguas y saber nadar era garantía de supervivencia en casos desafortunados.

El primer cuerpo de "salvadores" como servicio público fue creado por el emperador Augusto en el 63 a.C. Sin embargo fue en China donde por primera vez se instalaron salvadores a orillas de los ríos, para proteger las vidas de la gente.

En 1785 se fundó la "Massachusetts Human Society" [de la que no he encontrado referencias], que condecoraba a socorristas voluntarios con medallas y retribuciones económicas. En el s. XIX aparece en París el cuerpo de "Salvadores del Sena", un cuerpo profesional y experimentado en la lucha contra los ahogamientos.

El salvamento moderno aparece a finales del s.XIX cuando experimentó un gran impulso de la mano de Raymond Pitet (del cual sólo he encontrado esto), fundador del Instituto de Salvamento Acuático y promotor del primer congreso Internacional de Salvamento en 1878, celebrado en Marsella. Gracias a él se extendieron las asociaciones nacionales dedicadas al salvamento: en España se creó la Sociedad Española de Salvamento de Náufragos en 1890, en Portugal su homóloga en 1892, en Australia en 1894... A principios del siglo pasado, gracias fundamentalmente a Raymond Pitet, ya existía una Federación Internacional de Salvamento (FIS).

Por cierto que de la misma época data la invención del primer flotador salvavidas: fue desarrollado por el capitán Harry Sheffield para un club de salvamento de Sudáfrica en 1987. Era terriblemente pesado. (Y aún hoy los de plástico duro naranja son bastante inmanejables).

Gracias a estas asociaciones y a sus méritos el salvamento empezó a ser profesional a principio de siglo pasado: La ciudad de Long Beach (California) contrató su primer socorrista en 1908. Los famosos vigilantes de la playa de Los Ángeles comenzaron su andadura en 1925 y su primer jefe formuló el principio que hoy en día rige el salvamento acuático: "prevenir un rescate en lugar de hacerlo". Hoy en día, tras la unión de FIS y WLS, una gran sociedad agrupa la mayor parte de federaciones nacionales bajo los mismo principios.

Por su parte, en España, tras muchos cambios y vicisitudes, se creó en 1961 la Federación Española de Salvamento y Socorrismo, de la que surgieron las federaciones provinciales. Con la autonomía se creó la Federación de Salvamento y Socorrismo de la Comunidad Valenciana en 1987, dependiente de la administración valenciana, agrupando las tres federaciones provinciales.

En la actualidad la FSSCV tiene como objetivo fomentar el deporte del salvamento acuático (algún día hablaré de él), la formación de de profesores y socorristas acuáticos y la difusión del salvamento por medio de programas educativos, además de concienciar a la población de su tarea y los riesgos del agua.

Y parece que en esto último está fracasando. Cada verano escuchamos advertencias institucionales acerca de los incendios, del calor, del ahorro de agua... pero nada acerca de los peligros del agua, que se cobra más víctimas que todos los anteriores. Por otro lado la autonomía de las federaciones ha supuesto mayor independencia y adecuación a los problemas locales... pero también la falta de una reglamentación unitaria en cuanto a la normativa del salvamento e instalaciones acuáticas. No está claro quién puede ejercer de socorrista, ni qué requisitos debe reunir el socorrista. En muchos pueblos vigila la playa o piscina el socorrista formado por una empresa privada que tiene un acuerdo con el ayuntamiento, ofreciendo sus servicios a bajo precio. Algunas empresas ahorrarán pues todo lo posible en formación.

La formación acuática de los miembros de la Cruz Roja (los más habituales) deja MUCHO que desear. Lo dice un servidor, que los ha visto hacer prácticas. En cuanto a la Federación, son más estrictos con las pruebas físicas y obligan a realizar cursos de reciclaje para mantener la licencia... pero son pocos los empleadores que demanden una licencia federativa en vigor.

Con esto no quiero decir que de haber estado un socorrista de la FSSCV se habrían salvado dos vidas. Ni que otro no hubiese hecho el rescate. Pero incluso el socorrista más experimentado puede ser arrastrado por las corrientes. Por eso mismo es necesario cierto respeto por la profesionalidad en el rescate... y evitar en lo posible las heroicidades 20minuteras.

"Reseña histórica del salvamento acuático" de la FSSCV.
FSSCV (advertencia, página horrible para diseñadores web)
Historia de la FIS
Atleta y socorrista

12 julio, 2007

Memes desde Springfield

Como Pinar y yo, currar, lo que se dice currar, más bien poco (nos dedicamos a la investigación y ya se sabe que, en España, para que la investigación esté bien pagada lo mejor es hacer lo mínimo posible) pues a veces almorzamos -de verdad- y a veces comentamos -electrónicamente- lo que vemos por la web.

Así me he enterado de lo que es un "meme". Recién llegado a la blogosfera, Aitor Menta está en pañales todavía. Pues nada. Para quien no lo sepa, un meme viene a ser una chorrada que se divulga rápido. Más que nada porque en la blogosfera es práctica habitual difundirlo a otros blogueros con los que uno esté en conexión (5 personas, por lo común). A veces son preguntas personales o manías... a veces son cosas como ésta.

Pues eso, que me he creado un avatar con la imagen de Aitor Menta, tal y como (yo creo que) sería de haber nacido en Springfield. Aprovecho para decir que el personaje favorito de Aitor Menta es el jefe Wiggum, al cual adora y reverencia.

Pero como a través de mis ojos Aitor Menta es demasiado guapo, creo que será mejor pedir ayuda a una mano inocente para que me ayude. Por supuesto, yo también plasmaré la esbelta figura de Aitor en Springfield... y luego publicaré ambas. De este modo sabremos hasta qué punto mi visión está sesgada por mi admiración por Aitor.

Así que la cosa continuará. Por cierto, que debería pasar este meme a cinco personas. Pero como no tengo mucho amigos, aparte (claro está) del vendedor de camisetas personalizadas, pues aquí lo dejo. Por otro lado, ya he explicado que a los informáticos nos dan miedo las potencias... y las de cinco ya ni te cuento.

Actualización

¡Ya están los avatares listos!. Pues bien, sorpresas no ha habido. La mano "inocente" que ha retratado a Aitor Menta (la llamaremos "Química Loca") ha finalizado su trabajo y por fin podemos comparar los resultados.



Este de la izquierda es el que he hecho yo. Y este, más bajito y cachas lo ha hecho Química Loca. ¡Muchas gracias, por cierto a la susodicha!

En fin, que habrá que preguntar a Pinar qué piensa del resultado. Lo siguiente será enviar a los creadores de la serie el avatar, por si les interesa tener algún informático menos freak que no esté obsesionado con los Monty Phyton.

¡Saludos desde Springfield!

Cosas del japonés (y la japonesa): Respeto

¡Qué cosas tienen los japoneses!. Eso, o algo similar es lo que decimos al contemplar, desde la ventana de Youtube, los vídeos que desde el país del sol naciente nos llegan. Dado que la cultura nipona es tan diferente de la nuestra (apenas hace 50 años que la cultura occidental ha penetrado en las islas), no puede dejar de sorprendernos.

La lengua propia recoge de forma natural las características de la cultura y es la correa transmisora de ésta. Un ejemplo que no me invento yo: la palabra esposa, que se puede escribir con los kanjis 家内 (casa y dentro) o 女房 (mujer y habitación). ¿Qué por qué sucede esto? Pues por esto.

El estudiante de japonés descubre estas características poco a poco. Y tardará más en aprender a usar correctamente el lenguaje. Pero una de las cosas que primero aprende y más llama la atención del estudiante es el respeto impreso en el lenguaje. Podemos decir que el japonés distingue entre el idioma formal y el informal... y nos quedaríamos muy cortos.


Existen tres tipos de lenguaje formal: el lenguaje de respeto 尊敬語 (sonkeigo), el de modestia 謙譲語 (kenjougo) y el pulcro 丁寧語 (teineigo). [Los más avispados concluirán que "go" significa lenguaje o idioma]. El informal admite muchas gradaciones, aunque principalmente se distingue entre coloquial y vulgar. La diferencia va más allá de lo que podemos expresar con ejemplos en castellano: la lengua japonesa es demasiado rica en ese sentido y muchos matices se suelen perder en la traducción. Pondremos algunos ejemplos sencillos, sin embargo.

Existen varios pronombres personales para referirse a la primera persona, por ejemplo. El uso de uno u otro dependerá del nivel de formalidad de la situación. Para los pronombres podemos distinguir hasta 4 grados de formalidad. Los mas formales sólo se utilizan en documentos oficiales o están sencillamente en desuso. Los más vulgares son insultos en sí mismos. Eso sucede con los pronombres para referirse a la segunda persona del singular: てめえ temee y きさま kisama. Se utilizan con profusión en mangas y animes y las traducciones siempre quedan algo cojas. Podemos traducir kisama por tú, gilipollas. Pero es más complicado traducir algo como てめえの力 temee no chikara (tu fuerza). Una solución es: Tu fuerza, gilipollas. Convendrán conmigo en que se pierde el toque.

Tabla ejemplo de pronombres:


Algunos pronombres (¡hay muchos más!)
Primera persona (singular) Segunda persona (singular)
Muy formal

watakushi


Formal私 watashiあなた anata
Informal僕 boku (hombres)
あたし atashi (mujeres)
君 kimi
Coloquial俺 ore (hombres)
お前  omae (hombres)
あんた anta (mujeres)
Vulgarあっし asshi (hombres)

(insultos)

てめえ

きさま



Hombres y mujeres no usan los mismos pronombres (y ese es el significado de los paréntesis). Esa es otra característica notoria del idioma. Expresiones, prefijos o partículas son usados exclusivamente por hombres o mujeres. Evidentemente, el hombre que "se equivoca" de partícula es visto como afeminado. La mujer que usa una expresión de hombre es "ruda".

Una vez conocemos los pronombres, suele ser útil aprender algunos verbos y decir cosas como "tú lees", o "yo escribo", o frases de similar trascendencia léxica. Conjugar verbos en japonés es más fácil que en castellano, y muy diferente. Fundamentalmente, porque existen dos tipos de conjugaciones: formal e informal. Por cierto, que sólo hay un pasado y un presente (y no hay futuro verbal). Incluso hay una conjugación especial para sonkeigo, y versiones kenjougo de algunos verbos.

De nuevo, atendiendo a la situación, tendremos que seleccionar la forma verbal que más se ajuste al grado de formalidad en que se desarrolle la conversación. No será lo mismo hablar con un desconocido que con un amigo íntimo. No es lo mismo un desconocido al que ayudamos que un desconocido que visita nuestra casa. El desconocido puede estar situado jerárquicamente por encima de nosotros (y utilizaremos el kenjougo) o puede tener un empleo de menor entidad (teineigo). Y, por si todo esto fuera poco, ¡también depende de lo que hablemos!.

Se entiende por tanto que el japonés pueda sonar completamente diferente en función de la situación en que se produzca la conversación (bueno, sólo si se entiende algo: de no entender nada suena todo igual). Y eso es lo hizo que Richard Feynman (que se dedicó a hacer de todo) desistiese del estudio del japonés. Según se cuenta en "¿Está usted de broma, Sr. Feynman?", no pudo entender por qué la misma frase, con el mismo significado, se debía expresar de forma distinta según quién la expresase. Así que al fin y al cabo, Feynman tenía una limitación poderosa: la lógica.

Y, como el tema da mucho de sí, lo dejaremos para otro día... y a otra cosa mariposa.

Japonés en viñetas. Norma editorial.
Japonés en viñetas 2. Norma editorial.

06 julio, 2007

CSI III: Ordenando longanizas (y 3)

Aprovecho para indicar que CSI significa Cosas que SÍ se dan en Informática, que, para quien no lo sepa, es una serie de cosas que se estudian en la carrera de Ingeniero Informático según el plan de estudios aprobado en les Corts que correspondan.

Vale, tras los posts 1 y 2 de la serie Ordenando Longanizas, tenemos algoritmos (formas de hacer cosas) para ordenar un vector. Todos tienen coste cuadrático en el peor caso, lo cual implica que, a malas y con un conjunto de datos muy grande, tendremos que inventar alguna excusa creíble (la red, un virus, el Windows...) para justificar el cuelgue. En eso somos muy buenos, los informáticos.

Afortunadamente, existen métodos mejores para ordenar vectores. Afortunadamente digo, porque los inventó gente bastante más lista que tú y que yo. Cuando se recuerda al autor de un algoritmo, entonces es que es muy bueno. Y uno de los más buenos es:

El Quicksort, de Sir Richard Hoare


En 1960 este señor inventó una técnica para ordenar vectores que, tras muchas aportaciones, se ha convertido en una de las más populares y eficaces para ordenar vectores. La idea es la siguiente: seleccionaré un elemento cualquiera del vector (pivote) y situaré los elementos más pequeños que él a su izquierda y los más grandes a su derecha. Cuando esto suceda, el pivote estará en su posición final.

Vale, eso es fácil de decir. ¿Cómo situamos a la derecha y a la izquierda para todos los elementos?. Bueno, pues sencillamente intercambiaremos los elementos mayores que el pivote que estén a la derecha (descolocados) con los menores que el pivote que estén a la izquierda (descolocados). Vamos recorriendo por ambos lados el vector y cuando nos crucemos... ahí colocaremos el pivote. En total sólo tenemos que recorrer la longitud del vector para obtener la posición de un elemento (como los trenes que al chocar suman la distancia que les separaba).

A ver 4 7 2 43 14 1. Suponed que cogemos el 4 como pivote. Empezamos a ver si tenemos que intercambiar por los extremos. Como 7 es mayor que el pivote y el 1 menor, los intercambio, hop: 1 2 43 14 7. Seguimos: como el 2 no es mayor que el 4 avanzo el indice y miro el 43. Lo señalo y busco elementos menores que 4 desde atrás: 14, no, 43, no, 2... un momento: ¡me he pasado!. Eso quiere decir que ya estoy señalando el lugar correcto donde insertar el pivote. Lo pongo donde señala el 2. Diréis: lo más listo sería ponerlo donde el 43. Sí, pero los algoritmos no son listos: hacen lo que tienen programado y ya. Como hemos intercambiado, tenemos algo como 2 1 4 43 14 7.

Y ahora viene lo bueno. El 4 está ordenado. Lo que no lo está son las 2 subvectores que tiene a cada lado. Para ordenarlas... aplicaremos el mismo algoritmo a cada una de ellas. La lista 2 1, el pivote es el 2 y hay que cambiar con el 1. Por tanto intercambio 2 con el 1. ¡La única dificultad consiste en saber cuándo parar de hacer esto!.

Por cierto que esto que hemos hecho (utilizar la función dentro de la misma función) se llama llamada recursiva. Al principio de programar no es sencillo pensar en funciones recursivas pero una vez las conocemos, resulta difícil no hacer uso de ellas.

Así que Quicksort funciona así: intercambia los elementos descolocados en relación al pivote y finalmente sitúa el mismo en su posición final de la lista. Luego utiliza el mismo algoritmo para ordenar los dos (o uno) subvectores que quedan a los lados del pivote.

¿Y cuánto cuesta esto?. Supongamos que, en el mejor caso, el pivote escogido resulta quedar en el medio del vector, partiendo el mismo en dos mitades equilibradas. Sabemos que entonces hay 1 elemento ordenado. Las siguientes llamadas a Quicksort hacen lo mismo, de modo que tras ellas, el vector queda dividido en cuatro partes equilibradas: en ese momento hay 3 elementos ordenados. Luego en 8, 16... . En fin que estamos calculando potencias de 2, que nos permiten ordenar tantos elementos -1. Razonando de forma inversa, si tenemos n elementos a ordenar, ¿cuántas veces hemos de aplicar este algoritmo?: pues los que nos enseñaron que era "el contrario" de la potencia: log(n).

Podemos imaginar este proceso en forma de árbol. En el primer nivel ordenamos el primer pivote y llamamos a las funciones para ordenar los elementos que quedan a la izquierda y a la derecha. Estas llamadas forman parte del segundo nivel, que ordenan otros dos elementos. El tercer nivel ordena cuatro más... Como las cantidades crecen muy rápido, el número de datos que podemos ordenar también lo hace sin más que aumentar un poco la altura del árbol. Por eso son tan buenos los algoritmos de costes logarítmico.

En cada nivel, las distintas llamadas sólo tratan partes disjuntas del vector original, de tamaño n. Ya sabemos que en cada una de ellas el coste de colocar un elemento en su posición es lineal con orden del tamaño del vector. Como las partes del vector en cada nivel suman n, el coste de cada nivel es O(n). Como tenemos log(n) niveles, el coste total del Quicksort en su mejor caso es O(nlog(n)).

¡Pero eso no nos vale!. ¿Qué pasa en el peor caso?. Pues que tenemos la mala pata de elegir siempre un pivote que resulta ser el mayor o el menor elemento de los que tenemos que ordenar. De modo que siempre perdemos una de las ramas del árbol y resulta que tenemos llamar n veces a una función que tarda O(n) en ejecutarse:. Total O(n2). Sucedería si siempre escogiésemos como pivote el primer elemento en un vector ordenado. Hay formas muy sencillas de evitar esto, escoger como pivote el mediano de tres elementos, o escogerlo simplemente al azar.

Pero ya sabemos un poco más y nos preguntamos: ¿qué sucede en el caso medio?. Pues que, aunque la elección del pivote separe de forma descompensada el resto de elementos, el coste sigue teniendo una forma logarítmica. Supongamos un caso mínimamente mejor que el peor caso: sólo dejando dos elementos a ordenar en un lado en cada partición. En ese caso la altura del árbol se reduce a la mitad y por tanto, el coste es la mitad que el del peor caso. La altura del árbol se reduce mucho con poco que equilibremos las ramas

Resultado final: mejor caso O(nlog(n)), peor caso (evitable) O(n2), caso medio O(nlog(n)). Por cierto no hay ningún algoritmo que ordene un vector con coste teórico inferior a O(nlog(n)). Los hay que tienen mejor coste en circunstancias muy especiales, los hay que arrojan mejores resultados experimentales que el Quicksort en el caso medio, los hay cuyo peor caso es mejor... Pero si usted descubre algún método de ordenar longanizas con un coste teórico menor... no se lo cuente a nadie y envíelo a Aitor Menta para que, amablemente, lo publique verifique.

Posts relacionados