T3 - ALGORITMOS

Question 1

ALGORITMOS: ¿Qué es un algoritmo?

Answer 1

Un conjunto de instrucciones claras y ordenadas
que se siguen paso a paso
para resolver un problema o hacer una tarea
en un tiempo finito
a partir de unos datos de entrada

Question 2

ALGORITMOS: ¿Cuáles son los métodos para representar o resolver algoritmos?

Answer 2

• Diagrama de flujo: Representación gráfica con símbolos y flechas
• Pseudocódigo: Descripción en lenguaje informal estructurado
• Sistemas formales: Uso de expresiones matemáticas lógicas

Question 3

ANÁLISIS Y DISEÑO: ¿Qué es el análisis y diseño en algoritmia?

Answer 3

• Análisis: Estudiar la eficiencia del algoritmo
  (cuánto tiempo tarda y cuánta memoria usa)
• Diseño: Crear una solución paso a paso
  que sea clara, eficiente y correcta

Question 4

ANÁLISIS Y DISEÑO: ¿Cuáles son las principales TÉCNICAS DE DISEÑO de algoritmos?

Answer 4

• Divide y vencerás: Divide el problema en subproblemas más pequeños (merge sort)
• Voraces: Elige la mejor opción en cada paso
• Probabilísticas: Usan azar (ej. Montecarlo, Las Vegas)
• Backtracking: Explora todas las opciones posibles como un árbol
• Ramificación y poda: Como backtracking, pero eliminando ramas inútiles
• Programación dinámica: Resuelve subproblemas y combina soluciones
  (bottom-up o top-down con memorización)

Question 5

ANÁLISIS Y DISEÑO: ¿Ejemplo de la técnica divide y vencerás?

Answer 5

Problema: Ordenar una lista de números
Algoritmo: Merge Sort

Pasos:
- Dividir la lista en mitades hasta que quede una sola posición
- Ordenar cada mitad por separado
- Combinar (merge) las mitades ordenadas

Question 6

ANÁLISIS Y DISEÑO: ¿Ejemplo de la técnica voraz?

Answer 6

Problema: Encontrar el camino más corto entre dos nodos
Algoritmo: Dijkstra
Requiere: Un grafo con pesos no negativos

Pasos:
- Empieza desde el nodo inicial
- En cada paso, elige el nodo más cercano no visitado
- Actualiza las distancias más cortas conocidas
- Repite hasta llegar al destino

Question 7

ANÁLISIS Y DISEÑO: ¿Ejemplo de la técnica probabilísticos?

Answer 7

Problema: Verificar si un número es primo
Algoritmo: Miller-Rabin (tipo Monte Carlo)

Características:
- Usa números aleatorios para hacer pruebas
- Puede dar una respuesta incorrecta con muy baja probabilidad
- Es rápido y útil para números muy grandes

Question 8

ANÁLISIS Y DISEÑO: ¿Ejemplo de la técnica backtracking?

Answer 8

Problema: Resolver un Sudoku
Algoritmo: Búsqueda con retroceso (backtracking)
Método: Tipo prueba y error

Otros ejemplos clásicos:
- El problema del caballo
- Las ocho reinas (extensible a n²)

Pasos:
- Rellenar una celda vacía con un número posible
- Avanzar a la siguiente celda
- Si no hay opción válida, retroceder (backtrack) y probar otra
- Repetir hasta completar la solución válida

Question 9

ANÁLISIS Y DISEÑO: ¿Qué es la técnica ramificación y poda?

Answer 9

• Técnica basada en backtracking
• Explora un árbol de soluciones
• Ramificación: generar todas las posibles opciones desde un nodo
• Poda: eliminar ramas que no pueden mejorar la solución actual
• Reduce el número de caminos explorados
• Muy útil en problemas de optimización (como el del viajante)

Question 10

ANÁLISIS Y DISEÑO: ¿Qué es la técnica programación dinámica?

Answer 10

• Resuelve problemas dividiéndolos en subproblemas más pequeños
• Guarda las soluciones de los subproblemas para no repetir cálculos
• Usa enfoques bottom-up o top-down con memorización
• Ideal cuando el problema tiene subproblemas solapados y estructura óptima

Ejemplo clásico:
- Problema de la mochila
- Fibonacci (más eficiente que con recursión simple)

Question 11

ANÁLISIS Y DISEÑO: ¿Qué es la notación Big O?

Answer 11

• Es una forma de expresar la eficiencia de un algoritmo
• Mide cuánto crece el tiempo o memoria según el tamaño de los datos
• Describe el peor caso en la mayoría de los casos
• Permite comparar algoritmos de forma abstracta

