Resolución de problemas y representación de algoritmos
Programar es, sobre todo, resolver problemas. El lenguaje viene después: primero hay que entender qué se pide, planear la solución y poder explicarla sin ambigüedades.
01Qué es un algoritmo
Una receta de cocina, las instrucciones para armar un mueble y el procedimiento para medir una resistencia con un multímetro tienen algo en común: son pasos que, seguidos al pie de la letra, llevan a un resultado. Un algoritmo es eso mismo, con una exigencia más: tiene que poder seguirlo alguien que no entiende el problema, como una computadora. Donald Knuth le pide cinco propiedades:
| Propiedad | Qué exige | Una receta la viola si… |
|---|---|---|
| Finitud | Termina después de una cantidad finita de pasos | dice «revolver hasta que esté listo» |
| Definición | Cada paso es preciso y sin ambigüedad | dice «una pizca de sal» |
| Entrada | Tiene cero o más datos de partida bien especificados | no dice para cuántas porciones es |
| Salida | Produce al menos un resultado relacionado con la entrada | — |
| Efectividad | Cada paso se puede hacer con lápiz y papel en un tiempo finito | pide «el punto justo» |
El algoritmo es la idea, independiente del lenguaje. El programa es un algoritmo escrito en un lenguaje que una máquina puede ejecutar. El algoritmo de Euclides tiene 2300 años; sus programas, unas décadas. Primero se piensa el algoritmo, después se escribe el programa, y los errores más caros son los que se cometen antes de tocar el teclado.
02Un método para resolver problemas
George Pólya propuso en 1945 cuatro fases para resolver problemas de matemática que calzan exactamente con la programación:
- Comprender el problema. ¿Cuáles son los datos? ¿Qué se pide? ¿Qué condiciones hay? ¿Qué casos raros pueden aparecer?
- Concebir un plan. ¿Se parece a un problema ya resuelto? ¿Se puede partir en problemas más chicos?
- Ejecutar el plan, verificando cada paso: en programación, codificar.
- Examinar la solución. Probarla con casos conocidos y con los casos raros de la fase 1.
1 · Comprender. Datos: N valores de resistencia. Resultado: la resistencia equivalente del paralelo. Condición: . Casos raros: un resistor de 0 Ω es un cortocircuito y hace Req = 0 (y la fórmula dividiría por cero); un valor negativo es un error de carga; N = 0 no tiene sentido.
2 · Plan. Es una acumulación: sumar las conductancias en un acumulador y al final invertir.
3 · Ejecutar. Escribir el pseudocódigo, después el programa.
4 · Examinar. Dos resistores iguales de 100 Ω deben dar 50 Ω; 100 Ω y 0 Ω, 0 Ω; un solo resistor, su propio valor.
Los casos raros de la fase 1 son los que después se olvidan. Anotarlos antes de programar es la mitad de la prueba.
03Herramientas para representar algoritmos
Antes de escribir código conviene expresar el algoritmo en una notación que no distraiga con detalles del lenguaje. Hay tres clásicas:
Lenguaje natural estructurado con palabras clave (Si, Mientras, Para). Es el más cercano al código y el más rápido de escribir.
Símbolos normalizados unidos por flechas (norma ISO 5807). Muestra de un vistazo los caminos posibles, pero se enreda en algoritmos largos.
También llamado diagrama de Chapin. Cajas anidadas sin flechas: por construcción sólo admite las estructuras de control permitidas.
04Tres estructuras alcanzan para todo
En 1966 Corrado Böhm y Giuseppe Jacopini demostraron que cualquier algoritmo se puede escribir combinando sólo tres estructuras, cada una con una entrada y una salida:
Un paso después del otro.
Elegir un camino según una condición: Si … entonces … si no …, o Según para varios casos.
Repetir mientras se cumpla una condición: Mientras, Repetir … hasta, Para.
Como cada estructura tiene una sola entrada y una sola salida, se pueden anidar como cajas, y se puede razonar sobre cada una por separado. Eso es la programación estructurada, y es la base del tema siguiente.
| Iteración | Cuándo evalúa | Mínimo de vueltas | Se usa cuando… |
|---|---|---|---|
| Mientras | Antes de cada vuelta | 0 | puede no hacer falta ninguna vuelta |
| Repetir … hasta | Después de cada vuelta | 1 | hay que hacer algo al menos una vez, como leer un dato y validarlo |
| Para | Antes, con un contador | 0 | se sabe de antemano cuántas vueltas son |
05La prueba de escritorio
Antes de confiar en un algoritmo hay que ejecutarlo a mano, con lápiz, anotando en una tabla el valor de cada variable cada vez que cambia. Es la prueba de escritorio, y es la herramienta que más errores encuentra por minuto invertido. La máquina de abajo la hace paso a paso: elegí un algoritmo, cargá los datos y avanzá.
Tabla de la prueba
Que un algoritmo termine hay que demostrarlo. En Euclides, el resto r es siempre menor que b, así que b baja en cada vuelta y es un entero no negativo: no puede bajar para siempre. Y es correcto porque mcd(a, b) = mcd(b, a mod b): esa igualdad se mantiene en todas las vueltas. A una propiedad que se conserva en cada vuelta se la llama invariante del ciclo.
06Refinamiento sucesivo
Niklaus Wirth propuso en 1971 diseñar de arriba hacia abajo: escribir primero la solución en pasos gruesos y después reemplazar cada paso grueso por su detalle, hasta que todo sea ejecutable. Cada paso grueso termina siendo una función.
// Nivel 1: el problema entero
Leer los valores de resistencia
Calcular la resistencia equivalente
Mostrar el resultado
// Nivel 2: «Calcular la resistencia equivalente»
g ← 0
Para i ← 1 hasta N hacer
Si R[i] = 0 entonces
Req ← 0 ; terminar // hay un cortocircuito
g ← g + 1 / R[i]
FinPara
Req ← 1 / gLa ventaja no es sólo el orden: en cada nivel se puede verificar que el plan es correcto sin haber escrito todavía el detalle.
07Correcto no alcanza: también eficiente
Dos algoritmos correctos pueden tardar tiempos muy distintos. La eficiencia se mide contando cuántas operaciones hacen en función del tamaño n de la entrada, sin importar la máquina.
Buscar un valor en una lista de n elementos recorriéndola lleva, en el peor caso, n comparaciones. Si la lista está ordenada, la búsqueda binaria mira el elemento del medio, descarta la mitad que no puede contenerlo y repite: en el peor caso hace ⌊log2 n⌋ + 1 comparaciones.
| Elementos n | Búsqueda secuencial | Búsqueda binaria |
|---|---|---|
| 10 | 10 | 4 |
| 1 000 | 1 000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
Se dice que la primera es de orden n, O(n), y la segunda de orden logarítmico, O(log n). Con un millón de datos, una computadora más rápida no compensa elegir mal el algoritmo.
08En el laboratorio
Para un problema de electrónica —el valor comercial E12 más cercano a una resistencia calculada, o la potencia disipada por cada resistor de un divisor— hacer las cuatro fases de Pólya por escrito, el diagrama de flujo y la prueba de escritorio con tres juegos de datos, uno de ellos un caso raro.
Agregar un contador de vueltas al algoritmo de Euclides y probar con dos números consecutivos de Fibonacci (89 y 55, 144 y 89). Comparar con otros pares del mismo tamaño: los de Fibonacci son el peor caso.
Escribir el pseudocódigo en PSeInt, que ejecuta y dibuja el diagrama de flujo solo, y verificar que la salida coincide con la prueba de escritorio.
09Errores frecuentes
- Empezar a programar sin haber entendido el problema. Se nota cuando el programa «anda» pero resuelve otra cosa.
- El error de uno (off by one): el ciclo da una vuelta de más o de menos. Se detecta en la prueba de escritorio mirando la primera y la última vuelta.
- Un ciclo que no termina porque la variable de la condición no cambia adentro.
- Probar sólo con el caso fácil. Hay que probar el cero, el uno, el vacío y los extremos.
- Condiciones mal negadas. Lo contrario de «a > 0 y b > 0» es «a ≤ 0 o b ≤ 0» (leyes de De Morgan).
10Autoevaluación
¿Por qué «revolver hasta que tome color» no es un paso algorítmico?
Porque viola la definición: no dice cómo decidir que tomó color. Tampoco garantiza la finitud.
¿Cuáles son las tres estructuras de control de Böhm y Jacopini?
Secuencia, selección e iteración.
¿Qué diferencia hay entre Mientras y Repetir … hasta?
El Mientras evalúa la condición antes y puede no ejecutar nunca el cuerpo; el Repetir evalúa después y lo ejecuta al menos una vez.
Hacer la prueba de escritorio de Euclides con a = 48 y b = 18.
(48, 18) → r = 12 → (18, 12) → r = 6 → (12, 6) → r = 0 → (6, 0). Resultado: 6.
¿Cuántas comparaciones hace como máximo una búsqueda binaria en 4096 elementos ordenados?
⌊log2 4096⌋ + 1 = 12 + 1 = 13.
¿Qué es un invariante de ciclo?
Una propiedad que es verdadera antes de entrar al ciclo y se mantiene después de cada vuelta. Al salir, junto con la condición de salida, prueba que el resultado es correcto.
11Para ampliar
- Luis Joyanes Aguilar. Fundamentos de programación. Algoritmos, estructura de datos y objetos. 4.ª ed., McGraw-Hill, 2008. El texto de referencia en castellano para pseudocódigo, diagramas de flujo y de Nassi-Shneiderman.
- George Pólya. Cómo plantear y resolver problemas. Trillas (traducción de How to Solve It, 1945). Corto y vigente: el método de las cuatro fases con decenas de ejemplos.
- Niklaus Wirth. Algoritmos + estructuras de datos = programas. Ediciones del Castillo, 1980. Del creador de Pascal y del refinamiento sucesivo. El título es toda una declaración.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein. Introduction to Algorithms. 4.ª ed., MIT Press, 2022 (en inglés). Para cuando se quiera ir en serio con invariantes, corrección y análisis de eficiencia.