B2-T3_Algoritmos

Question 1

¿Cuál es una de las condiciones principales que debe de tener un algoritmo?

Answer 1

Debe ser finito

Question 2

¿A qué se refiere “Divide y vence”?

Answer 2

A una técnica de diseño de algoritmos “top-down”.

Que consiste en ir divididiendo el problema en otros más pequeño, hasta que podamos solucionar varios de estos trocitos para juntarlos y dar una solución global.

Question 3

¿Que optimizaciones se pueden aplicar a la técnica de “Divide y vence”?

Answer 3

• Programación dinámica
• Memoizacion de funciones

Question 4

¿En qué consiste la técnica de programación dinámica?

Answer 4

Es una técnica de diseño de algoritmos “bottom-up ó top-bottom+memoización”, es decir, lo contrario a “Divide y Venceras”.

En combinar las soluciones de pequeños subproblemas óptimos para alcanzar la solución global.

Question 5

Nombre dos tipos de algoritmos probabilísticos, y ¿en qué consiste?

Answer 5

• Montecarlo
• Las vegas

Introduce una variable aleatoria y del promedio de sus resultados al azar obtiene la solución al problema planteado. Al contrario que el algoritmo “Determinista”.

Question 6

¿Que mide la expresión O(n)?

Answer 6

La complejidad asintótica (espacial o temporal) de un algoritmo. Es una cota superior.
Se denomina: orden LINEAL de 1º Orden. O(n^2): Orden CUADRÁTICO de 2º Orden, O(n^3)…

Question 7

¿Qué tipo de algoritmo es HeapSort? y, ¿en qué consiste?

Answer 7

De selección.
Consiste en meter todos los elementos del array en un monticulo con forma de árbol, colocando en la raiz el valor máximo (MAX-HEAP) ó mínimo (MIN-HEAP).
Y, vamos extrayendo la raiz, a la que vamos colocando en nuestro elemento de ordenación, reconstruyendose el monticulo con una nueva raiz y así sucesivamente…

Question 8

Nombre dos algoritmos de ordenación que no se basan en realizar comparaciones entre sus elementos:

Answer 8

Son algoritmos de distribución:
* Bucket Sort
* Radix Sort

Ordenan colocando los datos en diferentes zonas de la memoria con algún sistema lógico.

Question 9

¿Qué algoritmo de ordenación se basa en calcular el digito más o menos significativo (MSD ó LSD) de cada elemento?

Answer 9

Radix Sort.
Es un algoritmo de Distribución, en el que vamos ordenando en buquets o colas en base al dígito más significativo (MSD) ó el dígito menos significativo (LSD).
Ej. LSD: Organiza por el último dígito de la cifra, luego sigue por el penúltimo, luego el siguiente,… y así va rellenando los buquets o colas.

Question 10

¿Qué es un algoritmo estable?

Answer 10

Aquel que mantiene el orden relativo original de los registros que tengan la misma clave, marcandolas para diferenciarlas.
Ej: 10, 3, 1, 7, 8, 6, 3 => 1, 3´, 3”, 6, 7, 8, 10.

Question 11

¿Cual es el caso peor para QuickSort y porque? ¿En qué consite?

Answer 11

O(n2) si el pivote (Xi) se elige mal y no particiona bien el array.

Se ordena colocando los valores más pequeños del pivote (Xi) a la izquierda y los más grandes a la derecha. Se repite el proceso en esos sub-arrays, y, así, sucesivamente…

Question 12

¿En que consite el agoritmo de Inserción Binaria?

Answer 12

Busca el lugar que corresponde a Xi dentro del subarray, que ya esta ordenado, pero la búsqueda es binara en lugar de una búsqueda secuencial (de uno en uno), para insertar el elemento Xi en la parte izquierda del array, desplanzando todos los elementos necesarios para hacerle hueco.
El proceso se repite desde el segundo hasta el n-ésimo elemento.

Question 13

Ordene de forma creciente las siguientes complejidades O(n!) , O(2n), O(nlog(n)), O(n2)

Answer 13

O(nlog(n)) → O(n2) → O(2n) → O(n!)

Question 14

¿Qué es un algortimo y cómo se analiza?

Answer 14

Es una receta o método con una serie de pasos FINITOS, que son aplicados secuencialmente (uno tras otro) hasta dicho FIN. En el caso de un problema, lo resolverían en un número FINITO de pasos.
Hay 2 formas de analizarlo: TIEMPO y ESPACIO.

Question 15

Maneras de expresar los algoritmos:

Answer 15

• DIAGRAMA DE FLUJO: con sus características simbolicas (rombos, flechas, …)
• PSEUDOCODIGO: lenguaje inventado.
• SISTEMAS FORMALES: matemáticas.

Question 16

Un algoritmo se divide en dos partes ANALISIS y DISEÑO, define la primera:

Answer 16

1.- ANÁLISIS: realiza un estudio de un algoritmo para ver como se comporta ESPACIAL (consumo en memoria) y TEMPORALMENTE (velocidad). Este estudio se expresa según la complejidad ASINTOTA de dicho algoritmo (Big O notation), que te indica en que posición del orden de complejidad se encuentra en concreto.

Question 17

Un algoritmo se divide en dos partes ANALISIS y DISEÑO, define la segunda:

Answer 17

2.- DISEÑO:
* Divide y venceras (Top-Down)
* Programación dinámica (Bottom-Up=>lo contrario al anterior)
* Voraces (GREEDY=codicioso)
* Probabilisicos (Montecarlo y Las Vegas)
* BackTracking (explora el árbol de soluciones solución x solución)
* Ramificación y Poda (optimiza el árbol de soluciones para NO repetir pruebas)

