Cosas que SÍ se dan en Informática (II)

Ordenando longanizas. Segundo capítulo.

Vale. Supongamos que nos hemos leído el primer capítulo. Dado que esto no es como una novela de Dan Brown, sería aconsejable haberlo leído para entender lo que viene ahora, sobretodo si uno no estudió informática (que raro, no estudiar informática).

Tenemos un procedimiento para ordenar vectores que tiene un coste temporal cuadrático O(n²) y ahora queremos otro método mejor, es decir, con un coste menor. O con el mismo coste y que además reproduzca una música linda al terminar.

Una idea consiste en disponer de un procedimiento (función) que calcule el mayor elemento de un vector, para colocarlo al final. Esta función es muy sencilla, recorre los elementos del vector comparando el mayor obtenido con el siguiente elemento. Es decir, almacena el mejor encontrado a cada paso, recorriendo todos los elementos. Esa función tiene por tanto un coste lineal -O(n)-, pues se ha pateado los n elementos. ¿Cuántas veces tenemos que llamara a esa función?. Pues n-1. Cuando todos los mayores elementos - 1 estén en su posición, el primero será el más pequeño. Cada vez que llamamos a la función, por otro lado disminuimos en uno el tamaño del vector, ya que la última posición ya ha sido correctamente ocupada por el mayor elemento que la función obtiene. Esto no nos preocupa cuando calculamos costes, como ya vimos. Por tanto el coste temporal es O(n²)

En resumen, que no hemos obtenido nada mejor de lo que teníamos. Al contrario, es peor, pues no podemos distinguir mediante este procedimiento si el vector está ordenado, así que aquí no hay mejor caso. En cualquier caso es una patata. Por eso es el primero que se aprende.

Imaginemos otra función que, en cambio, sirva para insertar un elemento en un vector ya ordenado. Esta función tiene un coste lineal y es muy sencilla. Para cada elemento, compara con el más grande (que estará a la derecha) y mientras el elemento a insertar sea más pequeño, le hace un hueco desplazando los más grandes a la derecha.
Un ejemplo: quiero insertar un 4 en el vector ordenado 2 7 43. Comparo con 43, como es más grande, muevo el 43 para hacer sitio al 4. Y nos queda esto: 2 7 (hueco) 43. Comparo con el 7, y éste, que es más grande, se aparta educadamente: 2 () 7 43. Pero al comparar con el 2, vemos que éste no se tiene que apartar. Y ha quedado un hermoso hueco donde ponemos el 4: 2 4 7 43.

¡Pero no tenemos un vector ordenado! ¡No queríamos esto!. Wakarimashita. Pero lo construiremos. Y si nos fijamos vemos que siempre hay una pequeña parte del vector ordenado: el primer elemento. El primer elemento es un vector ordenado... de un elemento. Y con nuestra maravillosa función podemos añadir cualquier elemento a este mini vector ordenado. Evidentemente, a no ser que queramos hacer el idiota un rato, los elementos que añadiremos serán los del propio vector desordenado. De este modo, construiremos nuestro vector.

El procedimiento es simple: recorreremos el vector llamando incrementalmente a nuestra función que inserta elementos. Tenemos nuestro glorioso vector 4 7 2 43 14 1. El 4 ya está ordenado... en el vector formado por el 4. Insertamos el 7 en ese vector. Y tenemos el 4 y el 7 ordenados en el vector 4 7. Al vector se apunta el 2, y los otros números le hacen hueco para que ocupe su lugar. Así tenemos 2 4 7. Insertamos el 43, que se queda muy atrás, cómodamente. Insertamos el 14 en 2 4 7 43. Sólo se mueve el 43 para dejarle hueco: 2 4 7 14 43. Por último, insertamos el 1, que obligará a todos los elementos a moverse un poco. Y ya está: 1 2 4 7 14 43.

Si habéis pillado lo del cálculo de costes y tenéis un poco de picardía me diréis: ¡eh! si la función para insertar tiene coste lineal (n) y hay que recorrer n-1 posiciones del vector llamándola, ¡volvemos a tener coste cuadrático!. ¡Chapuzas, más que chapuzas!

Tenéis razón, pero no. La gracia está en que la función para insertar tiene coste lineal... en el peor caso. Es decir, cuando ha de insertar el elemento más pequeño (como cuando insertamos el 1 en nuestro ejemplo). Entonces hay que recorrer todo el vector haciéndole hueco. Pero en promedio no será necesario llegar hasta el final. Cuando hemos insertado el 7 o el 43, la función ha tenido coste constante. y cuando hemos insertado el 14, sólo hemos recorrido un elemento. Al igual que el Bubble Sort, distinguimos entre un mejor caso (vector ordenado, coste O(n)) y un peor caso, coste (O(n²)).

Este algoritmo un mejor comportamiento que Bubble Sort, porque aprovecha el orden parcial en el que se encuentre el vector y no debe esperar a que se encuentre completamente ordenado como éste para obtener beneficios. ¿Cómo medimos lo que tarda el algoritmo en el caso medio, por otro lado?. Pues hemos de contar el número de veces que hemos tenido que "dejar hueco". A esto se le llaman inversiones. El dos ha realizado dos inversiones, puesto que antes estaba 2 posiciones más allá del 4 y el 7. Estos no han realizado ninguna, claro está. El cálculo absoluto es difícil de hacer, pero para eso están las notaciones. Decimos que en caso medio, el algoritmo cuesta O(n+d), donde d es el número de inversiones, una medida de lo (des)ordenado que está el vector.

