Repaso ADA

¿Que tienen en comun los algoritmos de ordenacion QuickSort y MergeSort. La complejidad temporal de la division en subproblemas. La complejidad temporal de la combinacion de las soluciones. El numero de llamadas recursivas que hacen en el mejor de los casos.

¿Que complejidad se obtiene a partir de la realcion de recurrencia T(n) = 9T(N/3) + N^3 con t(1) = 0(1). 0(N^3). 0 (n log n). 0 (N^3 LOG N).

Se pretende resolver el problema del viajente de comercio mediante el esquema de vuelta atrás, ¿cual de los siguientes valores se espera que se comporte mejor para decidir sin un nodo es prometedor. La suma de los pesos de las k aristas restantes mas cortas, donde k es el numero de cuidades que quedan por visitar. El valor que se obtiene de multiplicar k por el peso de la arista mas corta de entre las restantes, donde k es el numero de cidades que quedan por visitar. La suma de los pesos de las aristas que completan la solucion paso a paso visitando el vertice mas cercano al ultimo visitado.

Dado un problema de minimizacion resuelto mediante un esquema de ramificacion y poda, ¿que ocurre si la cota optimista resulta ser un valor excesivamente pequeño?. que se podria podr el nodo que conduce a la solucion optima. que se podria explorar mas nodos de los necesarios. que se podria explorar menos nodos de los necesarios.

el esquema de vuelta atras. las otras dos opciones son ambas verdaderas. garantiza que encuentra la solucion optima a cualquier problema de seleccion discreta. se puede aplicar a cualquier tipo de problemas aunque el coste es temporalmente elevado.

¿cual de las siguientes estrategias de busqueda es mas apropiada en un esquema de vuelta atras?. ninguna de las otras dos estrategias es compatible con el esquema de vuelta atras. explorar primero los nodos con mejor cota optimista. explorar primero los nodos con mejor valor hasta el momento en la funcion que se pretende optimizar.

de las siguientes expresiones, o bien dos son verdadera y una es falsa, o bien dos son falsas y una es verdadera. marca la que es distinta a las otras dos en ese sentido. n + n log 2 n pertenece a omega(n + n log 2 n). 0(n^2) C 0 (2 ^log 2 n). omega(n^2) C omega(n).

Dado el problema del laberinto con tres movimientos, se desea saber el numero de caminos distintos desde la casilla inicial(1,1) hasta la casilla (n.m) y para ello se aplica un esquema de divide y vencerás.¿Cual seria la reccurrencia apropiada para el caso general?. nc(n,m) = nc(n-1, m) * nc(n, m - 1) * nc(n-1, m-1). ninguna de las otras dos. nc(n,m) = nc(n-1, m) + nc(n, m - 1) + nc(n-1, m-1).

Dado el problema de las torres de Hanoi resuelto mediante divide y venceras, cual expresa mejor su complejidad temporal. 2T(n - 1) + n. 2T(n - 1) + 1. T(n - 1) + n.

Se desea obtener todas las permutaciones de una lista compuesta por n elementos. ¿que esquema es el mas adecuado?. divide y venceras, puesto que la division en sublistas se podria hacer en tiempo constante. ramificacion y poda, puesto que con buenas funciones de cotas es mas eficiente que el vuelta atras. vuelta atras, es el esquema mas eficiente de este problema.

De las siguientes expresiones, o bien son dos verdaderas y una es falsa, o bien son dos falsas y una verdadera. Marca la que es en ese sentido distinta. omega(n^2) C omega (n^3). 0(n^2) C 0(n ^3). promedio(n^2) C promedio (n^3).

En un problema de optimizacion, si el dominio de las deciones es un conjunto infinito. es probable que a traves de programacion dinamica se obtenga un algoritmo eficaz que lo solucione. podremos aplicar el equema de vuelta atras siempre que se trate de un conjunto infinito numerable. una estrategia voraz puede ser la unica alternativa.

En el esquema de vuelta atras, los mecanismos de poda basados en la mejor solucion hasta el momento. garantiza que no se va a explorar todo el espacio de soluciones. las otras opciones son ambas verdaderas. pueden eliminar vectores que representan posibles soluciones factibles.

decid cual de estas tres estrategias proveeria la cota pesimista mas ajustada al valor optimo de la mochila discreta. asumir que ya no se van a coger mas objetos. completar las decisiones restantes basandose en la mejor solucion vorz que pueda encontrarse para los objetos restantes y espacio disponible en la mochila. el valor de una mochila que contiene todos los objetos aunque se pase del peso maximo permitido.

