¿Cuáles de las siguientes afirmaciones referidas a conceptos básicos generales sobre grafos son correctas? (Más de una puede ser correcta...)
Seleccione una o más de una: Dos nodos a y b de un grafo (dirigido o no) pueden tener varios caminos de distinta longitud que los unan. Un grafo puede tener nodos aislados: nodos que no tienen ningún arco incidente a él (ninguno de entrada y ninguno de
salida). Todo arco de un grafo, necesaria y obligatoriamente une dos nodos diferentes de ese grafo. Un grafo puede tener subgrafos no unidos entre sí por arcos que los conecten (o sea, un grafo puede tener dos o más
componentes conexas).
¿Cuál de las siguientes afirmaciones es FALSA respecto de los ciclos en un grafo?
Seleccione una: Un ciclo es un camino que parte de un nodo y lleva de vuelta al mismo nodo. Los ciclos no están permitidos en un grafo. Los ciclos pueden ser válidos o no, dependiendo del problema que se quiere resolver. Es válido que un ciclo conste de un único arco que permita vincular a un nodo consigo mismo.
Suponga que se desea modelar con un grafo la estructura del plan de estudios de una carrera universitaria. El equipo de trabajo ha decidido que los vértices del grafo representen asignaturas y los arcos representen restricciones de correlativas previas. Así, el arco (x, y) que parte de la asignatura x y llega a la y indica que para cursar y debe estar regularizada x. Lo anterior implica además que el grafo debe ser dirigido. El equipo de trabajo ha determinado además algunas restricciones obvias que deben controlarse y validarse en todo momento en el sistema de gestión del plan. Indique cuáles de las siguientes situaciones no serían aceptables en el grafo propuesto, y deberían ser evitadas por procesos de validación (aclaración: más de una puede ser seleccionada):
Seleccione una o más de una: Vértices a los que no llega ningún arco de entrada (aunque podrían tener arcos de salida). La ocurrencia de auto ciclos en cualquiera de sus vértices La ocurrencia de ciclos en general en el grafo. La ocurrencia de algún tipo de relación transitiva explícita, es decir, que existan al mismo tiempo los arcos (x, y), (y, z) y (x, z). Vértices aislados, es decir, vértices a los que no llega ningún arco de entrada y de los cuales tampoco hay arcos de salida.
¿En cuál de las siguientes situaciones no debería usar un grafo dirigido?
Seleccione una: Para modelar un plan de estudios de una carrera universitaria. Para modelar un ”sociograma”: un gráfico que expresa en qué forma un grupo de personas se relacionan entre sí. Para modelar un plano de rutas entre localidades o ciudades. Para modelar un sistema de cañerías que transportan líquidos desde una fuente hasta un destino.
¿En cuáles de las siguientes situaciones sería ideal un grafo no dirigido? (Más de una puede ser correcta...)
Seleccione una o más de una: Para modelar un ”sociograma”: un gráfico que expresa en qué forma un grupo de personas se relacionan entre sí Para modelar un plano de rutas entre localidades o ciudades. Para modelar un sistema de rutas aéreas entre distintos aeropuertos del mundo. Para modelar un plan de estudios de una carrera universitaria.
¿Cuáles de las siguientes expresan afirmaciones ciertas cuando se quiere implementar un grafo ponderado en forma matricial simple? (Más de una puede ser correcta...)
Seleccione una o más de una: Una manera recomendable de implementar un grafo ponderado en forma matricial, es hacer que cada casilla de matriz de
adyacencias apunte a un objeto que represente a un arco, y guardar en ese objeto todos los atributos que sean necesarios
para la representación del arco. El problema no existe: no hay manera de representar grafos ponderados en forma matricial. Si se almacena directamente el peso del arco en cada casillero, un problema posible es el de la ambigüedad del cero: no
sería posible distinguir si el cero es el peso de un arco, o el indicador de que el arco no existe. Si se almacena solo un entero para representar al arco y su peso, sería inviable representar arcos con pesos múltiples.
Un grafo reflexivo es un grafo dirigido en el cual se cumple que todo vértice está relacionado consigo mismo (es decir, todo vértice tiene un auto ciclo). Suponga un grafo G dirigido y reflexivo con n vértices, implementado en forma matricial y asumiendo que la matriz de adyacencias almacena valores boolean en forma directa. ¿Qué se puede afirmar que es verdadero respecto de la matriz de adyacencias de G?
Seleccione una: Todos los casilleros de la diagonal principal de la matriz de adyacencia valen True, pero no es obligatorio que sólo ellos puedan valer true. Todos los casilleros de la matriz de adyacencia valen True. Todos los casilleros del triángulo superior de la matriz de adyacencia valen True. Todos los casilleros de la diagonal principal de la matriz de adyacencia valen True, y sólo ellos pueden valer True.
Un grafo simétrico es un grafo dirigido en el cual se cumple que si existe el arco (x, y) entonces existe también el arco (y, x) (es decir, toda vez que existe un arco en un sentido, existe también el arco en sentido contrario). Suponga un grafo G dirigido y simétrico con n vértices, implementado en forma matricial y asumiendo que la matriz de adyacencias almacena valores boolean en forma directa. ¿Qué se puede afirmar que es verdadero respecto de la matriz de adyacencias de G?
Seleccione una: Todos los casilleros de la matriz son True o todos los casilleros son False. Todos los casilleros del triángulo inferior de la matriz de adyacencia valen True y los del triángulo superior valen False. La matriz es simétrica (o espejada) respecto de la diagonal principal: el valor en el casillero ady[x][y] siempre será igual al
valor en ady[y][x]. Todos los casilleros de la diagonal principal de la matriz de adyacencia valen True.
Un grafo transitivo es un grafo dirigido en el cual se cumple que cada vez que existen los arcos (x, y) e (y, z) entonces existe también el arco (x, z). Suponga un grafo G dirigido y transitivo con n vértices, implementado en forma matricial y asumiendo que la matriz de adyacencias almacena valores boolean en forma directa. ¿Qué se puede afirmar que es verdadero respecto de la matriz de adyacencias de G?
Seleccione una: Si el casillero ady[y][z] es True entonces el casillero ady[x][z] será también True, sin importar el valor de ady[x][y]. Si los casilleros ady[x][y] y ady[y][z] son False, entonces el casillero ady[x][z] será True. Si el casillero ady[x][y] es True entonces el casillero ady[x][z] será también True, sin importar el valor de ady[y][z]. Si los casilleros ady[x][y] y ady[y][z] son True, entonces el casillero ady[x][z] será también True.
¿Cuáles de las siguientes afirmaciones relativas a la idea arcos de entrada o de salida de un nodo son correctas? (Más de una puede ser correcta...)
Seleccione una o más de una: El Fuera de Grado de un nodo (o Grado de Salida) en un grafo dirigido es la cantidad de arcos que tienen a ese nodo como
nodo de partida. El Grado de un nodo (tanto si el grafo es dirigido como si es no dirigido) es la cantidad de arcos incidentes a ese nodo (arcos
que tienen al nodo como partida o como llegada). El Entre Grado de un nodo (o Grado de Entrada) en un grafo dirigido es la cantidad de arcos que tienen a ese nodo como
nodo de llegada. El Grado de un nodo (tanto si el grafo es dirigido como si es no dirigido) es la cantidad de arcos no incidentes a ese nodo (arcos que no tienen a ese nodo ni como partida ni como llegada).
¿En qué universidad estudió, se doctoró y formó parte de su Academia de Ciencias el matemático Wilhelm Ackerman?
Seleccione una: Padova Göttingen Stanford Oxford.
¿Cuál de los siguientes era el nombre verdadero del matemático conocido como Fibonacci, que fue quien definió la famosa Sucesión de Fibonacci?
Seleccione una: Giuseppe Peano Carl Gauss Leonardo Pisano Leonhard Euler.
¿Cuál es la mejora esencial que el algoritmo Quicksort realiza sobre el algoritmo Bubblesort o Burbuja?
Seleccione una: Quicksort acelera el cambio de posición tanto de los elementos menores como de los mayores, mientras que Bubblesort solo
acelera a los mayores (o a los menores, dependiendo de la forma de implementación). Quicksort no implementa ninguna mejora sustancial sobre Bubblesort. En las versiones analizadas en clases, Quicksort sólo usa un ciclo para recorrer el arreglo, mientras que Bubblesort usa dos. Quicksort primero determina qué tan desordenado está el arreglo, mientras que Bubblesort procede directamente a ordenarlo .
¿Cuál de los siguientes esquemas simples de pseudocódigo representa a un algoritmo planteado mediante estrategia Divide y Vencerás, pero con tiempo de ejecución O(n*log(n))?
Seleccione una: proceso (partición) :
adicional() [ == > 0(1) ]
proceso (partición/2)
proceso (partición/2) proceso (partición) :
adicional () [ == > O(n) ]
proceso (partición/2)
proceso (partición/2) proceso (partición) :
adicional () [ == > O (n^2) ]
proceso (partición/2)
proceso (partición/2) proceso (partición) :
adicional () [ == > O(n^3) ]
proceso (partición/2)
proceso (partición/2).
¿Cuál de las siguientes situaciones haría que el algoritmo Quicksort degenere en su peor caso en cuanto al tiempo de ejecución, de orden n^2?
Seleccione una: Que el arreglo de entrada tenga sus elementos dispuestos de tal forma que cada vez que se seleccione el pivot en cada v
partición, resulte que ese pivot sea siempre el menor o el mayor de la partición que se está procesando. Que el arreglo esté ya ordenado, en la misma secuencia en que se lo quiere ordenar. Que el arreglo esté ya ordenado, pero al revés. El algoritmo Quicksort no tiene un peor caso O(n^2). Su tiempo de ejecución siempre es O(n*log(n)).
¿Cuál de las siguientes estrategias de obtención del pivot es la más recomendable para evitar que el algoritmo Quicksort se degrade en su peor caso O(n2) en cuanto a su tiempo de ejecución?
Seleccione una: En cada partición, obtener el pivot por la mediana de tres (ya sea la mediana entre el primero, el último y el central; o bien la
mediana entre tres elementos aleatorios la partición). En cada partición, usar como pivot al valor de la casilla central. En cada partición, usar como pivot al valor de la primera casilla. En cada partición, usar como pivot al valor de la última casilla.
¿Por qué es considerada una mala idea tomar como pivot al primer elemento (o al último) de cada partición al implementar el algoritmo Quicksort?
Seleccione una: Porque de esa forma aumenta el riesgo de caer en el peor caso, o aproximarse al peor caso, si el tamaño n del arreglo fuese muy grande. Porque de esa forma aumenta el riesgo de caer en el peor caso, o aproximarse al peor caso, si el arreglo estuviese completamente desordenado. Porque de esa forma aumenta el riesgo de caer en el peor caso, o aproximarse al peor caso, si el arreglo estuviese ya ordenado o casi ordenado. No es cierto que sea una mala idea. Ambas alternativas son tan buenas como cualquier otra.
¿Cuál es la cantidad de niveles del árbol de invocaciones recursivas que se genera al ejecutar el Quicksort para ordenar un arreglo de n elementos, en el caso promedio? (Es decir: ¿Cuál es la altura de ese árbol en el caso promedio?)
Seleccione una: Altura = n * log (n) Altura = n Altura = n^2 Altura = log(n) .
¿Cuál es la cantidad de niveles del árbol de invocaciones recursivas que se genera al ejecutar el Quicksort para ordenar un arreglo de n elementos, en el peor caso? (Es decir: ¿Cuál es la altura de ese árbol en ese peor caso?)
Seleccione una: Altura = n^2 Altura = log (n) Altura = n Altura = n * log (n).
¿Cuáles de las siguientes afirmaciones con correctas en relación a conceptos elementales del análisis de algoritmos? (Más de una respuesta puede ser válida, por lo que marque todas las que considere correctas).
Seleccione una o más de una: El análisis del caso promedio es aquel en el cual se estudia el comportamiento de un algoritmo cuando debe procesar una
configuración de datos que llegan en forma aleatoria. El análisis del peor caso es aquel en el cual se estudia el comportamiento de un algoritmo cuando debe procesar la
configuración más desfavorable posible de los datos que recibe. Los dos factores de eficiencia más comúnmente utilizados en el análisis de algoritmos son el tiempo de ejecución de un
algoritmo y el espacio de memoria que un algoritmo emplea La notación Big O se usa para expresar el rendimiento de un algoritmo en terminos de una función que imponga una cota
inferior para ese algoritmo en cuanto al factor medido (tiempo o espacio de memoria).
Dado un arreglo de n componentes ... ¿qué significa decir que en el peor caso la cantidad de comparaciones que realiza el algoritmo de búsqueda secuencial es O(n) (o sea: del orden de n)?
Seleccione una: Significa que en el peor caso el algoritmo no hará ninguna comparación. Significa que en el peor caso el algoritmo hará siempre más de n comparaciones. Significa que en el peor caso el algoritmo hara n comparaciones. Significa que en el peor caso el algoritmo siempre hará menos de n comparaciones.
¿Cuáles de las siguientes afirmaciones son ciertas en referencia a las Estrategias de Resolución de Problemas que se citan? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas ... )
Seleccione una o más de una: La estrategia de Backtracking es de base recursiva y permite implementar soluciones de prueba y error explorando las distintas soluciones y voviendo atrás si se detecta que un camino conduce a una solución incorrecta. cuando es aplicable, es más eficiente que la Fuerza Bruta, ya que permite eliminar caminos por deducción. La estrategia de Fuerza Bruta se basa en aplicar ideas intuitivas y directas, simples de codificar, pero normalmente producev
algoritmos de mal rendimiento en tiempo de ejecución y/o de espacio de memoria empleado. El empleo de la Recursividad para resolver un problema no es recomendable en ningún caso, debido a la gran cantidad de recursos de memoria o de tiempo de ejecución que implica. La técnica de Programación Dinámica se basa en calcular los resultados de los subproblemas de menor orden o tamaño que pudieran aparecer, almacenar esos resultados en una tabla, y luego re-usarlos cuando vuelvan a ser requeridos en el cálculo del problema mayor.
¿Cuál de las siguientes afirmaciones es falsa en relación a las Estrategias de Resolución de Problemas (o Estrategias de Planteo de Algoritmos)?
Seleccione una: Se trata de un conjunto de técnicas diversas que podrían ayudar a encontrar la solución a un problema, pero sin garantía de éxito. Son técnicas y recomendaciones para el planteo de problemas que garantizan que se encontrará una solución, empleando la estrategia correcta para cada problema que se enfrente. Un mismo problema podría ser resulto en base a dos o más estrategias de resolución diferentes, dando lugar a distintos algoritmos para ese mismo problema. Se trata de un conjunto de técnicas diversas que podrían ayudar a encontrar la solución a un problema, pero sin garantía de éxito, y aún si se llega a una solución, tampoco se garantiza que esa solución sea eficiente.
¿Cuáles de los siguientes son conocidos algoritmos basados en la estrategia Divide y Vencerás? (Más de una respuesta puede ser correcta, por lo que marque todas las que considere válidas)
Seleccione una o más de una: Algoritmo Heapsort para ordenamiento de arreglos. Algoritmo Quicksort para ordenamiento de arreglos. Algoritmo Shellsort para ordenamiento de arreglos. Algoritmo Mergesort para ordenamiento de arreglos.
¿Cuál de las siguientes resume en forma correcta la idea general de la estrategia Divide y Vencerás para resolución de problemas?
Seleccione una: Se usa una tabla para almacenar los resultados de los subproblemas que se hayan calculado, y luego cuando algún subproblema vuelve a aparecer se toma su valor desde la tabla, para evitar pérdida de tiempo. Se aplica una regla simple que parece ser beneficiosa, sin volver atrás ni medir las consecuencias de aplicar esa regla, con la esperanza de lograr el resultado óptimo al final. El conjunto de n datos se divide en subconjuntos de cualquier tamaño, sin importar si los tamaños de cada subconjunto coinciden entre sí. Luego se aplica recursión para procesar cada uno de esos subconjuntos. Finalmente se unen las partes que se acaban de procesar para lograr el resultado final. El conjunto de n datos se divide en subconjuntos de aproximadamente el mismo tamaño (n/2, n/3, n/4, etc.). Luego se aplica
recursión para procesar cada uno de esos subconjuntos. Finalmente se unen las partes que se acaban de procesar para lograr el resultado final.
Considere el problema del Cambio de Monedas analizado en clases, y la solución mediante un Algoritmo Ávido también presentada en clases ¿Cuáles de las siguientes afirmaciones son ciertas en relación al problema y al algoritmo citado? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas ... )
Seleccione una o más de una: Si el Problema de Cambio de Monedas no puede resolverse en forma óptima para un conjunto dado de monedas que incluya a la de 1 centavo, mediante el Algoritmo Ávido propuesto, entonces el problema no tiene solución. Sea cual sea el algoritmo que se emplee, es exigible que exista la moneda de 1 centavo, pues de otro modo no habrá solución posible para muchos valores de cambio. El Algoritmo Ávido sugerido para el problema del Cambio de Monedas funciona correctamente para cualquier conjunto de valores nominales de monedas, siempre y cuando ese conjunto incluya a la moneda de 1 centavo. El Algoritmo Ávido sugerido para el Problema del Cambio de Monedas falla si el valor x a cambiar tiene una moneda igual a x en el conjunto de valores nominales: en ese caso, el algoritmo provoca un error de runtime y se interrumpe.
Considere el problema del Cambio de Monedas analizado en clases, y la solución mediante Programación Dinámica también presentada en clases ¿Cuáles de las siguientes afirmaciones son ciertas en relación al problema y al algoritmo citado? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas ... )
Seleccione una o más de una: En el algoritmo basado en Programación Dinámica no es importante si el arreglo coins está ordenado o desordenado: funcionará correctamente de todas formas En el algoritmo basado en Programación Dinámica los valores de las monedas que sean mayores a x, son dejados de lado y la recurrencia de cálculo no se aplica sobre ellos. En el algoritmo basado en Programación Dinámica, el resultado final a retornar es igual a la suma o acumulación de todos los valores almacenados en el arreglo prev donde se almacenaron los resultados intermedios. En el algoritmo basado en Programación Dinámica, el resultado final a retornar es el que haya quedado almacenado en la casilla x del arreglo prev que contiene los resultados intermedios (o sea, en prev[x]).
Considere el problema de las Ocho Reinas presentado en clases. ¿Cuáles de las siguientes afirmaciones son ciertas en relación a las diagonales del tablero en el cual deben colocarse la reinas, suponiendo que el tablero es el normal del ajedrez, de 8 * 8? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas ... )
Seleccione una o más de una: En cada una de las diagonales que se orientan como la contra-diagonal o diagonal inversa, es constante la suma entre el
número de columna y el número de fila de cada uno de sus elementos. En general hay dos tipos de diagonales: las normales (orientadas en la misma forma que la diagonal principal) y las inversas
(orientadas en la misma forma que la contra-diagonal o diagonal inversa). La cantidad total de diagonales que contiene el tablero (sumando todas las diagonales de todos los tipos posibles) es 30. En cada una de las diagonales que se orientan como la principal, es constante la resta entre el número de columna y el número de fila de cada uno de sus elementos.
Considere el problema de las Ocho Reinas presentado en clases. ¿Cuáles de las siguientes afirmaciones son ciertas en relación a las diagonales normales del tablero en el cual deben colocarse la reinas, suponiendo que el tablero es el normal del ajedrez, de 8 * 8? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas ... )
Seleccione una o más de una: El valor de la resta entre el número de columna y el número de fila de cada componente de una diagonal normal, es un
número constante para cada diagonal, y los posibles valores están en el intervalo [-7 .. 7] Las diagonales normales pueden representarse con un arreglo qnd de 15 componentes, en el que cada diagonal cuyos elementos tengan el mismo valor (col + fil), se haga coincidir el casillero qnd[(col + fil)]. Las diagonales normales pueden representarse con un arreglo qnd de 15 componentes, en el que cada diagonal cuyos
elementos tengan el mismo valor (col - fil), se haga coincidir el casillero qnd[(col - fil) + 7] (evitando de esta forma los índices
negativos. El valor de la suma entre el número de columna y el número de fila de cada componente de una diagonal normal, es un
número constante para cada diagonal, y los posibles valores están en el intervalo [0 .. 14].
Considere el problema de las Ocho Reinas presentado en clases. ¿Cuáles de las siguientes afirmaciones son ciertas en relación a las diagonales inversas del tablero en el cual deben colocarse la reinas, suponiendo que el tablero es el normal del ajedrez, de 8 * 8? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas ... )
Seleccione una o más de una: El valor de la resta entre el número de columna y el número de fila de cada componente de una diagonal inversa, es un
número constante para cada diagonal, y los posibles valores están en el intervalo [-7 .. 7] Las diagonales inversas pueden representarse con un arreglo qid de 15 componentes, en el que cada diagonal cuyos elementos
tengan el mismo valor (col - fil), se haga coincidir el casillero qid[(col - fil) + 7]. El valor de la suma entre el número de columna y el número de fila de cada componente de una diagonal inversa, es un
número constante para cada diagonal, y los posibles valores están en el intervalo [0 .. 14] Las diagonales inversas pueden representarse con un arreglo qid de 15 componentes, en el que cada diagonal cuyos elementos tengan el mismo valor (col + fil), se haga coincidir el casillero qid[(col + fil)].
Considere el problema de las Ocho Reinas presentado en clases. Se ha indicado que se puede usar un arreglo rc de componentes, en el cual el casillero rc[col] = fil indica que la reina de la columna col está ubicada en la fila fil. ¿Cuáles de las siguientes configuraciones para el arreglo rc representan soluciones incorrectas para el problema de las Ocho Reinas? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas ... )
Seleccione una o más de una: rc = [5, 3, 6, 0, 7, 1, 4, 2] rc = [4, 7, 3, 0, 2, 5, 1, 6] rc = [2, 0, 7, 4, 5, 1, 6, 3] rc = [3, 5, 7, 0, 5, 1, 2, 4] .
|
