¿Qué es exactamente un algoritmo?

Sé que esto puede sonar un poco fuera de la caja, de hecho, solía pensar siempre dentro de la caja, pero recientemente he estado pensando, posiblemente porque la informática proporciona un alto grado de libertad, sobre formas de diseñar programas que no sean los que se enseñan en la universidad.

Considere la función factorial. Normalmente definimos esta función como

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

Yo llamaría a esto un algoritmo y no tengo dudas de que esta es la forma correcta de hacerlo. Entonces, me pregunté "¿puedo hacer esto en tiempo constante?", Lo que dejó la siguiente idea: ¿qué pasa si tuviera una matriz de enteros donde matriz [n] alberga el factorial de n? Una vez que esta matriz está llena, simplemente podría definir el hecho como:

 int fact(int n) 
 { 
 return array[n]; 
 } 

Todavía no puedo llamar a esto un algoritmo, a pesar de que proporciona el resultado correcto y opera en tiempo constante O (1). ¿Se puede llamar esto un algoritmo? De lo contrario, ¿por qué no? Podría argumentar que llenar el conjunto requeriría un algoritmo que hubiera funcionado en algún momento, incluso si estuviera en nuestro cerebro para que podamos completar el conjunto, pero ¿podría ser este el criterio? ¿Cómo se manejan formalmente estos aspectos?

Tenga en cuenta que este concepto podría extenderse a cualquier función que opere sobre enteros independientemente de su número de argumentos, solo tendría que usar una matriz si la función tuviera 2 argumentos, o 3 si la función tuviera 3 argumentos, y así sucesivamente. Además, ¿no se usan estas soluciones simplemente por el consumo de memoria?

Además, no es que las funciones también puedan abarcar cualquier programa con salida, ya que podría encontrar una manera de indexar cada salida posible que un programa pueda proporcionar.

Como otro ejemplo, considere el uso común de una matriz: asigno inicialmente una matriz de tamaño N, luego agrego elementos a la matriz almacenando el valor en el índice n y aumentando n en una unidad. Entonces, si quiero buscar un elemento, no puedo evitar realizar una búsqueda lineal sobre la matriz. Si, en cambio, creé una matriz de tamaño, por ejemplo, Integer.MAXVALUE, para almacenar enteros, inicializados con ceros, podría almacenar un entero colocando 1 en su índice. Entonces podría buscar su existencia en la matriz en O (1) tiempo. ¿Qué sucede si quisiera poder colocar varias unidades del mismo número? No hay problema, solo aumentaría el valor almacenado en el índice del entero.

La clasificación sería un poco más complicada, pero no obstante, la búsqueda y la suma podrían realizarse en el tiempo O (1).

La definición informal de un algoritmo en un libro de texto popular es algo así como:

Un algoritmo es (1) un procedimiento computacional bien definido (2) que toma algo de entrada y (3) produce algo de salida (4) para un problema computacional bien definido.

En su primer caso, ha codificado un algoritmo donde: El problema es encontrar el factorial (parte 4 de la definición), dado int n como entrada (parte 2 de la definición), el código describe el cálculo a realizar (parte 1 de la definición ), la salida es factorial (parte 3 de la definición).

En su segundo caso: el problema es encontrar el elemento de matriz en la posición n (parte 4 de la definición), dado n como entrada (parte 3 de la definición), el código describe el cálculo a realizar (parte 2 de la definición), el salida es el elemento en la posición n (parte 1 de la definición).

Ha almacenado factoriales allí, por lo que le da factoriales. Si hubiera almacenado cuadrados o cubos allí, obtendría cuadrados o cubos, por lo que no se puede decir que el segundo fragmento en sí mismo sea un algoritmo para calcular factoriales.

Y si usted dice que una matriz que mira hacia arriba junto con una matriz que tiene f (n) en la posición n es un algoritmo para calcular f (n), entonces se ha profundizado tanto que no hay más cálculos a continuación. Un procedimiento computacional bien definido debe ser una información finita. Si una matriz infinita de factoriales es parte del procedimiento computacional, esto no se cumple. Entonces ese no sería un algoritmo para calcular factoriales.

En términos más generales, un algoritmo es una serie de pasos para resolver un problema .

En CS, se entiende / asume comúnmente lo siguiente cuando se usa el término algoritmo:

