Cuestionario: Algoritmo Bron-Kerbosch y Paralelización en GPU

¿Qué representa V en la definición formal de un grafo G=(V,E)?. Conjunto de aristas. Conjunto de vértices. Conjunto de subgrafos. Conjunto de grafos.

¿Cuál es la complejidad de acceso a una arista usando una Matriz de Adyacencia?. O(1). O(V). O(E). O(grado(v)).

¿Qué es un Subgrafo Inducido?. Un grafo sin aristas. Un subgrafo creado eliminando vértices. Un subgrafo que conserva todas las aristas originales entre un subconjunto de vértices. Un grafo con un único vértice.

Según el documento, ¿qué tipo de subgrafos son importantes en GPU para evitar copiar subgrafos completos en memoria?. Subgrafos completos. Subgrafos disconexos. Partial induced subgraphs. Subgrafos unitarios.

¿Qué es un Maximal Clique?. El clique de mayor tamaño en el grafo. Un subgrafo completo que no puede extenderse añadiendo ningún vértice adyacente. Cualquier subgrafo completo. Un grafo con un solo vértice.

¿Cuál es la diferencia clave entre Maximal y Maximum Clique?. No hay diferencia, son sinónimos. Un Maximal Clique siempre es único, un Maximum Clique puede no serlo. Todo Maximum Clique es Maximal, pero no todo Maximal Clique es Maximum. Un Maximum Clique puede no ser un subgrafo completo.

¿Qué estrategia de búsqueda explora un camino hasta el fondo antes de retroceder?. BFS (Búsqueda en Anchura). DFS (Búsqueda en Profundidad). Backtracking. Prim's Algorithm.

¿Qué estrategia de búsqueda utiliza el algoritmo Bron-Kerbosch?. BFS. Dijkstra. Backtracking. A*.

En el algoritmo Bron-Kerbosch, ¿qué representa el conjunto P?. Vértices del clique en construcción. Vértices excluidos. Candidatos que pueden extender el clique actual. Vértices ya visitados.

¿Cuál es la condición de terminación para que R sea un Maximal Clique en Bron-Kerbosch?. P es vacío y X es vacío. P es vacío y X no es vacío. P no es vacío y X es vacío. P no es vacío y X no es vacío.

¿Qué técnica de optimización en Bron-Kerbosch reduce las ramas exploradas eligiendo un vértice pivote?. Degeneracy Ordering. Pivoting. Load Balancing. Worker Lists.

¿Qué garantiza el Degeneracy Ordering?. Encontrar el Maximum Clique. Reducir el número de vértices. Acotar el tamaño del conjunto P (candidatos). Evitar la recursión.

¿Cuál es el principal desafío en la paralelización GPU para la enumeración de cliques maximales?. La velocidad de los núcleos de la CPU. La falta de memoria RAM. El desbalance de carga (Load Imbalance). La complejidad de la definición de grafo.

¿Cómo se llama la estrategia para solucionar el Load Imbalance en GPU tomando dinámicamente trabajos disponibles cuando un bloque termina?. Pivoting. Degeneracy Ordering. Worker Lists. Maximal Clique Enumeration.

¿Qué métrica se utiliza para comparar el rendimiento entre CPU y GPU?. Load Imbalance. Speedup. Degeneracy. Clique Size.

En el contexto de Bron-Kerbosch, ¿qué representa 'd'?. El grado máximo del grafo (Delta). El número de vértices. La degeneracy del grafo. El tamaño del Maximum Clique.

Para grafos muy grandes, ¿qué estrategia permite que múltiples GPU trabajen simultáneamente?. Degeneracy Ordering. Worker Lists. Pivoting. Multi-GPU.

¿Cuándo se reporta un Maximal Clique en Bron-Kerbosch?. Cuando P no está vacío y X está vacío. Cuando P está vacío y X no está vacío. Cuando P está vacío y X está vacío simultáneamente. Cuando se alcanza el Maximum Clique.

¿Por qué DFS es preferido sobre BFS en Bron-Kerbosch?. BFS es más rápido. DFS consume menos memoria (O(profundidad) vs O(anchura)). BFS no puede encontrar cliques. DFS es más fácil de implementar.

En la paralelización GPU, ¿qué son los 'subárboles independientes'?. Partes del grafo que no tienen aristas entre sí. Subproblemas generados al fijar el primer vértice de la llamada raíz, que pueden ejecutarse en paralelo. Cliques que no comparten vértices. Ramas del árbol de búsqueda que no se solapan.

¿Qué problema resuelve la técnica de 'Pivoting' en el algoritmo Bron-Kerbosch?. El desbalance de carga. La alta complejidad de la degeneracy ordering. La exploración de ramas redundantes. El consumo excesivo de memoria.

¿Cuál es la complejidad temporal en el peor caso por llamada para Bron-Kerbosch con Degeneracy Ordering?. O(3^(Δ/3)). O(Δ). O(3^(d/3)). O(d).

En la Matriz de Adyacencia, ¿cuál es el espacio requerido para almacenar un grafo?. O(|V| + |E|). O(|V|^2). O(grado(v)). O(1).

¿Qué se busca en la Enumeración de Cliques Maximales (MCE)?. Solo el clique de mayor tamaño. Todos los cliques maximales del grafo. El camino más corto entre dos vértices. La conectividad del grafo.

En el contexto de Bron-Kerbosch, ¿qué representa el conjunto X?. Candidatos a extender el clique. Vértices del clique en construcción. Vértices que ya fueron procesados y no deben repetirse. Vértices excluidos del grafo.

¿Qué tipo de tareas son ideales para la paralelización en GPU?. Tareas con fuertes dependencias secuenciales. Tareas que requieren baja latencia. Tareas independientes que pueden ejecutarse simultáneamente. Tareas que necesitan un solo procesador potente.

