Skyline en Java

Memoria de la práctica de Programación III
Informática Técnica de Gestión
Curso 2011 - 2012
UNED
Centro Asociado Las Tablas

Índice
1. Enunciado de la práctica
2. Respuesta a las cuestiones planteadas.
2.1. Descripción del esquema algorítmico utilizado.
2.1.1. Ordenación por fusión (mergesort).
2.1.2. Ordenación rápida (quicksort).
2.2. Justificación del algoritmo utilizado
2.3.Aplicación al problema
2.3.1. Seguimiento del algoritmo recursivo.
2.4. Datos de prueba utilizados, y resultados obtenidos con ellos.
3. Ejemplos de ejecución para distintos tamaños del problema.
4. Estudio del coste del algoritmo.
5. Listado del código fuente

1. Enunciado de la práctica: Skyline de una ciudad
El problema consiste en calcular la línea de horizonte de la ciudad, en forma deuna secuencia de puntos sobre el plano. Sobre una ciudad se alzan los edificios
dibujando una línea de horizonte (conocida como "skyline"). Supongamos una
ciudad representada por un conjunto de edificios C = {e1, e2,..., en} y cada
edificio representado por un rectángulo sobre un eje de coordenadas.
El fichero de datos de entrada consta de una línea por cada edificio de la ciudad.
La entradatermina cuando se llega al final del fichero. Cada edificio se describe
por tres valores enteros: x1, x2, h. Los valores x1 y x2 representan las posiciones
inicial y final del edificio sobre el eje x. El valor h representa la altura.
Por ejemplo, para los 6 edificios de la ciudad ejemplo de este enunciado el fichero
de entrada contendría:
134
297
4 12 4
689
11 13 6
14 15 2
Y larepresentación gráfica es:

La solución al problema planteado consiste en una secuencia de pares (x, y),
donde x indica la posición de la coordenada x en la que se produce en cambio de
altura, e y la nueva altura.

La solución al problema se representa gráficamente con la siguiente figura:

2. Respuesta a las cuestiones planteadas
2.1. Descripción del esquema algorítmico utilizado
Elalgoritmo utilizado para la resolución del problema es del tipo Divide y
Vencerás. La estrategia que sigue esta técnica algorítmica consiste en
descomponer un problema en subproblemas del mismo tipo disminuyendo de esta
manera la complejidad del problema. Estos subproblemas se pueden resolver
después de forma similar.
Los algoritmos de este tipo suelen aceptar soluciones del tipo recursivo, aunque enalgunos casos, cuando el número de subproblemas es pequeño e independiente
del caso particular, se pueden aplicar bucles iterativos. En estos casos en los que
el número de subproblemas es muy pequeño divide y vencerás se llama reducción
o simplificación.
Para que resulte interesante utilizar divide y vencerás se deben dar una serie de
condiciones: El problema se tiene que poder descomponeren subproblemas, y
estos se pueden recomponer de forma eficiente. Los ejemplares deben tener un
tamaño aproximado. Y la elección del umbral, es decir, hasta cuando se tiene que
aplicar el algoritmo recursivo y cuando el básico, que debe tomarse
cuidadosamente, ya que puede disparar los tiempos de ejecución del algoritmo
debido a un aumento muy grande la constante oculta.
El valor óptimo parael umbral depende en general no sólo del algoritmo en
cuestión, sino también de la implementación particular. La selección del umbral se
puede realizar de varias maneras:
 Empíricamente, variando el valor del umbral y el tamaño de los casos que
se prueban, y tomando los tiempos de cada implementación.
 Teóricamente, que puede ser imposible ya que el umbral óptimo puede
variar según laimplementación.
 O con un enfoque hibrido, con el que primero se deducen teóricamente las
ecuaciones de recurrencia, y luego se buscan empíricamente los valores de
las constantes que se utilizan en las ecuaciones de la implementación que
se esté usando.
El esquema general del algoritmo divide y vencerás es el siguiente:
fun divide-y-vencerás (problema)
si trivial (problema) entonces
dev...