parcial 5 AED UTN CBA

Suponga que se quiere plantear una definición recursiva del concepto de bosque. ¿Cuál de las siguientes propuestas generales es correcta y constituye la mejor definición?. Un bosque es un conjunto de árboles que puede estar vacío, o puede contener n árboles (con n > 0). Un bosque es un conjunto de árboles que puede estar vacío, o puede contener uno o más árboles agrupados con otro bosque. Un bosque es un bosque. Un bosque es un conjunto que puede contener uno o más árboles agrupados con otro bosque.

¿Cuáles de los siguientes son factores esenciales a tener en cuenta cuando se realiza el análisis de la eficiencia de un algoritmo (por ejemplo, para efectuar una comparación de rendimiento entre dos algoritmos que resuelven el mismo problema)?. La complejidad aparente del código fuente. El tiempo de ejecución. El diseño de la interfaz de usuario. El consumo de memoria.

Suponga que la versión recursiva de la función para el cálculo del factorial que se presentó en clases fuese redefinida en la forma siguiente: Contiene todos los elementos que debería tener una función recursiva bien planteada, pero en el orden incorrecto: la condición para chequear si n es cero debería estar antes que la llamada recursiva para evitar la recursión infinita. No hay ningún problema. Funciona correctamente. Para calcular el factorial necesita un ciclo for que genere los números a multiplicar. Así planteada, la función hace un único primer cálculo incompleto y lo retorna. La función siempre retorna un 1, sin importar cual sea el valor de n.

A lo largo del curso hemos visto la forma de plantear programas controlados por menú de opciones, y sabemos que esos programas incluyen un ciclo para el control del proceso. Pero también podríamos hacer un planteo basado en recursión, sin usar el ciclo, en forma similar a la que se muestra aquí: Esta versión recursiva posiblemente sea más simple y compacta que la versión basada en un ciclo, pero la versión recursiva pide memoria de stack cada vez que se invoca, por lo que es más conveniente la iterativa. Esta versión recursiva es completamente equivalente a la versión iterativa. No hay ningún motivo para preferir la una sobre la otra. Da lo mismo si el programador usa la recursiva o la iterativa. No hay ningún problema ni contraindicación. Y no sólo eso: la versión recursiva es más simple y compacta que la versión basada en un ciclo, por lo cual es incluso preferible usarla. La versión recursiva que se mostró no funciona. Sólo permite cargar una vez la opción elegida, e inmediatamente se detiene.

El producto de dos números a y b mayores o iguales cero, es en última instancia una suma: se puede ver como sumar b veces el número a, o como sumar a veces el número b. Por ejemplo: 5 * 3 = 5 + 5 + 5 o bien 5 * 3 = 3 + 3 + 3 + 3 + 3. Sabiendo esto, se puede intentar hacer una definición recursiva de la operación producto(a, b) [a >= 0, b >= 0], que podría ser la que sigue: No. La propia definición previa del concepto de producto es incorrecta: un producto es una multiplicación, y no una suma... No. La función sugerida siempre retornará 0, sean cuales fuesen los valores de a y b. Sí. Es correcto. No. La última línea debería decir return a + producto(a-1, b-1) en lugar de return a + producto(a, b-1).

En la tabla siguiente se muestra un resumen comparativo entre las versiones iterativa (basada en ciclos) y recursiva del algoritmo de cálculo del término n-ésimo de la Sucesión de Fibonacci. Note que se han dejado sin completar los casilleros que corresponden al tiempo de ejecución para ambos casos. Versión iterativa: tiempo proporcional a n (lineal) - Versión recursiva: tiempo proporcional a bn (exponencial, para algún b > 1). Versión iterativa: tiempo constante (no depende de n) - Versión recursiva: tiempo proporcional a bn (exponencial, para algún b > 1). Versión iterativa: tiempo proporcional a bn (exponencial, para algún b > 1) - Versión recursiva: tiempo proporcional a n (lineal). Versión iterativa: tiempo proporcional a n (lineal) - Versión recursiva: tiempo proporcional a n (lineal).

¿Cuáles de las siguientes propuestas generales son ciertas en relación al segmento de memoria conocido como Stack Segment?. El Stack Segment se utiliza como soporte interno solamente en el proceso de invocación a funciones recursivas: se va llenando a medida que la cascada recursiva se va desarrollando, y se vacía a medida que se produce el proceso de regreso o vuelta atrás. El Stack Segment funciona como una pila (o apilamiento) de datos (modalidad LIFO: Last In - First Out): el último dato en llegar, se almacena en la cima del stack, y será por eso el primero en ser retirado. El Stack Segment funciona como una cola (o fila) de datos (modalidad FIFO: First In - First Out): el primer dato en llegar, se almacena al frente del stack, y será por eso el primero en ser retirado. El Stack Segment se utiliza como soporte interno en el proceso de invocación a funciones (con o sin recursividad): se va llenando a medida que se desarrolla la cascada de invocaciones, y se vacía a medida que se produce el proceso de regreso o vuelta atrás.

Suponga que se quiere calcular el valor del sexto término de la sucesión. Analice el árbol de llamadas recursivas que se genera al hacer la invocación t = fibo(6) ¿Cuántas veces en total la función fibo() se invoca para hacer más de una vez el mismo trabajo, SIN incluir en ese conteo a las invocaciones para obtener fibo(0) y fibo(1)?. 12. 11. 10. 0.

¿En cuáles de las siguientes situaciones el uso de recursividad está efectivamente recomendado? (Más de una respuesta puede ser válida. Marque todas las que considere correctas). Generación y procesamiento de imágenes y gráficos fractales (figuras compuestas por versiones más simples de la misma figura original). Recorrido y procesamiento de estructuras de datos no lineales como árboles y grafos. Nunca. Siempre que se pueda escribir una definición recursiva del problema.