• El algoritmo tiene una descripción finita y un procedimiento bien definido para llevar a cabo sus pasos ante cualquier instancia de problema. (Más abajo).
• Una instancia de problema dada como una cadena finita (secuencia de símbolos de entrada), y la salida del algoritmo puede codificarse como una cadena finita.
• Un problema es una colección de instancias problemáticas junto con posibles resultados "correctos" para cada instancia. "Resolver" significa producir una salida correcta.
• (Por lo general), las instancias del problema pueden ser arbitrariamente grandes (hay un número infinito de instancias posibles que su algoritmo finito debe resolver).

Antes de que se fundara CS, los matemáticos tenían los mismos tipos de inquietudes que usted planteó e introdujeron definiciones formales de cómputo para abordar estas inquietudes. Por lo tanto, hoy en día, podemos formalizar todos los supuestos anteriores simplemente diciendo "un algoritmo es un procedimiento que se puede implementar en una máquina de Turing" . Esta es probablemente la mejor respuesta formal a su pregunta.

Tenga en cuenta que la tesis de Church-Turing dice que creemos que no existe una formalización de algoritmos "más poderosa" que la máquina de Turing.

El ejemplo factorial se introduce en un modelo diferente de cómputo, llamado cómputo no uniforme. Una máquina de Turing es un ejemplo de un modelo uniforme de cómputo: tiene una descripción única y finita, y funciona para entradas de tamaño arbitrariamente grande. En otras palabras, existe una TM que resuelve el problema para todos los tamaños de entrada.

Ahora, podríamos considerar el cálculo de la siguiente manera: para cada tamaño de entrada, existe una TM (o algún otro dispositivo computacional) que resuelve el problema. Esta es una pregunta muy diferente. Tenga en cuenta que una única TM no puede almacenar el factorial de cada entero, ya que la TM tiene una descripción finita. Sin embargo, podemos hacer una TM (o un programa en C) que almacene los factoriales de todos los números por debajo de 1000. Luego, podemos hacer un programa que almacene los factoriales de todos los números entre 1000 y 10000. Y así sucesivamente.

Estos tipos de cómputo no uniformes se modelan típicamente en CS teórica por circuitos. Considera una construcción de circuito diferente para cada tamaño de entrada posible.

Los modelos de cómputo no uniformes generalmente no se consideran algoritmos , aunque podrían ajustarse a mi primera oración. La razón es que no encajan en nuestras suposiciones clave: no tienen una descripción finita que pueda implementarse para resolver el problema "completo" para cualquier tamaño de entrada. Por el contrario, necesitan una descripción más y más grande a medida que el problema se agrava (como necesitar una tabla de búsqueda más grande). Sin embargo, siguen siendo modelos interesantes de computación.

Un algoritmo es un programa escrito en C que debería funcionar para cualquier longitud de entradas (suponiendo memoria infinita y enteros ilimitados). En sus ejemplos, si quisiéramos que el programa funcionara para todas las longitudes de entradas, entonces la tabla en la que se almacenan los resultados sería infinitamente grande; Los programas en C son siempre finitos, por lo que este enfoque no puede utilizarse.

La definición de algoritmo es muy resistente: en los primeros días de la teoría de la recursividad, se propusieron muchas definiciones, y se demostró que todas eran equivalentes. Por ejemplo, en lugar de C puede usar máquinas de Turing. Sin embargo, estos modelos no son necesariamente equivalentes en términos de eficiencia : un problema podría resolverse de manera mucho más eficiente en C que con las máquinas Turing. Cuando nos interese la eficiencia, debemos restringirnos a todos los modelos que estén "lo suficientemente cerca" de C con respecto al tiempo de ejecución. Por ejemplo, si se nos permite usar una instrucción que calculeen una unidad de tiempo, entonces el modelo resultante todavía define el mismo conjunto de funciones computables, pero algunas funciones (como ) se pueden calcular de manera mucho más eficiente, en comparación con C.n $n!$$n!$

Cuando nos preocupan los tiempos de funcionamiento reales en una computadora real, deberíamos ser aún más cuidadosos, pero desafortunadamente esto generalmente está más allá de los límites de la informática teórica.

