Voy a dar la misma respuesta que di la vez anterior que surgió esta pregunta.

Primero, comprenda que no existe una buena definición formal de «algoritmo» en el momento de escribir este artículo. La palabra clave aquí es «formal».

Sin embargo, hay gente inteligente trabajando en él.

Lo que sabemos es que sea lo que sea un «algoritmo», se encuentra en algún lugar entre «función matemática» y «programa de computadora».

Una función matemática es noción formal de un mapeo de entradas a salidas. Así, por ejemplo, «ordenar» es un mapeo entre una secuencia de elementos ordenables y una secuencia de elementos ordenables del mismo tipo, que mapea cada secuencia a su secuencia ordenada. Esta función podría implementarse utilizando diferentes algoritmos (por ejemplo, clasificación por fusión, clasificación por montón). Cada algoritmo, a su vez, podría ser implementado usando diferentes programas (incluso dado el mismo lenguaje de programación).

Así que el mejor control que tenemos sobre lo que es un «algoritmo» es que es algún tipo de clase de equivalencia en programas, donde dos los programas son equivalentes si hacen «esencialmente lo mismo». Dos programas cualesquiera que implementen el mismo algoritmo deben calcular la misma función, pero lo contrario no es cierto.

De manera similar, existe 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 captar lo que queremos decir con «esencialmente lo mismo».

Hay algunas cosas obvias que debemos incluir. Por ejemplo, dos programas son esencialmente iguales si solo se diferencian por el cambio de nombre de las variables. La mayoría de los modelos de lenguajes de programación tienen nociones nativas de «equivalencia» (por ejemplo, reducción beta y conversión eta en el cálculo lambda), por lo que deberíamos incluirlas también.

Cualquiera que 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 cociente de los programas. Se sabe que algunas relaciones de equivalencia interesantes dan lugar a interesantes estructuras categóricas; 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 consulta probablemente será útil.

Comentarios

• Gracias por su respuesta precisa, solo otra pregunta. Si consideramos cualquier programa, independientemente de lo que haga, todavía obtienen algunas entradas y siguen algunas instrucciones, y dan algunos resultados a medida que se ejecutan. Incluso pueden ‘ no resolver ningún problema (como lo llamamos), pero sigue siendo un mapeo. ¿podrían ser algoritmos conocidos, me refiero a cualquier programa?
• Si ‘ te estoy leyendo correctamente, ‘ estoy preguntando si una definición formal de un » algoritmo » debería o no incluir la condición de que debe ser » útil «. Yo diría » no «, aunque solo sea porque ‘ es imposible formalizar eso idea.
• ¡lo siento! mi inglés no está bien, entonces dices » no » ¿a qué? ¿Admite que es ‘ imposible formalizar la utilidad de un programa, y sólo por definición, cualquier programa es un algoritmo? ¿O dices que es ‘ necesario que consideremos la utilidad al lado del algoritmo?
• No ‘ t creo que una definición formal de un » algoritmo » debería requerir que sea útil, porque » útil » puede ‘ t ser definido formalmente.
• Su respuesta es la más útil en este hilo +1. Creo que por » esencialmente lo mismo «, te refieres a » semánticamente equivalente «. Además, creo que todos los programas son esencialmente algoritmos (como dice OP), ya que todos los programas son implementaciones que asignan alguna entrada a alguna salida, incluso si esta asignación es implícita. Como dijiste, todo depende de la perspectiva.

En última instancia, la diferencia es de perspectiva . Un programa es un programa: una secuencia de declaraciones en algún lenguaje, quizás un lenguaje de programación o instrucciones a nivel de máquina. Los algoritmos generalmente se describen en un nivel más alto que las instrucciones de la máquina o las declaraciones del lenguaje de programación, pero qué tan alto es un nivel bastante flexible. Por ejemplo, en algunas circunstancias, «Ordene la matriz, luego observe el elemento $ k $ ésimo» es una descripción perfectamente buena de un algoritmo para encontrar el objeto $ k $ ésimo más grande en una matriz; en otras circunstancias, es posible que desee especificar muchos más detalles sobre cómo se lleva a cabo la clasificación.

Como usted dice, un algoritmo es algo así como «un proceso o conjunto de reglas que se deben seguir en los cálculos u otros problemas -resolver operaciones, especialmente por computadora. » Entonces, literalmente hablando, cada programa es un algoritmo. Sin embargo, normalmente hablamos de programas que implementan algoritmos. Por lo general, al describir un algoritmo, evitamos el detalle de bajo nivel de exactamente cómo se implementan las cosas, asumiendo que un programador competente podría implementarlo en el idioma que elija.

Comentarios