Question 18

¿Qué es la complejidad temporal: Big O notation?

Answer 18

Representa una asintota superior respecto del tiempo que tarda un algortimo, tipificando, con curvas de tiempo, el rendimiento del algoritmo.
*O: cota superior.
*La expresión O(n): mide la complejidad asintota (espacial o temporal) de un algoritmo.

Question 19

Pon un ejemplo de un Orden de Complejidad Asintotica:

Answer 19

O(1)=Orden constante->O(logn)=Orden logaritmica->O(n)=Lineal o de 1º orden->O(n^2)=cuadrática o 2º orden->O(n^c)=Orden potencial->O(c^n)=Orden exponencial->O(n!)=Orden factorial->O(N^n)=Potencial exponecial.

• Para mejorar estos ordenes y, por ejemplo, convertir un O(n!) en O(n^c), se usan las tecnicas de diseño.

Question 20

Define las técnicas de diseño Voraces:

Answer 20

Escogen la opción más óptima en cada paso del algoritmo, por eso lo de “voraz”, porque van comiendo la mejor en cada paso.
Ej: GREEDY (codicioso)

Question 21

Define el algoritmo LINEAL ó de 1º Orden O(n):

Answer 21

El eje “x” e “y” crecen proporcionalmente.

Question 22

Define el algoritmo CUADRÁTICO ó de 2º Orden O(n^2):

Answer 22

Tiene una curva más pronunciada que el de 1º Orden O(n), porque al aumentar el eje de la “x” aumenta en mayor medida el de la “y”.

Question 23

Explica la clasificación de los algoritmos de ordenación:

Answer 23

• INTERNOS (memoria) / EXTERNOS (fichero)
• NATURAL (tarda lo mínimo al darse cuenta si los datos estan ordenados)
• ESTABLE (no desordena las claves iguales, sólo las marca para difernciarlas)

Question 24

¿En qué consiste la MEMOIZACIÓN?

Answer 24

Evita las repeticiones recursivas, porque almacena los resultados para devolverlos directamente cuando se necesiten, sin tener que repetir todo el proceso.

Question 25

Define el tipo de algortimo de ordenación EXCHANGE SORTS:

Answer 25

Intercambian o mueven datos de un lado para otro, comparando e intercambiando continuamente.
Ej: BURBUJA, QuickSort, COCKTAIL ó BURBUJAS BI-DIRECCIONAL.

Question 26

Define el tipo de algortimo de ordenación SELECTION SORTS:

Answer 26

Seleccionan el DATO a introducir en el hueco.
EjemploS:
*SELECCION (selecciona el mínimo y lo coloca en la 1ª posición, luego busca el mínimo a partir de esa 1ª posición y lo coloca el 2º).
* HeapSort (va seleccionando la raiz y reconstruyendo el monticulo, ya sea MIN-SORT ó MAX-SORT)

Question 27

Define el tipo de algortimo de ordenación INSERTION SORTS:

Answer 27

Selecciona o busca el HUECO donde insertar el dato a ordenar a través de busqueda LINEAL (secuencialmente) ó BINARIA (Inserción Binaria). Luego, desplaza a todos los elementos necesarios para hacerle hueco.
Ej: INSERCCIÓN y ShellSort.

Question 28

Define el tipo de algortimo de ordenación MERGE SORTS:

Answer 28

Primero, divide la lista en sublistas. Y, segundo, va MEZCLANDO las sublistas de a dos, a cuatro,… para obtener una lista ordenados.

Es decir, basado en la técnica divide y vencerás. La idea de los algoritmos de ordenación por mezcla es dividir la matriz por la mitad una y otra vez hasta que cada pieza tenga solo un elemento de longitud.

Question 29

Define el tipo de algortimo de ordenación DISTRIBUTION SORTS:

Answer 29

Ordenan colocando los datos en diferentes zonas de la memoria con algún sistema lógico. Pero, NO se basan en comparaciones.
Ej: BucketSort ó BinSort, y RadixSort.

Question 30

¿Qué hace el algoritmo BURBUJA de tipo “Exchange Sort”?

Answer 30

Vamos desplazando el número más grande que nos encontramos a base de comparaciones e intercambios con sus adyacentes hacia la derecha (como si fuera una burbuja flotante). Una vez colocado, se empieza con el siguiente y, así, sucesivamente…

Question 31

¿Qué hace el algoritmo BucketSort/BinSort de tipo “Distribution Sort”?

Answer 31

1º Distribuye los datos en casillas o urnas.
2º Ordena cada casillero con el agoritmo adecuado (hace interacción con algoritmos + pequeños).
3º Concatena los casilleros.

Question 32

¿Qué 4 tipos de algoritmos de grafos existen?

Answer 32

*CAMINO MÍNIMO (Dijstra, Floyd y Bellman-Ford)

*RECUBRIMIENTO MÍNIMO (Prim y Kruscal => utilizados en los STP)

*DE MAXIFICACIÓN DE FLUJO (Ford-Fulkerson)

*DETECTAR COMPONENTES CONEXOS (Tarjan)

Question 33

Enumera los 3 tipos de Algoritmos:

Answer 33

FOTO:

Question 34

¿En qué consiste un algoritmo de BackTracking?

Answer 34

También conocido como “retroceso” o “vuelta atrás”.

Explorar todas las posibles soluciones de manera sistemática (TODO el árbol de soluciones una a una), descartando las ramas que sabemos que no conducirán a una solución válida y retrocediendo cuando alcanzamos un punto donde no podemos avanzar más.

Esta técnica es particularmente útil para problemas en los que la fuerza bruta sería ineficiente debido a la cantidad de posibles combinaciones a explorar.