¿Cuáles de las siguientes son CIERTAS en relación al sistema de coordenadas de pantalla?. Las filas de pantalla o de ventana con número de orden más alto, se encuentran más cerca del borde superior que las filas con número de orden más bajo. El origen del sistema de coordenadas se encuentra en el punto inferior izquierdo de la pantalla o de la ventana que se esté usando. El origen del sistema de coordenadas se encuentra en el punto superior izquierdo de la pantalla o de la ventana que se esté usando. Las filas de pantalla o de ventana con número de orden más bajo, se encuentran más cerca del borde superior que las filas con número de orden más alto.

El cálculo del valor an (para simplificar, asumimos a > 0 y n >= 0 y sabiendo que si n = 0 entonces a0 = 1) es igual a multiplicar n veces el número a por sí mismo. Por caso, 53 = 5 * 5 * 5 = 125. Sabiendo esto, ¿cuál de las siguientes sería una definición recursiva matemáticamente correcta de la operación potencia(a, n)?. a * potencia(a-1, n). a * potencia(a, n). a + potencia(a, n-1). a * potencia(a, n-1).

¿Cuál es la principal característica de todos los métodos de ordenamiento conocidos como métodos simples o directos?. Tienen muy buen rendimiento en tiempo de ejecución, cualquiera sea el tamaño n del arreglo. Tienen muy mal rendimiento en tiempo de ejecución si el tamaño n del arreglo es grande o muy grande, y un rendimiento aceptable si n es pequeño. Tienen muy mal rendimiento en tiempo de ejecución si el tamaño n del arreglo es pequeño, y un rendimiento aceptable si n es grande o muy grande. Tienen muy mal rendimiento en tiempo de ejecución, cualquiera sea el tamaño n del arreglo.

¿Cuál de las siguientes describe mejor la idea de funcionamiento en la que está basado el algoritmo conocido como ordenamento por Inserción Simple para ordenar un arreglo de n componentes?. Realizar n pasadas, de forma que en cada una se compare a cada elemento con el siguiente, logrando que en cada pasada los mayores vaya acomodándose al final del arreglo. Realizar n pasadas, de forma que en cada una se determine el menor de los elementos analizados, y llevar ese menor a la casilla pivot. Reacomodar los n elementos del arreglo en forma aleatoria, controlar si quedó ordenado, y en caso de negativo, volver a reacomodarlos en forma aleatoria, continuando así hasta que en algún momento se obtenga un arreglo ordenado... Suponer que el arreglo tiene un subconjunto inicialmente ordenado que contiene sólo al primer elemento, luego realizar n pasadas, de forma que en cada una agregue el siguiente elemento al grupo que está ordenado.

¿Cuál de las siguientes describe mejor la idea de funcionamiento en la que está basado el algoritmo conocido como ordenamento por Intercambio Directo u Ordenamiento de Burbuja para ordenar de menor a mayor un arreglo de n componentes?. Suponer que el arreglo tiene un subconjunto inicialmente ordenado que contiene sólo al primer elemento, luego realizar n pasadas, de forma que en cada una agregue el siguiente elemento al grupo que está ordenado. Reacomodar los n elementos del arreglo en forma aleatoria, controlar si quedó ordenado, y en caso negativo, volver a reacomodarlos en forma aleatoria, continuando así hasta que en algún momento se obtenga un arreglo ordenado... Realizar n pasadas, de forma que en cada una se determine el menor de los elementos analizados, y llevar ese menor a la casilla pivot. Realizar n pasadas, de forma que en cada una se compare a cada elemento con el siguiente, logrando que en cada pasada los mayores vayan acomodándose al final del arreglo.

¿Cuál de las siguientes describe mejor la idea de funcionamiento en la que está basado el algoritmo conocido como ordenamento por Selección Simple o Selección Directa para ordenar un arreglo de n componentes?. Reacomodar los n elementos del arreglo en forma aleatoria, controlar si quedó ordenado, y en caso de negativo, volver a reacomodarlos en forma aleatoria, continuando así hasta que en algún momento se obtenga un arreglo ordenado... Realizar n pasadas, de forma que en cada una se determine el menor de los elementos analizados, y llevar ese menor a la casilla pivot. Suponer que el arreglo tiene un subconjunto inicialmente ordenado que contiene sólo al primer elemento, luego realizar n pasadas, de forma que en cada una agregue el siguiente elemento al grupo que está ordenado. Realizar n pasadas, de forma que en cada una se compare a cada elemento con el siguiente, logrando que en cada pasada los mayores vaya acomodándose al final del arreglo.

¿Por qué motivo el algoritmo Bubblesort para ordenamento de un arreglo usa una bandera de corte en la versión presentada en las fichas de clase?. La bandera de corte se usa para garantizar que el arreglo quede ordenado. La bandera de corte se usa para terminar el proceso apenas se detecte que en la pasada actual no hubo intercambios, para ahorrar tiempo. No es cierto que la versión vista en clases use una bandera de corte. La bandera de corte se usa para determinar si el ordenamento debe hacerse de manor a mayor (bandera = True) o de mayor a menor (bandera = False).

¿Cuál de los siguientes es el creador del famoso algoritmo de ordenamiento conocido como Quicksort?. Edsger Wybe Dijkstra. Charles Antony Richard Hoare. Donald Shell. J. W. J. Williams.

¿Cuáles de las siguientes son características correctas del algoritmo Shellsort? (Más de una puede ser cierta... marque TODAS las que considere válidas). El algoritmo Shellsort es complejo de analizar para determinar su rendimientos en forma matemática, ya que ese rendimiento depende fuertemente de la serie de incrementos decreciente que se haya seleccionado. El algoritmo Shellsort consiste en una mejora del algoritmo de Inserción Directa (o Inserción Simple), consistente en armar subconjuntos ordenados con elementos a distancia h > 1 en las primeras fases, y terminar con h = 1 en la última. El algoritmo Shellsort consiste en una mejora del algoritmo de Selección Directa, basada en buscar iterativamente el menor (o el mayor) entre los elementos que quedan en el vector, para llevarlo a su posición correcta, pero de forma que la b;usqueda del menor en cada vuelta se haga en tiempo logarítmico. Una muy buena serie de incrementos decrecientes a usar, es la serie h = {...16, 8, 4, 2, 1}.

