UNIVERSIDAD TÉCNICA DE MANABÍ
NOMBRE:
MICHAEL STEEVEN JAIME TUAREZ
CARRERA:
COMPUTACIÓN
MATERIA:
ANÁLISIS Y DISEÑO DE ALGORITMOS
Profesor:
Luis Oyarzun
FECHA:
3/5/2025
1.1-1
Describe tu propio ejemplo del mundo real que requiere ordenación.
Organizar una lista de estudiantes por sus calificaciones finales.
Imagina que eres profesor y tienes una lista con las calificaciones de tus
alumnos. Para premiar a los mejores, decide ordenar la lista de mayor a menor
nota. Esta ordenación te permite ver rápidamente quiénes son los estudiantes
con mejor desempeño y asignar reconocimientos.
Nombre Calificación
Ana 85
Luis 92
Marta 78
José 90
Camila 95
Objetivo: Ordenar de mayor a menor calificación.
Solución:
1. Camila – 95
2. Luis – 92
3. José – 90
4. Ana – 85
5. Marta – 78
Explicación:
Hicimos una ordenación descendente basada en los valores numéricos de las
calificaciones.
Describe uno que requiera encontrar la distancia más corta entre dos puntos.
Buscar la ruta más rápida para llegar al hospital desde tu casa.
Supón que alguien en tu familia se siente mal y necesitas llegar al hospital lo
más rápido posible. Utiliza una aplicación de mapas (como Google Maps), la cual
calcula la distancia más corta o la ruta más rápida considerando el tráfico, calles
cerradas y otros factores. El objetivo es minimizar el tiempo de llegada.
• Casa a A: 1,6 kilómetros
B: Un Hospital : 6 km
Hay dos posibles caminos:
Hay dos posibles caminos:
1. Casa → A → Hospital: 1,6 + 6 = 7.6km/min
2. Respuesta: La ruta más corta desde la Casa → A → Hospital VERDI
SEVALLOS Casa → B → Hospital con 6 km.
Casa C: 2,1 km
• D: Hospital : 10min
3. Casa → C→ Hospital: 2.1+ 10 = 12.1km/min
Mapa conceptual
1.1-2
Aparte de la velocidad, ¿qué otras medidas de eficiencia podrías necesitar
considerar en un entorno del mundo real?
• Uso de memoria (espacio):
Qué tanto espacio en memoria (RAM o almacenamiento) consume un sistema o
algoritmo. Esto es crucial en dispositivos con recursos limitados, como teléfonos
móviles, microcontroladores o sistemas embebidos.
• Consumo de energía:
Especialmente importante en dispositivos móviles, sensores o sistemas que funcionan
con batería. Un sistema eficiente energéticamente puede funcionar por más tiempo sin
recargarse.
• Escalabilidad:
Qué tan bien se comporta el sistema a medida que aumentan los datos, usuarios o
conexiones. Un sistema que funciona bien con 100 usuarios, pero cae con 1000 no es
eficiente a gran escala.
• Tolerancia a fallos:
Qué tan capaz es el sistema de seguir funcionando en caso de errores o caídas
parciales. Esto incluye respaldo, recuperación rápida y redundancia.
• Costo económico:
Implica tanto el costo de implementación como de mantenimiento. Un sistema puede
ser rápido y eficiente, pero si es demasiado costoso, no será viable en el mundo real.
• Facilidad de mantenimiento:
Un sistema debe ser fácil de actualizar, depurar y adaptar a nuevos requisitos. La
eficiencia también incluye el tiempo que toma mantener operativo.
• Latencia:
El tiempo que tarda en responder una petición, especialmente importante en tiempo
real, como videojuegos, sistemas financieros o videollamadas.
• Ancho de banda:
Qué tanto tráfico de géneros rojos. En aplicaciones distribuidas o móviles, reducir el
uso de red mejora la eficiencia.
• Seguridad:
Aunque no siempre se incluye directamente en "eficiencia", un sistema que es
más seguro evita pérdidas o daños costosos.
• Usabilidad (experiencia de usuario):
Un sistema puede ser técnicamente eficiente, pero si es complicado de usar o
entender, pierde eficiencia práctica.
1.1-3
Selecciona una estructura de datos que hayas visto y discute sus fortalezas y
limitaciones.
✓ Fortalezas de una Pila:
1. Modelo LIFO (Último en entrar, primero en salir):
El último elemento en entrar es el primero en salir, lo que es ideal para ciertos
procesos como deshacer acciones, evaluar expresiones matemáticas, o
recorridos en profundidad (DFS).
2. Simplicidad de uso Las operaciones básicas:
Las operaciones básicas (apilar y desapila, o empujar y pop) sony pop) son
rápidos y fáciles de implementar.
3. Uso en recursividad:
Los lenguajes de programación usan pilas internamente para manejar llamadas
a funciones, especialmente en funciones recursivas.
4. Gestión del flujo de control:
Son útiles para tareas como revertir una cadena, verificar paréntesis
balanceadas, o realizar backtracking.
Limitaciones de una pila:
1. Acceso restringido:
Solo puedes acceder al elemento en la cima de la pila. No puedes acceder
directamente a elementos más antiguos sin desapilar los que están encima.
2. Capacidad limitada (en algunas implementaciones):
Si se implementa con un arreglo, puede tener un tamaño máximo definido.
3. No es adecuado para búsquedas complejas:
Si necesita buscar elementos de forma aleatoria o acceder a elementos
específicos, la pila no es la mejor opción.
1.1-4
¿En qué son similares los problemas de camino más corto y el problema del
vendedor viajero que se mencionan arriba? ¿En qué son diferentes?
Diferencias
Característica Camino más corto Vendedor viajero (TSP)
Objetivo Encontrar el camino más Encontrar un recorrido mínimo que
corto entre dos nodos visite todos los nodos exactamente
dados. una vez y regrese al punto de inicio.
Tipo de Puede pasar por algunos Cada nodo se visita una sola vez.
recorrido nodos o aristas más de una
vez.
Complejidad Tiene algoritmos eficientes Es NP-completo, no se conoce ningún
(como Dijkstra o Bellman- algoritmo eficiente para todos los
Ford). casos.
Escalabilidad Escala bien con grandes Escala mal; el número de soluciones
grafos. posibles crece factorial mente (n!).
Usos Navegadores, routers de Planificación de rutas de entrega,
comunes internet, planificación de problemas logísticos complejos.
viajes punto a punto.
Conclusion
• Ambos implican rutas óptimas en grafos, pero el camino más corto busca la
mejor conexión entre dos puntos, mientras que el TSP busca un circuito
completo que pase por todos los puntos sin repetir.
• Resolver el camino más corto es eficiente y directo; resolver el TSP requiere
técnicas más complejas como algoritmos de aproximación o heurísticas si hay
muchos nodos.
1.1-5
Sugiere un problema del mundo real en el que solo la mejor solución sea
suficiente. Luego, plantea uno en el que “aproximadamente” la mejor solución
sea suficiente.
Problema donde solo la mejor solución es suficiente:
Ejemplo:
Algoritmos de navegación para aviones (control de tráfico aéreo)
Por qué necesita la mejor solución: En el control, los aviones deben seguir rutas
exactas para evitar colisiones
En el control del tráfico aéreo, los aviones deben seguir rutas exactas para evitar
colisiones y optimizar el uso del espacio aéreo. Un pequeño error puede tener
consecuencias graves para la seguridad. Aquí no basta con una solución “casi buena”,
se necesita la mejor ruta posible, basada en distancias, tráfico, clima, combustible y
otros factores críticos.
Problema donde una solución "aproximadamente buena" es suficiente:
Ejemplo:
Recomendación de películas en plataformas como Netflix
Por qué no necesita la solución perfecta:
No es necesario recomendar la película perfecta, solo una que probablemente le guste
al usuario. Los sistemas de recomendación trabajan con algoritmos aproximados
basados en gustos similares, historial y popularidad. Una buena sugerencia que
mantenga al usuario interesado es suficiente, aunque no sea la mejor opción de todas.
1.1-6
Describe un problema del mundo real en el que a veces toda la entrada esté
disponible antes de que necesites resolver el problema, pero otras veces la
entrada no esté completamente disponible de antemano y llegue con el tiempo.
Problema:
Gestión de pedidos y stock en una tienda en línea
Situación 1: Toda la entrada está disponible de antemano
Imagina que la tienda recibe un pedido grande de un solo cliente. En este caso, y ese
pedido ya viene con la lista completa de productos que se necesitan.
En este caso, el sistema puede analizar todo el pedido de una vez y verificar si stock,
aplicar descuentos, calcular y verificar si hay stock suficiente, aplicar descuentos,
calcular el envío y generar la factura.
Situación 2: La entrada llega con el tiempo
Ahora imagina el caso diario de múltiples clientes. comprando en distintos. Los
pedidos llegan uno comprando en distintos momentos.
Los pedidos llegan uno por uno, el sistema debe:, a lo largo del día.
Aquí, el sistema debe:
• Registrar cada pedido apenas llega.
• Verifique el stock en tiempo real.
• Reservar productos antes de que se agoten.
• Y, si el stock está demasiado bajo, actualice la disponibilidad para los
siguientes clientes.
En este escenario, el sistema no conoce todos los pedidos por adelantado, y debe ir
resolviendo el problema a medida que llegue la información.
Conclusión:
Este ejemplo muestra cómo un mismo problema (gestionar pedidos) puede variar
dependiendo de si tienes toda la información al inicio o si esta llega en partes. Eso
afecta la forma en que se diseñan los algoritmos: a veces se puede usar un enfoque
estático, y otras veces se necesita un enfoque dinámico o en línea.
1.2 Algoritmos como tecnología
1.2-1
Dé un ejemplo de una aplicación que requiera contenido algorítmico a nivel de
aplicación y analice la función de los algoritmos involucrados.
tipo de aplicación es Google Maps. De algoritmos como algoritmo de Dijkstra o el de
búsqueda A * *A nivel de aplicación, utiliza algoritmos como el de Dijkstra. Ruta entre
dos ubicaciones. Estos algoritmos procesan redes, donde las intersecciones ruta, lo
cual es esencial. O una búsqueda * para encontrar la ruta más corta o rápida entre dos
ubicaciones.
Estos algoritmos procesan un grafo de redes viales, donde las intersecciones son
nodos y las carreteras son aristas con pesos (distancia o tiempo). El algoritmo
encuentra la ruta más eficiente, esencial para la navegación.
1.2-2
Suponga que, para entradas de tamaño n en una computadora específica, la
ordenación por inserción se ejecuta en 8n² pasos y la ordenación por fusión se
ejecuta en 64 n² pasos. ¿Para qué valores de n la ordenación por inserción
supera a la ordenación por fusión?
Para n=2: 2<8log22=8, se cumple.
Para n=4: 4<8log24=16, se cumple.
Para n=8: 8<8log28=24, se cumple.
Para n=16: 16<8log216=32, se cumple.
Para n=32: 32<8log232=40, se cumple.
Para n=64:64 <8log264=48, no se cumple.
Parece que alrededor de n=44 o 45 empieza a no cumplirse.
Vamos a afinar:
Prueba con n=43:
8 log2 43 ≈ 8×5.42 ≈43.36
43<43.36
Prueba con n=44:
• 8log244 ≈8×5.46≈43.68
• 44>43.68
• Por tanto, hasta n=43, la ordenación por inserción es más rápida.
Respuesta:
• Si la ordenación por fusión corre en 64 n log2 n pasos, entonces la
ordenación por inserción es más rápida para n≤43.
• Para n≥44, ordenación por fusión es más rápida.
1.2-3
¿Cuál es el valor mínimo de n tal que un algoritmo cuyo tiempo
de ejecución es 100 n² se ejecuta más rápido que un algoritmo
cuyo tiempo de ejecución es 2 n en la misma computadora?
n 100n² 2ⁿ
1 100 2
2 400 4
3 900 8
4 1600 16
5 2500 32
6 3600 64
7 4900 128
8 6400 256
9 8100 512
10 10000 1024
11 12100 2048
12 14400 4096
13 16900 8192
14 19600 16384
15 22500 32768
16 25600 65536
Se ve que en n=15, 2n=32768 ya es mayor que 100n2=22500. Probamos n=14n:
• 100⋅142=19600
• 214=16384
• todavía no es mayor. Entonces:
• El valor mínimo de n tal que 100n2<2n es 15.
