0% encontró este documento útil (0 votos)
68 vistas12 páginasParcial 5
Cargado por
Marcos Garcia RamirezDerechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF o lee en línea desde Scribd
0% encontró este documento útil (0 votos)
68 vistas12 páginasParcial 5
Cargado por
Marcos Garcia RamirezDerechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF o lee en línea desde Scribd
s9/tti21 20:38 Parla § [para Aprobaciin Drecta 0 Promocién) [A Distancia}: Revision del inento
Pigina Principal / Mis cursos / AED (2021) / 14 de noviembre 20 de naviemive
1 Pavcial $ jpara Aprobacién Diracta © Promocién] /A Distancia]
Comenzado el viernes, 19 de noviembre de 2021, 13.47
Estado Finalizado
Finalizade en viernes, 19 de noviembre de 2021, 14°17
‘Tiempo 20 minutos 4 segundos
‘empleado
Puntos 16/20
Calificacion 8 de 10 (60%)
Prequna 1
Suponga que dispone de cuatro algoritmos ciferentes para resolver el mismo problema, y que se sabe que los tempos de ejecucién (en
peor caso) son, respectivamente: Ofn*lag(n)), O(n?) Ofn3) y O(n).
{Cul de esos tes algorimos deberlaelegit, suponiendo que todos hacen el mismo consumo razonable de memoria?
Seleccione una
a. Hlalgoritmo cuyo tiempo de elecucién es O(n?)
b._Elalgoritmo cuyo tiempo de ejecucion es O(n")
Hlalgoritmo cuyo tiempo de ejecucién es O(n) YY iCorectolEfectivamente este
algaritmo seria el més pido.
4. Hlalgoritme cuyo tiempo de ejecucién es O(n"login))
iCorrectol
a respuesta correcta es
El algoritme cuyo tiempo de ejecucién es O(n)
htpssfuv te utn edu arimodiquziroviow php?atiompt=1213147&emid=231326 ne s9/tti21 20:38 Parla § [para Aprobaciin Drecta 0 Promocién) [A Distancia}: Revision del inento
regina
Que significa decir que un algoritmo dado tiene un tiempo de eecuci6n O(n)?
Seleccione una
EL proceso normalmente consist en dos ciclos (uno dentro del otro) de aproximadamente n iteraciones cada uno, \Correcto!
de forma que las operaciones critcas se aplican un nimero euadritic de veces.
b. El tiempo de ejecucién es constant, sin importarla cantidad de datos,
Armedida que aumenta el nimero de datos, aumenta el tiempo pero en forma muy suave: el conjunto de datos se divide en dos. se
pprocesa una de las mitades, se desecha la otra se repte el proceso hasta que no pueda volver a dividirse la mitad que haya
quedad
4. Flsiempo de ejecucin es neal: si aumenta el nimero de datos, aumenta el tiempo en la misma proporcién,
\Correcto!
La respuesta correcta es:
El proceso normalmente consiste en dos ciclos (uno dentro del otro) de aproximadamente 1 iteraciones cada uno, de forma que las
operaciones erticas se aplican un nero cuadritico de veces.
regina 3
Con qué nombre general se conace en la Teoria de la Complejidad a un problems para el cual sélo se conocen algoritmas cuye tiempo de
ejecucian es exponencal (0 sea, problemas para los que todas las soluciones conacidas son algoritmos con tiempo O2")?
Seleccione una
2. Problemas Iresolubles
b._Problemas imperdonables
Problemas Inmanejables
4. Problemas intratables Y icorecto!
iCorectol
La respuesta correcta es:
ProblemasIntratables
htpssuv te utn edu arimodiquziroviow php?atiompt=1213147&emid=231326 ane s9/tti21 20:38 Parla § [para Aprobaciin Drecta 0 Promocién) [A Distancia}: Revision del inento
regina
{Cuil esa principal caracerstca de todos los métodos de ordenamiiento conacidos como métodos simples o directos?
Seleccione una
3. Son muy ficiles de programar.
b. Son muy veloces para cualquier tamafo del areglo a ordenar.
._Tienen un tiempo de ejecucion de orden cuadratico, Y icorecto!
4. Tienen un tiempo de ejecucion de orden lineal
‘Correcto!
La respuesta correcta es:
Tienen un tiempo de ejecucién de orden cuadrético,
Pequna 5
Si los algaritmos de ordenamiento simples tienen todos un tiempo de ejecucién Of’) en el peor caso, entonces: icémo explica que las
‘ediciones efectvas de los tiempos de elecucién de cada Uno sean diferentes fente al mismo arreglo?
Seleccione una
a. La notacién Big O rescata el término més signifcativo en la expresién que calcula el rendimiento, descartandoY Correct!
constantes y otfostérminos que podiian no coincidir en ls tes algoritms.
b. Los tiempas deben coincidi. Si hay diferencias, se debe a errores en los intrumentes de medicién o a un planteo incorrecto del
proceso de medicion,
._Lanotacién Big O no se debe usar para estimar el comportamiento en el peor caso, sina sélo para el caso medio.
4. La notacién Big O no se usa para medir tempos sino para contar comparaciones u otro elemento de interés. Es un error, entonces,
decir que los tiempos tienen "arden n cuadrado’.
‘Correcto!
a respuesta correcta es
La notacién Big O rescata el término més significative en la expresién que calcula el rendimiento, descartando constantes y otros téminos
que podtian no coincicr en les tes algoitmos.
htpssuv te utn edu arimodiquziroviow php?atiompt=1213147&emid=231326 ana s9/tti21 20:38 Parla § [para Aprobaciin Drecta 0 Promocién) [A Distancia}: Revision del inento
regina 6
Si se realiza un analisis preciso del ordenamiento por Seleccién Directa para un arreglo de n componentes, se llega a Ia conclusién que ese
algoritme hard n-1 pasadas, con n-1 comparaciones en la primera, n-2 en la segunda, y asi sucesivamente reduciendo de a 1 lacantidad de
comparaciones hasta hacer sélo una comparacién en la ikima pasada, Por lo tanto, el algoritmo hard invariablemente una cantdad total de
‘240? ~ 0) comparaciones, Sabiendo esto, scales de las siguientes expresiones son correctas para describ ly cantidad de comparaciones
ue hard el algoritmo, usando distintos tipes de notaciones? (Mas de una respuesta puede ser correcta. Marque TODAS las que considere
correctas)
Seleccione una 0 mas de una:
Cantidad de comparaciones: ofa?) 2% Incorrecto..|a natacién litle o supene que la funcién
analizada se mantenci siempre menor que la funcion de
orden.
Cantidad de comparaciones: (0?) Y correcto!
Cantidad de comparaciones: (m2) Y icomecto!
1. Cantidad de comparaciones: O(n?) Y icorrecto!
a5 respuestas corectas son
Cantidad de comparaciones: O(n
Cantidad de comparaciones: (0%),
Cantidad de comparaciones: O(a?)
regina 7
En cules de Ias siguientes situaciones el uso de recursividad esta efectivamente recomendado? (Mas de una respuesta puede ser valida,
Marque todas las que considere correctas)
Seleccione una 0 mis de una:
a. Nunca
b. Generaciin y procesamianto de imagenes y grifcos fractales (figuras compuestas por versiones més simples de IY Correct!
-nvsma figura original,
._ Siempre que se pueda escribir una definicibnrecursva del problema,
4. Recorrde y procesamiento de estructuras de datos no lineales com dtboles y grafos. Y icorecto!
‘Correcto!
Las respuestas correctas son
Recorrido y procesamiento de estructuras de datos no ineaes como arboles y grafos.
Generacin y procesamiento de imagenes y grificos fractals (guras compuestas por versiones més simples de la misma figura origina.
1219147 Bemid=291926 ana
htpssiuv te uln edu [Link]?atiomy 9/1121 20:38 Parla § [para Aprobaciin Drecta 0 Promocién) [A Distancia}: Revision del inento
regina B
CConsidere a siguiente funcién (vista en clases) basada en backtracking para resoluci6n del Problema de las Ocho Reinas,¢ indique cusl de
las opciones que se muestran es correcta
lef intend(col):
global rc, qr, gid, and
fil, res = -1, False
while not res and #11 I= 7:
res = False
filed
di = col + fil
@n = (col - #11) +7
Af qr[ Fil] and gic[di] and qnd{an]:
refcol] = #42
‘ar[Fil] = qid[éi] = qnd[dn] = False
Af col <7:
res = intend(col + 1)
if not res:
ar fil] = qidfdi] = qnd{dn] = True
a
rc{col]
else:
res = True
return res
Seleccione una
La funcién no es correcta porque qr debe sefialar las columnas disponibles y no las fas.
b. La funcién no es correcta porque no debe asignarse a refeol] el valor de -1 X incorrecto... sa asignacién es
Vilda en el algoritme,
La funcién no es correcta porque la diagonal normal debe almacenar valores (columna + fila)
4. La funcién es correcta y funciona sin problemas.
Revise el funcionamiento y la explicacion de este algoritmo en la Ficha 28
a respuesta correcta es
La funcién es correcta y funciona sin problemas.
htpssuv te utn edu arimodiquziroviow php?atiompt=1213147&emid=231326 en2 9/1121 20:38 Parla § [para Aprobaciin Drecta 0 Promocién) [A Distancia}: Revision del inento
regina
Suponga que se quiere plantear una definicién recursiva del concepto de bosque. :Cusl de las siguientes propuestas generales es corecta
y consttuye Ia mejor definicién?
Seleccione una
a. Un bosque es un conjunte que puede contener no © més drboles% — incorrecto..Si bien esta definiién es reeursiva, produce
_agrupados con otro bosque. Luna regresin infnta..y porlo tanto ests incomplete
b. Un bosque es un conjunto de arboles que puede estar vaco, o puede contener n Srboles (con n > 0}
Un bosque es un conjunto de arboles que puede estar vacio, o puede contener uno o mas rboles agrupadas con otro basque.
Un bosque es un bosque.
Revise la Ficho 26, pagina 535,
La respuesta correct
Un bosque es un conjunto de drboles que puede estar vaco, o puede contener uno o mis Srboles agrupados con otro bosque.
Prequna 10
2Qué elementos son necesari para que una funcién recursva se considere bien planteado?
Seleccione una
La funcién debe tener al menos un ciclo en su bloque de acciones y ese ciclo debe estar plantendo de forma tal que nunca entre en
‘un L220 infnito.
La funci6n deben tener al menos una invocacién asi misma en su bloque de acciones.
La funcién debe tener al menos una invecacién a si misma en su bloque de accianes, y después de esas invocaciones debe tener
‘una o mis condiciones de control que permitan interrumpir el proceso recusivo sis ha legado a alcanzar alguna de las situaciones
‘rviales o base del problems,
La fncién debe tener al menos una invacacién a si misma en su bloque de acclones,y antes de esas invocaciones Correct!
debe tener una 0 més condiciones de control que permitan interrumpir el proceso recusiva si se ha legado 2
aleanzar alguna de las situaciones tiviales o base del problema,
iCorectal
a respuesta correcta es:
La funcidn debe tener al menos una invocacion a si misma en su bloque de acciones, y antes de esas invocaciones debe tener una o més
condiciones de control que permitan interrumpir el proceso recurso si se ha lagado a aleanzar alguna de las situacionestrvaleso base del
problema,
htpssuv te utn edu arimodiquziroviow php?atiompt=1213147&emid=231326 enz 9/1121 20:38 Parla § [para Aprobaciin Drecta 0 Promocién) [A Distancia}: Revision del inento
Pagina 1
{Qué hace el siguiente programa (que inchye una funciénrecursivay?
‘ef repetin(numero, rep, res):
if rep I= 6
es append(numero)
repetir(nunero, (rep - 1), res)
13,3, 71
es = []
‘or 4 in range(len(v)):
repetir(v[i], 2, res)
rint(res)
Seleccione una
a. Produce un error de jecucién, porque la funcién recutsiva no tiene valor de retorno.
b. Genera y muestra un nuevo vector res con los nimeros que en el vector original v eran negatives,
Genera y muestra un nuevo vector res con cada elemento del vector orginal vrepetido dos veces, Y corecto!
4. Produce un error de ejecucién alintentar el print) final ya que el vector res no es generado en ningtn momento.
iCorectal
La respuesta correcta es:
Genera y muestra un nuevo vect
res con cada elemento del vector original v repetid dos veces
regina 12
{Cuil sla cantidad de niveles del drbol de invocaciones recursivas que se genera al ejecutar el Quicksort para ordenar un arreglo de
elementos, en el caso promedio? (Es deci ,CuSl es Ia altura de ese rol en el caso promedio?)
Seleccione una
a Altura =a
b. Altura = nt
© Altura =n * Logiad
. Altura = Login) Y icorrecto!
\Correcto!
La respuesta correcta es:
Altura = log(n)
htpssuv te utn edu arimodiquziroviow php?atiompt=1213147&emid=231326 m2 s9/tti21 20:38 Parla § [para Aprobaciin Drecta 0 Promocién) [A Distancia}: Revision del inento
regina 13,
eCuales de las siguientes afrmaciones son correctas respecto de las caractersticas de los algoritmos avides? (Ms cle una puede ser cieta,
pporla que marque todas las que considerevsldas)
Seleccione una o mis de unas
a Aplican una regla formal global o general en cada paso proceso, buscando lograr® Incorrecte... Estos algoritmos hacen (en
‘una solucién 6ptima local ‘esencia) justamente lo contraro.
Los algortmas para obtener el camino més corto entre dos nodos de un graf © para obtener el érbal de expansin minimo de un
4grafo, son ejemplo de este tipo de algoritmos,
La generacin de grficos fractals es un ejemplo de este tipo de algoritmos.
4. [Link] es un ejemplo de este tipo de algoritmos
Aplican una regla intuitvamente vilida en cada pasa local del proceso, buscando lograr una solucién global jCorrecto!
