El Teorema de los 4 colores establece que cualquier plano dividido en regiones contiguas puede ser coloreado usando a lo más 4 colores, ( no aplicable a otras superficies como el toro ) de forma que dos regiones adyacentes cualesquiera (que tengan un borde en común, no sólo un punto) tienen colores distintos. Por ejemplo, el siguiente plano dividido puede colorearse con sólo 4 colores:
Aunque hay casos en que es posible colorear un plano de forma válida usando menos colores, el teorema se sigue cumpliendo, ya que dice que hacen falta como mucho 4. Este teorema es usado por los cartógrafos desde siempre, pero no había suscitado interés en los matemáticos desde que se planteó aproximadamente en 1850, este teorema recién pudo ser comprobado (no sin algunos reparos) en la década del 70, apoyado por computación.
Ante esto (a mis ex alumnos de Estructura de Datos seguro les traerá mas de algún dolor de cabeza), nos podemos dar cuenta que este teorema es perfectamente aplicable a la teoría de grafos, para poder desarrollar algunos ejercicios, o mas aún podemos advertir que es perfectamente factible mediante este teorema dar solución a ciertos trabajos que nuestros programas realizan en forma diaria (mediante los registros) .
En teoría de grafos, el problema se puede formular convirtiendo el mapa en un grafo plano tal que cada región es un vértice y las aristas van desde los vértices que se corresponden con regiones adyacentes. La solución sería aquella en la que cada vértice tiene un color, de forma que dos vértices adyacentes no tengan el mismo color. Estimados como ven en la siguiente imagen se representa claramente mediante grafos el teorema de los 4 colores (el programa que implementa este grafo queda de tarea)
En general, un grafo es k-coloreable si necesita k colores como mínimo para ser coloreado. A este número se le llama número cromático del grafo, y se representa con la letra χ. El problema de calcular el número cromático de un grafo es NP-duro, aunque existen distintos algoritmos de clase P que se basan en ciertas asunciones para tipos concretos de grafo.
Aplicación de Teorema de los 4 colores en Compiladores usando grafos
Cuando un compilador ha calculado ya la serie de instrucciones para máquina abstracta, el siguiente paso es asignar los registros de la CPU a cada variable, teniendo en cuenta cuando se necesita cada una y cuando deja de utilizarse, para optimizar la ejecución al máximo y acceder a memoria el menor número de veces posible, agilizando así la ejecución.
La forma usual de resolver este problema empieza con un análisis de flujo, del que se calcula el llamado grafo de interferencia. Por ejemplo, dado el siguiente código que empieza con las variables k y j, y termina con las variables d, k y j (asumiendo un pseudoasembler):
k, j
g = mem[ j + 12 ]
h = k -1
f = g * h
e = mem[ j + 8 ]
m = mem[ j + 16 ]
b = mem[ f ]
c = e + 8
d = c
k = m * 4
j = b
d, k, j
Podríamos dibujar un grafo con estos datos a priori, pero necesitamos ir desde el final hacia arriba analizando el uso de y aparición de cada variable, por ejemplo, d es necesaria en la transición 11→12, ya que su valor debe ser devuelto en el estado 12. Paso a paso hacia atrás, se ve que en el estado 9 se le asigna un valor, por lo que ha de mantenerse hasta el estado 12. Si continuamos hacia atrás, se ve que no es usada anteriormente, por lo que se concluye que d debe mantenerse en las transiciones 9→10→11→12. De forma parecida, j debe mantenerse en 11→12, ya que es en 11 donde se le asigna un valor. Sin embargo, retrocediento puede verse que desde el estado 1 es usada hasta el estado 6, a partir de donde su valor puede desecharse hasta el estado 11. Así pues, j debe mantenerse en las transiciones 1→2→3→4→5→6 y 11→12. Continuando con cada variable, construimos la siguiente matriz de interferencia:
Matriz que, a su vez, se corresponde con el siguiente grafo de interferencia, en donde cada vértice es una variable y las aristas unen las variables que están vivas al mismo tiempo y, por tanto, deben estar en registros distintos de la CPU:
Como se ve, el grafo puede colorearse de forma válida con 4 colores. La idea detrás de este grafo es que dos vértices adyacentes contienen variables que deben guardarse en registros distintos. Así, el color asignado a cada vértice se corresponde con un registro de la CPU, y por ello ambos vértices deben tener colores distintos.
De esta forma, 4 registros son válidos para el anterior programa, asignando cada variable al registro de color correspondiente. En general, si la CPU tiene n registros y el número cromático del grafo de interferencia es m, no será necesario llevar variables a la memoria RAM si m es menor o igual que n.
Mucho de este material es sacado de otra WEB, pero me parece importante la visión y enfoque del teorema aplicado a grafos y su solución aplicado a compiladores, es posible mejorar este grafo, por supuesto, recibo comentarios.
No hay comentarios.:
Publicar un comentario