Examen Parcialito - 75.41. Algoritmos y Programación II - 23/11/2012

Cátedra: Wachenchauzer
Fecha: Primera Oportunidad - (Segundo Cuatrimestre) 2012
Día: 23/11/2012

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.

Un camión debe viajar desde una ciudad a otra deteniéndose a cargar combustible cuando sea necesario. El tanque de combustible le permite viajar K kilómetros. Las estaciones se encuentran distribuidas a lo largo de la ruta siendo d_i la distancia desde la estación i-1 a la estación i.
a) Implementar un algoritmo que decida en qué estaciones debe cargar combustible, de manera que se detenga la menor cantidad de veces posible.
b) Indique la estrategia utilizada.
c) ¿Cuál es la complejidad algorítmica?

a) Muestre los pasos de ejecución del algoritmo heapsort para ordenar el siguiente arreglo: [8, 64, 4, 2, 32, 16]
b) En un max-heap imlementado sobre un arreglo de n posiciones, ¿entre qué posiciones se puede encontrar el menor elemento?

a) ¿Qué condiciones debe cumplir un problema para poder resolverlo mediante Programación Dinámica? ¿Qué desventaja tiene esta técnica en general?
b) ¿Bajo qué condiciones un algoritmo Greedy no encuentra la solución óptima a un problema? De un ejemplo.