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.

Puntos Extra "Algoritmo Dijkstra"

Algoritmo Dijkstra:

A Este algoritmo, tambien se le llama algoritmo del "Camino Minimo" ya que consiste en encontrar y tomar 1 de los "n" posibles caminos para llegar al objetivo, este camino elegido debe ser, el de menor costo, ya se a de tiempo, esfuerzo, distancia, etc, si s posible estas caracteristicas juntas en un solo camnino, pues el algoritmo seria más optimo aún.

Es común representar este algoritmo con un grafo, como se muestra en el ejemplo:

• Se enumeran los vertices, para identificar cada punto.
• Se enumeran las aristas conforme a su peso o coste.
• Se inicia de un vertice base, o el vertice de salida.
• Despues se fija un objetivo.
• Luego el algoritmo empieza a reconocer todos posibles caminos a elegir, para comenzar.
• Toma el camino de menor coste o más corto.
• Así sucesivamente hasta llegar al punto final ó meta.
• La suma de todo el coste total del el algoritmo, es por ende

  , el más optimo, ya que escogio la ruta que le convenia.

De que me sirve???

Si nos damos cuenta, este algoritmo es más común de lo que su nombre aparenta, ya que, lo utilizamos muy a menudo, si refleccionamos, a cualquier lado al que vamos pensamos detenidamente cual es la mejor manera de llegar a ese lugar, ya sea de como llegar mas rapido, o como llegar con menos gastos ó como llegar con el menor esfuerzo y si es posible uno solo que cumpla con todos estos requisitos.

Pero enfocado a mi carrera, este algoritmo es demaciado utlil, ya que hoy en dia podriamos decir que tiempo es dinero, es decir, el tiempo vale y mucho, entonces me es muy util dominar este algoritmo para aplicarlo a mi desarrollo laboral, ya que hay empresas que pagan muy bien por que el trabajo se haga a tiempo y que sea de calidad, y este algoritmo es una muy buena referencia para basarse en este aspecto.

Video

Explicacion:

En el video se mustra un robot, que es una maquina deterministica que primero reconoce el lugar en el que se encuentra, despues, mediante una computadora ligada al robot, se le asignan puntos u objetivos a llegar, y el robot recorre el camino que mas le conviene en este caso el mas optimo.

Puntos Extra "Quick Sort"

Definición:

El sistema de ordenamiento rápido Quick Sort es un algoritmo que no solo nos sirve para organizar una lista de datos desorganizados, si no también, para optimizar el tiempo que se ocupa en realizar esta labor, ya que permite ordenar "n" elementos en un tiempo proporcional de O(n log n), lo cual es muy eficiente.

Algoritmo:

La función de este sistema de ordenamiento en una lista de datos desorganizada escoger un pivote, el cual puede ser elegido al azar, pero yo creo mas conveniente, escoger uno que este en medio, después se mandan todos los elementos con valor menor que el pivote al lado izquierdo y a todos los mayores del lado derecho:

elemento < pivote =" Izquierda

elemento > pivote = Derecha

Después empieza a ordenar del lado izquierdo a todos los elementos menores que el pivote de manera recursiva hasta que queden ordenados y lo mismo del lado derecho, hasta el punto en que ambos lados quedan e orden, y por consecuencia toda la lista.

Ejemplo: (Dar clic a la palabra ejemplo para verlo)

• Es una lista desordenada la cual esta representadas por barras de diferentes tamaños.
• El algoritmo primeramente escoje un pivote.
• Después al resto de los elementos los evalúa, así que los que sean menores que el pivote los manda del lado izquierdo y a los mayores del lado derecho.
• Hace de cada lado lo mismo recursivamnte hasta tenerlos en orden.
• Y al final como cada lado del pivote esta ordenado entonces nos quedaría una lista en orden.

Para que me sirve???

Bueno a mi en lo personal, este algoritmo es muy útil, ya que me permite organizar datos de manera que puedo enlistar ordenadamente una lista de prioridades a hacer, lo cual me ahorra tiempo y esfuerzo, pero para mi carrera creo que es un algoritmo que me sera muy útil, ya que hay múltiples aplicaciones para este, como hacer programas que me organizen ciertos datos, por que depende de esos datos ordenados para obtener un resultado y si este resultado lo puedo obtener en un mejor tiempo pues me seria muy útil usarlo, un ejemplo seria, que al ingresar ciertos datos (en desorden) tenga que sacar la mediana (Estadística), entonces aquí vendría a aplicar muy bien este algoritmo.

