Algoritmos

Question 1

Algoritmos definición

Answer 1

Conjuntos de reglas que, aplicadas sistemáticamente a unos datos de entrada apropiados, resuelven un problema en un número finito de pasos elementales.

Question 2

Diseño. Técnicas

Answer 2

-Divide y venderás (TOP-DOWN)
-Voraces (opción óptima en cada caso)
-Probabilísticos (MonteCarlos/Las Vegas)
-Backtracking (explora árbol de soluciones) - Fuerza bruta
-Ramificación y poda
-Programación dinámica (combinar subproblemas óptimos)

Question 3

Análisis (complejidad espacial y temporal)

Answer 3

Question 4

Algoritmos de búsqueda

Answer 4

Búsqueda secuencia. O(n).
Búsqueda binaria. O(log n). El arreglo debe estar ordenado y no se deben repetir los elementos.

Question 5

Clasificación de algoritmos ordenación

Answer 5

Interno (memoria) / externo (fichero)
Natural. Tarda lo mismo si la entrada está ordenada
Estable. Mantiene el orden relativo original para claves iguales

Question 6

Tipos de algoritmos de ordenación

Answer 6

-Exchange sorts: Burbuja/ QuickSort/ Cocktail
-Selection sorts: Selection/ HeapSort
-Insertion sorts: Insertion/ ShellSort
-Merge sort: Merge Sort
-Distribution sorts: Bucket Sort o BinSort/ Radix Sort

Question 7

Burbuja

Answer 7

O (n^2)
Ω(n)
Vamos desplazando el nº máx grande que nos encontramos a base de comparaciones e intercambios entre elementos adyacentes

Question 8

Inserción directa

Answer 8

O (n^2)
Ω(n)
1. Busca el lugar que le corresponde a Xi dentro del subarray que ya está ordenado.
2. Desplaza los elementos necesarios para hacerle hueco a Xi.

Question 9

Selección

Answer 9

O (n^2)
1. Busca el mínimo y lo pones el 1º
2. Busca el siguiente mínimo y lo coloas el 2º

Question 10

MergeSort

Answer 10

O(n log n)
1. Divide la lista en sublistas hasta llegar al caso trivial (recursivo)
2. Mezcla dos sublistas para tener una ordenada

Question 11

QuickSort

Answer 11

O (n^2)
Ω(n log n)
1. Elegimos un elemento al que llamamos Pivote
2. Intercambiamos elementos menores de Xi y mayores de Xi
3. Misma operativa de forma recursiva

Question 12

HeapSort/Montículo

Answer 12

O(n log n)
Consiste en meter todos los elementos del array en un montículo MAX y realizar N llamadas a eliminar_max

Question 13

BucketSort / BinSort

Answer 13

O (n^2)
Ω (n+k)
1º Distribución inicial
2º Ordenar cada casillero
3º Concatenar casilleros

Question 14

Radix Sort

Answer 14

O(n*k)
LSD: dígito menos significante
MSD: dígito más significante