Si somos muy quisquillosos, debemos ser claros acerca de la diferencia entre algoritmos y funciones calculadas por algoritmos . Por ejemplo, la función factorial obtiene como entrada un número natural y produce. La función factorial se puede calcular mediante un algoritmo. Decimos que una función es computable si se puede calcular usando algún algoritmo.n $n$$n!$

¿Qué noción de algoritmo debemos usar? Una sugerencia, descrita anteriormente, es utilizar programas en C. Podemos llamar a esta noción C-cálculo. El cálculo de Turing es lo que obtienes cuando usas máquinas de Turing. Resulta que una función es C-computable si y solo si es Turing-computable. Es en este sentido que ambos modelos de cálculo son equivalentes. De hecho, muchos otros modelos son equivalentes, por ejemplo, todos los lenguajes de programación de uso común (suponiendo memoria infinita y variables ilimitadas).

Decimos que un lenguaje de programación P es Turing-complete es una función es P-computable si y solo si es Turing-computable. La hipótesis de la Iglesia-Turing es una declaración informal en el sentido de que todos los modelos de cómputo razonables que tienen una descripción finita y que toman un tiempo finito son completos de Turing. Su modelo tiene una descripción finita, pero no toma un tiempo finito.

La parte importante de la definición común de un algoritmo que falta el suyo es que la especificación debe ser finita , y el tamaño de la especificación no debe variar con el tamaño de la entrada.

La memoria puede ser arbitrariamente grande, al igual que las entradas, pero para ser una definición útil de un algoritmo, el espacio de código debe ser finito. De lo contrario, obtendrá el problema que acaba de identificar.

$O(\log A)$$A$$O(\log n)$$O(\log n!)$$O(n (\log n)^2)$$s$$n = O(2^s)$$O(2^s~s^2)$$O(1)$

Algunas observaciones que pueden ser útiles:

Los problemas son declaraciones sobre entradas permitidas y salidas correspondientes. Son lo que queremos resolver. Los algoritmos son procedimientos computacionales. Podemos decir que un algoritmo es correcto con respecto a un problema si acepta entradas que están permitidas con respecto al problema y produce salidas de acuerdo con la descripción del problema.

Ambos ejemplos son algoritmos, ya que ambos son claramente procedimientos computacionales. Si los algoritmos son correctos o no depende de cómo defina el problema y de cómo interprete la representación del algoritmo. Algunas declaraciones de problemas:

1. $n$$n!$
2. $n > 0$$n! <$ INT_MAX$n!$

Algunas interpretaciones de su primer fragmento de código:

1. Este es un pseudocódigo que se parece a C / C ++ excepto en los detalles. intrealmente significa "cualquier número entero", por ejemplo.
2. Esto debe interpretarse como si fuera un verdadero programa C / C ++.

La interpretación 1 es correcta para el enunciado del problema 1, siempre que el factorial asuma el valor 1 para los números negativos (de lo contrario, podríamos modificar el enunciado del problema para restringir el dominio o el algoritmo para dar cuenta del comportamiento deseado). La interpretación 2 es correcta para el enunciado del problema 2, con la misma advertencia.

arrayarray$n$$n > 0$$n! <$ INT_MAX$n!$$n < 0$

$n$$n! \geq 2^{32}$$n! \geq 2^{64}$

$k$$k$$n$$kn$$k+n$

Un algoritmo es un programa escrito en un lenguaje completo de Turing que probablemente se detiene en todas las entradas válidas. Todos los lenguajes de programación estándar son completos de Turing. La palabra se origina como una traducción europea del nombre al-Khwārizmī, un matemático persa, astrónomo y geógrafo, cuyo trabajo se basó en el del matemático indio del siglo VII Brahmagupta, quien introdujo el sistema de numeración indio en el mundo occidental.

La pregunta parece ser básicamente si las tablas de búsqueda son parte de algoritmos. ¡Absolutamente! En las máquinas Turing (TM), las tablas se pueden codificar en la tabla de estado de la TM. El TM puede inicializar la cinta en función de una cantidad finita de datos almacenados en la tabla de transición. Sin embargo, los "algoritmos" que no se ejecutan en entradas infinitas, solo entradas finitas, son máquinas de estado finito (FSM) "trivialmente" .