Por supuesto, este genial procedimiento no lo ha inventado Aitor Menta, así que ya tenía nombre: Insertion Sort.

¿Nos quedamos con este algoritmo tan maravilloso?. Pues no, porque no nos vale. Para jugar con pocos elementos está bien, pero no podemos permitirnos un coste cuadrático cuando tratamos con cantidades realmente grandes. ¿Saben lo que hace una función n² con datos grandes?.

¿Existe alguna función que nos ayude a ordenar vectores con coste inferior a Insertion Sort? La respuesta (afirmativa) a tan interesante cuestión será dilucidada en el siguiente -y último de la serie- capítulo de: ¡Ordenando Longanizas!

Seguir leyendo

Cosas que SÍ se dan en Informática

Ya sabemos que Aitor es informático. Lo explicábamos en este post, donde también vimos qué cosas no hace un informático. Entre lo que aprende un informático y lo que la gente espera que sepa un informático hay enorme vacío, que sólo se puede llenar con muchos fascículos "La informática es fácil" y revistas "MAXimiza TODO TU PC".

Hay informáticos, compañeros de carera, que a la pregunta: qué ordenador tienes responden, uno blanco. Hay informáticos que se quejan de que escriben su contraseña y sólo aparecen asteriscos. Hay doctores que no saben qué es UNIX y dan clases de seguridad en UNIX (de estos hay al menos uno).

Si no nos enseñan a formatear un disco duro, ni a configurar una tarjeta de video ni a hacer páginas web... ¿qué nos enseñan en la carrera?.

Con este post iniciamos una apasionante a la par que didáctica serie:

Cosas que SÍ se dan en Informática

Capítulo 1. Ordenando longanizas.

Aitor me sugiere un problema clásico de la algoritmia para comenzar. Algoritmia es, para nosotros, el arte de resolver problemas paso a paso. El problema, que se estudia en primero de carrera, consiste en ordenar un vector. Un vector no es más que una longaniza de números, que se sitúan consecutivamente en memoria. En inglés se llaman arrays y en Sudamérica lo apañan y los llaman arreglos. He aquí una gloriosa representación de un vector: 4 7 2 43 14 1. Y éste es el mismo vector ordenado: 1 2 4 7 14 43. No parece difícil hacerlo y, de hecho, no lo es. Ahora veamos cómo le decimos a un computador que lo haga.

Un computador dispone de una serie de operaciones -instrucciones-. Entre éstas, saber si un número es mayor que otro, sumar, restar... y poco más, al fin y al cabo. Y una restricción que me invento yo: no puede conocer el valor de más de dos posiciones del vector en la misma operación, es decir, en el mismo instante. Si los computadores tuviesen una instrucción para comparar hasta un millón de números, ordenar vectores sería más sencillo. Pero como no la hay, restringimos a dos los números a comparar y nos las ingeniamos, que la tecnología es cara y los ingenieros baratos.

Veamos cómo lo hacemos. Cogemos los dos primeros números y los comparamos. Si el segundo es menor que el primero, los intercambiamos. En nuestro caso no sería necesario pues 4 es menor que 7. Damos un pasito y realizamos la misma operación. Ahora sí que se cumple nuestra condición e intercambiamos el 7 con el 2. Por tanto, en el siguiente paso compararemos otra vez el 7 con el 43. No cambiamos, damos un pasito, e intercambiamos 43 y 14. Un pasito e intercambiamos 43 con 1. De este modo hemos llegado al final del vector (hemos iterado sobre el vector una vez) y tenemos una cosa como ésta: 4 2 7 14 1 43. Y, como no hemos acabado... ¡empezamos otra vez!

Pero ahora... ¿hace falta llegar al final?. Pues no, porque con este método nos hemos asegurado de arrastrar al elemento más grande hasta el final. Así que cada vez que hagamos una iteración podemos acabar un elemento antes. Tras la segunda iteración, nuestro vector será así: 2 4 7 1 14 43. El 14 ya esta en su lugar. Luego 2 4 1 7 14 43 -> 2 1 4 7 14 43 -> 1 2 4 7 14 43. Hemos hecho tantas iteraciones como elementos del vector menos uno.

Algo tan tonto tenía que tener nombre. Este sistema se llama Bubble Sort. Me dijeron que se llamaba así porque veías cómo los elementos más grandes (burbujas) subían rápidamente hacia arriba. A lo largo de esta fascinante serie veremos cómo los informáticos tenemos mala pata para poner nombre a las cosas.

Un momento... ¿hemos acabado?. Hombre, pues, sí, el vector está ordenado. Pero un informático no sería un ingeniero si se contentase con esto, no señor, ni mucho menos. Vale, tenemos un método para ordenar vectores, pero... ¿es el mejor método posible sobre el mundo mundial para ordenar siempre toda clase de vectores?.

