EDD Y ALGORITMOS Flashcards
¿En que consiste la tecnica de Backtracking?
Tecnica de diseño de algoritmos basada en explorar todo el “arbol” de posibles soluciones (prueba y error) –> Fuerza Bruta
NOTA: Una posible optimizacion para no “repetir” calculos seria Ramificacion y Poda
¿Que requisito tiene el algoritmo de la busqueda binaria y que complejidad computacional tiene?
a) Que los datos estén ordenados (array, arbol, …)
b) O(log n)
Ordene, de mas eficiente a menos, estas complejidades: n!, nlogn, n^2, 2^n
n log(n) - n^2 - 2^n - n!
¿En que consiste cada iteracion del algoritmo Radix-Sort?
En distribuir en las colas/urnas los numeros segun un determinado digito (unidades,decenas,centenas,… o al reves)
NOTA: Necesitamos de un “espacio” adicional
De una definición de la propiedad de “estabilidad” en los algoritmos de ordenacion
Mantiene el orden relativo original para claves iguales
¿En que consiste el algoritmo de insercion binaria?
Que mediante busqueda binaria obtenemos el lugar donde insertar el elemento a ordenar en cada iteracion
¿El algoritmo de ordenacion BubleSort siempre presenta un complejidad O(n^2)?
No, en el mejor de los casos seria O(n) -> Se da cuenta si los datos ya están ordenados
¿Que requisito necesita cualquier función recursiva?
Una condicion de parada (CASO BASE)
¿Como explicaría el mecanismo que se produce en una llamada a una función?
Cuando se llama a una funcion
g(a,b) {
var d,e;
....
....
f(b) ----------------> f(b) { .... return ...}
.... (1)
....
}
se introducen en la "pila" los siguientes datos:
a) Parametros de entrada
b) Variables locales
c) DIRECCION DE RETORNO (1)
d) Valor de retorno
¿Que es la complejidad espacial?
Representa la cantidad de espacio adicional (a los datos de entrada) que necesita el algortimo
¿En que consiste un max-heap?
Un arbol binario (monticulo) cuya raiz es el elemento mayor de todos los del arbol
NOTA: Esta propiedad se cumple en cualquier nivel
¿A que TAD pertenecen las primitivas push y pop?
TAD Pila (LIFO)
¿En que consiste una “colision” en una tabla Hash?
Una colision se da cuando aplicando el algoritmo de hash a la distintas “keys” dan el mismo resultado (indice de la tabla)
Definicion de grado de un nodo y orden del arbol
a) grado(nodo) –> nº de hijos que tiene un nodo en un momento determinado (limitado por el orden del arbol)
b) orden(arbol) –> nº MAXIMO de hijos que PUEDE tener cualquier nodo
Definicion de altura y profundidad de un nodo
a) altura(nodo) –> nº de aristas desde ese nodo hasta el nodo hoja mas alejado
b) profundidad(nodo) –> nº de aristas desde ese nodo hasta la raiz
