• Author / Uploaded
• ToXiC GoLDeN - Android Gaming

Citation preview

Segundo examen parcial - Fundamentos de an´alisis y dise˜no de algoritmos Duraci´on: 2 horas Carlos Andres Delgado S, Ing 17 de Junio 2017 Nombre: C´ odigo:

1.

Estructuras de datos

*

bote. A continuaci´on un ejemplo con 4 embarcaderos, se quiere ir de 1 a 4. [30 puntos]

1 2 3

2 10 -

3 40 20 -

4 100 80 5

1. (10 puntos) En el procedimiento Build-Heap, se construye el mont´ıculo, en un ciclo desde length[A]/2 hasta 1 de manera creciente. Esto es La soluci´on ´optima en este caso es tomar 1 a 2 (costo un capricho, pues de igual forma, el mont´ıculo puede ser construido, si el ciclo fuese desde 1 hasta 10), 2 a 3 (costo 20), 3 a 4 (Costo 5) para un costo total lenght[A]/2, aplicando Heapify en cada iteraci´on. de 35. Indique si es verdadero o falso, justifique su afirmaci´ on. 2.2. Problema del cambio de monedas 2. (10 puntos) Si se deseara que el algoritmo HeapUsted se encuentra administrando un peque˜ no neSoft ordenara descendentemente, es suficiente con gocio ubicado en la ciudad de Tul´ ua. Las personas le la siguiente modificaci´ on. compran productos y al momento de pagar usted entrega una devuelta en monedas. Se desea encontrar un H e a p S o f t D e s c (A) B u i l d−Heap (A) algoritmo que minimice el n´ umero de monedas que se f o r i =2 t o n−1 retornan. El problema se puede describir as´ı: H e a p i f y (A, i ) Tiene un valor num´erico entero a devolver A

Indique si es verdadero o falso, justifique su afirmaci´ on.

Tiene un conjunto de monedas B = {b1 , b2 , ..., bn }

3. (10 puntos) ¿C´ omo se puede implementar una cola utilizando pilas? Analice las complejidades de las operaciones.

2. 2.1.

Se busca encontrar el subconjunto de monedas Bs = {bi , .., bj , ..., bn } de tal forma su suma sea igual A y el tama˜ no de Bs sea el menor posible. Ejemplo:

Programaci´ on din´ amica y voraz [70 puntos]

A = 50

Problema del viaje m´ as barato

B = {10, 10, 20, 30, 10, 20}

Sobre el r´ıo Cauca hay n embarcaderos. En cada uno de ellos se puede alquilar un bote que permite ir a cualquier otro embarcadero r´ıo abajo (es imposible ir r´ıo arriba). Existe una tabla de tarifas que indica el coste del viaje del embarcadero i al j para cualquier embarcadero de partida i y cualquier embarcadero de llegada j m´ as abajo en el r´ıo i < j. Puede suceder que un viaje de i a j sea m´ as caro que una sucesi´ on de viajes m´as cortos, en cuyo caso se tomar´ıa un primer bote hasta un embarcadero k y un segundo bote para continuar a partir de k. No hay coste adicional por cambiar de

La soluci´on ´optima a este problema es Bs = {20, 30} ya que es el subconjunto de menor tama˜ no que suma 50

2.3.

Preguntas

Para cada uno de los problemas anteriores responda: 1. (4 puntos) ¿Cual es la complejidad de la soluci´ on ingenua? Justifique.

* [email protected]

1

2. Cocinemos una deliciosa soluci´ on din´ amica: a) (9 puntos) Paso 1: Caracterice la soluci´on optima. Identifique si el problema se puede solucionar mediante divide y vencer´as. Observe si existe solapamiento de problemas y s´ı una soluci´ on optima esta compuesta por soluciones ´ optimas de los subproblemas. b) (7 puntos) Paso 2: Defina recursivamente el valor de una soluci´ on ´ optima. Identifique la estructura de memorizaci´ on, que significa cada una de sus posiciones y c´ omo se calcula cada una. Justifique formalmente. c) (7 puntos) Pasos 3 y 4: Muestre c´omo se calcula el valor de la soluci´ on optima de forma Bottom-up. 3. (8 puntos) A partir de la caracterizaci´ on realizada dise˜ ne una soluci´ on voraz al problema. Justifique formalmente.

¡Exitos!

2