Lo mejor varía según quien considere el problema. Los informáticos atendemos a dos variables para evaluar lo buena que es una solución algorítmica: el tiempo que lleve completarla y el espacio que necesitemos en memoria para resolver el problema (costes temporal y espacial). Un empresario también evalúa en función del tiempo y coste: el tiempo en que tiene que tener listo el producto (o urgencia) y lo que le cueste el informático.

Los costes se determinan, normalmente, en función de la entrada. Los costes constantes no se suelen considerar. Si un algoritmo requiere siempre trescientos segundos para resolver cualquier problema (independientemente de la complejidad del problema), es posible que nos parezca lento para decirnos la hora... pero es que no lo dedicaremos a decir horas. Le pediremos que nos haga la quiniela.

En nuestro caso, necesitamos n-1 iteraciones para resolver el problema (donde n es el número de datos de entrada), pero ese -1 es irrelevante para un n grande. Decimos entonces que la complejidad temporal depende de n. ¿Hasta qué punto?. Pues, en general, cada vez que empezamos una iteración tenemos que recorrer el vector, primero hasta el final, luego hasta el final - 1 posición, luego - 2... como los informáticos no atendemos estas disquisiciones matemáticas, decimos que el coste temporal es de n*n, es decir, de n². No contentos con decirlo lo notamos así: O(n²). Esto significa que, en el peor caso, los datos de entrada al cuadrado serán una cota máxima a la complejidad temporal de la solución. Por otro lado, la complejidad espacial de este algoritmo es "nula": no requerimos más espacio que el propio vector durante el proceso.

¿Qué es el peor caso?. Pues depende. En nuestra solución, que el vector esté ordenado, pero al revés. ¿Existe un mejor caso para nuestra solución?. Sí, que ya esté ordenado. Si tras la primera iteración no hemos hecho ningún cambio, sería idiota continuar el proceso. El coste sería O(n). También existe el concepto de caso medio, pero por hoy ya hemos tenido bastante.

Así que tenemos un algoritmo de coste temporal cuadrático para ordenar un vector... ahora bien: ¿existe algún otro método para ordenar longanizas de números que sea mejor?.

La respuesta en el siguiente capítulo.

Pista: sí.

Posts relacionados

Ordenando longanizas II
Ordenando longanizas III

Seguir leyendo

Muy breve historia de la CERVEZA (I)

(De Sumeria a Ingolstadt)

En verdad es difícil atribuir a una cultura la invención de la cerveza. En todo el mundo han sido hallados restos de civilizaciones o pueblos que, habiendo descubierto la fermentación de cereales germinados, la empleaban en ritos o ceremonias.

Como no podemos atribuir a nadie el descubrimiento de la fermentación, se suele citar pues a los mesopotámicos como padres de la cerveza. Fueron éstos los primeros que analizaron y detallaron el proceso mediante el cual se obtenía la bebida, aunque entonces se fabricaba a partir del pan de cebada fermentada. Detallar una fecha es igualmente imposible. Si bien se cree que se consumían bebidas similares en torno al 6000 a.C. (gracias a evidencias arqueológicas de tabletas y útiles de fabricación en Sumeria), no se tiene evidencia escrita hasta el 2000 a.C.¹.

Por otro lado, los egipcios también adoptaron la cerveza como bebida ritual. Se confirmaría esto mediante el análisis de restos hallados a los pies de sarcófagos. El fallecido se hacía acompañar de toda clase de riquezas para la nueva vida, alimentos y cerveza. Aitor Menta también desearía hacerse acompañar de cerveza para la vida eterna, pero el coste sería inasumible por sus deudos.

La cerveza egipcia era de mayor calidad que la mesopotámica: fueron los egipcios quienes desarrollaron la industria del malteado, esto es, el tueste del grano de cebada. Más tarde los fenicios, primeros grandes comerciantes del Mediterráneo, introdujeron la cerveza en la península ibérica².
Sin embargo, a estas alturas de la historia, todas las civilizaciones habían desarrollado la fabricación de la cerveza, de una forma u otra. En América con maíz, en las estepas rusas con pan, en Asia oriental se consumía tsiou, producida con mijo.
Por otro lado, si se ha de señalar una cultura que adoptó la cerveza como propia, ésta es la celta. La beer, bière, Bier, birra, bëoir, boirc'h... provienen del celta brai.

En la literatura griega y romana podemos encontrar cuantiosas referencias al uso popular de esta bebida y se remarca la dualidad cerveza – vino.

A propósito de los egipcios, Herodoto dice en el libro II de sus Historias: “El vino que beben de ordinario es una especie de vino hecho de cebada, pues ellos no tienen viñas en su país”. Sobre los armenios, Jenofonte, en el libro IV de Anábasis, escribe que tienen vino de cebada, bebida muy fuerte si no se mezcla con agua.

Diodoro de Sicilia, escritor del siglo I a.C., en su Libro I, dice: "Cuando una región no puede producir vino, se procura un vino sacado de la cebada que poco desmerece al vino por su fuerza y su sabor". Cuenta Estrabón que los gallegos bebían citrus, una especie de cerveza. De todos modos nunca estuvo en la península ibérica, así que no lo pudo probar.