¿Cuál es el problema si en el algoritmo Shellsort se elige una serie de incrementos decrecientes de la forma { ..., 16, 8, 4, 2, 1} ?. Los subconjuntos analizados contendrán casi los mismos elementos cuando la distancia usada sea cada vez menor, sin garantías de lograr una buena organización del arreglo antes de la última pasada. No sólo no hay ningún problema, sino que esa serie es la mejor posible para el algoritmo Shellsort. Ningún problema: esa serie es tan buena como cualquier otra. El arreglo no quedará ordenado al final.

Sabemos que en el algoritmo de Shell se termina haciendo una última pasada sobre el arreglo con incremento de compración h = 1 ¿Cuál de las siguientes es cierta respecto de esa última pasada con h = 1?. Con h = 1 el algoritmo se convierte en un ordenamiento por inserción simple, y sólo entonces garantiza que el arreglo quede ordenado. No es obligatorio que lo haga, pero favorece un ordenamiento más rápido. Con h = 1 el algoritmo sólo controla si el arreglo está ya ordenado, y en caso de no estarlo relanza el proceso con otra sucesión de valores h. La pasada con h = 1 es obligatoria pero no es necesario que sea la última.

¿Cuáles de las siguientes son características correctas del algoritmo Heapsort? (Más de una puede ser cierta... marque TODAS las que considere válidas). El algoritmo Heapsort utiliza una cantidad de memoria adicional igual al tamaño del arreglo, para armar el heap o grupo de ordenamiento con el que se ordena el vector. El algoritmo Heapsort es muy eficiente en tiempo de ejecución, tanto para el caso promedio como para el peor caso. El algoritmo Heapsort se basa en encontrar sucesivamente el menor (o el mayor) de entre los elementos que quedan, para llevar ese valor a su casillero final, pero de forma que la búsqueda del menor (o el mayor) en cada vuelta se haga en forma muy veloz. El algoritmo Heapsort arma el heap o grupo de ordenamiento con el que se ordena el vector, pero lo hace en el mismo vector, sin usar memoria extra.

¿En qué universidad estudió, se doctoró y formó parte de su Academia de Ciencias el matemático Wilhelm Ackerman?. Göttingen. Stanford. Oxford. Padova.

¿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?. Carl Gauss. Giuseppe Peano. Leonhard Euler. Leonardo Pisano.

¿Cuál es la mejora esencial que el algoritmo Quicksort realiza sobre el algoritmo Bubblesort o Burbuja?. 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. Quicksort no implementa ninguna mejora sustancial sobre Bubblesort. 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).

¿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))?. O(n3). O(1). O(n2). O(n).

¿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 n2?. Que el arreglo de entrada tenga sus elementos dispuestos de tal forma que cada vez que se seleccione el pivot en cada partición, resulte que ese pivot sea siempre el menor o el mayor de la partición que se está procesando. El algoritmo Quicksort no tiene un peor caso O(n2). Su tiempo de ejecución siempre es O(n*log(n)). Que el arreglo esté ya ordenado, pero al revés. Que el arreglo esté ya ordenado, en la misma secuencia en que se lo quiere ordenar.

¿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?. En cada partición, usar como pivot al valor de la casilla central. 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 última casilla. En cada partición, usar como pivot al valor de la primera 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?. 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 ya ordenado o casi ordenado. No es cierto que sea una mala idea. Ambas alternativas son tan buenas como cualquier otra. Porque de esa forma aumenta el riesgo de caer en el peor caso, o aproximarse al peor caso, si el arreglo estuviese completamente desordenado.

Considere la función presentada en clases para calcular mediana entre el primero, el central y el último elemento de una partición del arreglo v delimitada por los elementos en las posiciones izq y der: El tamaño de la partición analizada es entonces n = der - izq + 1 elementos. ¿Cuál es el tiempo de ejecución de esta función, expresado en notación O y de acuerdo a ese valor de n?. O(log(n)). O(n). O(n2). O(1).

¿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?). Altura = log(n). Altura = n * log(n). Altura = n2. Altura = 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?). Altura = n2. Altura = n * log(n). Altura = n. Altura = log(n).

¿Cuáles de las siguientes afirmaciones referidas a conceptos básicos generales sobre grafos son correctas? (Más de una puede ser correcta...). 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). Todo arco de un grafo, necesaria y obligatoriamente une dos nodos diferentes de ese grafo. 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).

¿Cuál de las siguientes afirmaciones es FALSA respecto de los ciclos en un grafo?. Los ciclos pueden ser válidos o no, dependiendo del problema que se quiere resolver. Los ciclos no están permitidos en un grafo. Un ciclo es un camino que parte de un nodo y lleva de vuelta al mismo nodo. 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): 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. 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). La ocurrencia de ciclos en general en el grafo. 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.

¿En cuál de las siguientes situaciones no debería usar un grafo dirigido?. 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. Para modelar un plan de estudios de una carrera universitaria.

¿En cuáles de las siguientes situaciones sería ideal un grafo no dirigido? (Más de una puede ser correcta...). Para modelar un plano de rutas entre localidades o ciudades. Para modelar un ”sociograma”: un gráfico que expresa en qué forma un grupo de personas se relacionan entre sí. Para modelar un plan de estudios de una carrera universitaria. Para modelar un sistema de rutas aéreas entre distintos aeropuertos del mundo.

¿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...). El problema no existe: no hay manera de representar grafos ponderados en forma matricial. 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. 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?. 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 del triángulo superior de la matriz de adyacencia valen True. Todos los casilleros 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?. Todos los casilleros de la matriz son True o todos los casilleros son False. Todos los casilleros de la diagonal principal de la matriz de adyacencia valen True. 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].

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?. Si los casilleros ady[x][y] y ady[y][z] son False, entonces el casillero ady[x][z] será True. Si los casilleros ady[x][y] y ady[y][z] son True, entonces el casillero ady[x][z] será también True. 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 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].

