TEMA ALGORITMOS

Question 1

1.- ¿En que consiste la tecnica de Backtracking?

Answer 1

Tecnica de diseño de algoritmos que se basa en la idea de probar todas las soluciones (de un arbol o conjunto de posibles soluciones)
Categoria: Fuerza Bruta
NOTA: Tipicamente se usa Recursividad (aunque no es imprescindibleO

Question 2

2.- ¿Que requisito tiene el algoritmo de la busqueda binaria y que complejidad computacional tiene?

Answer 2

a) los elementos deben de estar ordenados
b) 0(log n)

Question 3

3.- Ordene, de mas eficiente a menos, estas complejidades: n!, nlogn, n^2, 2^n

Answer 3

nlogn
n^2
2^n
n!

Dani lo puso en linea, yo lo pongo así porque me entero mejor.

Question 4

4.- ¿En que consiste cada iteracion del algoritmo Radix-Sort?

Answer 4

Se obtiene el digito n-esimo (Ej. Radix Sort LSD y el número 3478)

Question 5

5.- De una definición de la propiedad de “estabilidad” en los algoritmos de ordenación

Answer 5

mantiene (después de ordenar) el orden relativo que tuvieran ciertos registros con la misma clave

p.ejemplo.
4 1’’ 2 3 1’ 5 6 —> 1’’ 1’ 2 3 4 5 6

los 1 prima y 1 prima prima, los deja en la posición que los encuentra.
Busca el lugar que le corresponde (en el array ya ordenado) y lo mete, pero si al buscar hace una búsqueda binaria es inserción binaria y no directa.

Question 6

6.- ¿En que consiste el algoritmo de insercion binaria?

Answer 6

Busca el lugar que le corresponde

Question 7

7.- ¿El algoritmo de ordenacion BubleSort siempre presenta un complejidad O(n^2)?

Answer 7

En general de un algoritmo podemos estudiar/analizar/calcular su complejidad asintotica en ..
a) Mejor caso <— Omega
b) Peor caso <– Mas usada 0(…)
c)caso medio <—theta
En la burbuja
a) medio y peor –> 0(n^2)
b)Mejor –> 0(n) <– porque es un algoritmo natural/adaptativo (que se da uenta de que los adtos pueden ya estar ordenados)

Question 8

8.- ¿Que requisito necesita cualquier función recursiva?

Answer 8

Condicion de salida/parada —> caso BASE

Question 9

9.- ¿Como explicaría el mecanismo que se produce en una llamada a una función?

Answer 9

g() {
…
…
…
x <– F(2,3)
… <— esto seria la instruccion donde “retorno”
…
}
f(a,b) {….. retorno a*ab}

Paso1) los parametros de entrada (numeros 2 y 3) de la funcion se colocan en la “Pila” (zona de la memoria)
Paso2) Se coloca en la “Pila” la dirección de retorno
Paso3) Se invoca a la funcion f()
Paso4) Ponemos en la “Pila” el valor de retorno (ej a*b)
Paso5) Devolvemos el control (salto) a la dirección de retorno (donde está la siguiente instrucción de g() por donde continuar)

Question 10

10.- ¿Que es la complejidad espacial?

Answer 10

Espacio “adicional” que necesita el algoritmo de ordenacion