Presentació de Guifi.net a Campus Nord de la UPC

Ordenación topológica inversa

Grafos

Un grafo es, de forma intuitiva, un conjunto de vértices y aristas que los unen. No es más que una representación abstracta de un conjunto de elementos (representados por los vértices) y alguna relación entre ellos (representada por las aristas). Por ejemplo, las relaciones entre un grupo de personas se pueden representar como un grafo, dónde las personas son los vértices y la relación de amistad una arista entre dos vértices (Más información).

Recorrido (o búsqueda) en profundidad

Recorrer un grafo consiste en visitar los nodos del mismo viajando a través de las aristas. Básicamente existen dos maneras de recorrer un grafo, dependiendo del recorrido elegido: el recorrido en profundidad y el recorrido en anchura.
El recorrido en anchura es análogo al recorrido por niveles de un árbol, sólo que generalizado a grafos. Primero visitamos el nodo raiz, posteriormente todos sus hijos, seguidos de los hijos de los hijos, etc.
El recorrido en profundidad, en cambio, viaja hasta el final de cada rama, en lugar de viajar por niveles. Cuando no puede visitar más nodos por una rama en concreto (bien sea porque los nodos vecinos ya han sido visitados o porque no hay más), vuelve atrás y sigue visitando las otras ramas.

En la imagen adjunta (wikipedia) vemos un ejemplo de recorrido en profundidad de un árbol, siendo los valores de los nodos el orden en que estos son visitados.

El algoritmo usado es algo así:

procedure profundidad(G : grafo)
      for all v in vértice de G do
           visitado[v] := false

      tiempo := 0

      for all v in vértice de G do
           if not visitado[v] then
                profundidad(G, v)

procedure profundidad(G : grafo; v : vértice)
      visitado[v] := true
      tiempo := tiempo + 1

      for all w in vértice adyacente de v do
           if not visitado[w] then
                profundidad(G, w)

      tiempo := tiempo + 1
      final[v] := tiempo


Alguna información almacenada, como el tiempo de visita y de finalización, son prescindibles para hacer el recorrido, pero reportan información útil para otros algoritmos sobre grafos basados en el recorrido en profundidad.

Ordenación topológica

La ordenación topológica de un grafo consiste en ordenar los nodos del mismo de manera que para toda arista (v, w) dentro del grafo dirigido, el nodo v aparezca antes que el nodo w en la ordenación topológica. Imaginemos que usamos un grafo para modelar cualquier conjunto de tareas, como por ejemplo la construcción de una casa. Antes de construir las paredes deberemos cimentar la construcción, del mismo modo que antes que construir el tejado hay que poner los pilares de la casa. De este modo, representamos las tareas parciales como nodos del grafo, y la dependencia entre ellas como aristas. Una ordenación topológica de este grafo nos indicaría el orden en que debemos realizar las tareas para cumplir las dependencias. En la wikipedia podéis encontrar un ejemplo muy ilustrativo.

Una nota: es importante tener en cuenta que para realizar la ordenación topológica de un grafo este no debe contener ciclos!

Ordenación topológica inversa

La ordenación topológica inversa es, como su nombre indica, justo lo contrario. Para cada arista (v, w) del grafo dirigido G, con v != w, el resultado contiene w antes que v. Todo este post mal estructurado tiene por objetivo explicar un algoritmo muy interesante para obtener la ordenación topológica inversa de un grafo, basado en el recorrido en profundidad. Si observamos el resultado de aplicar un recorrido en profundidad como el enunciado anteriormente, comprovamos que el vector de vertices ordenado en función del tiempo final de visita es equivalente a una ordenación topológica inversa. Por lo tanto, lo único que deberiamos hacer es usar el algoritmo dfs presentado. A continuación mostramos una implementación senzilla usando el paquete networkx para representar el grafo dirigido mostrado. El resultado de la ejecución de este código es, partiendo del vértice s, ['t', 'c', 'b', 'f', 'i', 'e', 'a', 'd', 'h', 'g', 's'].


# -*- coding: utf-8 -*-
import networkx as nx

def inverted_topsort(G, vertex):
      sorted_list = []
      visitat = {}

      for v in G.nodes():
           visitat[v] = False

      dfs(G, vertex, visitat, sorted_list)

      return sorted_list

def dfs(G, v, visitat, sorted_list):
      visitat[v] = True

      for w in G.neighbors(v):
           if not visitat[w]:
                dfs(G, w, visitat, sorted_list)

      sorted_list.append(v)


G = nx.DiGraph()

