Como parte de su definición de algoritmo, en el primer capítulo del primer volumen de The Art of Computer Programming, Knuth dice que un algoritmo tiene cero o más entradas. Creo que lo hizo desde el punto de vista de la corrección, a pesar de que (creo) no ve ningún valor real o interés en un algoritmo de entrada cero. No puedo pensar en un solo ejemplo de los volúmenes. Si bien esa podría ser mi memoria defectuosa, las restricciones que agrega a la definición estándar de un algoritmo de computadora, restricciones que insisten en que un algoritmo sea lo más simple y práctico posible, dificultan la creación de un algoritmo útil de entrada cero en sus términos
Antes de intentar dar ejemplos de algoritmos sin entrada, voy a mirar las definiciones y restricciones de Knuth y explicar por qué limitan nuestras opciones.
¿Qué son las entradas de un algoritmo?
- ¿Aproximadamente cuántas personas en el mundo pueden resolver un cubo rubix sin algoritmos?
- Probé el problema 'Impresión espiral de matriz' durante 2 días. Incluso después de ver la solución, sigo fallando. ¿Qué tengo que hacer?
- ¿Cómo afecta el subprocesamiento múltiple al rendimiento de diferentes algoritmos de clasificación?
- ¿Por qué el tipo Bubble se llama Bobble?
- ¿Qué son los árboles de búsqueda binarios?
Del libro mismo: “cantidades que se le dan inicialmente antes de que comience el algoritmo, o dinámicamente a medida que el algoritmo se ejecuta”
Cualquier valor no especificado en uno de los pasos del algoritmo, no generado automáticamente durante el cálculo pero requerido para completar el cálculo es una entrada. Independientemente de la fuente (ubicación de memoria, archivo en disco, entrada de teclado, conexión de red, reloj del sistema o algún otro dispositivo de hardware), si el valor proviene del exterior del algoritmo, entonces es una entrada.
Los algoritmos son funcionales.
“Un algoritmo tiene una o más salidas: cantidades que tienen una relación específica con las entradas”.
Por “funcional”, no me refiero a que Knuth solo codifica en Haskell. Quiero decir que define un algoritmo como algo que calcula los valores de salida en función de los valores de entrada. Escribe sus algoritmos en un código de máquina muy imperativo que inventó para una computadora imaginaria, pero sus algoritmos son funciones puras .
Los algoritmos son finitos
Para Knuth, un algoritmo solo debe tomar un número finito de pasos; se permiten números muy grandes, pero no
- Serie de pasos potencialmente infinitos (los denomina “métodos computacionales”)
- Procesos que interactúan continuamente (los denomina “procesos reactivos”)
La descalificación de procesos que son procesos potencialmente infinitos es controvertida pero práctica. La descalificación de los procesos reactivos es totalmente justa.
¿Qué no está permitido?
Siguiendo las restricciones dadas, los algoritmos de entrada cero no pueden ser
- Generadores de números aleatorios. Lo sentimos, pero todos toman insumos (semillas) y algunos de ellos son procesos reactivos.
- Generadores de secuencia infinita. Si tiene un proceso para calcular la secuencia de Fibonacci o encontrar números primos y no especifica una condición de parada finita demostrable (por ejemplo, después de generar n números o solo números más pequeños que n ), entonces es un método computacional pero no un algoritmo. Yn es una entrada.
¿Qué está permitido?
Se podría argumentar que la codificación dura de la (s) entrada (s) en un algoritmo lo convierte en entrada cero: que codificar 100 en un algoritmo para encontrar todos los primos menores que n lo convierte en un algoritmo de entrada cero para encontrar todos los primos menores que 100. Creo eso es trampa y ciertamente no es interesante, ya que significa que cualquier algoritmo también puede ser de entrada cero.
De lo contrario, la regla “no se permite el infinito” excluye muchos procesos de entrada cero potencialmente interesantes y útiles.
Los algoritmos de juego resueltos son una opción, aunque un pedante podría argumentar que un algoritmo de tic-tac-toe podría funcionar para cuadrículas de cualquier tamaño y 3 × 3 es un par de entradas.
Hay algunas cosas útiles relacionadas con interesantes secuencias de números finitos. Los números de la suerte de Euler ofrecen una forma barata de generar una lista (no exhaustiva) de números primos, por ejemplo.
Así que voy a hacer de eso mi ejemplo. El afortunado generador de números primos de Euler. Espero que le sea útil.
