Bloque2-Tema3-Algoritmos

Question 1

Que es un algoritmo?

Answer 1

Conjunto de reglas aplicadas sistematicamente a unos datos de entrada apropiados, resuelven un problema en un NUMERO FINITO de pasos elementales.

Question 2

Medidas de expresion de un algoritmo.

Answer 2

-Diagramas de flujo
-Pseudocodigo.
-Sistemas formales.

Question 3

Tecnicas de analisis y diseño?

Answer 3

-Divide y venceras
-Voraces(Opcion optima en cada paso) (Djistra/ A* / Prim /Kruskal)
-Probalisticas (Montecarlo/las vegas)
-Backtracking (Explora arbol soluciones)
-Ramificacion y poda
-Programacion dinamica (Combinar subproblemas optimos)

Question 4

Que es la memoizacion (usada en resursividad)?

Answer 4

Es una técnica de optimización que se usa principalmente para acelerar los tiempos de cálculo, almacenando los resultados de la llamada a una subrutina en una memoria intermedia o búfer y devolviendo esos mismos valores cuando se llame de nuevo a la subrutina o función con los mismos parámetros de entrada.

Question 5

Que es la Cota superior asintótica (Big O Notation)

Answer 5

Una cota superior asintótica es una función que sirve de cota superior de otra función cuando el argumento tiende a infinito.

Question 6

Tiempo logaritmico ordenado de menos tiempo a mas.

Answer 6

O(1) / O(logN) / O(n) / O(NLogN) / O(N^2) / O(2^N) / O (N!)

Question 7

Tipos de clasificacion de algoritmos.

Answer 7

-Interno (Memoria) o Externo (fichero)

-Natural/adaptativo (Tarda lo minimo si la entrada esta ordenada)

-Estable (Mantiene orden relativo original para claves iguales)-> Quiere decir que mantiene el orden de los valores duplicados, por ejemplo dos 3, va a tener en el orden que venian ordenados.

Question 8

Algoritmos de ordenacion de tipo Exchange Sorts?

Answer 8

-Burbuja
-Quicksort
-Cocktail o burbuja bi-direccional

Question 9

Algoritmos de ordenacion de tipo Selection Sorts?

Answer 9

-Seleccion
-HeapSort

Question 10

Algoritmos de ordenacion de tipo Insertion Sorts?

Answer 10

-Insercion
-ShellSort (Insercion con pasos mas grandes)

Question 11

Algoritmos de ordenacion de tipo Merge Sorts?

Answer 11

-Merge sort

Question 12

Algoritmos de ordenacion de tipo Distribution Sorts?

Answer 12

-Bucket Sort/Binsort
-Radix Sort

ESTOS NO HACEN COMPARACIONES.

Question 13

Complejidad logaritmica del algoritmo de burbuja

Answer 13

Mejor caso -> O (N)
Caso medio-> O (N^2)
peor caso-> O (N^2)

Question 14

COmo funciona el algoritmo de burbuja?

Answer 14

Vamos desplazando el Nº mas grande que nos encontramos a base de comparaciones e intercambios entre elementos adyacentes.

Question 15

Complejidad logaritmica del algoritmo de insercion directa

Answer 15

Mejor caso -> O (N)
Caso medio-> O (N^2)
peor caso-> O (N^2)

Question 16

Como funciona el algoritmo de insercion directa?

Answer 16

1-> Busca el lugar que le corresponde a Xi dentro del subarray que ya esta ordenado.

2-> Desplaza a todos los elementos necesario para hacerle hueco a Xi

NOTA: Si en el paso 1 en lugar de comparar 1 a 1 realiza una busqueda binario, se denomina insercion binaria.

Question 17

Complejidad logaritmica del algoritmo QuickSort

Answer 17

Mejor caso -> O (N log(N))
Caso medio-> O (N log(N))
peor caso-> O (N^2)

Question 18

Como funciona el algoritmo de QuickSort?

Answer 18

1-Crea un pivote
2-Intercambio de elementos > Xi y elementos < Xi
3-Misma operativa para cada subarray(Resursivo)

Osease que divide un array y mete los grandes a un lado y los pequeños al otro.

Question 19

Complejidad logaritmica del algoritmo MergeSort

Answer 19

Mejor caso -> O (N log(N))
Caso medio-> O (N log(N))
peor caso-> O (N log(N))

Question 20

Como funciona el algoritmo de MergeSort?

Answer 20

1- Divide la lista en sublistas hasta llegar al caso trivial (Recursividad)
2- Mezcla dos sublistas para obtener una lista ordenada.

Question 21

Complejidad logaritmica del algoritmo HeapSort O monticulos.

Answer 21

Mejor caso -> O (N log(N))
Caso medio-> O (N log(N))
peor caso-> O (N log(N))

Question 22

Como funciona el algoritmo de HeapSort?

Answer 22

Consiste en meter todos los elementos del array de datos en un monticulo MAX y luego realizar N veces llamadas a eliminar_max(), lo que lo ordena en resultado decreciente.

Question 23

Complejidad logaritmica del algoritmo de Seleccion.

Answer 23

Mejor caso -> O (N^2)
Caso medio-> O (N^2)
peor caso-> O (N^2)

Question 24

Como funciona el algoritmo de Seleccion?

Answer 24

1-Busca el minimo y lo pones en la 1º posicion.
2-Busca el siguiente minimo a partir de la primera posicion y lo pones en la segunda, etc.

Question 25

Complejidad logaritmica del algoritmo Radix Sort

Answer 25

O (N*K)

Question 26

Como funciona el algoritmo Radix Sort?

Answer 26

Hay dos versiones:
LSD: Usa el digito menos significativo.
MSD: Usa el digito mas significativo.

ordena enteros procesando sus dígitos de forma individual. Va metiendo por digitos en colas/buckets.

Question 27

Complejidad logaritmica del algoritmo Bucket Sort/Binsort?

Answer 27

O (N)

Question 28

Como funciona el algoritmo Bucket Sort/Binsort?

Answer 28

Distribuye todos los elementos a ordenar entre un número finito de casilleros. Cada casillero solo puede contener los elementos que cumplan unas determinadas condiciones.

Question 29

Mirar ejercicio resursividad. Imagen bloque 2 tema 3.