Aplicacion a mi vida diaria:

Yo actualmente trabajo en unas cintas de música, Audio Scream, y aunque no lo creean este algoritmo "Quick Sort" es aplicable ahí, ya el equipo de aparatos con el que contamos difiere unos de otros en peso y tamaño, y los trasladamos por medio de un camión, contamos con aparatos suficientes para atender a 3 eventos al mismo tiempo:

Equipo:

• 2 Elevadores Gennie.
• 2 Bajos JBL.
• 8 Bajos Cerwin-Vega.
• 3 Periferias.
• 2 Estructuras tipo punta (y complementos).
• 4 Luces Blancas (Cabezas Mobiles).
• 10 Luces Power Spot Negras (Cabezas Mobiles).
• 2 Centros de Carga.
• 10 Luces Technobeam.
• 12 Bocinas Mackie.
• 3 Tornamesas Dj (2 Denon y 1 Mezcladora c/u).
• 3 maquinas de humo.
• 2 Laptops.
• 3 Interfaces.
• Cableado (Extensiones, cables Canon, AC de corriente, etc).

*La lista del equipo esta ordenada con forme a su peso y tamaño*

Entonces, aveces es necesario bajar del camión solo los bajos ó nada mas una estructura o nada mas cable, etc. de manera que si metemos todo al camión desorganizadamente, aparte que no cabria bien, al momento de sacar algo en especifico, nos llevaría mas tiempo primero buscar donde esta y después mover todo lo que hay antes para poder sacarlo; con el algoritmo Quick Sort nos evitariamos todos esos contratiempos, de manera que antes de subir el equipo al camión, podríamos acomodarlo conforme su peso y tamaño, entre más pesado y grande más al fondo y entre entre más ligero y pequeño al frente. De esta manera sabemos que si queremos sacar un Bajo Cerwin-Vega sabríamos que esta al fondo ó si queremos sacar un rac de luces, este estará en medio, y así sabríamos que mover o bajar para poder llegar al objetivo.

Video

Explicacion:
El video muestra la comparacion del metodo Quick Sort vs. Bubble Sort (Ordenamiento Burbuja) que ambos son algoritmios de ordenamiento, pero claramente se muestra que el Quick Sort es mas eficiente, es decir, es más rapido y funcional, ya que el algoritmo Quick Sort hace la misma tarea en menos pasos, por lo que termina antes. En conclucion el Quick Sort es de los algoritmos mas optimos de ordenaminento.

Proyecto #4 "Tablas de Dispersion"

Introducción:

Una Tabla de Dispersión, en pocas palabras, es aquella que asocia claves o llaves a determinados valores, atraves de una función Hash, también se les llaman Tablas Hash.

Trabajo en Equipo:

¿Que hice yo?

Mi trabajo individual mente dentro del equipo fue como el de los demás, checar información de distintas fuentes acerca del tema, tablas de dispersión, y compartirlo con mis compañeros para estar en el mismo canal y no desviarnos del tema, también cheque previemante todos los demás temas disponibles a exponer para tener una idea superficial de como iba a ser este proyecto 4, también le di estructura a la presentación de las diapositivas que después editamos, también trate de buscar los ejemplos mas entendibles y que creí que los demás compañeros de clase pudieran entender en nuestra clase.

¿Como me salio?

En mi opinión digo que me salio excelente, hay que ser optimista :D pero si creo que hicimos las cosas bien como equipo y cada quien individualmente trato de acoplarse a los demás para mejorar la clase que vamos a dar.

¿En que aspectos estoy bien y en que aspectos puedo mejorar?

Creo que estoy bien tratando de hacer las cosas de la mejor manera posible, ya que quiero obtener todos los puntos completos de los proyectos restantes y obtener la calificación mejor que se pueda, también yo creo que estoy satisfecho conmigo mismo por que no solo me limite en buscar lo que sea para hacer la clase, si no que busque lo que mejor se entendiera para ofrecer una buena clase.

Yo creo que en los aspectos que debería de mejorar seria, el de dedicar un poco mas de tiempo a investigar a cosas que van mas aya de lo que se ve en clase, no solo para que me vaya bien en la materia, si no también para enriquecerme de mas conocimientos que me ayuden con mi formación profesional.

Ayudo a los demás o me apoyo en ellos?