¿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...). 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). 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.

Sabemos que en un árbol binario (sea o no de búsqueda) un nodo puede tener a lo sumo dos hijos. Por otra parte, un nodo tendrá un único nodo padre (salvo la raiz, que no tiene padre) ¿Qué parte de la definición de árbol binario es la que impide que un nodo pueda tener más de un padre?. La sección en la que se afirma que del nodo raiz se desprenden dos subconjuntos. La sección en la que se afirma que el árbol puede estar vacío o puede contener un nodo designado como la raiz del árbol. La sección en la que se afirma que los dos subconjuntos que dependen del nodo raiz son conjuntos separados o mutuamente excluyentes. La sección en la que se afirma que los dos subconjuntos que dependen del nodo raiz pueden estar vacíos.

¿Cuál de las siguientes es CIERTA respecto de los árboles binarios de búsqueda?. Siempre tienen altura mínima. Si el árbol tiene n nodos, el tiempo de búsqueda en el peor caso es O(n*log( n )) si la altura del árbol h es O(log(n)). Siempre tienen altura máxima. Si el árbol tiene n nodos, el tiempo de búsqueda en el peor caso es O(log(n)) si la altura del árbol h es O(log(n)).

¿Cuántas comparaciones por nivel se realizan en un árbol de búsqueda de n nodos cuando se busca una clave? (no importa si la búsqueda llega o no al último nivel del árbol: sólo queremos saber cuántas comparaciones se hacen en aquellos niveles hasta los que llegue la búsqueda). Comparaciones por nivel: n. Comparaciones por nivel: n2. Comparaciones por nivel: log(n). Comparaciones por nivel: 1 (una).

Considere el método contains() que busca un objeto x en un árbol de búsqueda de n nodos, según se vió en las fichas de clase de la asignatura: Si el algoritmo de inserción mediante el cual se ha creado el árbol es el algoritmo simple visto en la ficha y en clases, sin control de altura o balance, ¿cuáles de las siguientes afirmaciones son correctas en relación al algoritmo implementado en el método contains()? (Más de una respuesta puede ser cierta. Marque todas las que considere correctas). El tiempo de ejecución del algoritmo mostrado es O(log(n)) en el peor caso, pero sólo si el árbol tiene altura h = O(log(n)) = mínima. El tiempo de ejecución del algoritmo mostrado es O(n) en el peor caso. El tiempo de ejecución del algoritmo mostrado es O(log(n)) en el peor caso. El tiempo de ejecución del algoritmo mostrado es O(1) en el peor caso.

Suponga que desconoce la forma gráfica de un árbol binario (que no es necesariamente de búsqueda) con el que está trabajando, pero se le da la posibilidad de conocer una o dos secuencias de recorrido de ese árbol, en distintos órdenes. ¿Con cuáles de las siguientes secuencias de recorrido se garantiza que podrá volver a dibujar el árbol original, sin ambigüedades ni errores? (Piense un poco para responder, y en todo caso, haga algunos intentos dibujando un árbol y tratando de reconstruirlo a partir de sus secuencias de recorrido) (Observación: más de una respuesta puede ser correcta. Marque todas las que considere válidas). Recuerde: se supone que el árbol original es binario, pero NO NECESARIAMENTE de búsqueda. Podrá volver a dibujar el árbol si conoce la secuencia de recorrido en preorden y la secuencia de recorrido en postorden. Podrá volver a dibujar el árbol si conoce la secuencia de recorrido en preorden y la secuencia de recorrido en entreorden. Podrá volver a dibujar el árbol si sólo conoce la secuencia de recorrido en entre orden. Podrá volver a dibujar el árbol si conoce la secuencia de recorrido en postorden y la secuencia de recorrido en entreorden.

¿En qué condiciones el recorrido en preorden de un árbol binario de búsqueda visitará los nodos del árbol en secuencia ordenada de menor a mayor?. Nunca. Siempre. Sólo si el árbol es una diagonal con todos los hijos izquierdos nulos. Sólo si el árbol es una diagonal con todos los hijos derechos nulos.

¿Qué es lo peor que puede pasar con un árbol de búsqueda de n nodos si no se lo mantiene equilibrado (o balanceado) (o sea, intuitivamente, si los n nodos se distribuyen en más de log(n) niveles)?. Que una búsqueda obligue a O(2n) comparaciones. Que una búsqueda obligue a O(n) comparaciones. Que una búsqueda obligue a O(log(n)) comparaciones. Que una búsqueda obligue a O(n2) comparaciones.

Típicamente (y por diversas razones) en un árbol binario de búsqueda no se acepta la inserción de claves o valores repetidos. Pero existen estrategias simples que pueden usarse para permitir esa repetición de claves. Una de ellas es la de relajar la regla de inserción de forma que los menores sigan yendo a la izquierda, pero ahora los mayores o iguales vayan a la derecha. ¿Cuáles de las siguientes afirmaciones son ciertas si en un árbol binario de búsqueda se cambia la regla de inserción para aplicar la regla relajada citada más arriba? (Más de una respuesta puede ser cierta, por lo que marque todas las que considere correctas). Si solo se insertan claves que sean iguales a la que contiene la raíz, el árbol tendrá estructura de una diagonal con todos los enlaces derechos nulos. Dos claves iguales quedarán siempre en el árbol una como hija derecha e inmediata de la otra. Si solo se insertan claves que sean iguales a la que contiene la raíz, el árbol tendrá estructura de una diagonal con todos los enlaces izquierdos nulos. Dos o más claves iguales podrán quedar separadas por dos o más niveles de distancia.