En pocas palabras : un algoritmo es la parte constructiva de una prueba constructiva de que un problema dado tiene una solución. La motivación para esta definición es el isomorfismo de Curry-Howard entre programas y pruebas, considerando que un programa tiene un interés solo si resuelve un problema, pero probablemente así sea. Esta definición permite una mayor abstracción, y deja algunas puertas abiertas con respecto al tipo de dominios que pueden preocuparse, por ejemplo, con respecto a las propiedades de finitud.

Advertencia . Estoy tratando de encontrar un enfoque formal adecuado para responder la pregunta. Creo que es necesario, pero parece que ninguno de los usuarios que respondieron hasta ahora (incluido yo mismo, y algunos fueron más o menos explícitos al respecto en otras publicaciones) tiene los antecedentes adecuados para desarrollar adecuadamente los problemas, que están relacionados con Matemáticas constructivas, teoría de pruebas, teoría de tipos y resultados como el isomorfismo de Curry-Howard entre pruebas y programas. Estoy haciendo mi mejor esfuerzo aquí, con cualquier fragmento de conocimiento que tenga (creo), y soy muy consciente de las limitaciones de esta respuesta. Solo espero dar algunas pistas de cómo creo que debería ser la respuesta. Si ve algún punto que está claramente equivocado formalmente (probablemente), permítame ahora en un comentario, o por correo electrónico.

Identificando algunos problemas

Una forma estándar de considerar un algoritmo es establecer que un algoritmo es un programa arbitrariamente especificado para algunos dispositivos informáticos , incluidos aquellos que no tienen limitaciones en la memoria. El idioma también puede ser el lenguaje de la computadora. En realidad, es suficiente considerar todos los programas para un dispositivo informático completo de Turing (lo que implica no tener limitaciones de memoria). Es posible que no le proporcione todas las presentaciones de algoritmos, en el sentido de que los algoritmos deben expresarse de una forma que dependa en sus detalles del contexto de interpretación, incluso teórico, ya que todo está definido hasta cierta codificación. Pero, dado que calculará todo lo que hay que calcular, incluirá de alguna manera todos los algoritmos, hasta la codificación.

$\pi$

$\pi$, posiblemente en el sentido matemático de casi todos. Pero eso requeriría más precisión en las definiciones.

Entonces, la verdadera pregunta es saber cuáles son los algoritmos significativos. La respuesta es que los algoritmos significativos son aquellos que resuelven un problema, calculando paso a paso la "solución", la "respuesta" a ese problema. Un algoritmo es interesante si está asociado con un problema que resuelve.

Entonces, dado un problema formal, ¿cómo obtenemos un algoritmo que resuelva el problema? Ya sea explícita o implícitamente, los algoritmos están asociados con la idea de que existe una solución al problema, que puede probarse que es correcta. Si nuestras técnicas de prueba son precisas es otra cuestión, pero al menos tratamos de convencernos. Si se limita a las matemáticas constructivas, que en realidad es lo que tenemos que hacer (y es una restricción axiomática muy aceptable para la mayoría de las matemáticas), la forma de demostrar la existencia de una solución es pasar por los pasos de prueba que realmente muestran una construcción eso representa la solución, incluidos posiblemente otros pasos que establecen su corrección.

Todos los programadores piensan algo así: si jugueteo con los datos de tal o cual manera, obtengo este widget que tiene las propiedades correctas debido al teorema de Sesame, y al ejecutar esta transformación de preservación de foo obtengo la respuesta deseada . Pero la prueba suele ser informal, y no elaboramos todos los detalles, lo que explica por qué un satélite intentó orbitar Marte bajo tierra (entre otras cosas). Hacemos gran parte del razonamiento, pero en realidad solo conservamos la parte constructiva que construye la solución, y la describimos en un lenguaje de computadora como el algoritmo que resuelve el problema.

Algoritmos (o programas) interesantes

Todo esto fue para introducir las siguientes ideas, que son objeto de mucha investigación actual (de las cuales no soy especialista). La noción de " algoritmo interesante " utilizada aquí es mía, introducida como un lugar informal para obtener definiciones más precisas.

Un algoritmo interesante es la parte constructiva de una prueba constructiva de que un problema dado tiene una solución . Eso significa que la prueba realmente debe exhibir la solución en lugar de simplemente demostrar su existencia, por ejemplo, por contradicción. Para más detalles, ver Lógica intuitiva y constructivismo en matemáticas.

