3.10: Discusión

Última actualización
Guardar como PDF

Page ID: 118584

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

El grupo estaba debatiendo el valor de las pruebas combinatorias versus las pruebas formales por inducción. Xing dijo que en realidad prefería hacer una prueba por inducción, como prueba combinatoria, podría argumentarse, no era realmente una prueba. Dave murmuró “Las pruebas combinatorias siempre se pueden hacer rigurosas”. Ellos iban y venían un rato y luego Alice dijo “Pero el profesor nunca explicó esa extraña secuencia

\(1,2,3,4,1,2,3,4,5,1,2,3,4,5,2,3,4,5,6,2,3,4,5,6,1,2,3,4,5,2,3,4,5,6,…,\)

¿lo hizo?”

Dave estaba en racha. Preguntó: “¿Quién tiene cambio por un dólar?” pero nadie entendió por qué descarrilaría una discusión sobre pruebas cuando todos ya habían pagado por el café. Alice fue más al grano “Sabes Dave, a veces simplemente no entiendo por qué dices las cosas que haces”. Dave sonrió (tal vez fue más una sonrisa) “Se trata de hacer un cambio. Los términos en esta secuencia son el menor número de monedas que se requieren para realizar el cambio”. Bob dijo “no lo entiendo”. Dave continuó “El término\(a_n\) es el menor número de monedas estadounidenses requeridas para sumar a\(n\) centavos”. Ahora todos gimieron, todos menos Carlos, quien pensó que al menos esta vez, Dave era realmente listo.

“Bueno”, dijo Bob, “eso se encarga de la extraña secuencia, pero todavía no veo ninguna diferencia entre la inducción y la recursión”. Dave no pudo callarse “Nadie lo hace”. Xing pensó de manera diferente y dijo “En muchos lenguajes de programación, intentas evitar la recursión, prefiriendo usar bucles en su lugar. De lo contrario, terminas sobrecargando la pila. Como solo un ejemplo, se puede calcular el mayor divisor común\(d\) de\(m\) y\(n\), así como encontrar\(a\) y\(b\) para que\(d=am+bn\) usando un bucle, con muy poco almacenamiento. El enfoque recursivo discutido anteriormente, con el seguimiento de la espalda inherente al final, no es realmente necesario”. Yolanda quedó impresionada con la amplia experiencia y conocimiento de Xing en programación, pero Alice lo estaba menos.

Zori estaba perdiendo la paciencia y hoy estaba especialmente gruñón “No veo ningún valor en ninguna de estas cosas. ¿Quién me va a pagar para encontrar los mayores divisores comunes?” Dave dijo “Nadie”. Alice dijo: “Pero tal vez aquí hay algunos principios que tienen aplicación práctica”. Carlos se unió, diciendo “Creo que los principios básicos detrás de establecer que un programa de computadora hace lo que pretendes tienen mucho que ver con la inducción y la recursión”. Bob dijo: “No entiendo. Cuando escribo un programa, solo presto atención a los detalles y después de solo algunas correcciones, siempre funcionan”. Alice fue brutal “A lo mejor es porque no haces nada complicado”. Carlos fue más gentil “Los grandes proyectos de software podrían tener cientos de miles de líneas de código, y las piezas del producto final podrían ser escritas por diferentes grupos de programadores en diferentes momentos en el tiempo. Establecer la corrección puede ser una tarea muy difícil”. Los oídos de Zori se animaron al pensar que vio algo en esta última conversación que podría ser una forma de ganar un salario.