Ejemplos:
- O(1) → constante
- O(log n) → logarítmico (búsqueda binaria)
- O(n) → lineal
- O(n²) → cuadrático
- O(cⁿ) → exponencial (ej. backtracking en problemas complejos)
- O(n^f(n)) → subexponencial (f(n) < n, más lento que polinómico)
- O(nⁿ) → superexponencial (crece muchísimo más rápido que exponencial)

Question 12

ANÁLISIS Y DISEÑO: ¿Qué es la complejidad logarítmica?

Answer 12

• Es una complejidad donde el problema se reduce a la mitad en cada paso
• Se representa como O(log n)
• Es muy eficiente con grandes cantidades de datos
• Ejemplo: búsqueda binaria en listas ordenadas

Question 13

ALGORTIMOS DE ORDENACIÓN: ¿Clasificación general de los algoritmos de ordenación?

Answer 13

• Interno (memoria) / Externo (fichero)
• Natural: tarda lo mínimo si la ENTRADA está ordenada
• Estable: mantiene el orden relativo original para claves iguales

Question 14

ALGORTIMOS DE ORDENACIÓN: ¿Métodos de ordenación más comunes?

Answer 14

• Exchange sort: burbuja, quicksort, cocktail (burbuja bidireccional)
• Selection sort: selección, heapsort
• Insertion sort: inserción, shellsort
• Merge sort
• Distribution sort: bucket sort, bin sort, radix sort

Question 15

ALGORTIMOS DE ORDENACIÓN: ¿Cómo funciona el algoritmo Burbuja sort?

Answer 15

• Pertenece a la categoría exchange sort
• Compara elementos adyacentes y los intercambia si están en orden incorrecto
• El número más grande va subiendo al final en cada pasada
• Habrá que dar varias pasadas hasta que toda la lista esté ordenada
• Complejidad: O(n²) (lento para listas grandes)

Question 16

ALGORTIMOS DE ORDENACIÓN: ¿Cómo funciona el algoritmo Quicksort?

Answer 16

• Pertenece a la categoría exchange sort
• Elige un elemento como pivote
• Divide la lista en dos: menores y mayores que el pivote
• Ordena recursivamente cada sublista
• Muy eficiente en promedio: O(n log n)
• Peor caso: O(n²) (si el pivote es muy mal elegido)

Question 17

ALGORTIMOS DE ORDENACIÓN: ¿Cómo funcionan los algoritmos inserción e inserción binaria?

Answer 17

• Ambos pertenecen a la categoría insertion sort
• Recorren la lista de izquierda a derecha
• Cada nuevo elemento se inserta en su posición correcta respecto a los anteriores

Inserción directa:
- Compara hacia atrás uno a uno hasta encontrar su lugar
- Ejemplo: en [2, 4, 7], insertamos 3
- Compara con 7 → luego con 4 → ve que 3 < 4 y 3 > 2
- Inserta antes de 4
- Se empieza a comparar desde el último dato porque la lista ya está ordenada

Inserción binaria:
- Usa búsqueda binaria para encontrar la posición correcta
- En cada paso compara con el pivote (el elemento central del rango)
- Luego desplaza los elementos para insertar
- Ejemplo: en [2, 4, 7], insertamos 3
- Pivote = 4 → 3 < 4, va a la izquierda
- Pivote = 2 → 3 > 2, posición final: entre 2 y 4
- Inserta entre 2 y 4

• Complejidad: O(n²) (menos comparaciones en binaria, pero igual desplazamientos)

Question 18

ALGORTIMOS DE ORDENACIÓN: ¿Cómo funciona el algoritmo Merge Sort?

Answer 18

• Pertenece a la categoría divide y vencerás
• Divide recursivamente la lista en mitades hasta que queden elementos individuales
• Luego fusiona (merge) esas mitades ordenándolas

Pasos:
- Dividir: separar la lista en mitades
- Ordenar cada mitad de forma recursiva
- Combinar ambas mitades en orden

• Complejidad: O(n log n) (eficiente incluso en el peor caso)

Question 19

ALGORTIMOS DE ORDENACIÓN: ¿Cómo funciona el algoritmo HeapSort?

Answer 19

• Pertenece a la categoría selection sort
• Usa una estructura llamada montículo (heap) para ordenar
• En un montículo, el valor máximo siempre está en la raíz

Pasos:
- Construir un montículo máximo con todos los elementos
- Extraer el valor de la raíz (el mayor) y colocarlo al final
- Reorganizar el montículo (y subir el nuevo montículo)
- Repetir hasta vaciarlo

• Complejidad: O(n log n)
• No necesita espacio adicional

Question 20

ALGORTIMOS DE ORDENACIÓN: ¿Cómo funciona el algoritmo de selección?

Answer 20