Se desea ordenar una lista enlazada de n elementos adaptando el algoritmo mergesort. En este caso, al tratarse de una lista, la complejidad temporal asintotica de realizar la division en subproblemas resulta ser lineal con el tamaño de esa lista ¿cual seria entonces el coste temporal de realizar dicha ordenacion?. promedio(n^2). ninguna es correcta. promedio(n log n).

Un algoritmo recursivo basado en el esquema de divide y venceras. alcanza su maxima eficiencia cuando el problema de tamaño n se divide en a problemas de tamaño n/a. nunca tendrá un coste temporal asintotico exponencial. ambas son verdaderas.

dado un problema de minimizacion resuelto mediante un esquema de ramificacion y poda, ¿que propiedad cumple la cota optimista?. siempre es mayor o igual que la mejor solucion posible alcanzada. las otras dos son falsas. asegura un ahorro en la comprobacion de todas las soluciones factibles.

dado el problema del laberinto con tres movimientos, ¿cual de las estrategias siguientes proveeria de una cota optimista para ramificacion y poda?. Suponer que en adelante todas las casillas del laberinto son accesibles. las dos estrategias son ambas validas. suponer que ya no se van a realizar mas movimientos.

El algoritmo de ordenacion quicksort divide el problema en dos subproblemas. ¿cual es la compeljidad temporal asintotica de realizar esa division. promedio log n. promedio n. promedio n log n.

La siguiente relacion de recurrencia expresa la complejidad de un algoritmo T(n) = 2T (n/2) + g(n) en otro caso y 1 si n<= 1. Si g(n) pertenece a promedio de (n), la relacion es del mergesort. Si g(n) pertenece a promedio de (1), la relacion es de busqueda dicotomica. Si g(n) pertenece a promedio de (n^2), la relacion es del insercion binaria.

de las siguientes afirmaciones, marca la que es verdadera. las cotas pesimistas no son compatibles con un esquema de vuelta atras. en un esquema de vuelta atras, las cotas pesimistas no tienen sentido si lo que se pretende es obtener todas las soluciones factibles. el esquema de vuelta atras no es compatible con el uso conjunto de cotas pesimistas y optimistas.

En un algoritmo de optimizacion resuelto mediante ramificacion y poda, ¿podria encotntrarse la solucion optima sin haber alcanzado nunca un nodo hoja?. no, los nodos hojas son los nodos completados y por lo tanto hay que visitar al menos uno de ellos para almacenarlo como la mejor solucion al momento. si, pero esto solo podria ocurrir si se hace uso de cotas pesimistas. si, esto puede ocurrir incluso si no se hace uso de cotas pesimistas.

En ausencia de cotas optimistas y pesimistas, la estrategia de vuelta atras. no se puede usar para resolver problemas de optimizacion. no recorre todo el arbol si hay manera de descartar subarboles que se representen conjuntos de soluciones no factibles. debe recorrer siempre todo el arbol.

cual de estos problemas tiene una solucion eficiente utilizando programacion dinamica. el problema de la asignacion de tareas. la mochila discreta con pesos y valores reales positivos. el problema del cambio.

en el problema del viajante de comercio queremos listar todas las soluciones factibles. lo mas adecuado seria usar una tecnica de ramificacion y poda ya que es muy importante el orden en el que se explorar las soliciones parciales. el orden en el que se exploran las soluciones parciles no es relevante, por ello, la tecnica de ramificacion y poda no aporta nada con respecto a la vuelta atras. lo mas importante es conseguir una cota pesimista adecuada, las diferentes entre ramificacion y poda y vuelta atras son irrelevantes en este caso.

Queremos resolver mediante vuelta atras el problema de las 8 reinas(colocar 8 reinas en un tablero de ajedrez de manera que no se maten mutuamente) Una buena cota optimista permitiria. No es aplicable este tipo de podas a este problema. muy probablemente, explorar menos nodos. muy problablemente, resolver el problema de forma mas rapida.

Si f no pertenece a 0(g1) y f pertenece a 0(g2) entonces siempre se cumplirá que. f pertece al omega(min(g1,g2). f no pertece a 0(max(g1,g2)). f pertece a omega(g1 + g2).

con respecto a la complejidad espacial de los algoritmos de ordenacion quicksort, heapsort, y mergesort. las complejidades espacial de todos ellos es lineal con el tamaño del vector a ordenar. mergesort y heapsort tienen complejidad espacial lineal, con el tamaño del vector a ordenar, la de quicksort es constante. mergesort tiene compeljidad espacial lineal con el tamaño del vector, la de los otros dos es constante.

Si lim n-> infinito f(n)/g(n) = infinito entonces. f(n) pertenece a 0 (g(n)). f(n) pertenece a omega (g(n)). f(n) pertenece a theta (g(n)).