En el periodo de la Baja Edad Media (coincidiendo con las invasiones bárbaras) la cerveza se mantiene como una bebida de poca o nula calidad. Sin técnicas de enfriamiento, filtración, ni almacenaje, la cerveza resulta apenas bebible. Tuvieron que ser los monjes de las órdenes monásticas los que dignificasen la producción de cerveza a través de nuevas técnicas. La adición del lúpulo, por ejemplo -que da el amargor característico a la bebida- data del s. IX.

Los cerveceros debemos mucho al monje benedictino Arnoldo, obispo de Oudenburg (Bélgica) y santo patrón del gremio de los cerveceros. A principios de s. XI mejoró el proceso de filtrado en la fabricación, inspirándose en las celdas de los panales. Usualmente se le confunde con San Arnulf de Metz, otro santo patrón de la cerveza anterior (s.VI-VII) al que pudimos ver en el anterior post. No está claro a quien se le atribuye la frase "Bebe cerveza, no agua". En cualquier caso, esa también podría ser de Aitor Menta.

A Arnoldo (of Soissons) se le atribuye un milagro de multiplicación de cervezas tras la ruptura de un tejado de la abadía donde se fabricaba la cerveza. Tras esto, que pasase a ser la imagen de los Cerveceros de Bélgica era sólo cuestión de tiempo.

La invitación a beber cerveza no era gratuita. En la Edad Media proliferaban las enfermedades debido a la mala calidad del agua. El proceso de ebullición a la que era sometida durante la elaboración de la cerveza disminuía el riesgo de infección. Durante muchos años ha sido más sano beber cerveza que agua.

La cerveza fue la bebida favorita de reyes y nobles, especialmente del norte de Europa. Otro de ellos es considerado santo patrón cervecero y se le conoce como rey Gambrinus, aunque su nombre posiblemente fuese Jan Primero, duque de Bravant en el s. XIII, amante de la cerveza e impulsor de la industria cervecera en Bruselas. Otro duque famoso fue Guillermo IV, que, entre otras cosas menos importantes, será recordado por promulgar en 1516 la Ley de Pureza de Ingolstadt, hoy conocida a lo largo y ancho del mundo como Ley de Pureza Alemana (Reinheinsgebot).

La ley de pureza alemana establecía el precio de una cerveza y los ingredientes que se podían emplear en su fabricación (malta, lúpulo y agua). La ley se promulgó para la ciudad de Ingolstadt, en el condado de Bavaria. Luego fue adoptada en algunas otras zonas. Las motivaciones de la la ley que cambiaría para siempre la historia de la cerveza alemana eran puramente económicas y buscaban proteger a los productores de cebada frente a otros cereales. De todos modos, también es de remarcar que es una de las primeras leyes destinadas a proteger al consumidor. Sin una regulación firme, en aquella época cualquier cosa era vendida como cerveza, y a los más variados precios.

Y aquí acaba nuestro recorrido. Dice Pinar que un buen bloguero no escribe posts de más de 500 palabras y yo ya llevo exactamente 957... pues paro y ya seguiré más adelante... otro día... mientras bebo... ¿qué?

¹ Aitor Menta recuerda haber leído que el código de Hammurabi ya somete la fabricación de cerveza a ciertas reglas, pero no ha encontrado claras referencias aquí.
² Restos arqueológicos hallado en Denó (Lleida) indican que se debía consumir cerveza ya en el 1200 a.C. En Soria hay todavía restos más antiguos (2000 a.C.).

La Cerveza, Manual de uso. Pedro Plasencia.
¡Y todas la referencias del texto!

Posts relacionados

Historia de la cerveza (II)

Seguir leyendo

La Cerveza (Introducción)

Tomo las ofrendas que hay en los altares y al caer la noche bebo dos cántaros de cerveza y adopto mi dignidad de Señor de todo cuanto existe

¿Saben por qué este blog se llama civada (cebada)? Pues porque iba a ser un blog de cervezas¹. ¿Y por qué me llamo Delirium?. Pues por esto.

Aitor Menta está enfadado. Se han escrito muchas tonterías en este blog, piensa. No se ha hablado de lo verdaderamente importante. Y tiene razón. Se supone que es un blog personal y apenas hemos arañado la superficie de sus deseos. Todavía no hemos desvelado que late en el interior del corazón de Aitor Menta. Néctar que le da la vida y se la arrebata. Bien, pues ya está claro. Hoy hablaremos de cerveza.

La cita del principio no es de Aitor Menta, aunque sin duda le correspondería por porte y rango. Es de Atón, Dios solar egipcio, y figura en el Libro de los Muertos². Hay frases que uno simplemente llegó tarde a decirlas.

Si yo les digo que "La cerveza es la bebida resultante de la fermentación alcohólica, mediante levaduras seleccionadas, de un mosto procedente de malta de cebada, sola o mezclada con otros productos amiláceos transformables en azúcares por digestión enzimática, adicionado con lúpulo y/o sus derivados y sometido a un proceso de cocción. La malta puede ser sustituida por malta de cereales, granos crudos que contengan féculas, así como azúcares, siempre que las sustancias añadidas no excedan del 50% en masa de la materia prima utilizada" (Def. Reglamentación Técnico Sanitaria)...
¿estaríamos haciendo justicia a tan insigne brebaje?.


