Diferencia entre revisiones de «Práctica 7: Camino Mínimo (Algoritmos III)»
(→Ejercicio 07.03:: Link al pseudocódigo de la wikipedia con heaps) |
m (Arreglo estructura de la práctica 7) |
||
| Línea 1: | Línea 1: | ||
{{Back|Algoritmos y Estructuras de Datos III}} | {{Back|Algoritmos y Estructuras de Datos III}} | ||
== Camino Mínimo == | |||
==Ejercicio 07.01:== | ===Ejercicio 07.01:=== | ||
<br>a) S={I, VI, II, V, III, IV} | <br>a) S={I, VI, II, V, III, IV} | ||
<br>b) | <br>b) | ||
<br>c)Se podría aprovechar hasta el nodo el cual es incidente en nuevo eje que se agrega (no inclusive). | <br>c)Se podría aprovechar hasta el nodo el cual es incidente en nuevo eje que se agrega (no inclusive). | ||
==Ejercicio 07.02:== | ===Ejercicio 07.02:=== | ||
<br>a) Por ejemplo, en un grafo de 3 nodos, donde hay un camino de 1 al 3 de longitud 2, de 1 al 2 de longitud 3 y otro de 2 al 3 de longitud -2, Dijkstra no encuentra la ruta mas corta de 1 a 3. | <br>a) Por ejemplo, en un grafo de 3 nodos, donde hay un camino de 1 al 3 de longitud 2, de 1 al 2 de longitud 3 y otro de 2 al 3 de longitud -2, Dijkstra no encuentra la ruta mas corta de 1 a 3. | ||
Encuentra el camino de longitud 2 y no el de longitud 1 | Encuentra el camino de longitud 2 y no el de longitud 1 | ||
| Línea 14: | Línea 14: | ||
<br>c) Efectivamente, Dijkstra es un algoritmo Goloso. | <br>c) Efectivamente, Dijkstra es un algoritmo Goloso. | ||
==Ejercicio 07.03:== | ===Ejercicio 07.03:=== | ||
Se explica en la toerica, el ciclo interno cuesta O(m) considerando el ciclo mayor(o sea, todo junto), el O(log n) viene de reacomodar el heap luego de la actualizacion de TT en el mismo => m veces log n => O(m log n). | Se explica en la toerica, el ciclo interno cuesta O(m) considerando el ciclo mayor(o sea, todo junto), el O(log n) viene de reacomodar el heap luego de la actualizacion de TT en el mismo => m veces log n => O(m log n). | ||
| Línea 20: | Línea 20: | ||
En la wikipedia está el pseudocódigo utilizando heap o cola de prioridad: http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra#Pseudoc.C3.B3digo | En la wikipedia está el pseudocódigo utilizando heap o cola de prioridad: http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra#Pseudoc.C3.B3digo | ||
==Ejercicio 07.04:== | ===Ejercicio 07.04:=== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
<br>d) | <br>d) | ||
==Ejercicio 07.05:== | ===Ejercicio 07.05:=== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 07.06:== | ===Ejercicio 07.06:=== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
| Línea 34: | Línea 34: | ||
<br>d) | <br>d) | ||
<br>e) | <br>e) | ||
==Ejercicio 07.07:== | ===Ejercicio 07.07:=== | ||
==Ejercicio 07.08:== | ===Ejercicio 07.08:=== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 07.09:== | ===Ejercicio 07.09:=== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 07.10:== | ===Ejercicio 07.10:=== | ||
'''HECHO EN CLASE, EL QUE PUEDA SUBALO (por favor)''' | '''HECHO EN CLASE, EL QUE PUEDA SUBALO (por favor)''' | ||
==Ejercicio 07.11:== | ===Ejercicio 07.11:=== | ||
==Ejercicio 07.12:== | ===Ejercicio 07.12:=== | ||
==Ejercicio 07.13:== | ===Ejercicio 07.13:=== | ||
==Ejercicio 07.14:== | ===Ejercicio 07.14:=== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==PERT== | |||
==Ejercicio 07.15:== | ===Ejercicio 07.15:=== | ||
Tiempo mínimo de ejecución de un proyecto en un grafo de actividades en los nodos es lo mismo que hacer camino màximo. Para hacer camino màximo se puede cambiar el signo de los pesos en los ejes y luego aplicar camino mìnimo con Dantzig o Ford. | Tiempo mínimo de ejecución de un proyecto en un grafo de actividades en los nodos es lo mismo que hacer camino màximo. Para hacer camino màximo se puede cambiar el signo de los pesos en los ejes y luego aplicar camino mìnimo con Dantzig o Ford. | ||
Las actividades críticas son las que pertenecen al camino máximo. | Las actividades críticas son las que pertenecen al camino máximo. | ||
==Ejercicio 07.16:== | ===Ejercicio 07.16:=== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
[[Category: Prácticas]] | [[Category: Prácticas]] | ||
Revisión actual - 01:41 14 may 2015
Camino Mínimo[editar]
Ejercicio 07.01:[editar]
a) S={I, VI, II, V, III, IV}
b)
c)Se podría aprovechar hasta el nodo el cual es incidente en nuevo eje que se agrega (no inclusive).
Ejercicio 07.02:[editar]
a) Por ejemplo, en un grafo de 3 nodos, donde hay un camino de 1 al 3 de longitud 2, de 1 al 2 de longitud 3 y otro de 2 al 3 de longitud -2, Dijkstra no encuentra la ruta mas corta de 1 a 3.
Encuentra el camino de longitud 2 y no el de longitud 1
b) n veces Dijkstra, o sea, o(n^3), o con un Heap, O(n m log n)
c) Efectivamente, Dijkstra es un algoritmo Goloso.
Ejercicio 07.03:[editar]
Se explica en la toerica, el ciclo interno cuesta O(m) considerando el ciclo mayor(o sea, todo junto), el O(log n) viene de reacomodar el heap luego de la actualizacion de TT en el mismo => m veces log n => O(m log n). El pseudocódigo es igual al dado en clase, tambien se puede extraer del Aho o el Cormen. En la wikipedia está el pseudocódigo utilizando heap o cola de prioridad: http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra#Pseudoc.C3.B3digo
Ejercicio 07.04:[editar]
a)
b)
c)
d)
Ejercicio 07.05:[editar]
a)
b)
Ejercicio 07.06:[editar]
a)
b)
c)
d)
e)
Ejercicio 07.07:[editar]
Ejercicio 07.08:[editar]
a)
b)
Ejercicio 07.09:[editar]
a)
b)
c)
Ejercicio 07.10:[editar]
HECHO EN CLASE, EL QUE PUEDA SUBALO (por favor)
Ejercicio 07.11:[editar]
Ejercicio 07.12:[editar]
Ejercicio 07.13:[editar]
Ejercicio 07.14:[editar]
a)
b)
PERT[editar]
Ejercicio 07.15:[editar]
Tiempo mínimo de ejecución de un proyecto en un grafo de actividades en los nodos es lo mismo que hacer camino màximo. Para hacer camino màximo se puede cambiar el signo de los pesos en los ejes y luego aplicar camino mìnimo con Dantzig o Ford. Las actividades críticas son las que pertenecen al camino máximo.
Ejercicio 07.16:[editar]
a)
b)