Por supuesto, esta es una definición muy restrictiva, que considera solo lo que llamé algoritmos interesantes. Entonces los ignora a casi todos. Pero también lo hacen todos nuestros libros de texto sobre algoritmos. Intentan enseñar solo algunos de los interesantes.

Dados todos los parámetros del problema (datos de entrada), le indica cómo obtener un resultado específico paso a paso. Un ejemplo típico es la resolución de ecuaciones (el algoritmo de nombre se deriva realmente del nombre de un matemático persa, Muḥammad ibn Mūsā al-Khwārizmī , que estudió la resolución de algunas ecuaciones). Partes de la prueba se utilizan para establecer que algunos valores calculados en el algoritmo tienen algunas propiedades, pero estas partes no necesitan mantenerse en el algoritmo mismo.

Por supuesto, esto debe tener lugar dentro de un marco lógico formalizado que establezca con qué se computan los datos, cuáles son los pasos computacionales elementales permitidos y cuáles son los axiomas utilizados.

Volviendo a su ejemplo factorial, puede interpretarse como un algoritmo, aunque sea trivial. La función factorial normal corresponde a una prueba de que, dado un marco aritmético, y dado un número entero n, hay un número que es el producto de los primeros n números enteros. Esto es bastante sencillo, como lo es el cálculo factorial. Podría ser más complejo para otras funciones.

Ahora, si decide tabular factorial, suponiendo que puede, lo cual no es cierto para todos los enteros (pero podría ser cierto para algunos dominios finitos de valores), todo lo que está haciendo es incluir en sus axiomas la existencia de factorial definiendo con un nuevo axioma su valor para cada número entero, por lo que ya no necesita probar (por lo tanto, calcular) nada.

Pero se supone que un sistema de axiomas es finito (o al menos finitamente definido). Y hay una infinidad de valores para factorial, uno por entero. Por lo tanto, tiene problemas para su sistema finito de axiomas si axiomatiza una función infinita, es decir, definida en un dominio infinito. Eso se traduce computacionalmente en el hecho de que su posible búsqueda de tabla no se puede implementar para todos los enteros. Eso eliminaría el requisito habitual de finitud para los algoritmos (pero ¿será tan estricto como se presenta a menudo?).

Podría decidir tener un generador de axiomas definido de forma finita para manejar todos los casos. Esto equivaldría, más o menos, a incluir el programa factorial estándar en su algoritmo para inicializar la matriz según sea necesario. Eso se llama memorización por parte de los programadores. Esto es en realidad lo más cerca que está del equivalente de una tabla calculada previamente. Se puede entender que tiene una tabla precalculada, excepto por el hecho de que la tabla se crea realmente en modo de evaluación diferida , siempre que sea necesario. Esta discusión probablemente necesitaría un poco más de atención formal.

Puede definir sus operaciones primitivas como lo desee (de acuerdo con su sistema formal) y asignarles el costo que elija cuando lo utilice en un algoritmo, para realizar análisis de complejidad o rendimiento. Pero, si los sistemas concretos que realmente implementan su algoritmo (una computadora o un cerebro, por ejemplo) no pueden respetar estas especificaciones de costos, su análisis puede ser intelectualmente interesante, pero no tiene valor para el uso real en el mundo real.

$2^{1000}$

¿Qué programas son interesantes?

Esta discusión debería estar más correctamente vinculada a resultados como el isomorfismo de Curry-Howard entre programas y pruebas. Si algún programa es en realidad una prueba de algo, cualquier programa puede interpretarse como un programa interesante en el sentido de la definición anterior.

Sin embargo, a mi entender (limitado), este isomorfismo se limita a programas que se pueden escribir bien en algún sistema de escritura apropiado, donde los tipos corresponden a proposiciones de la teoría axiomática. Por lo tanto, no todos los programas pueden calificar como programas interesantes. Supongo que es en ese sentido que se supone que un algoritmo resuelve un problema.

Esto probablemente excluye la mayoría de los programas "generados aleatoriamente".