NO. ¡EXIGIMOS JUSTICIA!.

La cerveza ha sido esencial en la vida de las gentes desde la noche de los tiempos y en nuestros días gana cada vez más importancia, tanto económica como social, en las sociedades occidentales. En los tiempos antiguos, el uso ritual de la cerveza se evidencia por su utilización en ceremonias religiosas. Hoy en día, en cambio, este uso ritual está más diluido en ceremonias civiles pero, sin duda, sigue existiendo en la actualidad.

En la serie de posts que se avecina recorreremos brevemente la Historia, con mayúsculas, y tocaremos muchos aspectos del mundo (que digo mundo, ¡Universo!) de la cerveza.

¹ Pues no señor. Castellanismo como una catedral. Cebada es en catalán ordi. Civada significa "avena". Uno no deja de aprender idiomas nunca.
² La cita ha sido extraía del Libro Blanco de la Cerveza, disponible en la página web de Cerveceros de España. Aitor Menta duda de la exactitud de la autoría.

Seguir leyendo

Aficiones secretas: japonés

!Freaky warning! en este post aparecer'an s'imbolos raros si no tienen instalado en su equipo el soporte a lenguas orientales. Ahora mismo, como pueden ver, mi teclado cree ser japon'es. !end of freaky warning!

Ahora que ya saben de qué trabaja Aitor, es necesario que sepan que la informática no es sino una afición productiva. Aitor no desea trabajar de informático, que va. Pero le deja tiempo (de momento) para otras muchas cosas. En realidad, son este tipo de cosas, completamente improductivas, las que llenan de gozo y regocijo el corazón de Aitor Menta.

Aitor Menta estudia japonés. No por nada, sino porque le da la gana. No es un fanático de la cultura japonesa, aunque de vez en cuando se pasee por Kirai, a ver que cuenta. No le va el anime (アニメ) ni los manga (マンガ).　Piensa que bastante poco conocemos nuestra propia cultura y tradiciones para quedarnos atrapados con otras. Hay quien se fascina cuando, casualmente, ve una Moixeranga en Valencia.

Pero vamos, que Aitor un día se aburría, descubrió un libro de Autoaprendizaje de japonés y se dijo: pues venga, vamos. El libro, por cierto, es Japonés en Viñetas 1, un libro increiblemente bueno.

El japonés o nihongo (日本語)　tiene 2 silabarios. Se llaman silabarios porque cada símbolo (kana: 仮名)　representa un sonido silábico de consonante más vocal -o vocales si hay diptongo-. Las únicas excepciones son las vocales y la 'n'. Así, a ojo, hay unos 109 sílabas japonesas, más algunas pocas importadas de otras pronunciaciones. Parecen pocas, pero son muy pocas. Un alfabeto fonético como el nuestro puede combinar 5 vocales con otros 21 fonemas. Si cada vocal se puede poner delante o detrás de cada consonante (en japonés no), pues tenemos 210 combinaciones de vocal+consonante. En el idioma japonés, a diferencia del chino, la entonación no es relevante, así que podemos imaginar que la pronunciación del japonés es realmente sencilla.

Veamos algunos ejemplos típicos de kanas en los dos silabarios.

	sa	shi	su	se	so
Hiragana	さ	し	す	せ	そ
Katakana	サ	シ	ス	セ	ソ

アイトルメンタモラムチョ　Aitoru Menta mora mucho. Gracias a este ejemplo podemos averiguar:

1. Que los japoneses no separan las palabras al escribir. (Un informático tiembla ante la idea de desarrollar un parser para esta lengua)
2. Que los japoneses suelen añadir la 'u' a las consonantes que no se pueden emparejar en kanas (Aitor -> Aitoru)
3. Que los japoneses no pronuncian la 'l' y la sustituyen por una 'r' (mola -> mora. Al revés que los chinos, que lalo).
4. Que Aitor Menta mola, y mucho.

Aprender los dos silabarios es también fácil, ya que a partir de 46 kanas básicos se construye el resto. Además, ambos silabarios representan los mismos fonemas silábicos. Una vez los hemos aprendido, surge, natural, una duda razonable: ¿cuándo se gasta uno y cuando el otro?.

El hiragana ひらがな　es el silabario natural para la escritura del japonés. Las palabras propias o autóctonas se escriben con estos caracteres. En cambio, el katakana カタカナ　se emplea para representar extranjerismos o fonemas ajenos. Además, se suele utilizar para representar onomatopeyas o para resaltar palabras. Dado el gran número de extranjerismos en Japón, es necesario su tener un dominio completo de ellos.

Y si ya nos apetece realizar un esfuerzo intelectual considerable diremos: "Leches, ¿y por qué hay dos?". Buena pregunta. Resulta que el japonés ya se hablaba mucho antes de que se escribiera (lógico), pero también resulta que fueron los chinos los que aportaron la escritura a las islas japonesas (junto con parte de su cultura, como el budismo). La escritura china se compone de ideogramas, cada uno de ellos con su pronunciación o pronunciaciones propias. Así, para el mismo concepto, conocido por chinos y japoneses, había al menos dos pronunciaciones: la "nueva", china y la tradicional japonesa.

