Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si
inicias sesión o
creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.
Puedes deshacer la edición.
Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual |
Tu texto |
Línea 1: |
Línea 1: |
| {{Back|Algoritmos y Estructuras de Datos III}}
| | ==Ejercicio 01:== |
| | | ==Ejercicio 02:== |
| == Camino Mínimo ==
| | ==Ejercicio 03:== |
| | | ==Ejercicio 04:== |
| ===Ejercicio 07.01:===
| | ==Ejercicio 05:== |
| <br>a) S={I, VI, II, V, III, IV}
| | ==Ejercicio 06:== |
| <br>b)
| | ==Ejercicio 07:== |
| <br>c)Se podría aprovechar hasta el nodo el cual es incidente en nuevo eje que se agrega (no inclusive).
| | ==Ejercicio 08:== |
| | | ==Ejercicio 09:== |
| ===Ejercicio 07.02:===
| | ==Ejercicio 10:== |
| <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.
| | ==Ejercicio 11:== |
| Encuentra el camino de longitud 2 y no el de longitud 1
| | ==Ejercicio 12:== |
| <br>b) n veces Dijkstra, o sea, o(n^3), o con un Heap, O(n m log n)
| | ==Ejercicio 13:== |
| <br>c) Efectivamente, Dijkstra es un algoritmo Goloso.
| | ==Ejercicio 14:== |
| | | ==Ejercicio 15:== |
| ===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).
| |
| 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:===
| |
| <br>a)
| |
| <br>b)
| |
| <br>c)
| |
| <br>d)
| |
| ===Ejercicio 07.05:===
| |
| <br>a)
| |
| <br>b)
| |
| ===Ejercicio 07.06:===
| |
| <br>a)
| |
| <br>b)
| |
| <br>c)
| |
| <br>d)
| |
| <br>e)
| |
| ===Ejercicio 07.07:===
| |
| ===Ejercicio 07.08:===
| |
| <br>a)
| |
| <br>b)
| |
| ===Ejercicio 07.09:===
| |
| <br>a)
| |
| <br>b)
| |
| <br>c)
| |
| ===Ejercicio 07.10:===
| |
| '''HECHO EN CLASE, EL QUE PUEDA SUBALO (por favor)'''
| |
| | |
| ===Ejercicio 07.11:===
| |
| ===Ejercicio 07.12:===
| |
| ===Ejercicio 07.13:===
| |
| ===Ejercicio 07.14:===
| |
| <br>a)
| |
| <br>b)
| |
| | |
| ==PERT==
| |
| | |
| ===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 16:== |
| <br>a)
| | ==Ejercicio 17:== |
| <br>b)
| | ==Ejercicio 18:== |
| | | ==Ejercicio 19:== |
| [[Category: Prácticas]]
| | ==Ejercicio 20:== |