• Pertenece a la categoría selection sort
• Busca en cada pasada el candidato prometedor (el menor de los no ordenados)
• Lo intercambia con la posición actual

Pasos:
- Recorre toda la lista y selecciona el valor más pequeño
- Lo coloca en la primera posición
- Repite el proceso con el resto de la lista

• Complejidad: O(n²) (aunque hace menos intercambios que burbuja)

Question 21

ALGORTIMOS DE ORDENACIÓN: ¿Cómo funciona el algoritmo Radix Sort?

Answer 21

• Pertenece a la categoría distribution sort
• Ordena los elementos dígito a dígito, empezando por una posición concreta
• No compara elementos directamente como otros algoritmos
• Utiliza almacenamiento adicional como colas o bucket para agrupar los datos temporalmente

Variantes:
- LSD (Least Significant Digit): ordena primero por el dígito menos significativo (derecha)
- MSD (Most Significant Digit): comienza por el dígito más significativo (izquierda)

Aspectos clave (más sencillo):
- Cuantos más dígitos tengan los números, más tiempo llevará ordenarlos
- El algoritmo hace una pasada por cada dígito
- Funciona muy bien si todos los números tienen la misma cantidad de dígitos

• Complejidad: O(n·k)
  (siendo n los elementos y k la cantidad de dígitos por número)

Question 22

ALGORTIMOS DE ORDENACIÓN: ¿Cómo funcionan los algoritmos Bucket Sort y Bin Sort?

Answer 22

• Pertenecen a la categoría distribution sort
• Dividen los datos en varios grupos llamados buckets (cubos o contenedores)
• Cada bucket agrupa elementos que están dentro de un mismo rango
• Luego se ordena cada bucket (usando otro algoritmo como inserción)

Características clave:
- Muy eficiente si los datos están uniformemente distribuidos
- Ideal para ordenar números en un rango conocido (por ejemplo, entre 0 y 100)
- Bin Sort es una variante muy similar, especialmente usada para enteros

• Complejidad promedio: O(n + k)
  (n elementos, k número de buckets)
• En el peor caso: puede llegar a O(n²) si los datos caen todos en un solo bucket

Question 23

BUCLES ¿Qué es un bucle?

Answer 23

Es una estructura que permite repetir una serie de instrucciones varias veces
hasta que se cumpla una condición

Question 24

BUCLES ¿Qué es un bucle for?

Answer 24

Es un bucle que se repite un número exacto de veces

Tiene 3 partes:
- Inicio: se define una variable (por ejemplo, i = 1)
- Condición: se repite mientras se cumpla (por ejemplo, i ≤ 5)
- Incremento: cambia el valor en cada vuelta (por ejemplo, i++)

Se usa cuando sabemos cuántas veces queremos repetir algo

En este ejemplo, se repite 5 veces porque empieza en 1 y termina cuando i llega a 5

Question 25

**BUCLES** ¿Qué es un `bucle while`?

Answer 25

Es un `bucle` que se repite mientras se cumpla una `condición` Tiene 2 partes principales: - La `inicialización` va fuera del `bucle` (por ejemplo, `i = 1`) - La `condición` se comprueba antes de cada repetición (por ejemplo, `i ≤ 5`) - El `incremento` va dentro del `bucle` (por ejemplo, `i++`) Se usa cuando `no sabemos exactamente cuántas veces` se va a repetir, ya que `i` está `fuera del bucle` y éste no sabe esa información

Question 26

**BUCLES** Ejemplo `#1`

Answer 26

Función que suma valores impares desde 1 mientras sean menores que 7 Antes → `j = 0` y `i = 1` `Iteración 1` → `j = 1` y `i = 3` `Iteración 2` → `j = 4` y `i = 5` `Iteración 3` → `j = 9` y `i = 7`

Question 27

**RECURSIVIDAD** ¿Qué es una función `recursiva`?

Answer 27

Es una función que se llama a `sí misma` para resolver un problema `dividiéndolo en partes más pequeñas` Se repite hasta llegar a un `caso base` que detiene las llamadas Se usa una `condición` (como un `if`) para parar y no repetir infinitamente Suele ser más `lenta` que otras opciones como los `bucles` Ejemplo: una cuenta atrás que imprime los números desde `n` hasta `1`

Question 28

**EXTRA** ¿Cuál es la fórmula del `n-ésimo` término de la `serie de Fibonacci`?

Answer 28

La fórmula es: `F(n) = F(n−1) + F(n−2)` Cada número se obtiene sumando los dos anteriores Ejemplo: - `F(0) = 0` - `F(1) = 1` - `F(2) = 1` - `F(3) = 2` - `F(4) = 3` - `F(5) = 5` Se puede resolver con `recursividad` o con `programación dinámica`