Div y Conquista: Contando Inversiones, Puntos en el Plano, Karatsuba & Puntos Extremos en Polígonos Flashcards
Explique el Problema de Contar Inversiones
Sean:
- Un conjunto de
nelementos - Dos listas ordenadas de los
nelementos
Queremos tener una medida de semejanza / diferencia entre las dos listas.
Contar Inversiones: Explique el concepto de Diferencias entre las Preferencias
Llamaremos A y B a las listas de preferencias.
Utilizaremos el orden de aparición de los elementos de A para identificar las diferencias: 1, 2, ... , n.
Por otro lado estará B, que posiblemente estará “fuera de órden”: 2, 1, 5, ... , n.
Si B está en orden, se dice que representa el mismo orden de preferencia que A.
Explique qué se quiere saber en el problema de Contar Inversiones
Queremos saber qué tan lejos está B de estar ordenada de forma ascendente.
Si bi < b(i + 1) para todo i, entonces A = B.
Contar Inversiones: ¿En qué condiciones dos elementos están invertidos?
Dos elementos bi, bj con i < j están invertidos si bi > bj.
Contar Inversiones: ¿Qué complejidad tiene calcular la cantidad de inversiones con fuerza bruta?
Con fuerza bruta, calcular la cantidad de inversiones es O(n^2), porque se compara cada posición con todas las siguientes.
Contar Inversiones: ¿Cuál es la forma óptima de contar la cantidad de inversiones entre A y B?
La forma óptima es usando un merge sort, que alamacena la cantidad de inversiones necesarias para ordenar la lista B.
Explique el pseudocódigo para contar inversiones con Merge Sort
El código tiene dos partes:
ordenar_contarmerge_contar- Para la función de
ordenar_contar, tenemos:
a. Sea L el arreglo con los elementos de B b. L1 = primer mitad del arreglo L a procesar c. L2 = segunda mitad del arreglo L a procesar d. Llamar a la función `ordenar_contar` para L1. Devuelve r1 (#inversiones) y L1_ord, L1 ordenado. e. Llamar a la función `ordenar_contar` para L2. Devuelve r2 (#inversiones) y L2_ord, L2 ordenado. f. Llamar a la función `merge_contar` para L1_ord y L2_ord. Devuelve r (#inv) y L (ordenado). g. Devolver (r1+r2+r, L)
- Para la función de
merge_contar, tenemos:
a. Un contador de inversiones y L una lista vacía
b. Dos contadores i y j de posición para la lista A y B
c. Mientras i < |A| y j < |B|:
a = A en posición i
b = B en posición j
Si a > b:
Guardar elemento a en la posición i+j de L
i ++
De lo contrario:
Guardar el elemento b en la posición i+j
j++
inversiones += |A| - i
d. Para los elementos entre i y |A| - 1: agregarlos a L[i+j] e inversiones +=|B|.
e. Para los elementos entre j y |B| - 1: agregarlos a L[i+j].
f. Retornar la cantidad de inversiones y la lista L
¿Qué complejidad tiene Contar Inversiones con Merge Sort?
Cada problema de n elementos se deivide en 2 subproblemas de n/2 elementos.
- La unión de los resultados se construye recorriendo los
nelementos => O(n).
=> La relación de recurrencia es:
T(n) = 2 T(n/2) + O(n)
Usando el teorema maestro, nos queda T(n) = O(n logn)
Explique el problema de Puntos Más Cercanos en el Plano
Sean:
- P un conjunto de ´n´ puntos en el plano
-
d(p1,p2)la función distancia entrep1yp2. - Queremos encontrar los puntos más cercanos en P.
Puntos Más Cercanos en el Plano: ¿Cuál es la complejidad por fuerza bruta?
Si quisiéramos solucionar esto por fuerza bruta, calcularíamos la distancia entre cada punto y el resto de ellos, y nos quedaríamos con los dos de menor distancia.
Teniendo n puntos, la complejidad es O(n^2).
Puntos Más Cercanos en el Plano: ¿Cuáles son los preliminares a tener en cuenta?
Asumiremos:
- No existen puntos repetidos o que compartan coordenadas en
xoy. Cada apunto es único. - Existe
Px, que almacena los puntos ordenados de acuerdo a la coordenadax; yPy, para hacer lo mismo con respecto a la coordenaday.
Puntos Más Cercanos en el Plano: Explique la división en subproblemas.
Vamos a llamar Q al set de puntos que se encuentran en la mitad izquierda del eje x, y R al set de puntos que se encuentran en la mitad derecha.
- Para cada Q, calcularemos Qx y Qy.
- Para cada R, calcularemos Rx y Ry.
- Para cada punto q en Q y r en R, almacenaremos en qué posición aparece en Qx, Qy y Rx, Ry.
Esto podemos hacerlo en O(n) usando P, Px y Py.
Puntos Más Cercanos en el Plano: ¿Cómo se resuelve de forma recursiva? ¿Cuál es la complejidad? ¿Qué posible problema existe?
El problema base es un set de 2 o 3 puntos.
- Vamos a subdividir los problemas en 2 partes.
- Vamos a juntar los problemas comparando los pares de puntos retornados por cada subproblema, y quedándonos con el que tenga menor distancia.
La complejidad es de O(n logn).
Un posible problema es que la distancia mínima podría darse entre dos puntos de distintos espacios. Para esto debemos comparar los puntos de un lado con los del otro, lo cual nos da una complejidad de O(n^2), que es igual que la complejidad en fuerza bruta.
Puntos Más Cercanos en el Plano: Explique la Solución Eficiente con División y Conquista
Siendo n la cantidad de elementos, creamos Q con puntos de P de 1 hasta n/2 y R con puntos de P desde n/2 a n
- Llamamos
x*a la coordenada más a la derecha en Q. - Llamamos L a la línea vertical en x*, tal que L separa a Q de R.
- Vemos que si la distancia mínima está entre un punto entre Q y R, entonces tiene que ser menor a δ.
δ = min (δq, δr). Ambos δq y δr son la distancia más chica entre dos puntos, en cada parte Q y R.
- Nos interesa conocer qué puntos S están a una distancia menor a δ de L. Podemos obtenerlos recorriendo P en O(n).
- Subdividimos el espacio en celdas de
δ/2 x δ/2, tal que sólo puede existir un punto o ninguno en cada celda. - Como cada punto de S está en una celda, podemos comparar cada punto únicamente con otros puntos de S que estén en celdas cercanas. Recorriendo de menor a mayor en orden del eje y, comparo únicamente con las celdas que están hasta 3 filas más arriba que la actual (15 celdas en total).
Este proceso es O(n), en vez de ser un O(n^2). - Una vez que obtenemos el par de puntos del conjunto S que está a menor distancia, comparamos con δ:
a. Si es menor, devolvemos ese par de puntos.
b. Si no, devolvemos el mínimo entre δq y δr. - Se sigue de forma recursiva hasta que se alcanza el nivel más alto y se devuelve el par de puntos con menor δ para todo el plano.
Karatsuba: Explique el problema
Sean X e Y números enteros de n bits cada uno, queremos calcular su multiplicación. La idea es mejorar la complejidad con el método tradicional (multiplicación bit a bit), que es O(n^2).
Karatsuba: ¿Cómo se mejora la complejidad?
La idea es dividir los bits en 2 partes. Se representan de la siguiente forma:
X = x1 * 2^(n/2) + x0 Y = y1 * 2 ^(n/2) + y0
De esta forma, al querer operar X * Y, nos queda la distributiva de ambos:
(x1 * 2^(n/2) + x0) * (y1 * 2^(n/2) + y0) = x1.y1 * 2^n + (x0.y1+x1.y0) * 2^(n/2) + x0.y0
Esta multiplicación se puede realizar recursivamente hasta que sea de 1 a 1 bits.
Además, todos los x*y que ya calculé puedo guardarlos, no hace falta volver a calcularlos. Por lo que como hay cálculos que nos ahorramos, la relación de recurrencia es:
T(n) = 3T(n/2) + cn
Que es O(n^1.59), aunque el algoritmo terminó evolucionando y su complejidad llegó a probarse poder ser O(n logn).
Puntos Extremos en polígonos: Explique el problema
Sea un polígono de n vértices V = (v0, ..., vn) con vn = v0 en orden contrareloj, queremos determinar el vértice extremo (mayor o menor) a un eje u.
Puntos Extremos en polígonos: Explicar la solución por fuerza bruta y su complejidad
- Se realiza una proyección ortogonal a una recta
u. - Se verifica si es mayor al mayor de los anteriores.
ò - Se verifica si es menor al menor de los anteriores.
La complejidad es O(n).
Puntos Extremos en polígonos: ¿Se puede mejorar la complejidad de fuerza bruta?
Se puede, pero sólo si el polígono es convexo. Es decir, si sus ángulos miden como mucho 180 grados. Además, cualquier línea perpendicular L debe cortar como máximo 2 veces al polígono (tiene que ser más bien “redondito” digamos)
Puntos Extremos en polígonos: Explique la nomenclatura de los vértices
-
eies el iésimo segmento del vérticeviavi+1. -
eVies el vector que va de Vi a Vi+1
Si eVi mira para arriba en la proyección, es positivo. Si mira para abajo, es negativo.
Puntos Extremos en polígonos: Explique la idea general del problema.
Supongamos que sabemos que el vértice máximo se encuentra en el polígono entre los vértices a y b.
Elegimos un vértice c entre a y b.
Creamos dos líneas poligonales: una [a, c] y otra [c, b]. El máximo tiene que estar en alguno de los dos segmentos.
Analizamos el vector Va y Vc:
Para Va+
- Si Va+ y Vc -, me quedo con el tramo [a, c]
- Si Va+ y Vc+, con c arriba de a: [c, b]
- Si Va+ y Vc+, con a arriba de c: [a,c]
Para Va-
- Si Va- y Vc+, me quedo con el tramo [c,b]
- Si Va- y Vc-, con c arriba de a: [a,c]
- Si Va- y Vc-, con a arriba de c: [c, b]
Puntos Extremos en polígonos: Explique la solución y su complejidad.
Iteramos dividiendo el problema en 2 líneas poligonales.
- En el caso de que nos queden 3, comparamos 1:1 y obtenemos el máximo.
- De lo contrario, determinamos cuál de los casos de Va y Vc aplica.
- Finalmente, se actualizan a, b, y c según corresponda.
Complejidad:
- Reducimos a la mitad la cantidad de vértices
- Convertimos cada uno en un nuevo subproblema (1 llamada recursiva)
- Realizamos operaciones O(1).
=> La relación de recurrencia es:
T(n) = 1 * T(n/2) + c
Por lo que la complejidad nos queda: O(logn), por el teorema maestro.
Resuelva:
El orden de un listado en el ranking actual es:[ A, 3 | B, 4 | C, 2 | D, 8 | E, 6 | F, 5 ]
a. ¿Cómo se puede resolver por fuerza bruta? Analizar complejidad temporal / espacial
b. Proponer una solución, usando división y conquista.
c. Dar el pseudocódigo para el punto b.
d. Realice el análisis de la complejidad temporal por el teorema maestro.
e. Realice el análisis de la complejidad temporal desarrollando la recurrencia.
f. ¿Cuál es la complejidad espacial?
a. Para cada elemento, se recorre comparando con los posteriores. Si la posición del elemento es menor a la del actual, se suma 1 a las inversiones. La complejidad es O(n^2) y la espacial es O(n).
b. Se puede utilizar Mergesort, con un contador para inversiones.
Ordenar-Contar(L): Si |L|=1 Retornar (0,L) // No hay inversiones Sino Sea A los techo(n/2) primeros elementos de L Sea B los piso(n/2) restantes elementos de L (ra,A) = Ordenar-Contar(A) (rb,B) = Ordenar-Contar(B) (r,L) = Merge-Contar(A,B) Retornar (r+ra+rb,L) ----- Merge-Contar(A,B) Sea L lista inv = 0 i = 0, j = 0 // posición en la lista A y B Mientras i < |A| y j < |B|: a = A[i], b = B[j] Si a > b L[i+j] = a , i++ Sino L[i+j] = b , j++ inv =+ (|A|- i) Desde i hasta |A|-1: L[i+j] = A[i] inv += |B| Desde j hasta |B|-1 L[i+j] = B[i] Retornar (inv,L)
d. Solución: Θ(n logn)
e. Cada nivel consume cn operaciones. Tenemos logn niveles, por lo que se divide el problema una log2n cantidad de veces para pasar de n a 1.
El tiempo total es de cn . logn, por lo que la complejidad es O(n logn).
f. O(n) para guardar los n elementos.
Puntos más cercanos en el plano: Resuelva
p1 = 1, 4
p2 = 2, 8
p3 = 4, 9
p4 = 3, 3
p5 = 6, 10
p6 = 5, 6
p7 = 8, 2
p8 = 9, 7
p9 = 7, 1
p10 = 10, 5
d_min = p9, p7
δmin = 1.41
Resuelva
Se cuenta con un vector de n posiciones en el que se encuentran algunos de los primeros “m” números naturales, ordenados en forma creciente (m >= n).
En el vector no hay números repetidos.
Se desea obtener el menor número no incluído.
Ejemplo:
[ 1, 2, 5, 10]
a. Explicar la complejidad por fuerza bruta.
b. Proponer una solución por div y conquista, y explicar la complejidad por división y conquista. Dar el pseudocódigo.
c. Resolver para [1, 2, 3, 4, 5, 8, 10]
a. Por fuerza bruta, es O(n) temporal y O(n) espacial.
b. Propuesta:
Funcion encontrar_faltante
Parámetros iniciales: array = A índice = 0 1. dividir el array en A1 y A2. El último elemento de A1 se llama `Am`. 2. Comparar `m` y `m+1` contra `Am` y `Am+1`. 3. Si `m != Am`, devolver `encontrar_faltante(A1, index)` 4. Si `m+1 != Am+1`, devolver m+1 5. De lo contrario, devolver `encontrar_faltante(A2,m)`
c. 3 iteraciones:
[1, 2, 3, 4, 5, 8, 10]
[5, 8, 10]
[5, 8] => faltante: 6
Puntos Extremos en Polígonos:
Encontrar el punto extremo máximo y mínimo para el polígono formado por los siguientes vértices:
x, y:
1,2
2,3
3, 3.5
4, 3
4, 1
3, 0
1.5, 0.5
Máximo: 3, 3.5
Minimo: 3, 0