G.add_nodes_from(['s', 'a', 'g', 'd', 'b', 'e', 'h', 'c', 'i', 'f', 't'])
G.add_edges_from([('s', 'a'), ('s', 'd'), ('s', 'g'), ('g', 'd'), ('g', 'h'), ('g', 'e'), ('d', 'a'), ('d', 'e'), ('h', 'e'), ('h', 'i'), ('a', 'e'), ('a', 'b'), ('b', 'c'), ('e', 'c'), ('e', 'f'), ('e', 'i'), ('i', 'f'), ('i', 't'), ('f', 'c'), ('f', 't'), ('c', 't')])

print inverted_topsort(G, 's')


Actualitzar a Ubuntu 9.10

D'aquí 10 dies, seguint amb la seva política de nova versió cada 6 mesos, la gent d'Ubuntu arriba amb la nova versió de la distribució, la 9.10, anomenada Karmic Koala.

Pels que no poden esperar més, hi ha la possibilitat d'actualitzar abans del llançament oficial, en base a les diverses Alphas (versions en desenvolupament) que van llançant, o l'actual Beta (producte en fase de proves, que ajuda a reportar bugs i solucionar-los als desenvolupadors). Jo l'acabo d'instal·lar i la veritat és que funciona mel.

Per això, basta executar la comana sudo do-release-upgrade -d i seguir les instruccions que ens apareixen a la pantalla.

En cas de no funcionar, haurem d'instal·lar el paquet update-manager-core. També és important editar el fitxer /etc/update-manager/release-upgrades, i establir la opció Prompt=normal, si no estàs preestablerta.

Font: Upgrading from Ubuntu 9.04

Cap a Barcelona!

Després de pràcticament un any d'abandonament descarat, aquest blog (així com el seu autor) comença una nova etapa d'activitat. Des del desembre passat no publicava res, sense motiu aparent. En certa mesura aquesta letargia era motivada per l'aparició de nous canals de comunicació: xarxes socials com Facebook i twitter, on es pot estar en contacte amb la gent propera (i no tant) amb molta facilitat. De la mateixa manera que l'activitat a la plana web de Bulma va quasi desaparèixer amb el sorgiment dels blogs personals, el meu blog personal havia estat abandonat per una mescla d'apatia i la meva mudança cap a canals de comunicació que, d'alguna manera, el substituïen.

Tot i això, varies raons em porten a reviscolar aquest raconet de la xarxa. Per una banda, les xarxes socials abans esmentades tenen molts problemes com a canal de comunicació seriosa: des de la brevetat que exigeixen (qui pot argumentar segons que en un twitt de 140 lletres?), fins a la sobredosis d'irrellevància d'alguns missatges (mort a les galetes de la sort del facebook). Però tot té la seva utilitat, i com a instrument de conversa banal, font de noticies breus, o per a la comunicació instantània i el microblogging, continuen sent un bon lloc de trobada. Per això he afegit a la barra dreta del blog un petit gadget que us permet seguir la meva xerrameca pel twitter.

Però el que és més important, i el que m'ha fet donar la passa de tornar per aquí és que en uns dies començo una nova etapa de la meva vida com a estudiant de l'enginyeria superior en informàtica a la Universitat Politècnica de Catalunya. Després de tres anys passejant per la UIB, ja sóc Enginyer Tècnic en Informàtica de Sistemes i tenc moltes ganes de canviar d'aires, acadèmics i de ciutat. Una bona excusa per posar de nou en marxa el motor d'arrencada d'aquest lloc. Siau benvinguts!

Si els llenguatges de programació fossin religions

C would be Judaism - it's old and restrictive, but most of the world is familiar with its laws and respects them. The catch is, you can't convert into it - you're either into it from the start, or you will think that it's insanity. Also, when things go wrong, many people are willing to blame the problems of the world on it.

Java would be Fundamentalist Christianity - it's theoretically based on C, but it voids so many of the old laws that it doesn't feel like the original at all. Instead, it adds its own set of rigid rules, which its followers believe to be far superior to the original. Not only are they certain that it's the best language in the world, but they're willing to burn those who disagree at the stake.

PHP would be Cafeteria Christianity - Fights with Java for the web market. It draws a few concepts from C and Java, but only those that it really likes. Maybe it's not as coherent as other languages, but at least it leaves you with much more freedom and ostensibly keeps the core idea of the whole thing. Also, the whole concept of "goto hell" was abandoned.

C++ would be Islam - It takes C and not only keeps all its laws, but adds a very complex new set of laws on top of it. It's so versatile that it can be used to be the foundation of anything, from great atrocities to beautiful works of art. Its followers are convinced that it is the ultimate universal language, and may be angered by those who disagree. Also, if you insult it or its founder, you'll probably be threatened with death by more radical followers.

