Fundamentos de programación/Algoritmos

Lección 1

Algoritmos

El mundo moderno está lleno de aparatos electrónicos que desempeñan todo tipo de tareas para facilitarnos la vida diaria. Actividades tan diversas como escribir textos, realizar presupuestos y nóminas, intercambiar correos, comerciar bienes y servicios, asignar recursos a procesos de manufactura, analizar la estructura del genoma humano o buscar información sobre un tema de interés dependen en gran medida de los computadores.

Si bien los dispositivos que se usan para cada una de esas tareas son muy diferentes a primera vista, fundamentalmente se componen del mismo conjunto de elementos básicos: dispositivos de entrada, dispositivos de salida, dispositivos de almacenamiento secundario, una unidad de memoria para almacenar datos temporalmente, una unidad aritmético/lógica que puede ejecutar un conjunto relativamente limitado de instrucciones y una unidad central de procesamiento para coordinar la operación de las otras secciones. La diferencia fundamental entre ellas es el orden en que ejecutan esas instrucciones para resolver el problema que se les presenta o realizar la tarea deseada. Si la computadora carece de algo que le indique la secuencia apropiada de instrucciones para resolver el problema, sería una máquina vacía, incapaz de realizar ninguna actividad de utilidad. Esa secuencia de instrucciones se llama algoritmo e informalmente se puede entender como un procedimiento que recibe una entrada y la transforma para producir un valor o conjunto de valores de salida.

Formalmente se define un algoritmo como «un método de resolver un problema con una serie de pasos precisa, definida y finita». La precisión nos dice que un algoritmo debe especificar la secuencia exacta en la que se deben ejecutar los pasos. La definición requiere que si la secuencia de pasos se aplica sobre el mismo conjunto de datos múltiples veces se obtenga el mismo resultado en todas las ocasiones. Finalmente, el carácter finito de los algoritmos significa que deben terminar después de un número determinado de pasos.

Los algoritmos pueden ser correctos o incorrectos. Un algoritmo es correcto si para cada posible entrada que recibe, termina con la salida correcta, es decir, un algoritmo correcto resuelve un determinado problema. Por otro lado, un algoritmo incorrecto puede que nunca termine o que termine, pero que proporcione una salida incorrecta como solución al problema.

Al igual que existen múltiples formas de resolver los problemas que enfrentamos en la vida diaria, existen múltiples algoritmos para resolver un mismo problema con un computador. La rapidez con la que la máquina pueda resolver el problema así como la cantidad de espacio de almacenamiento que ocupe para hacerlo dependen en gran medida de la naturaleza del algoritmo seleccionado para hacerlo. Debido a eso, el diseño y selección del algoritmo adecuado para resolver un problema de la forma más eficiente posible es una de las tareas principales de todo programador de computadores.

Tipos de algoritmos

La ejecución de un algoritmo por parte de una máquina es posible porque estos no requieren ninguna decisión subjetiva ni el uso de la intuición o de la creatividad. Sin embargo, eso no significa necesariamente que los pasos que ejecuta un algoritmo se puedan determinar con precisión de antemano o que siempre den una respuesta exacta y sin errores. Los algoritmos probabilistas realizan elecciones aleatorias en determinados momentos de su ejecución. Los algoritmos aproximados dan una solución a un problema dentro de un margen de error que puede ser establecido de antemano. Los algoritmos heurísticos son algoritmos que dan una solución aproximada a un problema donde no podemos controlar la magnitud del error. Lo importante al considerar estos tipos de algoritmos es que en ningún caso implican la ejecución de instrucciones o la toma de decisiones de forma arbitraria. Los mecanismos siempre están determinados de antemano, lo que varían son los resultados de ejecutarlos, por ejemplo al usar un generador de números pseudoaleatorios.

Técnicas de diseño de algoritmos

La creación de algoritmos, como todo proceso de resolución de problemas, es una actividad eminentemente creativa, sin embargo, la investigación en el campo ha identificado diversas técnicas comunes que facilitan la resolución de problemas. Entre las más comunes se encuentran las siguientes:

• Algoritmos voraces: Los algoritmos voraces toman decisiones basándose en la información disponible en el momento y sin considerar sus consecuencias posteriores.
• Divide y conquista: Los algoritmos que usan la técnica de división y conquista descomponen el problema en varios subproblemas más pequeños y fáciles de resolver y luego se aplican a si mismos a esos subproblemas hasta llegar a un caso básico y fácil de resolver. Luego retroceden integrando las soluciones parciales para luego dar el resultado esperado.
• Programación dinámica: El método de programación dinámica permite el diseño de algoritmos que inician calculando las soluciones a un conjunto de casos básicos que luego van combinando hasta encontrar la solución al problema principal.

Representación visual de un problema modelado como un grafo.

• Recorridos sobre grafos: Los algoritmos de este tipo expresan un problema como un conjunto de elementos interconectados entre sí y buscan la solución recorriendo la estructura resultante, llamada grafo.

Representación de algoritmos

Los algoritmos son procedimientos conceptuales y no tienen una representación tangible por sí mismos. Para poder comunicarlos a otras personas o a las máquinas y para poder documentarlos para referencia posterior es necesario expresarlos de alguna manera. Esta representación debe ser clara y sin ambigüedades.

Existen muchas técnicas para representar los algoritmos y comunicarlos a otras personas. Sin embargo, las más comunes son el pseudocódigo y los diagramas de flujo. El pseudocódigo es una versión sumamente restringida del lenguaje natural que permite expresar los pasos de los algoritmos sin sufrir de las ambigüedades presentes en los textos que usamos para comunicarnos diariamente. Las computadoras no entienden directamente el pseudocódigo ya que no incluye todos los detalles que necesitan pero los seres humanos son capaces de traducirlo al lenguaje de las computadoras con relativa facilidad. Los diagramas de flujo son un conjunto de elementos gráficos que representan los diferentes pasos del algoritmo y un conjunto de líneas con dirección que los conectan y que indican el orden de ejecución.

Una vez que el algoritmo se ha especificado adecuadamente, es necesario convertirlo en un programa mediante un lenguaje de programación para que las computadoras puedan entenderlo y ejecutarlo.

Resumen de la lección

• Los algoritmos son métodos para resolver problemas con una serie de pasos precisos, definidos y finitos.
• Un algoritmo es correcto si para cada posible entrada que recibe termina con la salida correcta.
• Existen algoritmos que proporcionan una aproximación a la respuesta cuando calcular la respuesta exacta no es posible.
• La creación de algoritmos es un proceso creativo.
• Existen diversas técnicas de resolución de problemas que facilitan la creación de algoritmos.
• Los algoritmos se pueden representar usando "pseudocódigo" o diagramas de flujo, entre otras herramientas.

Términos clave

• Algoritmo
• Algoritmos probabilistas
• Algoritmos aproximados
• Algoritmos heurísticos
• Algoritmos voraces
• Aparato electrónico
• Computadora
• Diagrama de flujo
• Divide y conquista
• Grafo
• Programación dinámica
• Pseudocódigo

Lecturas adicionales

• ¿Qué es un diagrama de flujo?

Bibliografía

Proyecto: Fundamentos de programación

Anterior: Fundamentos de programación — Algoritmos — Siguiente: Evaluación de la lección 1