Programacion y algorimos priemer parcial

Algoritmo

Secuencia lógica y finita de pasos para resolver un problema o tarea específica

Problema P

Soluciones que se encuentran en tiempos razonables

Problemas NP

Difíciles de resolver y fáciles de verificar han vez propuesta la solución

Problema de decisión

Aquellos cuya respuesta es Si o No

Problemas de optimización

Buscan la mejor respuesta entre todas las posibles

Diferencia entre problemas P y NP

Los P se resuelven en tiempos razonables

Los NP son difíciles de resolver pero fáciles de verificar una vez propuesta la solución

Diferencia de problema de decisión a optimización

El de decisión responde si o no

El de optimización busca la mejor respuesta entre las posibles

Estrategia de fuerza bruta

Probar todas las posibilidades hasta encontrar la correcta , es simple pero ineficiente para problemas grandes

Divide y Vencerás

Dividir un problema grande en subproblemas mas pequeños hasta que sean fáciles de resolver

Cómo funciona Greedy

Lógica de un algoritmo voraz, tomar la mejor decisión en cada paso esperando encontrar el óptimo global , es rápido pero no perfecto

Algoritmo Dijkstra

Algoritmo voraz utilizado para encontrar la ruta más corta en un mapa

Optimización de algoritmos

Ajustar un algoritmo para usar menos recursos , ser más rápido mediante la reducción de pasos , reutilizacion de datos y mejores estructuras

Que mide la complejidad temporal en relación al hardware

Mide cuantas operaciones realiza el CPU

Más pasos - más ciclos de reloj se consumen , esto genera calor y más tiempo

Relación con el procesador

El CPU es el ejecutor, la complejidad temporal mide cuantas operaciones debe realizar el procesador

Complejidad espacial

Cantidad de memoria RAM que el algoritmo necesita para almacenar variables , datos temporales y pila de ejecución

Stack (Pila)

Para llamadas a funciones y recursion

Heap (Montículo)

Para datos dinámicos y grandes objetos

Uso eficiente

Evitar duplicar datos inecesarios

Función de Stack y Heap en la memoria

Stack- Se usa para llamadas a funciones y recursion

Heap-Datos dinámicos y grandes objetos

Trade off entre tiempo y memoria

Para ganar velocidad se necesita más memoria

Si la memoria es limitada el procesador debe trabajar más re calculando

Algoritmos en la vida diaria

GPS Y MAPAS - cálculos de rutas más rápidas

REDES SOCIALES - sugerencias de contenido basadas en tus gustos

Logística - Organización de paquetes para ahorrar espacio