¿Cuál es la razón por la que es recomendable usar una pila como soporte al recorrer un árbol binario (y por lo tanto, cuál es la razón por la que es recomendable usar recursión para ese recorrido?. Porque una pila permite almacenar en orden LIFO las direcciones de los nodos que se acaban de visitar en el recorrido, y cuando se necesite regresar a ese nodo luego de procesar alguno de sus dos hijos, su dirección quedará en el tope de la pila y será accesible en forma directa. En realidad, es mejor usa una cola en lugar de una pila. Una cola permite almacenar en orden FIFO las direcciones de los nodos que se acaban de visitar en el recorrido, y cuando se necesite regresar a ese nodo luego de procesar alguno de sus dos hijos, su dirección quedará en el frente de la cola y será accesible en forma directa. No hay ninguna razón para usar una pila o para usar recursión. Un ciclo y una referencia de persecución serían siempre suficientes para hacer el recorrido completo. No es necesario ni usar una pila ni usar recursión. El árbol puede recorrerse simplemente con un ciclo que comience en la raíz y luego se desplace vuelta tras vuelta hacia el hijo izquierdo, hasta llegar a un hijo izquierdo nulo, momento en el cual el ciclo debe detenerse y el árbol queda completamente recorrido.

Sabemos que para que un árbol binario de búsqueda favorezca búsquedas rápidas, el árbol debería tener cierta estructura a la que hemos designado como balance o equilibrio. No hemos dado una definición formal y detalla del concepto de balance o equilibrio (ya que eso escapa al alcance de esta asignatura) en un árbol binario: solo hemos tomado una idea intuitiva y muy conceptual. En base a esa idea intuitiva, ¿cuál de las siguientes describe conceptualmente mejor lo que se entiende por un árbol balanceado o equilibrado?. Intuitivamente, un árbol binario está balanceado si su altura es la máxima posible (o se acerca mucho a esa máxima) para la cantidad de nodos que tiene el árbol. Intuitivamente, un árbol binario está balanceado si tiene forma de zig-zag, con no más de un nodo en cada nivel del árbol. Intuitivamente, un árbol binario está balanceado si tiene forma de diagonal (hacia la derecha o hacia la izquierda). Intuitivamente, un árbol binario está balanceado si su altura es la mínima posible (o se acerca mucho a esa mínima) para la cantidad de nodos que tiene el árbol.

¿Cuál es la diferencia entre la abstracción de datos y la abstracción funcional?. La abstracción de datos busca captar el conjunto de datos más relevante para representar un tipo abstracto, mientras que la funcional buscar determinar el conjunto de procesos relevante para esos datos. Ninguna. Son sólo dos formas de referirse al mecanismo de abstracción. La abstracción de datos busca captar el conjunto de procesos relevante para el tipo abstracto que se quiere implementar, mientras que la funcional buscar determinar el conjunto de datos más relevante para implementar ese tipo. No existe un mecanismo de abstracción de datos ni un mecanismo de abstracción funcional. Existe sólo un mecanismo de abstracción, sin dividir en asbtracción de datos y abstracción funcional.

Suponga que se quiere implementar un nuevo tipo de datos abstracto llamado Fecha, para permitir la manipulación de fechas en un programa en Python para gestión de eventos sociales (casamientos, fiestas de cumpleños, reuniones de egresados, etc.) ¿Cuál de las siguientes estrategias de abstracción sería la más adecuada?. Abstracción de datos: un registro con tres campos para el año, el mes y el día. Abstracción funcional: funciones para buscar una fecha dada, reservar una fecha para un evento, liberar una fecha para un evento y modificar los datos de una fecha para un evento. Abstracción de datos: una tupla con tres componentes para el año, el mes y el día. Abstracción funcional: funciones para buscar una fecha dada, reservar una fecha para un evento, liberar una fecha para un evento y modificar los datos de una fecha para un evento. Abstracción de datos: un registro con campos para el año, el mes, el día, el nombre del cliente, el tipo de evento, el monto presupuestado y una proyección metereológica para ese día. Abstracción funcional: funciones para buscar una fecha dada, reservar una fecha para un evento, liberar una fecha para un evento y modificar los datos de una fecha para un evento. Abstracción de datos: una variable de tipo cadena de caracteres para representar toda la fecha (por ejemplo: '2015/08/31'). Abstracción funcional: funciones para mostrar la fecha en distintos colores, imprimir la fecha en forma de cartel anunciador, cambiar el número del mes por el nombre del mes.

¿Cuál de las siguientes expresiones describe la forma de trabajo general de una Pila?. OIRO (Ordered In - Random Out). LIFO (Last In - First Out). FIFO (First In - First Out). OIFO (Ordered In - First Out).

¿Cuál de las siguientes situaciones de programación es la principal aplicación de una Pila?. Procesar una secuencia de datos en el mismo orden en el que ingresaron. Procesar una secuencia de datos en orden inverso al de su entrada. Procesar una secuencia de datos en orden de menor a mayor. Procesar una secuencia de datos en orden aleatorio.

Suponga que se tiene una pila p con capacidad para almacenar números enteros y que las operaciones básicas pop(), peek() y push() están correctamente implementadas en el módulo stack.py presentado en clases. Suponga que se han insertado los siguientes valores: [8 - 6 - 5 - 3 - 7] (el número 8 es el valor del frente o tope de la Pila). ¿Cuál de las siguientes secuencias de instrucciones permite retirar el valor 5 de la pila, pero dejando el 6 y 8 nuevamente arriba? (es decir: ¿cuál de las siguientes secuencias, dejaría la pila p en el estado [8 - 6 - 3 - 7]?). Primero. Segundo. Tercero. Cuarto.

Suponga que se tiene una pila p en la cual se almacenaron ya una cierta cantidad de datos. ¿Cuál de las siguientes secuencias de instrucciones permite invertir la pila? (o sea: si la pila original p era: [3 - 4 - 6 - 7] (con el 3 al frente) ¿cuál de las siguientes permitiría dejar la pila p en el estado [7 - 6 - 4 - 3] (con el 7 al frente)?) (Suponga que p2 y p3 también son pilas, inicialmente vacías y listas para usar). Primero. Segundo. Tercero. Cuarto.

¿Cuál de las siguientes expresiones describe la forma de trabajo general de una Cola?. FIFO (First In - First Out). OIFO (Ordered In - First Out). OIRO (Ordered In - Random Out). LIFO (Last In - First Out).

¿Cuál de las siguientes situaciones de programación es la principal aplicación de una Cola?. Procesar una secuencia de datos en orden aleatorio. Procesar una secuencia de datos en orden inverso al de su entrada. Procesar una secuencia de datos en el mismo orden en el que ingresaron. Procesar una secuencia de datos en orden de menor a mayor.

Suponga que se tiene una cola c en la cual se almacenaron ya una cierta cantidad de datos. ¿Cuál de las siguientes secuencias de instrucciones permite invertir la cola? (o sea: si la cola original c era: [3 - 4 - 6 - 7] (con el 3 al frente), ¿cuál de las siguientes permitiría dejar la cola c en el estado [7 - 6 - 4 - 3] (con el 7 al frente)?). # suponga que c2 y c3 son dos colas inicialmente vacías, y listas para usar while not c.is_empty(): c2.add(c2, c.remove()) while not c2.is_empty(): c2.add(c2.remove()) while not c3.is_empty(): c.add(c3.remove()). # suponga que p1 y p1 son dos PILAS inicialmente vacías, y listas para usar while not c.is_empty(): p1.push(c.remove()) while not p1.is_empty(): p2.push(p1.pop()) while not p2.is_empty(): c.add(p2.pop()). # suponga que p es una PILA vacía y lista para usar... while not c.is_empty(): p.push(c.remove()) while not p.is_empty(): c.add(p.pop()). # suponga que c2 es OTRA cola vacía y lista para usar... while not c.is_empty(): c2.add(c.remove()) while not c2.is_empty(): c.add(c2.remove()).

Una Cola de Prioridad es una cola en la cual los elementos se insertan en algún orden, pero tal que cuando se pide retirar un elemento se obtiene siempre el menor de los valores almacenados en la cola ¿Cuál de las siguientes estrategias podría ser una forma básica de implementar una Cola de Prioridad en las condiciones aquí expresadas?. Soporte: una varable de tipo list en Python. Inserción: siempre al frente. Eliminación: siempre el primer elemento. Soporte: una variable de tipo list en Python. Inserción: ordenada de menor a mayor (mantener el arreglo siempre ordenado de menor a mayor: para insertar un valor x, recorrer el arreglo y al encontrar el primer mayor a x detener el ciclo y añadir allí a x con un corte de índices. Eliminación: siempre el primer elemento. Soporte: una variable de tipo list en Python. Inserción: ordenada de mayor a menor (mantener el arreglo siempre ordenado de mayor a menor: para insertar un nuevo valor x, recorrer el arreglo y al encontrar el primer menor, a x detener el ciclo y añadir allí a x con un corte de índices. Eliminación: siempre el primer elemento. Soporte: una variable de tipo list en Python. Inserción: siempre al final. Eliminación: siempre el último elemento.

¿Cuántas comparaciones en el peor caso obliga a hacer una búsqueda secuencial en una lista ordenada (o en un arreglo ordenado) que contenga n valores?. Peor caso: O(log(n)) comparaciones. Peor caso: O(n2) comparaciones. Peor caso: O(1) comparaciones. Peor caso: O(n) comparaciones.

¿Cuál es la diferencia entre el peor caso y el caso promedio en el análisis de algoritmos?. El peor caso es la configuración de datos de entrada más favorable para el algoritmo, mientras que el caso promedio describe una configuración aleatoria de datos (no pensada ni para favorecer ni para desfavorecer al algoritmo). El peor caso es la configuración de datos de entrada más desfavorable para el algoritmo, mientras que el caso promedio describe una configuración de datos pensada para favorecer al algoritmo. El peor caso es la configuración de datos de entrada más favorable para el algoritmo, mientras que el caso promedio describe una configuración de datos pensada para desfavorecer al algoritmo. El peor caso es la configuración de datos de entrada más desfavorable para el algoritmo, mientras que el caso promedio describe una configuración aleatoria de datos (no pensada ni para favorecer ni para desfavorecer al algoritmo).

¿Cuáles de los siguientes son factores de eficiencia comunes a considerar en el análisis de algoritmos? (Más de una respuesta puede ser válida... marque todas las que considere correctas). El tiempo de ejecución. La complejidad aparente del código fuente. La calidad aparente de la interfaz de usuario. El consumo de memoria.

¿Qué significa decir que un algoritmo dado tiene un tiempo de ejecución O(1)?. El tiempo de ejecución siempre es de un segundo, sin importar la cantidad de datos. El tiempo de ejecucíón es constante, sin importar la cantidad de datos. El tiempo de ejecución es logarítmico: a medida que aumenta el número de datos, aumenta el tiempo pero en forma muy suave. El tiempo de ejecución es lineal: si aumenta el número de datos, aumenta el tiempo en la misma proporción.

¿Qué significa decir que un algoritmo dado tiene un tiempo de ejecución O(n2)?. El tiempo de ejecución es lineal: si aumenta el número de datos, aumenta el tiempo en la misma proporción. El proceso normalmente consiste en dos ciclos (uno dentro del otro) de aproximadamente n iteraciones cada uno, de forma que las operaciones críticas se aplican un número cuadrático de veces. A medida que aumenta el número de datos, aumenta el tiempo pero en forma muy suave: el conjunto de datos se divide en dos. se procesa una de las mitades, se desecha la otra y se repite el proceso hasta que no pueda volver a dividirse la mitad que haya quedado. El tiempo de ejecucíón es constante, sin importar la cantidad de datos.

¿Qué significa decir que un algoritmo dado tiene un tiempo de ejecución O(n)?. El tiempo de ejecución es lineal: si aumenta el número de datos, aumenta el tiempo en la misma proporción. A medida que aumenta el número de datos, aumenta el tiempo pero en forma muy suave: el conjunto de datos se divide en dos. se procesa una de las mitades, se desecha la otra y se repite el proceso hasta que no pueda volver a dividirse la mitad que haya quedado. El tiempo de ejecucíón es constante, sin importar la cantidad de datos. El proceso normalmente consiste en dos ciclos (uno dentro del otro) de aproximadamente n iteraciones cada uno, de forma que las operaciones críticas se aplican un número cuadrático de veces.

¿Qué significa decir que un algoritmo dado tiene un tiempo de ejecución O(log(n))?. A medida que aumenta el número de datos, aumenta el tiempo pero en forma muy suave: el conjunto de datos se divide en dos. se procesa una de las mitades, se desecha la otra y se repite el proceso hasta que no pueda volver a dividirse la mitad que haya quedado. El tiempo de ejecucíón es constante, sin importar la cantidad de datos. El tiempo de ejecución es lineal: si aumenta el número de datos, aumenta el tiempo en la misma proporción. El proceso normalmente consiste en dos ciclos (uno dentro del otro) de aproximadamente n iteraciones cada uno, de forma que las operaciones críticas se aplican un número cuadrático de veces.

Suponga que dispone de cuatro algoritmos diferentes para resolver el mismo problema, y que se sabe que los tiempos de ejecución (en el peor caso) son, respectivamente: O(n*log(n)), O(n2), O(n3) y O(n). El algoritmo cuyo tiempo de ejecución es O(n). El algoritmo cuyo tiempo de ejecución es O(n2). El algoritmo cuyo tiempo de ejecución es O(n*log(n)). El algoritmo cuyo tiempo de ejecución es O(n3).

¿Con qué nombre general se conoce en la Teoria de la Complejidad a un problema para el cual sólo se conocen algoritmos cuyo tiempo de ejecución es exponencial (o sea, problemas para los que todas las soluciones conocidas son algoritmos con tiempo O(2n)?. Problemas Irresolubles. Problemas Inmanejables. Problemas Imperdonables. Problemas Intratables.

Analice el siguiente esquema de una función en Python: ¿Cuál de las siguientes expresiones de orden describe mejor el tiempo de ejecución de esta función en el peor caso?. O(n*n). O(n*m). O(n). O(m).

Si se realiza un análisis preciso del ordenamiento por Selección Directa para un arreglo de n componentes, se llega a la conclusión que ese algoritmo hará n-1 pasadas, con n-1 comparaciones en la primera, n-2 en la segunda, y así sucesivamente reduciendo de a 1 la cantidad de comparaciones hasta hacer sólo una comparación en la última pasada. Por lo tanto, el algoritmo hará invariablemente una cantidad total de ½(n2 - n) comparaciones. Sabiendo esto, ¿cuáles de las siguientes expresiones son correctas para describir la cantidad de comparaciones que hará el algoritmo, usando distintos tipos de notaciones? (Más de una respuesta puede ser correcta. Marque TODAS las que considere correctas). Cantidad de comparaciones: O(n2). Cantidad de comparaciones: Θ(n2). Cantidad de comparaciones: o(n2). Cantidad de comparaciones: Ω(n2).

¿Cuál es la principal característica de todos los métodos de ordenamiento conocidos como métodos simples o directos?. Son muy fáciles de programar. Son muy veloces para cualquier tamaño del arreglo a ordenar. Tienen un tiempo de ejecución de orden cuadrático en el peor caso. Tienen un tiempo de ejecución de orden lineal en el peor caso.

¿Cuáles de las siguientes son características correctas del algoritmo Shellsort? (Más de una puede ser cierta... marque TODAS las que considere válidas). El algoritmo Shellsort es complejo de analizar para determinar su rendimientos en forma matemática. Se sabe que para la serie de incrementos decrecientes usada en la implementación vista en las clases de la asignatura, tiene un tiempo de ejecución para el peor caso de O(n1.5). En el caso promedio, el algoritmo Shellsort es tan eficiente como el Heapsort o el Quicksort, con tiempo de ejecución O(n*log(n)). El algoritmo Shellsort consiste en una mejora del algoritmo de Inserción Directa (o Inserción Simple), consistente en armar suconjuntos ordenados con elementos a distancia h > 1 en las primeras fases, y terminar con h = 1 en la última. El algoritmo Shellsort consiste en una mejora del algoritmo de Selección Directa, consistente en buscar iterativamente el menor (o el mayor) entre los elementos que quedan en el vector, para llevarlo a su posición correcta, pero de forma que la búsqueda del menor en cada vuelta se haga en tiempo logarítmico.

¿Qué diferencia existe entre el conteo exhaustivo de operaciones críticas y el análisis asintótico del comportamiento de una función en el análisis de algoritmos?. Ninguna. Ambas se refieren a la misma técnica básica del análisis de algoritmos. El conteo exhaustivo busca determinar una expresión o fórmula que exprese de manera rigurosa la cantidad de operaciones críticas que lleva a cabo un algoritmo, mientras que el análisis asintótico busca determinar el comportamiento general de una función para valores muy grandes del tamaño del problema. El análisis asintótico busca determinar una expresión o fórmula que exprese de manera rigurosa la cantidad de operaciones críticas que lleva a cabo un algoritmo, mientras que el conteo exhaustivo busca determinar el comportamiento general de una función para valores muy grandes del tamaño del problema. El conteo exhaustivo busca determinar una expresión o fórmula que exprese de manera rigurosa la cantidad de operaciones críticas que lleva a cabo un algoritmo, mientras que el análisis asintótico busca determinar una expresión o fórmula que exprese de manera rigurosa la cantidad de operaciones no críticas que lleva a cabo un algoritmo.

¿Qué se entiende, en el contexto del Análisis de Algoritmos, por un Orden de Complejidad?. Un conjunto o familia de funciones matemáticas que se comportan asintóticamente de la misma forma. Un conjunto o familia de algoritmos que resuelven el mismo problema. Un conjunto o familia de subrutinas con similares objetivos (equivalente al concepto de módulo). Un conjunto de datos ordenados.

Si los algoritmos de ordenamiento simples tienen todos un tiempo de ejecución O(n2) en el peor caso, entonces: ¿cómo explica que las mediciones efectivas de los tiempos de ejecución de cada uno sean diferentes frente al mismo arreglo?. La notación Big O rescata el término más significativo en la expresión que calcula el rendimiento, descartando constantes y otros términos que podrían no coincidir en los tres algoritmos. Los tiempos deben coincidir. Si hay diferencias, se debe a errores en los intrumentos de medición o a un planteo incorrecto del proceso de medición. La notación Big O no se debe usar para estimar el comportamiento en el peor caso, sino sólo para el caso medio. La notación Big O no se usa para medir tiempos sino para contar comparaciones u otro elemento de interés. Es un error, entonces, decir que los tiempos tienen "orden n cuadrado".

Se tiene un algoritmo que realiza cierta cantidad de procesos sobre un conjunto de n datos y un minucioso análisis matemático ha determinado que la cantidad de procesos que el algoritmo realiza en el peor caso viene descripto por la función f(n) = 3n3 + 5n2 + 2n1.5 ¿Cuál de las siguientes expresiones representa mejor el orden del algoritmo para el peor caso?. O(3n3 + 5n2 + 2n1.5). O(n1.5). O(n3 + n2). O(n3).

¿Cuáles de las siguientes son correctas en cuanto a los tiempos de ejecución de los algoritmos de ordenamiento clásicos? (Más de una puede ser cierta... marque TODAS las que considere válidas). Algoritmo Shell Sort: O(n2) en el peor caso para la serie de incrementos decrecientes vista en clase. Algoritmo Quick Sort: O(n*log(n)) en el caso promedio, pero O(n2) en el peor caso. Algoritmo Heap Sort: O(n*log(n)) tanto para el caso promedio como para el peor caso. Algoritmos directos o simples: O(n2) en el peor caso para todos ellos.

Para cada uno de los algoritmos o procesos listados en la columna de la izquierda, seleccione la expresión de orden que mejor describe su tiempo de ejecución en el peor caso. Dado un arreglo v con n componentes, buscar un valor x aplicando búsqueda secuencial. Dado un arreglo v con n componentes, ordenarlo de menor a mayor mediante el algoritmo de selección directa. Dado un arreglo ya ordenado v con n componentes, buscar un valor x aplicando búsqueda binaria. Dado un arreglo v con n componentes, acceder y cambiar el valor del casillero v[k] (con 0 <= k <= n-1). Dadas dos matrices de orden n*n, obtener la matriz producto aplicando el método tradicional.

En la columna de la izquierda se muestra el código fuente en Python de diversos procesos sencillos. Para cada uno de ellos, seleccione de la lista de la derecha la expresión en notación Big O que mejor describa el tiempo de ejecución de cada proceso para el peor caso. (Aclaración: una expresión como n^2 debe entenderse como "n al cuadrado" o n2). n = int(input('N: ')) ac = 0 for i in range(n): for j in range(i+1, n): ac += i*j print(ac). ac = 0 for i in range(10): ac += i print(ac). n = int(input('N: ')) ac = 0 for i in range(n): ac += i print(ac). n = int(input('N: ')) ac = 0 for i in range(n): for j in range(i+1, n): ac += i*j for i in range(n): for j in range(n): for k in range(n): ac += (i+j+k) print(ac).

¿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). 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). 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. 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.

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)?. Significa que en el peor caso el algoritmo siempre hará menos de n comparaciones. Significa que en el peor caso el algoritmo no hará ninguna comparación. Significa que en el peor caso el algoritmo hará n comparaciones. Significa que en el peor caso el algoritmo hará siempre más de n comparaciones.

Para cada uno de los algoritmos básicos y/o técnicas de procesamiento generales que se indican en la columna de la izquierda, seleccione la expresión en notación Big O que mejor expresa el tiempo de ejecución de ese algoritmo en el peor caso: Búsqueda secuencial en un arreglo (ordenado o desordenado). Ordenamiento por selección directa. Multiplicación de matrices cuadradas de tamaño n*n. Ordenamiento rápido (Quicksort) (Considere aquí el tiempo para el caso promedio). Acceso directo a un casillero de un vector. Búsqueda binaria en un arreglo ya ordenado.

¿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...). 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. La estrategia de Fuerza Bruta se basa en aplicar ideas intuitivas y directas, simples de codificar, pero normalmente produce algoritmos de mal rendimiento en tiempo de ejecución y/o de espacio de memoria empleado. 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.

