Secuencia ordenada de pasos exentos de ambigüedad tal que, al llevarse a cabo con fidelidad, dará como resultado que se realice la tarea para la que se ha diseñado en un tiempo finito.
Un algoritmo nos permite obtener la solución del problema para el que esté diseñado.
📫
Propiedades
Finitud: La ejecución de un algoritmo debe tener un número finito de pasos.
Precisión: Cada paso debe estar rigurosamente especificado.
📖
Características
Entradas: Un algoritmo tiene 0 o más entradas.
Salidas: Un algoritmo tiene 1 o más salidas.
Resolución de Problemas
📝
En un ordenador es necesario:
Diseñar un algoritmo para un problema.
Programar el algoritmo en código.
Ejecutar el programa resultante.
Clasificación de Problemas
📖
Perspectiva Histórica
Años 3️⃣0️⃣ → Problemas computables y no computables.
Años 5️⃣0️⃣ → Complejidad de los problemas computables.
Años 7️⃣0️⃣ → Clasificación de los problemas computables.
Clase P
Problemas resolubles en Tiempo Polinómico.
Máquina de Turing Determinística.
Clase NP
Problemas resolubles en Tiempo Polinómico.
Máquina de Turing NO Determinística.
⌛
Reducción de Problemas y Complejidad
Reduciendo un problema A a otro B, se puede:
Obtener una solución con un algoritmo diseñado para B.
Obtener una solución y transformarlaen una solución para A
Si se conoce un algoritmo P que resuelva un problema NP-Completo, todos los problema de la clase NP se podrían resolver en tiempo polinómico.
Algorítmica
📖
La algorítmica es la disciplina que estudia los algoritmos
✏️Diseño
Conocimiento de las técnicas de diseño algorítmico.
Métodos exactos y heurísticos.
☑️Validación
Demostración de que la salida dada por el algoritmo es correcta para las entradas.
Demostración formal.
🔬Análisis
Recursos que consume el algoritmo.
Espacio y tiempo en la resolución de un problema.
Análisis de Eficiencia Algorítmica
📖
Determinar las características del algoritmo que permitan evaluar su rendimiento
Enfoques complementarios
Empírico.
Teórico.
Híbrido.
Ejemplo
Tiempo requerido para la ejecución de un algoritmo en término del número de veces que se ejecuta cada etapa.