• Creo que la precisión del algoritmo está relacionada con el concepto matemático, el cálculo lambda o la máquina de Turing, aún no ‘ no sé qué es eso lenguaje de abstracción? matemáticas o un lenguaje natural con muchas declaraciones borrosas
• @Ahmad El algoritmo es un concepto informal. No tiene una definición formal. En cierto sentido, ‘ es como una prueba matemática, que es diferente de una prueba formal en un sistema de prueba formal. Creemos que las pruebas informales se pueden » desarrollar » en pruebas formales en cualquier sistema de prueba formal elegido (lo suficientemente fuerte), al igual que cualquier El algoritmo se puede implementar completamente en cualquier lenguaje de programación (Turing-completo).

Algoritmos en el Turing -La mentalidad completa generalmente se especifica por entrada y salida. Los programas reales hacen más;

• se comunican con el usuario,
• se comunican con otras máquinas,
• reaccionan al entorno,
• no terminan y siguen siendo útiles,

y más. Por lo general, estas cosas no se consideran en los algoritmos o la teoría de la computación, pero son esenciales para la mayoría de los programas.

Comentarios

• Este es un muy buen punto. Pero, ¿te refieres a algo como » normalmente especificado como un medio para asignar la entrada a la salida «? Solo especificar la entrada y la salida no es ‘ t suficiente: por ejemplo, mergesort y quicksort producen la misma salida de cualquier entrada, pero no ‘ t se consideran para ser el mismo algoritmo.
• @DavidRicherby Estaba pensando en la especificación en el sentido PL; no ‘ t especificamos nada más, por lo que los algoritmos no pueden hacer nada más. Por supuesto, tenemos que dar más que la especificación para describir un algoritmo concreto.
• Buenos puntos, pero si admitimos que al final cualquier programa es un algoritmo, no ‘ No sé cómo se miden los asuntos que abordó sobre un algoritmo. ¿Quizás un tema de IA?
• ¿Quién admitiría eso y por qué? ¿Y a qué te refieres con medida aquí? (Y ciertamente no ‘ veo el ángulo de la IA aquí).
• @Raphael, puedo admitirlo (mirando la sintaxis, todos los programas se ven similares, son secuencias de instrucciones, o mapeo de entrada a salida), simplemente no ‘ no sé cómo otras características de un programa (aquellas a las que usted se dirigió) pueden extraerse de esa definición. por ejemplo, la diferencia entre clasificación rápida y MATLAB o Windows Media Player !!

• Un algoritmo es un enfoque sistemático para resolver un problema específico.

• Un programa es un conjunto de instrucciones que debe seguir una computadora.

Por lo tanto, un programa ni siquiera necesita resolver un problema.Estoy seguro de que todos podemos pensar en varios programas que han causado más problemas de los que han resuelto. Un programa puede ser una implementación de muchos algoritmos, o un algoritmo puede implementarse parcheando muchos programas. Un programa puede incluso no contener algoritmos. Por ejemplo, el programa vacío que simplemente sale, o quizás incluso un Hola mundo, podría considerarse un programa sin algoritmo.

Dado que un algoritmo resuelve un problema específico, se centra en un concepto completo específico. Por tanto, un algoritmo proporciona pasos abstractos para procesar un conjunto de información relacionada en un conjunto diferente de información derivada. Un programa no requiere que sus componentes estén relacionados conceptualmente. Por ejemplo, un programa puede tener un easter egg, pero algo que se llama correctamente algoritmo no debería. Puede tener un virus o un troyano al acecho en un programa, pero no en un algoritmo. Lo más cerca que puede llegar un algoritmo de esto sería algo así como una puerta trasera en un algoritmo de cifrado, donde la falla planificada es parte de la relación de información establecida por el algoritmo.

Y por último, un programa, tal como es abreviatura de un programa de computadora, tautológicamente requiere una computadora. Un algoritmo no lo hace. Si separo sistemáticamente las camisas, los pantalones y los calcetines de mi ropa antes de guardarlos, se trata de un algoritmo. Se trata de entradas y salidas relacionadas, se puede describir en un diagrama de flujo y tiene consecuencias calculables en términos de eficiencia (por ejemplo, el número de prendas que deben compararse para encontrar calcetines que combinen).

Un algoritmo es un conjunto autónomo de operaciones paso a paso que se realizarán para resolver un problema específico o una clase de problemas.

Un programa de computadora es una secuencia de instrucciones que cumplen con las reglas de un lenguaje de programación específico, escritas para realizar una tarea específica con una computadora.

Los algoritmos son generales y deben traducirse a lenguaje de programación específico (implementado).

Comentarios

• Pero el punto de la pregunta es que un programa (ya sea su código fuente o el binario compilado ) es » un conjunto autónomo de operaciones paso a paso que se realizarán para resolver un problema específico o una clase de problemas. »
• Pero no es ‘ t. Un programa no es Estas operaciones, pero una implementación de ellas: algo que las ejecuta en un contexto particular. P.ej. la utilidad Unix sort no es un algoritmo de clasificación, usa un algoritmo de clasificación.