Con el tiempo, con el fin de representar los fonemas de una forma propia, algunos de los símbolos chinos fueron "evolucionados" o transformados en una representación más suave y de trazos redondeados Así, hacia el siglo V nació el hiragana. Un poco más tarde, y como transcripción manual y rápida de los símbolos chinos, nació el katakana, de trazos más agudos tomados de partes de algunos símbolos. Se cree que fueron las mujeres japonesas las que realizaron este proceso.

Ejemplos:
AN: 安　(seguro, fácil)-------> あ a
TAI> 太　(grueso)------> た　 ta

Nota: Aitor Menta es consciente de que la pregunta "¿Y por qué hay dos?" sigue sin ser respondida.

La cosa hubiera ido bien para los estudiantes de japonés si tras estas representaciones se hubiesen dejado de gastar símbolos chinos. Pero no. Los símbolos "chinos" se conservaron y se conocen como kanjis 漢字. Kanjis hay unos 45000 o quizá alguno más. En primaria se aprenden unos 1000, algunos más de los que necesita una persona para no hallarse perdida en el idioma japonés. Existe una lista de Kanjis de uso común que se compone de 1945 kanjis. Lo normal es que habitualmente se gasten unos 3000, pero si un kanji no está en la lista se proporciona su pronunciación en hiragana.

Hiragana, representado con kanjis es así: 平仮名。
Katakana es 片仮名。
En el primer caso el primer kanji significa común, en el segundo, un lado o incompleto. El circulito del final es un punto como este.

Por si fuera poco, los japoneses no se quedaron sólo con los símbolos. También mantuvieron la(s) pronunciación(es) china de cada uno de ellos. A eso lo llaman pronunciación on'yomi. La lectura "a la japonesa" se denomina kun'yomi. El estudiante debe aprender ambas, porque a veces se pronuncia de un modo y a veces de otro. Y no existe una mejor manera de aprenderse los kanji. Hay trucos, eso sí, pero nada te libra de dedicarle un buen tiempo a ello. Aitor Menta lleva tres meses y pico estudiando y conoce las pronunciaciones y significados de unos 200.

Más cosas. El orden de los trazos en cada símbolo importa. Y la dirección de los trazos. Los zurdos lo tienen más difícil para escribir, porque son naturales para diestros. Por cierto que la caligrafía japonesa (shodou: 書道, algún día hablaré de ella) se debe realizar con la diestra, independientemente de si eres zurdo o no.

¿Hacen algo más los japoneses? Sí, claro, también escriben en caracteres occidentales. A eso se le llama roumanji.

La gente pregunta a Aitor Menta por qué estudia japonés y no chino, que tiene "más futuro". Principalmente, porque no tenía en casa un libro llamado "Chino en viñetas". Pero es que además... ¡el japonés es tan divertido!.

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

Seguir leyendo

El trabajo de Aitor Menta (II)

Una vez ya sabemos un poco de terminología, podemos adentrarnos sin miedo alguno en los recovecos de la Informática. Sin miedo alguno, digo, puesto que Aitor no guiará con firme paso y aguerrido pulso entre bits y buses, sin temer a perros guardianes con relojes ni a astutos manejadores (handlers).

[La informática es fácil. No puede ser de otro modo puesto que estamos intentando que trastos carentes de alma imiten muchos procesos que el ser humano lleva haciendo desde hace milenios. Cuando un informático te diga que algo es difícil de explicar, o es mal informático, o te está mintiendo]

Pero a lo que íbamos: ¿qué se puede hacer para fastidiar un ordenador?. Como sabemos, dedicarnos a golpearlo puede ser una (atrayente) idea, pero no nos sirve como computer science. En su lugar, los informáticos suelen utilizar lo que llaman Técnicas de Inyección de Fallos. Aitor lo llama putea al procesador.

Una cosa debe quedar clara. El objetivo de todas estas técnicas no es que un sistema funcione a la perfección, es decir, libre de errores, fallos y averías. El objetivo es evaluar hasta que punto estos comprometen algo que llamaremos, pomposamente, Garantía de Funcionamiento. La Garantía de Funcionamiento viene a ser la confianza que otorgamos a un sistema en funcionamiento, es decir, una medida de hasta cuánto podemos depender de él. Esto depende de muchos factores, a los que también nombramos con malas traducciones del inglés. Uno de esos factores puede ser la disponibilidad. Un ejemplo: podemos tener un sistema que autentique usuarios legítimos de una Base de Datos supersecreta del Gobierno. Este sistema puede ser a prueba de TODO fallo e intrusión maligna... pero si sólo está en funcionamiento el 10% del tiempo, pocas veces depositaremos en él nuestra confianza a la hora de identificarnos como espías.

Los informáticos hablan de dos variables a estudiar: cobertura y tiempo de latencia. Llaman cobertura a la probabilidad de detectar un fallo en el sistema. El tiempo de latencia es el transcurrido entre la detección del fallo hasta completar los mecanismos que tome el sistema frente a este. Inyectando fallos (puteando al procesador) estudiaremos:

1. De qué manera afectan los distintos fallos al sistema, para poder diseñar una buena respuesta a estos.
2. Una vez en marcha los tratamientos escogidos, estudiaremos si las coberturas y tiempos de latencia obtenidos en sistemas puteados pueden comprometer la Garantía de Funcionamiento.

