Examen Parcialito - 75.41. Algoritmos y Programación II - 07/12/2012
Cátedra: Wachenchauzer
Fecha: Primera Oportunidad - (Primer Cuatrimestre) 2012
Día: 07/12/2012
Enunciado
Resolvé los siguientes problemas en forma clara y legible, respetando sangrías e incluyendo la documentación necesaria. Si te parece que los comentarios no son suficientemente explicativos, podés agregar una descripción del funcionamiento del código. Podés escribir tantas funciones auxiliares como creas necesarias.
Punto I
Implementar una función, que dado un grafo G, un vértice V y un número natural N, devuelva una lista con todos los vértices del grafo G que se encuentren a N pasos del vértice V. (Puede implementarse en pseudocódigo). ¿De qué orden es la solución implementada? Haga una mínima explicación de la implementación, si cree que el código no es suficientemente claro.
Punto II
a) ¿Para qué se utilizan los algoritmos Prim y Kruskal? ¿En qué se diferencian?
b) ¿Cuál es el orden de cada uno? Justificar.
c) Aplicar alguno de los dos (a elección) al siguiente grafo:
| Nodo | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 7 | 0 | 5 | 0 |
| B | 7 | 0 | 8 | 9 | 7 |
| C | 0 | 8 | 0 | 0 | 5 |
| D | 5 | 9 | 0 | 0 | 15 |
| E | 0 | 7 | 5 | 15 | 0 |
Punto III
a) Describa brevemente la utilidad de la función heurística en el algoritmo A*.
b) ¿Qué significado tiene, en el algoritmo de Dijkstra, que un vértice haya quedado con distancia mínima de valor infinito?
