Algoritmos Flashcards
Definición de Algoritmo
Conjunto de reglas que , aplicadas sistematicamente a unos datos de entrada apropiados, resuelven un problema en un número FINITO de pasos elementales
Medios de expresion de un algoritmo
— Sin matarnos —–
Diagrama de flujo (ISO) –> en UML diagrama de flujo
Pseudocódigo
Sistemas formales (Matematicos)
En el análisis y diseño de un algoritmo que dos complejidades existen
Espacial –> cantidad de almacenamiento que necesitas para ejecutar el algoritmo
Temporal –> Se refiere al tiempo de resolución, pero en en terminos cuantitativos sino cualitativos. Identifica a que famila pertence el algoritmo, lineal, logaritmico, exponencial…. etc
Clasificación de la complejidad temporal y concepto de asintota o cota superior
Una asintota o cota superior es ‘a donde’ se aproxima la complejidad temporal de mi algoritmo y esto marca su familia.
De mejor asintota a peor (‘O’ Big notation):
O(1) –> constante, no le afecta el tamaño del ejemplar ‘n’
O(log n) –> logaritmico
O(n) – Lineal
O(n log n)
O(n^a) –> Siendo n^2 la menor de todas
O(C^n) –> Constante elevado al tamaño del ejemplar ‘n’
O(n!)
O(n^n)
NOTA: Podemos tener cota inferior o asintota inferior (‘Ω’) y cota media o asintota media(‘θ’) .
Qué tecnicas conoces para analizar y diseñar algoritmos
Divide y venceras –> Vamos dividiendo el ‘array’ a la mitad y cada parte a la mitad hasta que podemos resolver el caso base. Luego combinamos todas la soluciones (suma). Dividir un problema en subproblemas y luego combinar su solución. Top down
Voraces –> En cada paso cogemos las solución local optima. Esto no significa que la solución global también sea optima!!. Algoritmo de Dijkstra o A* para encaminamiento
Probabilisticos –> Montecarlo / Las Vegas
Backtracking –> No se ve la solución clara y hay que probar soluciones. Prueba y error.
Ramificación y poda –> optimización sobre backtracking para no pasar dos veces por la misma combinación
Programación dinamica –> Es lo contrario a divide y vencerás. Si yo identifico problemas que puedo resolver ya, los resuelvo sin llegar al caso base y los combino
Algoritmos de ordenación. Clasificación
- Interno (memoria) / externo (fichero)
- Natural –> Tarda lo mínimo si la entrada está ordenada. Identifica si está ordenado
- Estable –> Mantiene orden relativo original para las claves iguales.
Array = 9 5 1a 6 2 4 3 1b Orden= 1a 1b 2 3 4 5 6 9 (mantiene 1a y 1b en su orden relativo a la lista original)
No Estable: Contrario de estable. No mantiene el orden relativo de las claves iguales.
Orden= 1b 1a 2 3 4 5 6 9 - Exchange sorts –> Por intercambio. Quicksort / Burbuja / Cocktail
- Selection sorts –> Por selección. HeapSort
- Insertion sorts –> Por insercion. ShellSort
- Merge sorts –> Por fusión. Merge Sort
- Distribution sorts –> Por distribución. Bucket Sort o Bin Sort / Radix Sort
En que consite el algoritmo de ordenacion Burbuja
Algoritmo de intercambio. Complejidad Ω(n) - O(n^2)
Comparación e intercambiode elementos adyacentes, hasta colocarlo en su posición. El elemento va ‘ascendiendo’ como una burbuja.
En que consite el algoritmo de Inserción Directa
Algoritmo de inserción. Complejidad O(n^2)
Insertamos ya en orden. Supongamos unalista ordenada:
1) Buscamos el lugar que el corresponde al elemento del subarray ordenado.
2) Desplazmaos todos los elementos necesarios para hacer hueco al nuevo elemento.
NOTA: Si en el paso 1 en lugar de comparar elementos 1a1 se realiza una búsqueda binaria (árbol binario de búsqueda), se denomina INSERCION BINARIA, y mejoramos la complejidad a O(n log n)
En que consite el algoritmo de QuickSort
Algoritmo de intercambio divide y vencerás. Complejidad Ω(n log n) - θ(n log n) - O(n^2)
1) Elegimos un pivote y mandamos a los elementos más pequeños a la izquierda y a los elementos más grandes a la derecha.
2) Misma operativa para cada subarray
NOTA: Si elegimos mal el pivote nos podemos ir a complejidad O(n^2)
En que consite el algoritmo de MergeSort
Algoritmo de fusión (Merge sort). Complejidad O(n log n)
1) Divide la lista en sublistas hasta llegar al caso mas trivial (recursividad). Típicamente se empieza separando en dos listas elementos de 1 en 1, luego aumenta 2 en 2, 4 en 4 ….
2) Mezcla las dos sublistas para optener unalista ordenada.
En que consite el algoritmo de HeapSort
Algoritmo de selección. Complejidad O(n log n)
1) Consiste en meter todos los elementos del array de datos en un mónticulo Max/Min y luego realizar N veces llamadas eliminar-max/min() del monticulo. El resultado será orden decreciente en un max heap y orden creciente en un min heap.
En que consite el algoritmo de Selección
Algoritmo de selección. Complejidad O(n^2)
1) Buscas el mínimo y o pones en la 1ª posición
2) Buscas el siguiente mínimo a partir de la 1ª posición y lo pones en la 2ª posición
3) Se repite la operación para todos los elementos ordenandolos en la posición que le corresponda.
En que consite el algoritmo de Radix Sort
Algoritmo de distribución. Complejidad O(n * k)
LSD –> Usa el dígito menos significativo
MSD –> Usa el dígito mas significativo
Se distribuyen los elementos en una cola en función de su digito menos/mas significativo (LSD / MSD )
En que consite el algoritmo de Bucket Sort o BinSort
Algoritmo de distribución. Complejidad O(n)
Hacemos buckets con rangos de valores y repetimos la operación dentro de cada bucket.
NOTA: Se puede usar otro método de ordenación dentro de cada bucket.
Seguimiento del bucle While de la imagen
En el lenguaje C++, si hablamos de un bucle con estructura do…while:
a) Sólo se ejecuta si la condición del bucle es verdadera.
b) Evalúa la condición del bucle y después se ejecuta al menos una vez.
c) Se ejecuta una vez antes de evaluar la condición del bucle.
d) Se ejecuta una sola vez siempre y cuando sea verdadera la condición del bucle.
c) Se ejecuta una vez antes de evaluar la condición del bucle.
En el diseño del antiguo sistema se ha encontrado pseudocódigo con la siguiente expresión:
(NOT (c>d) and (a<c)) and NOT ((a>b) and (a<b))
¿Qué valor debería tomar c, siendo a=4, b=5 y d=5 para que el valor de la expresión fuera VERDADERO?
a) c=3
b) c=4
c) c=5
d) c=6
c) c=5
Se ha obtenido la complejidad de unos algoritmos de ordenación utilizados en el antiguo sistema, el único factor del que dependen es del tamaño de la muestra de entrada, ordenar las complejidades de mayor a menor eficiencia.
a) Orden exponencial, líneal, cuadrático, logarítmico y factorial.
b) Orden logarítmico, cuadrático, lineal, exponencial y constante.
c) Orden logarítmico, cuadrático, lineal, cúbico y factorial.
d) Orden logarítmico, líneal, cuadrático, exponencial y factorial.
d) Orden logarítmico, líneal, cuadrático, exponencial y factorial.
Indique qué número hay que pasar como parámetro a la siguiente función Java para que produzca como salida el número 8
int secuencia(int n){
if(n==1 || n==2) return 1;
else retum secuencia(n-1)+secuencia(n-2);
}
a) 4
b) 5
c) 6
d) 8
c) 6
De acuerdo al código Java mostrado anteriormente con el título “Funcionalidad 2”, la ejecución del main de las líneas 10 a la 15, dará como resultado:
a) 2 8 2 2 5 2
b) 0 4 1 4 3 2
c) 0 4 1 4
d) Da un error de compilación.
c) 0 4 1 4
Una de las funcionalidades del antiguo sistema utiliza el algoritmo Quicksort para organizar un array de elementos, el orden de complejidad dicho algoritmo es:
a) O(n * log n) en el caso promedio.
b) O(n^2) en el mejor caso.
c) O(n^2) en el caso promedio.
d) O(n * log n) en el peor caso.
a) O(n * log n) en el caso promedio.
Es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado:
a) Quicksort
b) Kruskal
c) QR
d) Rijndael
b) Kruskal
El método del intercamblo directo o algoritmo de la burbuja, es un algoritmo clásico de:
a) ordenación que recorre un vector de elementos e intercambia en cada recorrido un elemento con su sucesor si no estánen orden.
b) ordenación que recorre un vector de elementos hasta encontrar el menor de todos e intercambiarlo con el que está en la primera posición. Luego el segundo más pequeño, y así sucesivamente hasta ordenar todo,
c) busqueda que compara secuencialmente el elemento deseado con los valores contenidos en las posiciones 1..n del vector de elementos hasta que lo encuentre.
d) búsqueda que compara secuencialmente el elemento deseado con los valores contenidos en las posiciones 1..n del vector
de elementos hasta que lo encuentre, requisito indispensable es que el vector esté previamente ordenado.
a) ordenación que recorre un vector de elementos e intercambia en cada recorrido un elemento con su sucesor si no estánen orden.
Indique cual seria la salida que se obtendría ejecutando el siguiente trozo de código en C++:
for (int i=1; i++<10; i++) {
( (i == 5) ? cout<< "Cinco" : cout << i <<" ");
}
a) 0 2 4 6 8
b) 1 3 Cinco 7 9
c) 2 4 6 8 10
d) 1 3 5 7 9
c) 2 4 6 8 10
En el contexto del lenguaje C de ANSI, ¿cuál de las siguientes opciones consigue que los valores de “a” y “b” sean respectivamente 10 y 11?
a) int a=11, b; b=a - -;
b) int a=11, b; b=- -a;
c) int a=10, b; b=++a;
d) int a=10, b; b=a++;
a) int a=11, b; b=a–;
Seguimiento bucle For de la imagen
¿En que consiste la técnica de Backtracking?
Técnica de diseño de algoritmos basada en explorar todo el “arbol” de posibles soluciones (prueba y error) –> Fuerza Bruta (prueba y error)
¿Qué requisito tiene el algoritmo de la busqueda binaria y que complejidad computacional tiene?
a) Que los datos esten ordenados (array, arbol….)
b) O(long n)
Ordene, de la mas eficiente a menos eficiente, estas compejidades: n!, nlogn, n^2, 2^n
n log n, n^2 , 2^n, n!
¿En que consiste cada iteración del algoritmo Radix-Sort?
En distribuir en las colas/urnas los números según un determinado dígito (unidades, decenas, centenas ….. o al revés)
NOTA: Necesitamos de un ‘espacio’ adicional
De una definición de la propiedead de “estabilidad” en los algoritmos de ordenación
Mantiene el orden relativo original para claves iguales en una ordenación
¿En que consiste el algoritmo de inserción binaria?
Que mediante busqueda binaria obtenemos el lugar donde insertar el elemento a ordenar en cada iteracion.
¿El algoritmo de ordenación BubleSort siempre presenta una complejidad O(n^2 )?
No, en el mejor de los casos sería O(n). Se da cuenta si los datos ya están ordenados.
¿Que requisito necesita cualqueir función recursiva?
Una condición de parada (Caso Base)
¿Cómo explicaría el mecanismo que se produce en una llamada a una función ?
Cuando se llama a una función:
g (a, b){
….
….
f(b) —> tiene un código y devuelvel un dato
…. (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 espaciál ?
Representa la cantidad de espacio adicional (a los datos de entrada) que necesita el algoritmo
