¿Cuáles de las siguientes propuestas generales son ciertas en relación al segmento de memoria conocido como Stack Segment?
Seleccione una o más de una: 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 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. 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 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.
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í:
___author__ 'Cátedra de AED'
def menu():
print('1. Opcion 1')
print('2. Opcion 2')
print('3. Salir')
op = int(input('Ingrese opcion: '))
if op == 1:
print('Eligio la opcion 1...')
elif op == 2:
print('Eligio la opcion 2... ')
elif op == 3:
return
menu()
# script principal...
menu()
¿Hay algún problema o contraindicación respecto del uso y aplicación de esta versión recursiva para la gestión de un menú? Seleccione la respuesta que mejor describa este punto.
Seleccione una:
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. La versión recursiva que se mostró no funciona. Sólo permite cargar una vez la opción elegida, e inmediatamente se detiene. 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. 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.
Suponga que se desea generar Python el dibujo de un campo de edición de textos para una aplicación que simule una interfaz visual de usuario, como el que se muestra aquí (con las mismas proporciones y colores, aunque sin importar las coordenadas de visualización).
El siguiente programa está pensado para generar esa gráfica, pero dejando la función edit(canvas) sin hacer:
__author 'Cátedra de AED'
from tkinter import
def edit (canvas):
pass
def render():
# configuracion inicial de la ventana principal...
root = Tk()
root.title('Cuestionario')
# calculo de resolucion en pixels de la pantalla...
maxw= root.winfo_screenwidth()
maxh root.winfo_screenheight()
# ajuste de las dimensiones y coordenadas de arranque de la ventana... root.geometry("%dx%d+%d+%d" % (maxw, maxh, 0, 0))
# un lienzo de dibujo dentro de la ventana...
canvas = Canvas (root, width-maxw, height=maxh) canvas.grid(column=0, row=0)
# desarrollar la gráfica...
edit (canvas)
# lanzar el ciclo principal de control de eventos de la ventana... root.mainloop()
if
name
'__main__':
render()
¿Cuál de las siguientes versiones de la función edit(canvas) permitiría dibujar la gráfica sugerida? def edit (canvas):
x, y, ancho, alto 100, 100, 100, 25
# el fondo y el texto del campo de edición...
canvas.create_rectangle((x, y, x+ancho, y+alto), fill='white') canvas.create_text (x-25, y+alto//2, text='Valor: ', fill='black')
for fin range (2):
#los bordes oscuros...
canvas.create_line ((x+f, y+f, x+ancho-f, y+f), fill='dark gray') canvas.create_line((x+f, y+f, x+f, y+alto-f), fill='dark gray')
# los bordes claros...
canvas.create_line ((x+f, y+alto-f, x+ancho-f, y+alto-f), fill='white') canvas.create_line ((x+ancho-f, y+alto-f, x+ancho-f, y+f), fill='white') def edit (canvas):
x, y, ancho, alto 100, 100, 100, 25
# el fondo y el texto del campo de edición...
canvas.create_rectangle ((x, y, x+ancho, y+alto), fill='white') canvas.create_text(x-25, y+alto//2, text='Valor: ', fill='black')
for fin range (2):
# los bordes oscuros...
canvas.create_line ((x+f, y+f, x+ancho-f, y+f), fill='white') canvas.create_line ((x+f, y+f, x+f, y+alto-f), fill='white')
# los bordes claros...
canvas.create_line((x+f, y+alto-f, x+ancho-f, y+alto-f), fill='dark gray') canvas.create_line ((x+ancho-f, y+alto-f, x+ancho-f, y+f), fill='dark gray').
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.
¿Cuál es la estimación para el tiempo de ejecución de ambos algoritmos? Versión iterativa: tiempo proporcional a n (lineal) - Versión recursiva: tiempo proporcional a n (lineal)
Versión iterativa: tiempo proporcional a b" (exponencial para algún b> 1) - Versión recursiva: tiempo proporcional a in (lineal) Versión iterativa: tiempo constante (no depende de n) Versión iterativa: tiempo proporcional a n (lineal).
Sabemos que la recursión es una de las técnicas o estrategias básicas para el planteo de algoritmos y que una de sus ventajas es que permite el diseño de algoritmos compactos y muy claros, aunque al costo de usar algo de memoria extra en el stack segment y por consiguiente también un algo de tiempo extra por la gestión del stack. Algunos problemas pueden plantearse en forma directa procesando recursivamente diversos subproblemas menores. Tal es el caso de la sucesión de Fibonacci, en la cual cada término se calcula como la suma de los dos inmediatamente anteriores [esto se expresa con la siguiente relación de recurrencia: F(n) = F(n-1) + F(n-2) con F(0) = 0 y F(1) = 1]. La función sencilla que mostramos a continuación que calcula el término n-ésimo de la sucesión en forma recursiva:
def fibo (n) :
if n <= 1:
return 1
return fibo (n-1) + fibo (n-2)
Sin embargo, un inconveniente adicional es que la aplicación directa de dos o más invocaciones recursivas en el planteo de un algoritmo podría hacer que un mismo subproblema se resuelva más de una vez, incrementando el tiempo total de ejecución. Por ejemplo, para calcular fibo(4) el árbol de llamadas recursivas es el siguiente: (ver imagen)
y puede verse que en este caso, se calcula 2 veces el valor de fibo(2), 3 veces el valor de fibo(1) y 2 veces el valor de fibo(0)... con lo que la cantidad de llamadas a funciones para hacer más de una vez el mismo trabajo es de 7 (= 2 + 3 + 2).
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)?
Seleccione una: 10 0 11 12.
¿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). Siempre que se pueda escribir una definición recursiva del problema. Generación y procesamiento de imágenes y gráficos fractales (figuras compuestas por versiones más simples de la misma figura original). Nunca. Recorrido y procesamiento de estructuras de datos no lineales como árboles y grafos.
¿Cuáles de las siguientes son CIERTAS en relación al sistema de coordenadas de pantalla?
Seleccione una o más de una:
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. 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.
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?
Seleccione una: 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 que puede contener uno o más árboles agrupados con otro bosque. 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.
¿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)?
Seleccione una o más de una: El diseño de la interfaz de usuario. El consumo de memoria. La complejidad aparente del código fuente.
El tiempo de ejecución.
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:
¿Cuá es el problema (si lo hubiese) con esta versión de la función?
Seleccione una: 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.
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:
(imagen)
¿Es correcto el siguiente planteo de la función producto(a, b)?
def producto (a, b):
if a == or b == 0:
return 0
return a producto (a, b-1)
Seleccione una: Si. Es correcto. No. La función sugerida siempre retornará 0, sean cuales fuesen los valores de a y b. No. La última línea debería decir return a + producto(a-1, b-1) en lugar de return a + producto(a, b-1). No. La propia definición previa del concepto de producto es incorrecta: un producto es una multiplicación, y no una suma...
¿Cuál es la principal característica de todos los métodos de ordenamiento conocidos como métodos simples o directos?
Seleccione una: 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.
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.
¿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?
Seleccione una: 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 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 vaya acomodándose al final del arreglo. 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..
¿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?
Seleccione una: 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. 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 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?
Seleccione una: 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. 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. 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.
¿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?
Seleccione una: 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) No es cierto que la versión vista en clases use una bandera de corte La bandera de corte se usa para terminar el proceso apenas se detecte que en la pasada actual no hubo intercambios, para
ahorrar tiempo. La bandera de corte se usa para garantizar que el arreglo quede ordenado.
.
¿Cuál de los siguientes es el creador del famoso algoritmo de ordenamiento conocido como Quicksort?
Seleccione una: Edsger Wybe Dijkstra Donald Shell Charles Antony Richard Hoare
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)
Seleccione una o más de una: 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 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} 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.
¿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} ?
Seleccione una: El arreglo no quedará ordenado al final. 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. Ningún problema: esa serie es tan buena como cualquier otra No sólo no hay ningún problema, sino que esa serie es la mejor posible para el algoritmo Shellsort.
.
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?
Seleccione una: 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 No es obligatorio que lo haga, pero favorece un ordenamiento más rápido Con h = 1 el algoritmo se convierte en un ordenamiento por inserción simple, y sólo entonces garantiza que el arreglo quede
ordenado.
¿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)
Seleccione una o más de una: 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 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 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 es muy eficiente en tiempo de ejecución, tanto para el caso promedio como para el peor caso. .
¿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?
Seleccione una: Peor caso: O(n^2) comparaciones. Peor caso: O(n) comparaciones. Peor caso: O(1) comparaciones.
Peor caso: O(log(n)) comparaciones.
¿Cuál es la diferencia entre el peor caso y el caso promedio en el análisis de algoritmos?
Seleccione una: 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 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 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).
Seleccione una o más de una: La calidad aparente de la interfaz de usuario El consumo de memoria. El tiempo de ejecución. La complejidad aparente del código fuente.
¿Qué significa decir que un algoritmo dado tiene un tiempo de ejecución O(1)?
Seleccione una: El tiempo de ejecución es lineal: si aumenta el número de datos, aumenta el tiempo en la misma proporción 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 siempre es de un segundo, sin importar la cantidad de datos 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^2)?
Seleccione una: 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. El tiempo de ejecucíón es constante, sin importar la cantidad de datos. 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 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(n)?
Seleccione una: 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 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. 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(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 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. El tiempo de ejecución es lineal: si aumenta el número de datos, aumenta el tiempo en la misma proporción El tiempo de ejecucíón es constante, sin importar la cantidad de datos.
.
¿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(2^n )? Problemas Intratables Problemas Inmanejables
Problemas Irresolubles
Problemas Imperdonables.
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(n^2), O(n^3) y O(n).
¿Cuál de esos tres algorimos debería elegir, suponiendo que todos hacen el mismo consumo razonable de memoria?
Seleccione una El algoritmo cuyo tiempo de ejecución es O(n*log(n)) El algoritmo cuyo tiempo de ejecución es O(n^3) El algoritmo cuyo tiempo de ejecución es O(n) El algoritmo cuyo tiempo de ejecución es O(n^2).
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 ½(n - 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)
Seleccione una o más de una:
Cantidad de comparaciones: Θ(n^2) Cantidad de comparaciones: o(n^2) Cantidad de comparaciones: Ω(n^2) Cantidad de comparaciones: O(n^2).
¿Cuál es la principal característica de todos los métodos de ordenamiento conocidos como métodos simples o directos?
Seleccione una: 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)
Seleccione una o más de una: 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. 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 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. 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(n^1.5).
¿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?
Seleccione una: 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?
Seleccione una: 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(n^2) 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?
Seleccione una: 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) = 3n^3 + 5n^2 + 2n^1.5
¿Cuál de las siguientes expresiones representa mejor el orden del algoritmo para el peor caso?
Seleccione una: O(3n^3 + 5n^2 + 2n^1.5) O(n^1.5) O(n^3+ n^2) O(n^3).
¿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)
Seleccione una o más de una: Algoritmo Quick Sort: O(n*log(n)) en el caso promedio, pero O(n^2) en el peor caso. Algoritmo Shell Sort: O(n^2) en el peor caso para la serie de incrementos decrecientes vista en clase Algoritmos directos o simples: O(n^2) en el peor caso para todos ellos. Algoritmo Heap Sort: O(n*log(n)) tanto para el caso promedio como para el peor caso. .
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 seccion en la que se afirma que los dos subconjuntos que dependen del nodo raiz son conjuntos separados o mutuamente excluyentes La seccion en la que se afirma que los dos subconjuntos que dependen del nodo raiz pueden estar vacios La seccion en la que se afirma que del nodo raiz se desprenden dos subconjuntos La seccion en la que se afirma que el arbol puede estar vacio o puede contener un nodo designado como la raiz del arbol.
¿Cuál es la diferencia entre la abstracción de datos y la abstracción funcional?
Seleccione una: Ninguna. Son sólo dos formas de referirse al mecanismo de abstracción. 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. 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 astracción de datos y abstracción funcional. 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.
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?
Seleccione una: 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 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: 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. 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 v 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.
¿Cuál de las siguientes expresiones describe la forma de trabajo general de una Pila?
Seleccione una: OIFO (Ordered In - First Out) LIFO (Last In - First Out) FIFO (First In - First Out) OIRO (Ordered In - Random Out).
¿Cuál de las siguientes situaciones de programación es la principal aplicación de una Pila?
Seleccione una: 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. Procesar una secuencia de datos en orden aleatorio.
¿Cuál de las siguientes expresiones describe la forma de trabajo general de una Cola?
Seleccione una:
FIFO (First In - First Out) OIFO (Ordered In - First Out) LIFO (Last In - First Out) OIRO (Ordered In - Random Out).
¿Cuál de las siguientes situaciones de programación es la principal aplicación de una Cola?
Seleccione una: 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.
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 ¿Cual de las siguientes estrategias podria ser una forma básica de implementar una Cola de Prioridad en las condiciones aquí expresadas?
Seleccione una: 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 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: siempre al final. Eliminación: siempre el último 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.
¿Cuál de las siguientes es CIERTA respecto de los árboles binarios de búsqueda?
Seleccione una: 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 arbol h es O(log(n)). 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)).
¿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)
Seleccione una: Comparaciones por nivel: n Comparaciones por nivel: 1 (una) Comparaciones por nivel: n^2 Comparaciones por nivel: log(n).
Suponga que desconoce la forma gráfica de un árbol binario 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)
Seleccione una o más de una: Podra volver a dibujar el arbol si conoce la secuencia de recorrido en postorden y la secuencia de recorrido en entreorden. Podra volver a dibujar el arbol 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 preorden y la secuencia de recorrido en postorden.
¿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?
Seleccione una: Nunca. Sólo si el árbol es una diagonal con todos los hijos izquierdos nulos. Siempre. 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)?
Seleccione una: Que una búsqueda obligue a O(log(n)) comparaciones. Que una búsqueda obligue a O(n) comparaciones. Que una búsqueda obligue a O(2") comparaciones. Que una búsqueda obligue a O(n^2) 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).
Seleccione una o más de una: 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. 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 o más claves iguales podrán quedar separadas por dos o más niveles de distancia. Dos claves iguales quedarán siempre en el árbol una como hija derecha e inmediata de la otra.
¿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?
Seleccione una: 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. 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. 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. 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.
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?
Seleccione una: 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.
|
