Mejor respuesta
No hay respuesta para esto.
Busquemos la respuesta a este enunciado del problema:
Q. ¿Cómo saber si algún algoritmo funciona mejor?
A. Formas más comunes de comparar algoritmos:
1) Complejidad temporal
2) Complejidad espacial
3) Calidad de la solución (puede no ser aplicable si se propone resolver exactamente un problema). Este puede ser un factor enorme si hablamos de algoritmos de aproximación.
4) Facilidad de implementación / adaptación del algoritmo. Algunos algoritmos pueden tener mucha sobrecarga para implementarlos correctamente. A veces hay algoritmos más adecuados para su aplicación. Por ejemplo, en computación paralela, la mayoría encontrará Bellman-Ford más útil que el algoritmo de Dijkstra debido a la forma en que funciona Bellman-Ford.
Sin embargo, el tiempo y la complejidad no son * siempre * la característica deseable para maximizar; Proporcionaré dos ejemplos.
Uno es «estabilidad numérica» , una característica de los algoritmos tanto en álgebra lineal como en ecuaciones diferenciales. Dedicaremos más tiempo algorítmico y más complejidad algorítmica a algoritmos que sean más estables numéricamente. En álgebra lineal, la inestabilidad generalmente se produce cuando un algoritmo encuentra números demasiado cercanos a cero o al infinito o ambos, debido a la representación finita de los números, la resolución se puede perder. En general, esto provoca que números muy ligeramente diferentes, solo unos pocos épsilon diferentes entre sí (donde épsilon es el número más pequeño que se puede agregar a uno, en una máquina, y obtener un resultado! = 1), para producir grandes diferencias en la respuesta. Entonces, por ejemplo, gastamos mucho tiempo y complejidad de espacio «pivotando» en la factorización LU para obtener un algoritmo estable; sin LU pivotante no es estable. Asimismo, tenemos algoritmos que no hacen nada más que «condicionar» matrices para evitar la inestabilidad.
Un segundo ejemplo es «robustez» en su sentido técnico estadístico. Robustez significa una medida o algoritmo que * no * es sensible a valores atípicos. Entonces, por ejemplo, cuando ajusto una línea de mínimos cuadrados a un conjunto de puntos, la línea puede estar muy sesgada por un solo valor extremadamente grande. Incluso si tengo 99 pares de números que forman una línea perfecta de 45 grados, si agrego un solo par de valores atípicos para el cual el valor de Y es cien veces más de lo que «debería» ser para caer en la misma línea, la línea ajustada será severamente sesgado fuera de la línea de 45 grados. El algoritmo «renunciará» al ajuste perfecto de 99 puntos para representar mejor el único punto atípico. Eso es * no * robusto.
Un enfoque robusto de mínimos cuadrados es, en lugar de encontrar la línea que minimiza la suma de los errores cuadrados creados al usar esa línea, encontrar la línea que minimiza la * mediana * de los errores al cuadrado creados al usar esa línea. En el ejemplo, esa línea es la línea de 45 grados, y la mediana de los errores al cuadrado es cero, y el punto atípico (y de hecho hasta 98 valores atípicos más) se ignoraría por completo. Se encontraría la línea de 45 grados.
Existen algoritmos robustos similares para ajustar curvas estadísticas, encontrar formas, etc. Sin embargo, son costosos en el tiempo, a veces de manera severa. Pero el costo del tiempo vale la pena porque las estadísticas sólidas son efectivamente inmunes al «ruido» en las señales, donde los enfoques de error mínimo cuadrado no lo son. El mundo real está lleno de ruido y valores atípicos, algunos de ellos causados por errores humanos o mecánicos, en particular en las imágenes pixeladas o el sonido muestreado. En tales circunstancias, un algoritmo robusto más costoso en tiempo puede encontrar señales en un entorno ruidoso donde algoritmos más rápidos producen respuestas tan corrompidas por el ruido que son inútiles, o incluso peligrosas si se aceptan.
En algunos casos, el tiempo y la complejidad del espacio no son tan importantes como encontrar una respuesta que probablemente modele la señal real a pesar del ruido y la degradación de la señal.
Respuesta
Los algoritmos se originaron en matemáticas como «recetas» para realizar cálculos basados en funciones, que se pueden seguir mecánicamente. En la cosmovisión matemática basada en funciones, todas las entradas deben especificarse al comienzo del cálculo, que procede en forma de caja cerrada. La noción de 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.
Papel 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.
Los primeros científicos de la computación adoptaron los algoritmos en la década de 1950, quienes hicieron 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 la informática. En su definición de algoritmos, Knuth fue consistente con los fundamentos basados en funciones matemáticas 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, usando TM)”.
Knuth especificó explícitamente que los algoritmos son cerrados; no se aceptan nuevas entradas una vez que ha comenzado el cálculo: «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 de los cálculos arbitrarios que pueden involucrar E / S. Un ejemplo que dio de un problema que no es algorítmico es la siguiente instrucción de una receta: «arrojar 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 condiciones externas que cambian dinámicamente, como la humedad, que no se pueden predecir con certeza antes de tiempo.
Si bien no existe un 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 50 y perfeccionado durante los 60, sirvió como estándar para la publicación de algoritmos. Fiel a la conceptualización de algoritmos basada en funciones, 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 impidiera 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 ciencias de la computación (CS). Según la Association for Computing Machinery (ACM), el número de programas de informática en los Estados Unidos aumentó de 11 en 1964 a 92 en 1968. Este aumento fue acompañado de 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 descripción de la informática como disciplina, que sirvió como base de sus recomendaciones de 1968 para los programas de informática de pregrado
La descripción de ACM de la informática identificó la transformación efectiva de la información como una preocupación central: » La informática se ocupa de la información en el mismo sentido que la física se ocupa de la energía … El informático está interesado en descubrir los medios pragmáticos por los que la información se puede transformar ”. Esta descripción coloca a 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 explícito este enfoque en los algoritmos en la siguiente oración de su informe:
“Este interés lleva a indagar sobre formas efectivas de representar información, algoritmos efectivos para transformar información, lenguajes efectivos para 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 la informática como una disciplina académica legítima a la par con física. Los algoritmos han sido fundamentales para las ciencias de la computación hasta el día de hoy.
La coexistencia de los enfoques informales (basados en algoritmos) y formales (basados en MT) para definir problemas con solución 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 científicos informáticos, al permitirnos describir la computación algorítmica de manera informal usando «pseudocódigo», con el conocimiento de que se puede construir una máquina de Turing equivalente.
– Un problema se puede resolver si se puede especificado por un algoritmo. – Un problema se puede resolver si existe una Máquina de Turing para él.
La decisión de los teóricos y educadores de la década de 1960 de colocar los algoritmos en el centro de la informática 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 últimas ediciones se están utilizando hasta el día de hoy: “Un procedimiento es una secuencia finita de instrucciones que se pueden realizar mecánicamente, como un programa de computadora …Un procedimiento que siempre termina se llama algoritmo ”.
Esta descripción de un algoritmo no excluye explícitamente el cálculo no funcional como preparar alimentos. Sin embargo, sus ejemplos de varios problemas dejan en claro que solo consideraron el cálculo basado en funciones. De hecho, usaron ALGOL para sus ejemplos, que ni siquiera ofrecían construcciones para entrada y salida.
Desde finales de los 60, los lenguajes de programación de alto nivel utilizados en la práctica y enseñados en programas de CS ya no se obligado por las restricciones algorítmicas de los primeros ALGOL. Podrías escribir programas que interactuaran con su entorno de manera continua a lo largo de 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) amplió 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 volvió típico de los libros de texto no teóricos. El tema de estos libros de texto es la metodología de programación en lugar de la teoría de la computación, y los principios matemáticos que sustentan nuestros modelos de computación se dejaron de lado en aras de la practicidad.
En la superficie, la definición de un algoritmo en Rice y 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 suele solucionar un problema de algún tipo «. Sin embargo, sus ejemplos de problemas computables ya no se basan en funciones, admitiendo precisamente el tipo de cálculo que Knuth había rechazado. Dos de esos ejemplos, que supuestamente pueden resolverse mediante un algoritmo, son hacer vodka de patata y llenar una zanja con arena; Knuth los habría rechazado a ambos.
Estos libros de texto no afirmaron equivalencia TM para sus «algoritmos». Sin embargo, los estudiantes no fueron conscientes de que esta noción de algoritmos es diferente de la de Knuth y que, por lo tanto, el conjunto de problemas considerados computables se había ampliado. Al emparejar una conceptualización más amplia y práctica de los algoritmos (y por lo tanto de los problemas computables) con las teorías que afirman que las MT pueden calcular un problema muy computable, el plan de estudios de informática centrado en algoritmos dejó a los estudiantes con la impresión errónea de que este conjunto más amplio de problemas también puede ser resuelto por TM.
Si bien los científicos informáticos prácticos han seguido desde hace mucho tiempo el ejemplo 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 cálculo como basado en funciones, y delimita en consecuencia nuestra noción de problema computacional. Esto es cierto al menos a nivel de pregrado. El resultado es una dicotomía, donde la comunidad de ciencias de la computación piensa en los algoritmos como sinónimo de la noción general de computación («lo que hacen las computadoras») pero al mismo tiempo como equivalente a las Máquinas de Turing.
Pensé Tuve que escribir esta larga respuesta para que la gente se diera cuenta de esta dicotomía. Como dije al principio, la noción de algoritmo es informal. Podemos pensar en ello como equivalente al cálculo de funciones (oa las Máquinas de Turing) o podemos pensar en ello como cualquier cosa para la que se 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 en sentido contrario.