Los algoritmos se originaron en las matemáticas como “recetas” para llevar a cabo cálculos basados en funciones, que pueden seguirse mecánicamente. En la cosmovisión matemática basada en funciones, todas las entradas deben especificarse al comienzo del cálculo, que procede de forma cerrada. La noción de un algoritmo es inherentemente informal, ya que una descripción algorítmica no está restringida a un solo lenguaje o formalismo.
Quizás el ejemplo más antiguo es el algoritmo de Euclides para encontrar divisores comunes. Los algoritmos capturan lo que significa que un cálculo sea “efectivo”. Al igual que las fórmulas matemáticas, los algoritmos nos dicen cómo calcular un valor; a diferencia de ellos, los algoritmos pueden involucrar lo que ahora llamamos bucles o ramas.
Rol del algoritmo: dado un valor de entrada finito x, un algoritmo describe los pasos para transformarlo efectivamente en un valor de salida y, donde y es f (x) para alguna función recursiva f.
- ¿Cuáles son los ejemplos de colas en la vida real con algoritmo?
- ¿Qué puedes hacer con los algoritmos?
- ¿Qué es una matriz en Java? ¿Y cuál es un ejemplo de su uso?
- ¿Cuál es el futuro de la música generada por computadora?
- ¿Cuál es su proceso de pensamiento cuando selecciona y define nuevas variables cuando escribe código?
Los primeros científicos informáticos adoptaron los algoritmos en la década de 1950, quienes establecieron la conexión entre los algoritmos y las máquinas de Turing (TM, un modelo formal de computación que data de 1936), equiparando su expresividad.
El famoso e influyente libro de texto de Knuth, “The Art of Computer Programming, Vol. 1” a fines de la década de 1960 popularizó la centralidad de los algoritmos en informática. En su definición de algoritmos, Knuth era consistente con la función matemática basada en funciones.
fundamentos de la teoría de la computación. “Hay muchas otras formas esencialmente equivalentes de formular el concepto de un método computacional efectivo (por ejemplo, utilizando TM)”.
Knuth especificó explícitamente que los algoritmos están cerrados; no se aceptan nuevas entradas una vez que el cálculo ha comenzado: “Un algoritmo tiene cero o más entradas, es decir, cantidades que se le dan inicialmente antes de que comience el algoritmo”. Distinguió los algoritmos del cálculo arbitrario que puede involucrar E / S. Un ejemplo que dio de un problema que no es algorítmico es la siguiente instrucción de una receta: “agitar ligeramente hasta que la mezcla se desmorone”. Este problema no es algorítmico porque es imposible que una computadora sepa cuánto tiempo mezclar; Esto puede depender de una condición externa que cambia dinámicamente, como la humedad, que no puede predecirse con certeza con anticipación.
Si bien no hay acuerdo sobre la noción exacta de algoritmos, la discusión de Knuth sobre los algoritmos sigue siendo definitiva.
El primer lenguaje de programación de alto nivel desarrollado expresamente para especificar algoritmos fue ALGOL (ALGOrithmic Language). Introducido a finales de los años 50 y refinado a través de los años 60, sirvió como un estándar para la publicación de algoritmos. Fiel a la conceptualización basada en funciones de algoritmos, ALGOL no proporcionó construcciones para entrada y salida, considerando estas operaciones fuera de la preocupación de los algoritmos. (No es sorprendente que esta ausencia obstaculizara la adopción de ALGOL por parte de la industria
para aplicaciones comerciales)
La década de 1960 vio una proliferación de programas de pregrado en informática (CS). Según la Association for Computing Machinery (ACM), el número de programas de CS en los EE. UU. Aumentó de 11 en 1964 a 92 en 1968. Este aumento fue acompañado por una intensa actividad para establecer la legitimidad de esta nueva disciplina a los ojos de los académicos. comunidad. ACM jugó un papel central
en esta actividad En 1965, enunció la justificación y la descripción de CS como disciplina, que sirvió como base de sus recomendaciones de 1968 para programas de pregrado de CS
La descripción de ACM de CS identificó la transformación efectiva de la información como una preocupación central: “La informática se preocupa por la información en el mismo sentido que la física se preocupa por la energía … El informático está interesado en descubrir los medios pragmáticos por los cuales la información puede transformarse. “Esta descripción coloca los algoritmos en el centro de la informática, ya que
son las “recetas” para realizar estas transformaciones efectivas de entradas a salidas. De hecho, ACM hizo este enfoque en algoritmos explícitos en la siguiente oración de su informe:
“Este interés lleva a investigar formas efectivas de representar información, algoritmos efectivos para transformar información, lenguajes efectivos con los que expresar algoritmos … y formas efectivas de lograrlos a un costo razonable”.
Tener una preocupación algorítmica central, análoga a la preocupación por la energía en la física, ayudó a establecer CS como una disciplina académica legítima a la par con la física. Los algoritmos han seguido siendo centrales para la informática hasta el día de hoy.
La coexistencia de los enfoques informales (basados en algoritmos) y formales (basados en TM) para definir problemas solucionables persiste hasta el día de hoy y se puede encontrar en todos los libros de texto modernos sobre algoritmos o computabilidad. Esto ha demostrado ser muy conveniente para los informáticos, ya que nos permite describir la computación algorítmica de manera informal utilizando “pseudocódigo”, con el conocimiento de que se puede construir una máquina de Turing equivalente.
– Un problema es solucionable si puede ser especificado por un algoritmo.
– Un problema es solucionable si existe una máquina de Turing para ello.
La decisión de los teóricos y educadores de la década de 1960 de colocar algoritmos en el centro de CS se reflejó claramente en los primeros libros de texto de pregrado. Sin embargo, no había una definición estándar explícita de un algoritmo y varios libros de texto optaron por definir este término de manera diferente. Si bien algunos libros de texto como el de Knuth tuvieron cuidado de restringir explícitamente los algoritmos a aquellos que calculan funciones y, por lo tanto, son equivalentes a las máquinas de Turing, la mayoría de los libros de teoría dejaron esta restricción implícita pero no declarada.
Un ejemplo temprano es un libro de texto de Hopcroft y Ullman de 1969, cuyas ediciones posteriores se están utilizando hasta el día de hoy: “Un procedimiento es una secuencia finita de instrucciones que pueden llevarse a cabo mecánicamente, como un programa de computadora … Un procedimiento que siempre termina se llama algoritmo “.
Esta descripción de algoritmos no excluye explícitamente el cómputo no funcional, como la preparación de alimentos. Sin embargo, sus ejemplos de varios problemas dejan en claro que solo consideraron el cálculo basado en funciones. De hecho, utilizaron ALGOL para sus ejemplos, que ni siquiera ofrecían construcciones para entrada y salida.
Desde finales de los años 60, los lenguajes de programación de alto nivel utilizados en la práctica y enseñados en los programas CS ya no estaban sujetos a las restricciones algorítmicas de ALGOL temprano. Puede escribir programas que interactúen con su entorno de manera continua durante la computación, como sistemas operativos, interfaces gráficas de usuario o vehículos automáticos y otros robots.
En respuesta, los libros de texto de programación contemporáneos como Rice y Rice (1969) ampliaron explícitamente la noción de algoritmos para incluir problemas no funcionales. Este enfoque, que refleja la centralidad de los algoritmos sin restringirlos al cálculo de funciones, se convirtió en típico de los libros de texto no teóricos. El tema de estos libros de texto es la metodología de programación más que la teoría de la computación, y los principios matemáticos que sustentan nuestros modelos de computación fueron descartados por razones prácticas.
En la superficie, la definición de un algoritmo en Rice and Rice y otros libros de texto similares no es diferente de Hopcroft y Ullman: “Un algoritmo es una receta, un conjunto de instrucciones o las especificaciones de un proceso para hacer algo. Ese algo generalmente está resolviendo un problema de algún tipo ”. Sin embargo, sus ejemplos de problemas computables ya no se basan en funciones, admitiendo solo el tipo de cómputo que Knuth había rechazado. Dos de estos ejemplos, que supuestamente pueden resolverse mediante un algoritmo, son hacer vodka de papa y llenar una zanja con arena; Knuth los habría rechazado a ambos.
Estos libros de texto no hicieron afirmaciones de equivalencia TM para sus “algoritmos”. Sin embargo, a los estudiantes no se les hizo saber que esta noción de algoritmos es diferente de la de Knuth, y que el conjunto de problemas considerados computables se había ampliado. Al combinar una conceptualización más amplia y práctica de algoritmos (y, por lo tanto, de problemas computables) con teorías que afirman que los TM pueden calcular un problema muy computable, el plan de estudios de CS centrado en algoritmos dejó a los estudiantes con la impresión errónea de que este conjunto más amplio de problemas podría También se resolverá por TMs.
Si bien los científicos informáticos prácticos han seguido desde hace mucho tiempo el liderazgo de Rice y Rice y han ampliado el concepto de algoritmos más allá del cálculo de funciones, la informática teórica ha conservado la cosmovisión matemática que enmarca la computación como basada en funciones y delimita nuestra noción de una computación problema en consecuencia. Esto es cierto al menos a nivel de pregrado. El resultado es una dicotomía, donde la comunidad de la informática considera los algoritmos como sinónimos de la noción general de computación (“lo que hacen las computadoras”) pero al mismo tiempo como equivalentes a las máquinas de Turing.
Pensé que tenía que escribir esta larga respuesta, para que la gente tomara conciencia de esta dicotomía. Como dije al principio, la noción de algoritmo es informal. Podemos considerarlo como equivalente al cálculo de funciones (o para Turing Machines) o podemos considerarlo como cualquier cosa para la que pueda escribir un programa, incluidos programas interactivos en tiempo real como sistemas operativos o automóviles automáticos. Pero las dos definiciones no son equivalentes, a pesar de la confusión común de lo contrario.
