Algoritmos: sistemas complejos e inteligencia artificial

I. Escribir y modelar un algoritmo

Análisis:

II. Paradigmas y estrategias de programación

III. Paradigmas algorítmicos

IV. Programación multiagente

Alternar contenido

V. Ejercicios y Tutoriales

VI. Sinopsis del curso

contenido

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 XX^mi y XXI^mi 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 XX^mi 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

Una estructura de control es un comando que controla el orden en que se ejecutan las diversas instrucciones de un algoritmo o un programa de computadora. El procesador se encarga de memorizar la dirección de la siguiente instrucción a ejecutar, los bloques (bucles, if, etc.) o las subrutinas.

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.

Una estructura de datos es una estructura lógica destinada a contener datos, con el fin de darles una organización que permita simplificar su procesamiento. Existen muchos tipos de estructura de datos en función de las acciones a realizar sobre ellos, no nos demoraremos más en este tema.

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

La complejidad de los algoritmos es una evaluación del costo de ejecutar un algoritmo en términos de tiempo (complejidad temporal) o espacio de memoria (complejidad espacial). Por tanto, la eficacia de un algoritmo depende de estos dos criterios, que intentaremos minimizar.

La complejidad algorítmica permite conocer la eficiencia intrínseca de un
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
$O (1)$	Complejidad constante: una tarea, un cálculo elemental, etc.
$O (\ log (n))$	complejidad logarítmica: dicotomía, árbol
$Nosotros)$	complejidad lineal: un bucle
$O (n \ log (n))$	complejidad casi lineal: divide y vencerás, árbol
$O (n ^ {2})$	Complejidad cuadrática: anidando dos bucles
$O (n ^ {3})$	complejidad cúbica: anidamiento de tres bucles
$O (n ^ p)$	Complejidad polinomial: anidamiento de bucles sin conocimiento de estados.
$O (n ^ {\ log (n)})$	Complejidad cuasi-polinomial: divide y vencerás
$O (2 ^ {n})$	complejidad exponencial: árbol, fuerza bruta
$¡Nosotros!)$	Complejidad factorial: enfoque ingenuo de la enumeración combinatoria