- Tutorial de codificación de Huffman
- Ejercicios corregidos sobre estructuras de control y estructuras de datos
- Ejercicios corregidos de complejidad temporal
- Ejercicios corregidos sobre complejidad del tiempo (es)
- Ejercicios corregidos sobre algoritmos recursivos, terminales, múltiples y cruzados
- Ejercicios corregidos de tipo licencia sobre el paradigma divide y vencerás
- Ejercicios corregidos sobre algoritmos en Divide and Conquer y Programación Dinámica
- Ejercicios corregidos sobre divide y vencerás y programación dinámica.
- Ejercicio de Branch and Bound corregido paso a paso en números enteros LP
- Ejercicios de Programación Lógica de Restricciones Corregidas
- Ejercicios corregidos sobre algoritmos de clasificación
Algorítmico
Los algoritmos han existido desde siempre, es un proceso de pensamiento que se describe de manera lógica. Si bien este sistema nos parece hoy fundamental para muchas ciencias, la sistematización de la escritura algorítmica ha ido evolucionando a lo largo del tiempo y a través de la tecnología. Comenzó en la época de los babilonios, hasta que fue concretamente establecido por René Descartes en el método general propuesto por el Discurso sobre el método en 1637.
Los algoritmos modernos, incluido el llamado lenguaje de "programa", hicieron su debut poco después en 1677. El término que usamos hoy, "algoritmo", aparece dos siglos después.
El algoritmo de XXmi y XXImi century se basa a menudo en formalismos como el de las máquinas de Turing, que proporciona un marco científico para estudiar las propiedades de los algoritmos.
Con la informática, los algoritmos se desarrollaron mucho en la segunda mitad del XXmi siglo y Donald Knuth, autor de la El arte de la programación informática poniendo las bases Matemáticas rigurosos en su análisis.
Se han desarrollado muchas herramientas formales o teóricas para describir algoritmos, estudiarlos, expresar sus cualidades y poder compararlos:
- estructuras algorítmicas: estructuras de control y estructuras de datos.
- las nociones de corrección, completitud y terminación.
- la teoria de complejidad.
Estructura de control y estructura de datos
Esta secuencia de instrucciones también se denomina flujo de ejecución de un programa y se puede representar mediante un grafico de flujo de control o un autómata. Cierto paradigma de programación que llama a varios procesadores se expone entonces al problema de la asignación de tareas en los procesadores.
Cada lenguaje de computadora tiene un tipo de estructura de control y estructura de datos. La escritura de un algoritmo se basa muy a menudo en lenguajes ampliamente utilizados como C, java, etc.
Nociones de terminación, corrección, integridad
La terminación es la garantía de que el algoritmo terminará en un tiempo finito. Las pruebas de terminación generalmente involucran una función entera positiva estrictamente decreciente en cada paso / iteración del algoritmo.
Dada la garantía de que un algoritmo terminará, la prueba de corrección debe proporcionar la seguridad de que si el algoritmo termina dando una solución propuesta, entonces esta solución es correcta (en el sentido de que responde al problema planteado).
La prueba de integridad garantiza que, para un espacio de problema dado, el algoritmo, si termina, dará una solución para cada una de las entradas del algoritmo.
Terminación : el algoritmo tiene complejidad de tiempo.
Corrección : cualquier respuesta calculada del algoritmo es la solución del problema.
Lo completo : el algoritmo puede calcular una respuesta para cualquier instancia del problema.
Complejidad algorítmica
algoritmo: el rendimiento "natural" de un algoritmo fuera del entorno en el que se implementará este último.
Existen varios tipos de análisis del rendimiento de un algoritmo:
- Análisis optimista (análisis del mejor de los casos o análisis del mejor de los casos).
- El análisis promedio es a menudo un factor en el paradigma de programación utilizado.
- Análisis pesimista (análisis del peor de los casos o análisis del peor de los casos).
Las clases de complejidad son conjuntos de problemas que tienen la misma complejidad según un determinado criterio. Las clases más conocidas son las clases definidas en máquinas de Turing (deterministas o no deterministas; consulte el curso sobre autómatas) con restricciones de tiempo y espacio. Existe una relación entre la complejidad algorítmica y su costo energético de operación, llamado principio de Landauer.
A continuación, se muestra una lista de las complejidades más comunes:
Clasificación | Tipo de complejidad |
---|---|
![]() | Complejidad constante: una tarea, un cálculo elemental, etc. |
![]() | complejidad logarítmica: dicotomía, árbol |
![]() | complejidad lineal: un bucle |
![]() | complejidad casi lineal: divide y vencerás, árbol |
![]() | Complejidad cuadrática: anidando dos bucles |
![]() | complejidad cúbica: anidamiento de tres bucles |
![]() | Complejidad polinomial: anidamiento de bucles sin conocimiento de estados. |
![]() | Complejidad cuasi-polinomial: divide y vencerás |
![]() | complejidad exponencial: árbol, fuerza bruta |
![]() | Complejidad factorial: enfoque ingenuo de la enumeración combinatoria |