Grafos

Ejercicio 1. Divide y vencer´s
a
[ITIS/ITIG, Septiembre 2008] Se dispone de un vector de secuencias de
v´
ıdeo video[1..N] en el que cada elemento contiene dos atributos: duraci´n
o
(en segundos) y secuencia (contiene el fragmento de v´
ıdeo). Se quiere
ordenar este vector en orden creciente de duraci´n.
o
Sin embargo, no es posible utilizar directamente uno de los algoritmos deordenaci´n conocidos, ya que las secuencias de v´
o
ıdeo almacenadas en el
atributo secuencia ocupan gran cantidad de memoria y se quiere evitar
mover estos datos de forma innecesaria durante el proceso de ordenaci´n.
o
Dise˜a un algoritmo basado en la t´cnica Divide y Vencer´s que
n
e
a
proporcione un vector ordenado de secuencias de v´
ıdeo, de forma que
realice una sola copia de los datoscontenidos en el atributo secuencia de
cada elemento del vector de origen video[1..N] al vector ordenado. Detalla
lo siguiente:
(0,5 puntos) las estructuras de datos utilizadas
(2 puntos) el c´digo completo del algoritmo
o
Yolanda Garc´ Jes´s Correas (DSIC - UCM)
ıa,
u

ucm-seal upm-seal unm-seal

1 / 21

Soluci´n ejercicio 1
o

proc videos(video[1..n],sol[1..n])
crear vp[1..n]//vp[i] tiene dos atributos: duracion y la posicion en la que se encuentra en video[i]

desde i ← 1 hasta n hacer
vp[i].duracion ← video[i].duracion ; vp[i].pos ← i
fin desde
mergesort(vp)
desde i ← 1 hasta n hacer
sol[i] ← video[vp[i].pos]
fin desde
fin proc

Yolanda Garc´ Jes´s Correas (DSIC - UCM)
ıa,
u

ucm-seal upm-seal unm-seal

2 / 21

Soluci´n ejercicio 1 (Cont.)
oproc mergesort(vp[1..n])
h ← n/2 ; m ← n-h
crear U[1..h], V[1..m]
// U[ ] y V[ ] tienen la misma estructura que vp[ ]

si n>1 entonces
U[1..h] ← vp[1..h]
V[1..m] ← vp[h+1..n]
mergesort(U)
mergesort(V)
combinar(U,V,S)
fin si
fin proc

Yolanda Garc´ Jes´s Correas (DSIC - UCM)
ıa,
u

ucm-seal upm-seal unm-seal

3 / 21

Soluci´n ejercicio 1 (Cont.)
o
proccombinar(U[1..h],V[1..m],S[1..h+m])
i←1;j←1;k←1
mientras i ≤ h Y j ≤ m hacer
si U[i].duracion < V[j].duracion entonces
S[k] ← U[i] ; i ← i+1
si no
S[k] ← V[j] ; j ← j+1
fin si
k ← k+1
fin mientras
si i>h entonces S[k..h+m] ← V[j..m]
si no S[k..h+m] ← U[i..h]
fin proc

Yolanda Garc´ Jes´s Correas (DSIC - UCM)
ıa,
u

ucm-seal upm-seal unm-seal

4 / 21

Ejercicio 2. Divide y vencer´s
a
[ITIS/ITIG, Junio2008] Un mont´
ıculo ascendente es un ´rbol binario en el que cada
a
nodo es mayor que sus hijos (si existen). Consideremos un mont´
ıculo de m nodos con
valores positivos implementado mediante un vector de la siguiente manera. Dado un
nodo que se encuentra en la posici´n i del vector:
o
El hijo izquierdo (si existe) est´ en la posici´n 2i.
a
o
El hijo derecho (si existe) est´ en laposici´n 2i + 1.
a
o
Si la posici´n i corresponde a un hijo inexistente, esta posici´n contiene el valor 0.
o
o
Dise˜a una funci´n utilizando la t´cnica Divide y Vencer´s que determine si un ´rbol
n
o
e
a
a
binario implementado mediante un array de P elementos contiene un mont´
ıculo
ascendente.
8
Ejemplo de implementaci´n de un ´rbol binario mediante un
o
a
array:

8

3

45

Array:
2 0 0

Yolanda Garc´ Jes´s Correas (DSIC - UCM)
ıa,
u

3

5
0

0

7

4

2

7

ucm-seal upm-seal unm-seal

7

7
5 / 21

Soluci´n ejercicio 2
o
fun chequear monticulo(i,v[1..P])
monticulo ← cierto
si 2i ≤ P entonces
si (v[i]>0 ∧ v[i]>v[2i]) ∨ (v[i]=0 ∧ v[2i]=0) entonces
monticulo ← chequear monticulo(2i,v)
si no
monticulo ← falso
fin si
simonticulo ∧ 2i+1 ≤ P entonces
si (v[i]>0 ∧ v[i]>v[2i+1]) ∨ (v[i]=0 ∧ v[2i+1]=0) entonces
monticulo ← chequear monticulo(2i+1,v)
si no
monticulo ← falso
fin si
fin si
fin si
devolver monticulo
ucm-seal upm-seal
fin fun
Yolanda Garc´ Jes´s Correas (DSIC - UCM)
ıa,
u

unm-seal

6 / 21

Ejercicio 3. Divide y vencer´s
a
[ITIS/ITIG, Junio 2007] Dada una matriz cuadrada M, cuya dimensi´n es...