¿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)?. 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. 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 exito.

Para problema general nombrado en la columna de la izquierda, seleccione la estrategia de planteo de algoritmos que se sabe haya resultado más útil para resolver ese problema, o bien la que sea que haya podido aplicarse para resolverlo aún sin llegar a una solución eficiente (considere a cada problema en su situación más general, y no casos particulares de cada uno): Ordenamiento rápido (Quicksort). Problema de la alineación de secuencias. Problema de las Ocho Reinas. Problema del árbol de expansión mínimo de un grafo. Problema del Viajante. Generación de gráficos fractales.

¿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). Algoritmo Quicksort para ordenamiento de arreglos. . Algoritmo Heapsort para ordenamiento de arreglos. Algoritmo Mergesort para ordenamiento de arreglos. Algoritmo Shellsort 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?. 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. 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. 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. 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.

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...). 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. 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. 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...). 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, 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]). 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.

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...). 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. 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. La cantidad total de diagonales que contiene el tablero (sumando todas las diagonales de todos los tipos posibles) es 30. 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).

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...). 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. 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)]. 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]. 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...). 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)]. 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]. 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].

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...). rc = [3, 5, 7, 0, 5, 1, 2, 4]. rc = [4, 7, 3, 0, 2, 5, 1, 6]. rc = [5, 3, 6, 0, 7, 1, 4, 2]. rc = [2, 0, 7, 4, 5, 1, 6, 3].