Técnicas de inyección de fallos

En primer lugar distinguimos entre fallos de verdad y de mentira. Los de verdad son de verdad. Los de mentira son fallos producidos en modelos de simulación. Es decir, de mentira. Lo de inyectar fallos en modelos de simulación queda genial para darse aires de sabidillo, pero en la realidad, es tan tonto como eliminar una linea del Paint que unía dos cajas. De hecho, suele ser eliminar una linea de un dibujo. Sólo que el dibujo representa un sistema programado con VHDL y el fallo simula una rotura de un cable. Se puede incluso programar para que falle a veces, lo cual no es mucho más complicado que seleccionar una opción del menú contextual. Los buenos programas de diseño deben estar hechos para tontos.

De entre los fallos de verdad distinguimos entre los de verdad y los de mentira. Los de verdad son los fallos hardware. Los de mentira pertenecen al mundo (imperecedero e incorruptible) del software.

Hay muchas y muy divertidas maneras de inyectar fallos HW sin utilizar martillos. Una muy utilizada consiste en destripar en lo posible el aparato y forzar niveles de tensión en los pines. Lo malo es que, como cada vez los componentes son más pequeños, esta técnica tiene un coste mayor y no podemos acceder a todos los sitios que desearíamos. Otra idea es someter al sistema a interferencias electromagnéticas (EMI), similares a las que encontrará en un entorno industrial hostil y malvado. Su problema es que apenas podemos decidir qué parte del sistema queremos afectar.

Otra más, y más chula, consiste en bombardear el sistema con pesados... iones de elementos radioactivos (como Californio 252). El problema es que nos es muy difícil reproducir varias veces el mismo experimento o fallo. Además, también es complicado precisar el componente o área a afectar. Para ello, podemos utilizar una radiación láser. En ambos casos, el coste de la infraestructura es considerable.

La inyección física presenta otro problema (marginal) que no hemos considerado: podemos cargarnos el bicho. Y no están las subvenciones en I+D+i como para romper coas alegremente.

Esa es una ventaja de la inyección software. Que normalmente no llegamos a cargarnos el sistema. Para quien no tenga ni papa de informática, diremos que un fallo SW es un fallo causado por un programa en ejecución. Hay un montón de clasificaciones de fallos SW, pero no es cuestión de ponernos pedagógicos. Según cuánto duran, por ejemplo. O según si producimos el error mientras se ejecuta o antes de cargar el código en el sistema.
Con los fallos SW podemos accecder de forma controlada y repetible a casi todos los componentes del sistema. Además podemos lograr un buen control del momento de inyección y entonces ponernos a medir el tiempo. Ejemplos de fallo SW: alterar la memoria de código para que el procesador se encuentre con instrucciones "chungas". Ejemplo 2, alterar los parámetros de las funciones del sistema. A los fallos SW es a lo que se está dedicando últimamente Aitor Menta.

¿Y todo esto para qué?

¿Y todo esto para qué?, digo yo. Pues porque los ingenieros quieren saber hasta qué punto puede fallar un sistema para poder ponerle un precio. He aquí lo que diferencia la ciencia más pura y nívea de la aceitosa ingeniería. Ingeniería no consiste en realizar sistemas perfectos... sino lo mejor posibles con unos recursos limitados.

Pregunta: ¿cuánto vale la vida de las personas que circulan en un cercanías?. Cualquier político dirá que no tiene precio. Pero lo tiene y se puede evaluar en relación a otros gastos. Si no se incorporan mecanismos de tolerancia a fallos a una vía porque el dinero se destina a acondicionar calles para circuitos de alta velocidad, entonces estamos considerando la seguridad de los viajeros del tren menos valiosa que los circuitos urbanos. Los ingenieros deben saber poner números al riesgo existente, usando conceptos como el de garantía de servicio, cobertura, fiabilidad... y luego calcular los costes.
Y posiblemente serán otros quienes decidan si merece la pena asumirlos.

Nota lectora: algunos dilemas como éste son abordados por Tim Harford en El Economista Camuflado.

Seguir leyendo

El trabajo de Aitor Menta (I)

Tras un par de posts que deben haber dejado bien claro qué opina Aitor de la política, viene a ser la hora de revelar más datos personales acerca de este extraordinario personaje. Hoy les he venido a contar de qué trabaja Aitor. Porque Aitor trabaja y es mileurista, como toca a los universitarios de su generación. Por suerte, sólo trabaja cuatro horas al día. Bueno, por suerte no, porque se lo merece.

Aitor es informático, como toca a los universitarios de su generación. Aitor decidió ser informático en pleno auge de las dotcom. E inició la carrera en pleno estallido de las dotcom. Son cosas que pasan. Nos decían antes de entrar que nos harían ofertas de trabajo en tercero, en cuarto, pero que debíamos renunciar a ganar mucho dinero si queríamos obtener el título.

Pues ya ves.

