coleccion prob 1






COLECCIÓN DE PROBLEMAS
DE
Introducción a los Esquemas Algorítmicos









María Teresa Abad Soriano
Conrado Martínez Parra

Febrero/2002
Departamento L.S.I.-U.P.C.



SECCIONES

I. DIVIDE Y VENCERÁS
2. GRAFOS
III. VORACES
IV. VUELTA ATRÁS y RAMIFICACIÓN Y PODA
V. MISCELÁNEA



Los problemas que vienen a continuación aparecen en una sola sección, pero eso no significa que la única forma deresolverlos, ni tan siquiera la mejor, sea la que corresponde al tema en que aparecen incluidos. El propósito de su ubicación es que no sea inmediato asignar un esquema para su resolución, ¡ es necesario pensar!


I. DIVIDE Y VENCERÁS


I.1. Dissenyar un algorisme de recerca ternaria en un vector. La idea és la següent: partir el vector en tres parts i activar la funció recursivament sobreles parts del vector que calgui. Analitzar el cost de l'algorisme i comparar-lo amb el de recerca binària.

I.2. Donats n valors reals (v1,…,vn) dissenyar un algorisme que calculi quant val la diferència d entre els dos valors més propers:

d = min | vi - vj |
1i, j  n , i  j
Suggeriment : Feu servir l'algorisme de partició delquicksort.

I.3. Sea a[1..n], n1, un vector de enteros diferentes y ordenados crecientemente, tal que algunos de los valores pueden ser negativos. Diseñar un algoritmo que devuelva un índice natural k, 1 k  n, tal que a[k]=k, siempre que tal índice exista. El coste del algoritmo debe ser O(log n) en el caso peor.
Se pide diseñar el algoritmo dando todo lujo de detalles. Justificar sucorrección y el coste.
Repetir el problema pero para un vector de n enteros posiblemente repetidos y ordenado decrecientemente.

I.4. Dada la localización exacta y la altura de varios edificios rectangulares de la ciudad, obtener la skyline, linea de recorte contra el cielo, que producen todos los edificios eliminando las líneas ocultas. Ejemplo : La entrada es una secuencia de edificios y un edificiose caracteriza por una tripleta de valores (xmin,xmax,h).
Una posible secuencia de entrada para los edificios de la siguiente figura podría ser : (7,10,3), (9,12,7), (1,4,10), (3,8,5) y (11,13,10).

Y ésta es la representación de la skyline de la salida que se debe producir :

Su secuencia asociada es : (1,4,10), (4,8,5),( 8,9,3), (9,11,7) y(11,13,10)

I.5. Se está jugando un torneo entre n jugadores. Cada jugador juega una vez contra los n-1 jugadores restantes ( es un round-robin ). No hay empates y los resultados de los partidos se anotan en una matriz. En general no se pueden ordenar los jugadores porque falla la transitividad, es decir, A le gana a B, B le gana a C pero C le gana a A. Estamos interesados en un orden más débil quedefinimos de la siguiente forma : en la secuencia ordenada que se obtiene P1,P2,..,Pn se cumple que P1 le ha ganado a P2, P2 le ha ganado a P3, etc. y Pn-1 le ha ganado a Pn. Diseñar un algoritmo que produzca esta secuencia ordenada con un coste de O(nlog n). La entrada del algoritmo es la matriz de resultados y el coste de acceder a una posición de la matriz es constante.

I.6. Sea T un árbol binariocompleto de altura h y n=2h-1 vértices. Queremos encajar el árbol T en un plano de la siguiente manera : A cada vértice le corresponde un único punto en el plano, vértices adyacentes están conectados por lineas rectas ( paralelas al eje x o paralelas al eje y ) y no pueden intersectar dos líneas. El problema general es encontrar el rectángulo de área mínima que contenga el árbol. Por ejemplo : ungrafo de k vértices ( k=4 en la figura ) que forma una secuencia :

, podría ser encajado en un rectángulo de área 2(k+1). Ver en la figura el encaje con k=4.

Encajar grafos en el plano de esta forma es un problema importante en el diseño de chips, sobre todo en VLSI. Diseñar un algoritmo que te indique como encajar el...