C# would be Mormonism - At first glance, it's the same as Java, but at a closer look you realize that it's controlled by a single corporation (which many Java followers believe to be evil), and that many theological concepts are quite different. You suspect that it'd probably be nice, if only all the followers of Java wouldn't discriminate so much against you for following it.

Lisp would be Zen Buddhism - There is no syntax, there is no centralization of dogma, there are no deities to worship. The entire universe is there at your reach - if only you are enlightened enough to grasp it. Some say that it's not a language at all; others say that it's the only language that makes sense.

Haskell would be Taoism - It is so different from other languages that many people don't understand how can anyone use it to produce anything useful. Its followers believe that it's the true path to wisdom, but that wisdom is beyond the grasp of most mortals.

Erlang would be Hinduism - It's another strange language that doesn't look like it could be used for anything, but unlike most other modern languages, it's built around the concept of multiple simultaneous deities.

Perl would be Voodoo - An incomprehensible series of arcane incantations that involve the blood of goats and permanently corrupt your soul. Often used when your boss requires you to do an urgent task at 21:00 on friday night.

Lua would be Wicca - A pantheistic language that can easily be adapted for different cultures and locations. Its code is very liberal, and allows for the use of techniques that might be described as magical by those used to more traditional languages. It has a strong connection to the moon.

Ruby would be Neo-Paganism - A mixture of different languages and ideas that was beaten together into something that might be identified as a language. Its adherents are growing fast, and although most people look at them suspiciously, they are mostly well-meaning people with no intention of harming anyone.

Python would be Humanism: It's simple, unrestrictive, and all you need to follow it is common sense. Many of the followers claim to feel relieved from all the burden imposed by other languages, and that they have rediscovered the joy of programming. There are some who say that it is a form of pseudo-code.

COBOL would be Ancient Paganism - There was once a time when it ruled over a vast region and was important, but nowadays it's almost dead, for the good of us all. Although many were scarred by the rituals demanded by its deities, there are some who insist on keeping it alive even today.

APL would be Scientology - There are many people who claim to follow it, but you've always suspected that it's a huge and elaborate prank that got out of control.

LOLCODE would be Pastafarianism - An esoteric, Internet-born belief that nobody really takes seriously, despite all the efforts to develop and spread it.

Visual Basic would be Satanism - Except that you don't REALLY need to sell your soul to be a Satanist...

Llegit a Aegisub.

Democràcia Re[i]al

Planificadores de disco genéticos

Los planificadores de disco (también conocidos como IO schedulers) son una parte del sistema operativo que se encarga de reordenar las peticiones de acceso al disco para garantizar equidad y el mejor tiempo de acceso posible. Esto es especialmente importante en entornos de multiprogramación, dónde el acceso concurrente de varios procesos al disco puede provocar que el acceso a bloques sea cercano a la aleatoriedad, provocando unos tiempos de posicionamiento (seek time) de los cabezales inaceptables. Para solucionar el problema se pueden aplicar distintas políticas (noop, elevator y sus variantes, etc..), pero en este caso vamos a hablar de schedulers genéticos.

Que son los algoritmos genéticos?

Los algoritmos genéticos son aquellos que, inspirados en la selección natural, ofrecen una heurística basada en la evolución de una población de posibles soluciones hasta llegar a la más óptima. Para ello deberemos determinar una función que sea capaz de evaluar en cada iteración lo adecuadas que son las soluciones. Para la siguiente iteración crearemos un nuevo grupo de soluciones usando los más óptimos del paso anterior y técnicas como la recombinación genética y la mutación.

Muy bien, todo muy bonito y elegante, pero ..

¿Por que usarlos para diseñar IO schedulers?

Las políticas de planificación de entrada/salida sirven a un fin en concreto; el Noop funciona muy bien para discos de estado sólido, el CFQ es ideal para sistemas multiusuario, y el anticipatorio funciona muy bien para servidores Apache, por ejemplo. Todos tienen terrenos muy marcados, y en caso de tener un entorno muy dinámico, con cargas de trabajo cambiantes, no sabremos por cual nos debemos decantar. Dado este ambiente, ¿que mejor que un algoritmo que evolucione hasta encontrar la solución más adecuada?

Las implementaciones actuales[1], desgraciadamente, no son capaces de estabilizar la población para encontrar una solución óptima en un tiempo razonable (se barajan tiempos de unos 1000 segundos para responder adecuadamente a la nueva carga del sistema). Afortunadamente, esto abre camino a nuevas investigaciones en este campo que prometen interesantes avances.

[1] A Study of Genetic Algorithms for I/O Scheduling