Aitor es un informático que no sabe lo que es pehachepe, ni ayax ni puntonet. No tiene ni zorra de flash, java ni nada de eso. No sabe qué es debian. Y no es extraño. La mayor parte de estudiantes de informática no ven eso en sus carreras. Se estudia teoría de colas, conjuntos, gramáticas, estadística, clasificadores, arquitecturas y protocolos. Ningún estudiante de informática sabe arreglar ni formatear un ordenador, al menos no gracias a la carrera. Entre los estudiantes circula el lema: "Soy informático y NO voy a arreglar tu ordenador". Lo más probable es que no sepan cómo.

Así que Aitor no hace páginas web, ni instala linuxes ni arregla ordenadores, tareas todas ellas que creemos típicas de un informático. Su trabajo es mucho, MUCHO más guay que todo eso junto: Aitor jode ordenadores. Los pringaos arreglan ordendores. Sólo los espíritus libres los joden y les pagan por ello.

¿Qué se debe hacer para fastidiar un ordenador?. Bueno, primero, Aitor no trabaja con ordenadores al uso. Trabaja con SOCs, que viene a ser como tener un pequeño procesador con unos cuantos componentes, interficies de comunicación y memorias. Molan más porque puedes toquitearlo todo. Puestos a liarnos a martillazos, ni siquiera es necesario quitarle la carcasa.

He aquí una imagen para que se hagan ustedes a la idea.



Pero no es cuestión de liarse a martillazos, no. No por nada, sino porque el tipo de fallos que esto comporta no suele ser reproducible ni estudiable, aunque seguro que también hay gente que se dedica a golpear cosas hasta que se rompen. No es el caso, por desgracia. La idea es analizar los fallos que pueden producirse en un aparato de este tipo (hasta las tostadoras tendrán cosas similares dentro) y ver de qué manera podemos garantizar cierto funcionamiento en caso de fallo.

Y de eso va la cosa: de sistemas tolerantes a fallos. ¿Y qué es un fallo?. Pues venga, un poco de terminología.

Un fallo es lo que todos tenemos en mente: algo que no va bien. Un fallo en informática puede ser un bit que no es el que debería, un nivel de tensión que no es el adecuado, una división por cero. Podemos clasificar los fallos de un montón de maneras distintas: accidentales o intencionados, maliciosos o no. Temporales o permanentes, internos o externos... Los fallos pueden estar dormidos (como un error en una posición de memoria que no se usa) o activos.

Un error es la manifestación del fallo. Continuamente se producen fallos en nuestro sistema. Muchas veces estos son tratados antes de que se conviertan en errores. Otros ni siquiera son percibidos por éste. Llamamos a un error latente cuando no ha sido detectado. Lo llamamos detectado cuando... bueno, vale. Cuando un error afecta al comportamiento del sistema y al usuario del mismo lo llamamos avería. Una avería viene a ser una exclamación del tipo "esto no furula".

Averías también hay de muchas clases. Puede ser de valor, cuando obtenemos un resultado que no toca. O puede ser de tiempo, cuando obtenemos un resultado cuando no toca. En sistemas de tiempo real, por ejemplo, tan importante es lo uno como lo otro. Podemos tener una avería coherente (en esos casos es fácil imaginar qué ha ido mal). O podemos tener una avería bizantina. En las averías bizantinas a veces la cosas van bien y a veces no. Quizá una parte del sistema piense que funciona correctamente y la otra lo contrario. Las averías bizantinas son la mejor manera de volverse loco en poco tiempo.

Podemos tener averías benignas o desastrosas. Un informático te lo explicará así: en las benignas, las consecuencias que se producen son de un orden de magnitud igual al beneficio obtenido por el servicio entregado en ausencia de averías. ¿Guay, eh?. Podemos imaginar, en contraposición qué es una avería desastrosa. Las averías desastrosas entrañan muerte y destrucción en los peores casos.

Definimos criticidad de un sistema como la mayor gravedad de sus posibles modos de avería. Debemos intentar que los sistemas más críticos tengan modos seguros de a avería. Hay sistemas críticos que simplemente parándose lo consiguen. Hay otros, como aviones, que es mejor que no lo hagan si no desean planear sin control durante lo que le queda de viaje.

Y aquí viene lo que buscamos: se dice que un sistema es tolerante a fallos cuando es capaz de continuar su trabajo aunque se manifiesten errores permanentes, transitorios o intermitentes. Un sistema tiene un comportamiento seguro, si una vez que se produce una avería, y además no se puede continuar con el correcto funcionamiento, el sistema se detiene en un estado conocido que no causa ningún tipo de riesgo.

¿Cómo consiguen hacer estas cosas maravillosas los informáticos?. Pues de muchas y sofisticadísimas maneras. A veces poniendo a funcionar varios componentes que hacen lo mismo. Por ejemplo. A eso le llamamos redundancia de componentes. Si nos queremos dar el pegote podemos hablar de redundancia intrínseca, si no hemos hecho nada para conseguirla o redundancia extrínseca, si ha sido intencionada para tolerar fallos.

[A estas alturas ya debe haber quedado claro que informática no es una carrera difícil, pero hacemos como que sí hablando raro].

¿Y de qué manera se puede uno dedicar a fastidiar ordenadores, que era lo que quería contar?. Pues como esta entrada ya queda muy larga, le pondré una I al título y ya continuaré más adelante.

Hasta la vista.

La imagen corresponde a una placa de evaluación de Keil.

Seguir leyendo