Un algoritmo expresa nuestra idea o solución para un problema específico en un enfoque paso a paso. Es solo resolución de problemas y un enfoque comprensible para el ser humano, no para el sistema informático

El programa es instrucciones paso a paso que se implementan para resolver el problema mediante el sistema informático. Debe ser comprensible no solo por el programador sino también por la computadora.

Comentarios

• Bienvenido a Computer Science Stack Exchange. Lea cs.stackexchange.com/tour.if aún no lo ha hecho.

Las otras respuestas aquí, creo, pierden un punto importante. La definición de «algoritmo» que me enseñaron incluía el requisito de que el procedimiento se detenga en todas las entradas . Naturalmente, eso hace que «programa» sea una clase de procedimientos más amplia que «algoritmo», ya que algunos programas se detienen en todas las entradas y otros no.

Comentarios

• Esto no es universal. La definición que me enseñaron no ‘ incluyó ese requisito.

Aquí hay un par de formas de trazar la línea entre un algoritmo y un programa:

Propósito significativo

Los programas están escritos con un propósito y representan un intento de lograr un objetivo. Los algoritmos pueden verse como herramientas para lograr ese objetivo.

Por ejemplo, un destornillador es un algoritmo para modificar el estado de un tornillo, pero el destornillador en sí no tiene el propósito de hacerlo.El propósito está en la cabeza del operador del destornillador que sostiene el programa como si estuviera colocando estantes.

Lógica empresarial

Este punto se relaciona fuertemente con el propósito de un programa. Dado que los programas tienen propósitos, inevitablemente tienen partes del mundo real, como fechas específicas, medidas, tecnologías, nombres, etc.

Por otro lado, los algoritmos no contienen ni lógica de negocios ni partes del mundo real y en lugar de operar en valores específicos operan sobre variables.

Por ejemplo, en este sentido, puede comparar una función matemática como f(x) = x^2 que es abstracta y opera sobre variables con una receta de cocina que contiene valores precisos (al menos uno como referencia).

Resultado

Este punto se relaciona fuertemente con la lógica empresarial de un programa. Un agente (como un usuario de un navegador web) consume el resultado de un programa, no el resultado de un algoritmo.

Por ejemplo, el consumidor de una receta de cocina consume el pastel, no el resultado de batir crema o calentar el horno.

Comentarios

• Quizás sería mejor decir que ¿El destornillador no ‘ no tiene la intención de girar los tornillos? En el inglés de todos los días, ciertamente diríamos que un destornillador sí tiene el propósito de girar tornillos: girar tornillos es exactamente para lo que fue diseñado.
• Además, I ‘ No estoy seguro de lo que quieres decir con » lógica empresarial » (muchos programas no tienen nada que hacer con negocios) o diciendo que un algoritmo » no contiene lógica comercial ni partes del mundo real «. Por ejemplo, podría formular perfectamente un algoritmo de ruta más corta en términos de ciudades y carreteras en lugar de vértices y bordes. ¿No ‘ t el algoritmo entonces » contiene … bits del mundo real » ?
• @DavidRicherby, tienes razón, mi fraseo es ambiguo. Lo que quise decir es un propósito significativo . Girar tornillos para girar tornillos es inútil, así como clasificar una matriz que nunca se utiliza. Por lógica empresarial me refiero a toda la lógica del programa, excepto la lógica de servicios públicos y el texto estándar de la pila de tecnología, es decir, toda la lógica que realmente implementa el propósito del programa, es decir, la lógica empresarial de hornear un pastel es mezclar ingredientes y hornear y no incluye aprender a mezclar u hornear ( que es lógica de utilidad reutilizada en este caso).
• @DavidRicherby, en cuanto a bits del mundo real , me refiero a la actualización, es decir, un programa a diferencia de un algoritmo tiene que comunicarse de alguna manera con el mundo físico. Un algoritmo, por otro lado, puede ser un concepto puramente matemático.

I Estoy bastante seguro de que otras respuestas son lo suficientemente buenas como para tomar la iniciativa, pero así es como veo la diferencia entre un algoritmo y un programa

• Un algoritmo consiste simplemente en los pasos (independientes de la máquina) que se deben seguir para resolver un problema.

• Un programa es un conjunto de instrucciones para un tipo específico de máquina para poner un algoritmo en práctica .

Por ejemplo.

Digamos que tiene un algoritmo que tiene un paso para llegar a un lugar en particular antes de hacer algún otro paso. Ahora bien, no está exactamente definido cómo se llevará a cabo este paso de alcanzar. Puede optar por caminar o correr o tomar un autobús para hacerlo, pero eso depende de cómo elija implementarlo. (que es tu prog ram).

Puede decir que un algoritmo es una abstracción de un programa, es decir, falta los detalles exactos pero establece un plan para hacer algo .