jueves, 20 de mayo de 2010

Ordenación Topológica



Algoritmo:

La ordenación topológica es un sistema de ordenamiento de un grafo acíclico, es decir, que no tiene ciclos; el cual consiste, en organizar de forma lineal ó en lista ascendente ó descendente, una serie de vértices en desorden, para lo cual primero debe de empezar de un "vértice padre" osea, un vértice sin predecesores, y después visitar a sus vecinos, después de que haya visitado a tos sus vecinos, pasa a analizar otro vértice, y de igual forma identifica todos sus vecinos, y así recursivamente, hasta que haya visitado a todos los vértices. En pocas palabras no se visitara un vértice, hasta que todos sus predecesores hayan sido visitados.
Después de que ya han sido visitados todos los vértices del grafo dirigido, se acomodan en lista ya sea d forma ascendente o descendente, según se requiera, y se acomodan en base a el coste de tiempo de los vértices.
Ejemplo: Este es un ejemplo común aplicado a la vida diaria, tan simple de como vestirse.
  • Arriba de cada vértice se muestra el coste de tiempo.
  • Distancia / Finalizacion

  • El algoritmo nos devuelve una lista enlazada, con los nodos del grafo, en orden decreciente en tiempo de finalizacion.



  • Una vez ya ordenado topologicamente se pueden ver las precedencias de las tareas:
  1. Ponerse la camisa antes que el cinturón y el jersey.
  2. Ponerse el pantalón antes que los zapatos y el cinturón.
  3. Ponerse los calcetines antes que los zapatos.

Pseudocódigo:

  1. Para cada vértice "u" que pertenezca al grafo hacer:
  2. El estado "u" No visitado, por que se comienza el algoritmo.
  3. El padre debe ser nulo, por que no tiene predecesores.
  4. El tiempo inicia de 0, obviamente por que se inicia el algoritmo.
  5. Después, si el estado = No visitado entonces: Se pone en marcha la ordenación topológica.
  6. El estado cambiara a Visitado por que ya fue visitado y analizados su s predecesores.
  7. Por lo tanto se le suma un 1 al tiempo por que es lo que tardo en ese vértice.
  8. Después para cada vértice adyacente hacer:
  9. Si el estado= No visitado entonces:
  10. El padre ahora sera ese vértice, ya que es el siguiente en orden.
  11. Cuando el estado del vértice = Terminado:
  12. Se suman los tiempos y este seria el coste total por el ordenamiento.
  13. Se inserta el resultado de la lista del algoritmo de ordenación topológico.

Análisis Asintótico:

En el análisis asintótico del algoritmo de ordenación topológica es costoso buscar vértice sin predecesores, varias veces.

La solución seria calcular previamente cuantos predecesores tiene cada vértice, almacenar el dato en un vector y actualizarlo siempre que se incorpore un nuevo vértice a la solución.

Coste de Tiempo:

  • Inicializacion:

Primer bucle: O(n) --- Quiere decir que va a depender del numero de vértices que tenga el grafo.

Segundo bucle: Examinacion de todas las aristas.

O(a+n) --- Para listas de adyacencia.

O(n^2) --- Para matriz de adyacencia.

  • Bucle Principal:

O(a+n) --- Para listas de adyacencia.

O(n^2) --- Para matriz de adyacencia.



Estructuras de datos:

  • Listas Enlazadas: Para este algoritmo de ordenación topológica, se usan las listas enlazadas, ya que la ordenación ya finalizada es una lista lineal simple con aristas que conectan de igual forma como se tenia antes.
  • Isomorfismo: Algo tiene que ver con ismorfismo, aunque no son grafos conexos y es acíclico el algoritmo permite alinear los vértices, pero conservando los enlaces entre cada uno de los vértices, es decir, solo se acomoda por prioridad, pero conserva su estructura.
  • Arboles: También se puede decir que esta relacionado con árboles ya que estos contienen nodos también llamados vértices, y los arboles pueden adoptar distintas formas de ordenamiento.
  • Búsqueda de profundidad (DFS): La ordenación topológica necesita del algoritmo de búsqueda DFS ya que necesita aplicarlo para ir explorando nodos, y al final llegar a un ordenamiento lineal.

Aplicaciones:

  • Puede ser aplicable a la reprecentacion de las fases de un proyecto , donde los vértices representen tareas, y las aristas relaciones temporales a ellas.
  • Evaluacion en la fase semántica de un compilador.
  • En la vida diaria lo podríamos aplicar en cosas simples por ejemplo, organizar los recibos de los servicios a pagar, ya que estos llegan en diferentes días, y difieren en precio y vencimiento, y al aplicarle este algoritmo, podríamos ordenarlos en orden de prioridad de vencimiento, para irlos pagando ordenadamente, sin que se nos pasen y sin que gastemos el dinero necesario para pagarlos.
  • También nos serviria para encontrar algun ciclo en un grafo e identificarlo.
  • También para encontrar algun problema o defecto de cierto algoritmo que se ordene topologicamente.

Autoevaluación

En lo personal este proyecto y los otros cuatro me han sido de gran ayuda ya que la mayoría de los temas vistos eran nuevos para mi, y me di cuenta que son de gran utilidad aplicarlos a la vida cotidiana; en lo que respecta a este de la ordenación topológica, pues me deja como enseñanza a los casos en los que puedo aplicar este algoritmo. Aprendí que para alguna tarea en particular hay una(s) antes de precedencia y otra(s) como consecuencia de esa tarea, y que al fin y al cabo están vinculadas unas con otras. En conclusión de ahora en adelante las cosas que tenga que hacer a las que se le pueda aplicar este algoritmo, me facilitara la tarea, y por lo tanto tiempo y esfuerzo.