También es una definición algo abierta de lo que es un "algoritmo interesante". Cualquier programa que pueda verse como interesante definitivamente lo es, ya que hay un sistema de tipos identificado que lo hace interesante. Pero un programa que no se podía escribir hasta ahora, podría convertirse en un sistema de escritura más avanzado y, por lo tanto, volverse interesante. Más precisamente, siempre fue interesante, pero por falta de conocimiento del sistema de tipos adecuado, no pudimos saberlo.

Sin embargo, se sabe que no todos los programas se pueden escribir, ya que se sabe que algunas expresiones lambda, como la implementación del combinador Y , no se pueden escribir en un sistema de tipo de sonido .

Esta vista solo se aplica a formalismos de programación que pueden asociarse directamente a algún sistema de prueba axiomático. No sé cómo se puede extender a formalismos computacionales de bajo nivel como la Máquina de Turing. Sin embargo, dado que la algorítmica y la computabilidad son a menudo un juego de codificación de problemas y soluciones (piense en la aritmética codificada en cálculo lambda ), se puede considerar que cualquier computación formalmente definida que pueda mostrarse como una codificación de un algoritmo también es un algoritmo. Tales codificaciones probablemente usan solo una parte muy pequeña de lo que se puede expresar en un formalismo de bajo nivel, como las Máquinas de Turing.

Un interés de este enfoque es que da una noción de algoritmo que es más abstracta e independiente de los problemas de codificación real, de "representabilidad física" del dominio de cómputo. Entonces, por ejemplo, uno puede considerar dominios con objetos infinitos siempre que haya una forma computacionalmente sólida de usarlos.

No existe una buena definición formal de "algoritmo" en el momento de la escritura. Sin embargo, hay personas inteligentes trabajando en ello.

Lo que sabemos es que, sea lo que sea un "algoritmo", se ubica entre la "función matemática" y el "programa de computadora".

Una función matemática es la noción formal de una asignación de entradas a salidas. Entonces, por ejemplo, "ordenar" es un mapeo entre una secuencia de elementos ordenables y una secuencia de elementos ordenables del mismo tipo, que asigna cada secuencia a su secuencia ordenada. Esta función podría implementarse utilizando diferentes algoritmos (p. Ej., Clasificación de combinación, clasificación de montón). Cada algoritmo, a su vez, podría implementarse utilizando diferentes programas (incluso con el mismo lenguaje de programación).

Entonces, el mejor manejo que tenemos de lo que es un "algoritmo" es que es algún tipo de clase de equivalencia en los programas, donde dos programas son equivalentes si hacen "esencialmente lo mismo". Cualquiera de los dos programas que implementan el mismo algoritmo debe calcular la misma función, pero lo contrario no es cierto.

Del mismo modo, hay una clase de equivalencia entre algoritmos, donde dos algoritmos son equivalentes si calculan la misma función matemática.

La parte difícil de todo esto es tratar de capturar lo que queremos decir con "esencialmente lo mismo".

Hay algunas cosas obvias que debemos incluir. Por ejemplo, dos programas son esencialmente lo mismo si difieren solo por cambios de nombre variables. La mayoría de los modelos de lenguajes de programación tienen nociones nativas de "equivalencia" (por ejemplo, reducción de beta y conversión de eta en cálculo lambda), por lo que también debemos incluirlos.

Cualquiera sea la relación de equivalencia que elijamos, esto nos da cierta estructura. Los algoritmos forman una categoría en virtud del hecho de que son la categoría de cociente de los programas. Se sabe que algunas relaciones equivalentes interesantes dan lugar a estructuras categóricas interesantes; por ejemplo, la categoría de algoritmos recursivos primitivos es un objeto universal en la categoría de categorías. Siempre que vea una estructura interesante como esa, sabrá que esta línea de investigación probablemente será útil.

Su pregunta y descripción no se relacionan tanto. El algoritmo es teórico y no se relaciona con ningún lenguaje de programación. El algoritmo es un conjunto de reglas o pasos (procedimiento) para resolver un problema. Su problema puede resolverse de muchas maneras o con muchos algoritmos.

Sus segundas soluciones significan calcular primero una gran variedad de factoriales que inicialmente llevarán mucho tiempo y luego almacenarlos. Consumirá más almacenamiento, pero eventualmente será más rápido, mientras que el primero no consume almacenamiento, sino que consume potencia informática, por lo que tendrá que elegir según su entorno.