Algorítmica 101

Algorítmico

La algoritmia siempre ha existido, es un proceso de pensamiento descrito de manera lógica. Aunque hoy en día este sistema nos parece imprescindible para muchas ciencias, la sistematización de la escritura algorítmica ha ido evolucionando con el tiempo y las tecnologías. Comenzó en la época de los babilonios, hasta que René Descartes lo estableció concretamente en el método general propuesto por los Discurso sobre el método en 1637.

La algoritmia moderna, incluido el llamado lenguaje de "programa", hizo su debut poco después, en 1677. El término que usamos hoy, "algoritmo", apareció 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.

Junto con las computadoras, los algoritmos se desarrollaron mucho en la segunda mitad del s. XX^mi Century y Knuth (1969), autor de The Art of Computer Programming definen 5 propiedades que constituyen los requisitos previos de un algoritmo.

1. Finitud: un algoritmo debe terminar después de un número finito de pasos.

2. Definición precisa: cada paso de un algoritmo debe definirse con precisión y sin ambigüedades.

3. Entradas: cantidades que se definen antes de que comience el algoritmo.

4. Productos: cantidades que tienen una relación específica con los insumos.

5. Rendimiento: todas las operaciones que debe realizar el algoritmo deben ser lo suficientemente básicas como para poder en principio ser realizadas en un periodo de tiempo finito por un hombre utilizando papel y lápiz.

Markov (1967) define un algoritmo como “una prescripción exacta que define un proceso de procesamiento que conduce desde los datos iniciales hasta el resultado final”.

Lo que implica las siguientes características:
• Precisión de la prescripción que no deja lugar a la arbitrariedad y la comprensión universal • Posibilidad de partir de datos iniciales que pueden variar dentro de límites dados • La orientación del algoritmo en la búsqueda de un resultado deseado que debe obtenerse al final de la ejecución de los datos iniciales: esta es la propiedad de conclusión del algoritmo.

Para Minsky (1967) la definición es aún más directa:
“Un conjunto de reglas que nos dicen, de momento en momento, exactamente cómo comportarnos”

Y finalmente para Stone (1972)
“Un algoritmo es un conjunto de reglas que define con precisión una secuencia de operaciones de modo que cada regla sea efectiva y esté definida y la secuencia se complete en un tiempo finito. »

Además especifica que:
“para quienes siguen las reglas del algoritmo, deben formularse de manera que se sigan mecánicamente sin tener que pensar”

Por ejemplo :
Si las instrucciones requieren extraer una raíz cuadrada y las realiza alguien que sabe hacer aritmética pero no sabe cómo extraer una raíz cuadrada, entonces se debe proporcionar un conjunto de reglas para extraer una raíz cuadrada, de modo que se cumpla la definición de el algoritmo

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.

Transcribir un algoritmo

LOSlenguaje natural : detallado y ambiguo, rara vez se usa para algoritmos complejos pero no está prohibido.
Pseudocódigo : un lenguaje estructurado, pero sin reglas estrictas definidas; Independiente de cualquier implementación
Organigrama : sin ambigüedad, buena legibilidad, escritura en forma de símbolos estandarizados
LOSlenguajes de programación : normalmente destinado a transcribir diagramas de flujo en una forma comprensible para las computadoras; También se puede utilizar para describir algoritmos.
LOSlenguajes algorítmicos : lenguaje que utiliza pseudocódigo compuesto de reglas fijas, comprensibles por una computadora, que permite la descripción y ejecución de algoritmos.

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 programa de computadora. El procesador se encarga de memorizar la dirección de la siguiente instrucción a ejecutar, bloques (bucles, if, etc.) o 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 programación tiene un tipo de estructura de control y estructura de datos. La escritura de un algoritmo se basa muy a menudo en lenguajes muy extendidos como C, java, etc.

Nociones de terminación, corrección, integridad

La terminación es la garantía de que el algoritmo se completará 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 completitud 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 una complejidad temporal.

Corrección : cualquier respuesta calculada del algoritmo es una solución del problema.

Lo completo : el algoritmo puede calcular una respuesta para cualquier instancia del problema.

Complejidad algorítmica

La complejidad del algoritmo es una evaluación del costo de ejecutar un algoritmo en términos de tiempo (complejidad de tiempo) o espacio de memoria (complejidad de espacio). La eficiencia de un algoritmo depende por tanto 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:

Las clases de complejidad son conjuntos de problemas que tienen la propiedad de tener todos la misma complejidad según un determinado criterio. Las clases más conocidas son clases definidas en máquinas de Turing (deterministas o no deterministas; consulte el curso sobre autómatas) con limitaciones de tiempo y espacio. Existe una relación entre la complejidad algorítmica y su costo energético de operación, llamada 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 de enumeración combinatoria ingenua