Yo creo que hago de ambos aspectos, ayudo a mis compañeros yo creo que si por que por ejemplo para la clase yo investigue en paginas que se explica sobre el tema pero en ingles y que yo si le entiendo y explicarle a mis compañeros de lo que dice, también les decía como era una mejor forma de explicar lo que ellos iban a dar de clase, osea de su parte de exposición, entre otras; pero también yo me apoyo en ellos para saber si estoy bien en lo que digo o de lo que investigue para la clase, en pocas palabras ambas son necesarias para una retroalimentación entre los cuatro y ayudarnos todos para hacer mejor las cosas, como el dicho "todos para uno y uno para todos" o "4 cabezas piensan mejor que una" jajaja.

¿Quien se encarga de coordinar el trabajo? ¿Que papel tomo yo?

En mi opinión yo soy el que coordina, pero creo que es mejor decir que yo era el medio de comunicacion entre el equipo por que yo me ponía en contacto para ponernos de acuerdo en juntarnos para hacer este proyecto, del cual todos necesitamos la mejor calificación, y por eso también me esfuerzo en que todo salga bien y poder ofrecer una buena presentación, en fin espero obtener 4 en este proyecto y en los que restan.

Presentación:

Link a la presentación aquí

Proyecto #3 - Computo de Factoriales

Iteración:

La iteración en pocas palabras es la repetición, y en este caso es la repetición del algoritmo las veces necesarias o que se requiera para la solución del algoritmo.

Recursion:

Esta propiedad consiste en sintetizar un algoritmo que no se sabe su resolucion, a partes mas simples las cuales si se puedan resolver, es decir, partir de un caso base, que es lo que si sabemos resolver y de ahí partir para encontrar la solución a nuestro algoritmo.

Recomendaciones:

Es muy útil usar la iteración cuando el algoritmo es repetitivo, es recomendable usar las estructuras for y while en la creación del pseudocódigo:

For → Cuando se sabe el numero de veces a repetir el algoritmo.
While → Cuando no se sabe el numero de veces a repetir el algoritmo.

La Recursion es muy útil cuando no se sabe la resolución de un algoritmo y es necesario simplificarlo para poder resolverlo a partir de un caso base.

Si no es necesario usar la recursion en la resolucion de algoritmos es preferible omitirmosm ya que de lo contrario haria un algoritmo que es facil de resolver a uno con un monton de pasos inesesarios para su solucion, lo cual ocuparia mas memoria de la computadora y seria contraproducente.

Trabajo en Grupo:

Lo que en equipo hicimos fue dividirnos el trabajo para no hacerlo tan pesado y que cada integrante investigara bien lo que se iba a exponer y ya después que cada quien explicara y a los demás que fue lo que investigo y que así todos estuviéramos enterados del trabajo de cada quien.

Trabajo Individual:

Lo que yo hice fue investigar como hacer un pseudocodigo iterativo del problema del factorial y después lo pase a un compilador para correrlo y hacerlo funcionar, también investigué de la complejidad del algoritmo, y todo lo respalde con mis compañeros de equipo para editar las diapositivas.

Diapositivas:

•Para descargarla:

•Para verla en linea:

Bloggs del Equipo:

http://algoritmoscomp.blogspot.com/
http://acrtb7.blogspot.com/
http://3imedio.blogspot.com/
http://raulelchupete.blogspot.com/

Proyecto #2

Optimización

Problema:

"El alcalde de San Nico va a recibir en nuestro municipio al presidente de México en la plaza municipal, para lo que dicha zona debe estar presentable para ese día, digamos que los días restantes para su llegada son 3, entonces el alcalde quiere encontrar la manera mas óptima para dejar esa zona muy bien presentable para tal fecha"

Supongamos que el alcalde cuenta con un presupuesto de $1,166,666.6 para una semana por lo que a los correspondientes 3 días son $500,000 ; el cual es sacado de los impuestos que pagan los ciudadanos; y los aspectos para arreglar en la zona son:

1. Basura

2. Pintura

3.Mantenimiento

El área del terreno a arreglarse es de 1800m cuadrados:

El alcalde cuenta con 3 compañias que se encargan de realizar el trabajo que se requiere y son las siguientes;

Opción 1:

Ellos se tardan 5 días en realizar este trabajo y cobran un 150% mas por cada día menos que se aplace la fecha. La ponderación de lo que cobran por cada aspecto es:

