TP4

Punto 4: ir alternando entre uno al azar (que va a estar más o menos en el centro) y uno que esté más lejos → mientras más grado de entrada tenga algo, más conectado está con el resto (está aprox en el medio)

Final de práctica 2023

[10] Dada una matriz de nxn (matriz cuadrada) queremos resolver el problema del elemento mínimo en una cierta submatriz: RMQ(i1,j1,i2,j2) que nos tiene que devolver el elemento mínimo de dicha submatriz, las submatrices pueden no ser cuadradas. Le pedimos diseñar una solución que permita resolver las consultas en O(n) (ojo no es O(nxn)), para ello va a necesitar un cierto pre-procesamiento que va a tener que explicar e indicar el orden del mismo

Construcción de Fisher-Heun por cada fila de mi submatriz, entonces P va a ser O(n) y Q va a ser O(1). RMQ en cada fila, luego comparo los mínimos de todas las filas

→El tiempo de preprocesamiento de toda la matriz es O(n cuadrado)

[6] Dado el siguiente vector: [30 21 8 45 62 73 9 6 2 11 20 19] Usando bloques con b=3 y tablas dispersas tanto para el superbloque como para los bloques individuales le pedimos que muestre la tabla del superbloque y las tablas individuales de cada bloque, estas últimas tiene que construirlas usando el método de los cuatro rusos. Una vez construidas las estructuras indique cómo resuelve las consultas RMQ(1,7). RMQ(4,11)

En O(n) armamos el superbloque cada 3 bloques: [8, 45, 2, 11] que es B1, B2, B3, B4 (el B3 es isomorfo a B1)

Armamos la tabla dispersa del superbloque (con valores) → la cantidad de columnas es el logaritmo redondeado para arriba, en este caso tengo 4 elementos en el superbloque, por lo que le tomo logaritmo y me quedan 2 columnas:

i/l	L1	L2
0	8	8
1	45	2
2	2	2
3	11	-

Tabla dispersa de B1 y B3 (con índices)

i/l	L1	L2
0	0	1
1	1	2
2	2	-

Tabla dispersa del B2

i/l	L1	L2
0	0	0
1	1	1
2	2	-

Tabla dispersa del B4

i/l	L1	L2
0	0	0
1	1	2
2	2	-

Ahora las consultas:

RMQ(1,7) Tengo un superbloque entero, entonces tengo Min(min(B2), B1(1,2), B3(0,1)) → el mínimo de B2 es 45. El mínimo entre 1 y 2 del B1 es en el índice 1 (8), y entre 0 y 1 del B3 es el índice 1 (6) → Al final, el mínimo es 6

Lo de los 4 rusos era para demostrar que eran isomorfos (pero lo vimos a ojo)