Para cualquier duda ó pregunta que tengan dejen su comentario y yo les responderé los mas pronto posible.





12 comentarios:

  1. me parecio muy interesante ya que yo no lo habia visto antes.
    En este tipo de algoritmo entonces su complejidad asintotica seria P porque ya sabras que tienes que visitar a los vecinos de cada vertice y ya tendra un numero determinado de pasos por lo cual no podria ser NP-completo porque no estas haciendo un recorrido al azar sino ya tendras un destino el cual lo visitara cada vertice que seria visitar todos sus vecinos para pasar al siguiente vertice y asi sucesivamente el cual ya tendras un tiempo estimado de finalización del ordenamiento.

    ResponderEliminar
  2. Ricki muy buena aplicacion para la vida diaria , sobre los resivos y acomodarlos de acuerdo a su vencimiento.

    nunca habia escuchado de tu problema, sin embargo tiene mucha utilidad, tu blog contiene muy buena informacion para estudiar para el examen.

    pero apoco si pertenece a P como dice mi compañero joel ??

    cuidate baii

    ResponderEliminar
  3. Olvida lo que pregunte que si pertenencia a P , voovlir a aleer el comentario de mic ompañero y con la clase que diste hoi entendi el porque

    grasias

    ResponderEliminar
  4. Hola, muy bueno el reporte, entendí bien el funcionamiento del algoritmo porque lo explicaste muy bien en la clase, y la mayoría de las aplicaciones se me hicieron interesantes.Solo tengo una duda. Como funcionaria en el caso de la evaluación semántica?. Espero me resuelvas la duda.
    Saludos

    ResponderEliminar
  5. aqui dejo mi nombre y blog para que la profe me reconosca me llamo Joel Angel soy de la clase de juves mi blog es
    http://jo0eel.blogspot.com/

    ResponderEliminar
  6. Hola soy Blanka...
    Es un reporte excelente ya que nos diste un ejemplo de la vida diaria... y asi es mucho mas facil de entenderle...

    http://blankardz22.blogspot.com

    ResponderEliminar
  7. me parecio muy interesante este algoritmo y como lo explicaste en la clase con el ejemplo, si llegue a entenderlo.
    Quien iba a imaginar que el solo vestirse podria ser un buen ejemplo de este algoritmo.
    Yo tambien tengo la duda de Emmanuel Garcia, en el caso de evaluacion semantica, su pudieras decir un solo ejemplo te lo agradeceria.
    Saludos, muy buen tema!

    ResponderEliminar
  8. holaa muy excelente explicacion habla detalladamente de todo no tengo dudas solo paso a firmar para decirte pues que esta muy bien :D

    ResponderEliminar
  9. Bueno aqui les va la respuesta a la duda que tenian de la aplicacion de la ordenacion topologica en el analisis semantico de un complilador.
    Bueno primero para empezar, hay que identificar a lo que nos referimos con "Evaluacion Semantica de un Compilador":

    Evaluacion---Algo que se tiene a prueba.
    Semantica---Se refiere al significado ó sentido de algun elemento.
    Compilador---Es un programa que interpreta o traduce un lenguaje de programacion.

    Entonces ya juntos la frase se refiere a que "evalua si el significado de determinado proceso de algún algoritmo pertenesca al conjunto y lo pueda traducir.

    Entonces lo que hace la ordenacion topologica, es comprobar que los argumentos que tiene un operador pertenecen al conjunto de los operadores.
    En definitiva, comprobará que el significado de lo que se va leyendo es válido.
    La salida de la fase de análisis semántico sería un árbol semántico. Consiste en un árbol sintáctico en el que cada una de sus ramas ha adquirido el significado que debe tener. En el caso de los operadores polimórficos el análisis semántico determina cuál es el aplicable.

    Espero haberles resuleto la duda, si de igual forma sigen sin entenderlo, con toda confianza, pregunten sus dudas y yo las responere. Gracias por los comentarios.

    ResponderEliminar
  10. gracias por la respuesta
    si aclaraste mi duda :D
    Saludos!

    ResponderEliminar
  11. Muy bien. La complejidad asintótica refiere a la una función en notación O, Omega o Theta. Normalmente se usa la notación O y para este algoritmo la complejidad asintótica es O(|V| + |E|) donde V es el conjunto de vértices (su cardinalidad siendo |V| = n) y E es en conjunto de aristas (su cardinalidad siendo |E| = m). Entonces, ya que sabemos que m es O(n^2) o sea n cuadrado, podemos concluir que en el peor-peor caso será O(n + n^2) = O(n^2) (ya que los términos de potencias menores se quitan de sumatorias en el caso asintótico por lo que vimos en clase hace mucho). En un caso típico, grafos suelen tener pocas aristas en comparación con el peor caso de n^2. De todos modos, siendo un polinomio n^2, se puede concluir que este problema (que es de _construcción_ y no tanto ni de decisión ni de optimización) se podría decir que pertenece a la clase P ya que podría ser formulado (aunque de manera algo artificial) como un problema de decisión que tiene un algoritmo determinista con complejidad asintótica polinomial.

    ResponderEliminar
  12. Gracias por la respuesta.Si se aclaro mi duda.
    Saludos.

    ResponderEliminar