En el ejemplo de 'Load Imbalance', ¿por qué el rendimiento cae?. Porque el subárbol A tarda mucho, mientras B y C terminan rápido. Porque la GPU tiene muy pocos núcleos. Porque el subárbol B es demasiado pequeño. Porque no se utilizan Worker Lists.

¿Qué significa que un clique sea 'maximal'?. Que es el de mayor tamaño. Que no se le puede añadir ningún otro vértice adyacente a todos sus miembros. Que es el único clique en el grafo. Que contiene todos los vértices del grafo.

¿Qué técnica se aplica en el 'Segundo Nivel de Paralelización'?. Utilizar un único GPU de forma más eficiente. Dividir los subproblemas generados por el primer vértice en nuevos trabajos independientes. Reducir la complejidad del algoritmo Bron-Kerbosch. Mejorar la eficiencia de la Matriz de Adyacencia.

La Lista de Adyacencia es más eficiente en memoria para grafos que son: Densos. Dispersos. Conectados. Complejos.

¿Qué representa Delta (Δ) en el análisis de complejidad?. La degeneracy del grafo. El número de vértices. El número de aristas. El máximo grado del grafo.

En Bron-Kerbosch, ¿qué función cumple la regla del pivote?. Aumentar el número de candidatos P. Reducir la cantidad de ramas a explorar. Garantizar que se encuentre el Maximum Clique. Simplificar la estructura del grafo.

¿Cuál es la principal ventaja de usar Worker Lists en lugar de una única Worklist compartida?. Mayor contención entre bloques. Menor escalabilidad. Menor contención y mayor escalabilidad. Implementación más simple.

Si el Tiempo_CPU = 200s y Tiempo_GPU = 40s, ¿cuál es el Speedup?. 0.2x. 5x. 160x. 240x.

¿Qué problema intenta solucionar la paralelización en GPU en el contexto de MCE?. La definición de clique. La lentitud de la CPU para procesar grandes grafos. El tamaño de los vértices. La complejidad de las aristas.

¿Qué se entiende por 'subgrafo completo' en la definición de clique?. Un grafo con el máximo número de vértices. Un grafo donde cada par de vértices está conectado por una arista. Un grafo con solo aristas. Un grafo sin aristas.

En el contexto del algoritmo Bron-Kerbosch, ¿qué representa N(v)?. El conjunto de vértices del grafo. El conjunto de aristas del grafo. El conjunto de vértices adyacentes a v (vecindad). El grado del vértice v.

¿Qué beneficio principal aporta el 'Pivoting' al algoritmo Bron-Kerbosch?. Reduce el espacio de memoria utilizado. Acelera el cálculo del grado de los vértices. Disminuye el número de llamadas recursivas. Simplifica la condición de terminación.

¿Qué es la 'degeneracy' (d) de un grafo?. El número total de vértices en el grafo. El máximo grado de cualquier vértice en el grafo. El mínimo valor k tal que todo subgrafo tiene al menos un vértice de grado ≤ k. El número de cliques maximales en el grafo.

Si un bloque GPU termina su tarea y hay más trabajos disponibles, ¿qué sucede para evitar el 'Load Imbalance'?. El bloque permanece ocioso. El bloque toma dinámicamente otro trabajo de la lista. Se detiene todo el proceso hasta que todos los bloques terminen. Se incrementa la velocidad del bloque ocioso.

¿Cuál es la relación entre 'd' (degeneracy) y 'Δ' (máximo grado)?. d > Δ siempre. d = Δ siempre. d ≤ Δ siempre. No hay relación entre d y Δ.

¿Qué representa la fórmula Speedup = Tiempo_CPU / Tiempo_GPU?. La complejidad del algoritmo. La memoria utilizada por la GPU. La mejora relativa en tiempo de ejecución de la GPU sobre la CPU. El número total de operaciones.

La enumeración de cliques maximales (MCE) es útil en: Optimización de rutas de vuelo. Detección de comunidades en bioinformática y redes sociales. Cálculo de integrales complejas. Simulación de fluidos.

¿Por qué la paralelización en GPU es efectiva para el problema de MCE?. Porque la GPU tiene menos núcleos pero más rápidos. Porque el algoritmo Bron-Kerbosch genera subproblemas independientes (subárboles). Porque la GPU utiliza el algoritmo BFS. Porque las GPU no sufren de 'Load Imbalance'.

¿Qué sucede si P = Ø y X ≠ Ø en la condición de terminación de Bron-Kerbosch?. Se reporta R como un Maximal Clique. R no es un Maximal Clique porque ya fue reportado (cubierto por X). Se reinicia la búsqueda. Se añade X a R.

¿Cuál es la complejidad de iterar sobre los vecinos de un vértice 'v' usando una Lista de Adyacencia?. O(1). O(V). O(E). O(grado(v)).

La técnica de 'Degeneracy Ordering' mejora la eficiencia al garantizar que: El número de vértices sea bajo. El grafo sea denso. El conjunto P (candidatos) se mantenga acotado. La matriz de adyacencia sea pequeña.

¿Cuál es la diferencia principal entre una Matriz de Adyacencia y una Lista de Adyacencia en términos de espacio?. Matriz usa O(V+E), Lista usa O(V^2). Matriz usa O(V^2), Lista usa O(V+E). Ambas usan O(V+E). Ambas usan O(V^2).

En el algoritmo Bron-Kerbosch, ¿qué se busca al aplicar 'Backtracking'?. Encontrar el camino más corto. Construir el clique paso a paso, deshaciendo elecciones si no llevan a una solución. Minimizar el uso de memoria. Aumentar la velocidad de procesamiento.