1. Basura → $25 c/m2
2. Pintura → $100 c/m2
3.Mantenimiento → $80 c/m2

f(x)=((25x+100x+80x)•3)+z

si z=25x+100x+80x

Opción 2

Ellos se acomodan al limite de tiempo que el cliente necesita para el trabajo. La ponderación de lo que cobran por cada aspecto es:

1. Basura → $35 c/m2
2. Pintura → $90 c/m2
3. Mantenimiento → $50 c/m2

f(x)=35x+90x+50x

Opción 3

Ellos tradan 2 dias en hacer su trabaj y hacen un descuento del 5% por cada dia de plazo que se le den de mas.

1. Basura → $60 c/m2
2. Pintura → $110c/m2
3. Mantenimiento → $70 c/m2

f(x)=60x+110x+70x - (z(0.05))

si z=60x+110x+70x

¿Cual sera la manera mas óptima para encargar el trabajo?

Como el área =1800m2 entonces los costos de cada una de las empresas son:

Opción 1

1. Basura → $202,500
2. Pintura → $810,000
3.Mantenimiento → $144,000

=$1,156,500 + 300%
Total =$4,626,000

Opción 2

1. Basura → $63,500
2. Pintura → $162,000
3.Mantenimiento → $90,000

Total=$169,200

Opción 3

1. Basura → $108,000
2. Pintura → $198,000
3.Mantenimiento → $126,000

=$432,000 - 5%
Total=$410,400

Complejidad Asintótica

La manera mas óptima seria encontrar una cota inferior a la del presupuesto, pero entre mas alejada se encuentre de esta sera menos el costo, por lo tanto, mas óptimo.

En este caso como se observa en la gráfica la cota óptima a elegir es la opción 2 de color azul, ya que cumple con los requisitos para optimizar el trabajo, se encuentra debajo de la cota de ingreso (verde) y es también la cota mas baja, por lo tanto la menos costosa.

Este problema de decisión pertenece a la clase "P", ya que la elección no es muy complicada y las ecuaciones de cada opción son lineales, es por eso que no es muy difícil su solución.
Aparte estos algoritmos no pertenecen a un problema NP-difícil, por que para empezar como no es un problema NP por lo tanto no puede ser NP-duro.

Esta es una representación del algoritmo:

*Este no es un diagrama de flujo, solo es una representación del algoritmo en diagrama simple.



Referencias :

http://www.google.com.mx/
http://es.wikipedia.org/wiki/NP-hard
http://es.wikipedia.org/wiki/Clases_de_complejidad_P_y_NP
http://es.wikipedia.org/wiki/Cota_superior_asint%C3%B3tica
http://es.wikipedia.org/wiki/Optimizaci%C3%B3n_de_software
http://maps.google.com.mx/?gclid=CKvjnPWen6ACFSpeagodMlwzag
http://es.wikipedia.org/wiki/Problema_de_decisi%C3%B3n

Proyecto #1 "Algoritmos Computacionales Simples"

Problema:

5. Elegir entre posibles objetos de valor cuáles llevar a un viaje en una
mochila con capacidad límitada.

Ejemplo#1

Algoritmo:

1. Inicio

2. Se declaran las constantes y variables (c, Ipod=500, Lap=2000, Celular=500, Diccionario=800, Calzado=1000, Ropa=3000, Joyeria=1000, Usb=200, Grabadora=3000, TV=5000, Xbox=3000)

3. Pedir d segun la funcion (d=suma de n articulos)

4. Asiganar d (Xbox, Ipod, Celular)

5. Evaluar condicion (d<=6000)

6. Imprimir (Verdadero)

7. Fin

Ejemplo#2

Algoritmo:

1. Inicio

2. Declarar las constantes y variables (c, Ipod=500, Lap=2000, Celular=500, Diccionario=800, Calzado=1000, Ropa=3000, Joyeria=1000, Usb=200, Grabadora=3000, TV=5000, Xbox=3000)

3. Pedir d segun la funcion (d=suma de n articulos)

4. Asiganar d (TV, Xbox, Ropa, Usb, Lap, Calzado)

5. Evaluar condicion (d<=6000)

6. Imprimir (Falso)

7. Asignar d nuevamente (Ropa, Lap)

8. Evaluar condicion (d<=6000)

9. Imprimir (verdadero)

10. Falso

*En estos videos vienen explicados paso a paso los diagramas de flujo.