Teoría de los Algoritmos
TEORÍA DE LOS ALGORITMOS
¿Qué estudia?
La teoría de los algoritmos estudia la estructura, la eficiencia y las propiedades de los algoritmos. Se centra en la formulación de procedimientos paso a paso para resolver problemas computacionales y analiza su rendimiento en términos de complejidad temporal y espacial.
Conceptos Fundamentales
Un algoritmo es una secuencia finita de pasos bien definidos que resuelven un problema o realizan una tarea. Debe cumplir con:
- Definición precisa: cada paso debe estar claramente especificado.
- Entrada y salida: recibe datos de entrada y produce un resultado.
- Eficiencia: debe ejecutarse en un tiempo razonable.
- Finitud: debe terminar en un número finito de pasos
Clasificación de Algoritmos
Los algoritmos pueden clasificarse según distintos criterios:
a) Según su diseño:
- Dividir y vencerás: divide el problema en subproblemas más pequeños y los resuelve recursivamente (ejemplo: Quicksort, MergeSort).
- Greedy (voraces): toman la mejor decisión en cada paso sin considerar el impacto global (ejemplo: Algoritmo de Dijkstra).
- Programación dinámica: resuelve problemas dividiéndolos en subproblemas superpuestos y almacenando resultados previos (ejemplo: Fibonacci, Algoritmo de Floyd-Warshall).
- Backtracking: explora todas las soluciones posibles descartando las que no cumplen con los requisitos (ejemplo: Sudoku, N-Queens).
- Algoritmos probabilísticos: incluyen aleatoriedad en su proceso (ejemplo: Monte Carlo, Algoritmos genéticos).
b) Según su complejidad computacional
- Polinomiales (P): pueden resolverse en tiempo polinomial (ejemplo: ordenamiento por inserción).
- NP (No determinísticos polinomiales): no se conoce un algoritmo eficiente para resolverlos, pero sí para verificarlos (ejemplo: el problema del viajante).
- NP-Completos y NP-Difíciles: problemas más complejos dentro de NP, que si se resuelven eficientemente, resolverían todos los problemas NP (ejemplo: SAT, el problema de la mochila).
Complejidad de Algoritmos
a) Notación Big-O
Se usa para expresar el peor caso del tiempo de ejecución de un algoritmo:
- O(1) → Tiempo constante (ejemplo: acceso a un elemento de un array).
- O(log n) → Logarítmico (ejemplo: búsqueda binaria).
- O(n) → Lineal (ejemplo: recorrer un array).
- O(n log n) → Cuasi-lineal (ejemplo: MergeSort, Quicksort).
- O(n²) → Cuadrático (ejemplo: ordenamiento burbuja).
- O(2^n) → Exponencial (ejemplo: Fibonacci recursivo sin optimización).
- O(n!) → Factorial (ejemplo: resolver el problema del viajante con fuerza bruta).
b) Espacio de memoria
Se mide en términos del uso de memoria en función del tamaño de la entrada.
- Puede ser constante O(1), lineal O(n) o exponencial O(2^n).
Importancia de los Algoritmos
Los algoritmos tienen muchas utilidades prácticas:
Para saber más, haz click en este enlace → Extensión de Info en La Teoría de los Algoritmos
Este comentario ha sido eliminado por el autor.
ResponderEliminarEl texto proporciona una explicación clara y concisa sobre la teoría de los algoritmos, abarcando su estructura, eficiencia y propiedades. Destaca los conceptos fundamentales de los algoritmos, su clasificación según la estructura y complejidad computacional, así como la notación Big O para evaluar el rendimiento. La información está bien organizada y resulta útil para estudiantes y profesionales en computación. Podría mejorarse con ejemplos prácticos para ilustrar mejor cada tipo de algoritmo y su aplicación en problemas reales.
ResponderEliminarAqui dejo un enlace sobre la importancia de los algoritmos https://ceslopedevega.com/la-importancia-de-los-algoritmos/
Este comentario ha sido eliminado por el autor.
ResponderEliminarMuy buena manera de explicar el tema, es clara y la habéis estructurado de manera que cualquiera pueda entender el contenido. Hasta que he leído esta entrada no era consciente de lo mucho que influyen en el día a día de la gente. Se me hace un poco difícil entender la notación big-o, a pesar de esto la parte que más interesante me ha resultado es la de la importancia de los algoritmos porque habéis incluido áreas en las que se utilizan que no sabía que los necesitaban. Muy buena entrada, me ha encantado chicas!!!
ResponderEliminarDejo por aquí un enlace para entender mejor la notación big-o : https://youtu.be/UPDjjuz1Hkw?si=l9Yfd_PueVP3yDX7
¡Me flipa la teoría de los algoritmos! Es impresionante cómo nos deja resolver problemas de manera tan eficiente. Me parece súper guay la manera en que diferentes enfoques algorítmicos pueden cambiar radicalmente lo que rinde un programa. Su enfoque en inteligencia artificial, ciencia de datos y mejora lo hace aún más divertido . Me encanta cómo los algoritmos no solo son teoría, también que tienen un impacto real en nuestra vida diaria y en la tecnología del futuro.
ResponderEliminarhttps://youtu.be/PcTldGqiy70?si=NP2Wtf7U2zWsd_Os
¡Que manera mas interesante de hablar sobre la teoría de los algoritmos! He estado un rato leyendola y he disfrutado mucho de la lectura ya que este blog es muy interesante y la manera en la que está estrito hace que la lectura sea muy amena y rápida. Se lo recomiendo a todo el mundo que esté minimamente interesado en este tema.
ResponderEliminarAqui dejo un video muy interesante sobre el tema https://youtu.be/U3CGMyjzlvM?si=CBkVugja_S0s3Ur1