Introducción a los algoritmos


¿Qué es un algoritmo? Una definición informal podría ser (no se considera aquí una definición formal, aunque existe):


Conjunto finito de reglas que dan una secuencia de operaciones para resolver todos los problemas de un tipo dado.


De forma más sencilla, podemos decir que un algoritmo es un conjunto de pasos que nos permite obtener un resultado.


El término algoritmo proviene del matemático Muhammad ibn Musa al-Khwarizmi, que vivió aproximadamente entre los años 780 y 850 d.C. en la actual nación Iraní. El describió la realización de operaciones elementales en el sistema de numeración decimal. De al-Khwarizmi se obtuvo la derivación algoritmo.



Muhammad ibn Musa al-Khwarizmi


Un algoritmo, además, debe cumplir estas condiciones:


Finitud: el algoritmo debe finalizar tras un número finito de pasos. Es más, es casi fundamental que sea en un número razonable de pasos.


Entrada: el algoritmo tendrá cero o más entradas, es decir, cantidades dadas antes de empezar el algoritmo. Estas cantidades pertenecen además a conjuntos especificados de objetos. Por ejemplo, pueden ser cadenas de caracteres, enteros, naturales, fraccionarios, etc. Se trata siempre de cantidades representativas del mundo real expresadas de tal forma que sean aptas para su interpretación por el autómata.


Salida: el algoritmo tiene una o más salidas, en relación con las entradas.


Efectividad: se entiende por esto que una persona sea capaz de realizar el algoritmo de modo exacto y sin ayuda de una máquina en un lapso de tiempo finito.


Todo algoritmo tiene una serie de características, entre otras que requiere una serie de recursos, algo que es fundamental considerar a la hora de implementarlos en una máquina. Estos recursos son principalmente:


El tiempo: período transcurrido entre el inicio y la finalización del algoritmo.


La memoria: la cantidad (la medida varía según la máquina) que necesita el algoritmo para su ejecución.


Obviamente, la capacidad y el diseño de la máquina (autómata) que va a ejecutar el algoritmo pueden afectar al diseño del mismo.


Divide y vencerás


La técnica de diseño de algoritmos llamada "divide y vencerás" consiste en descomponer el problema original en varios sub-problemas más sencillos, para luego resolver éstos mediante un cálculo simple. Por último, se combinan los resultados de cada sub-problema para obtener la solución del problema original.


Y, por supuesto, si los subproblemas son todavía demasiado grandes, podemos utilizar la misma táctica con ellos, esto es, dividirlos a ellos también, utilizando un algoritmo recursivo que vaya dividiendo más el sub-problema hasta que su solución sea trivial.


Pseudocódigo


En programación, el pseudocódigo (o falso lenguaje) es una descripción compacta e informal de la acciones que debe realizar un autómata para realizar una tarea, es decir, del algoritmo.


Utiliza convenciones propias de un lenguaje de programación real, pero está diseñado para la lectura humana en lugar de la lectura mediante máquina. Normalmente, el pseudocódigo omite detalles que no son esenciales para la comprensión humana del algoritmo, tales como declaraciones de variables, código específico del sistema, etcétera. El lenguaje de programación se complementa, donde sea conveniente, con descripciones detalladas en lenguaje natural, o con notación matemática compacta. Se utiliza pseudocódigo pues este es más fácil de entender para las personas que el código del lenguaje de programación convencional. No existe una sintaxis estándar para el pseudocódigo.


Veamos algunos ejemplos de algoritmos expresados como pseudocódigo:


// este es el ejemplo más simple de esta ayuda, 
                // toma dos números, los suma y muestra el resultado
                Proceso Suma
                    // para cargar un dato, se le muestra un mensaje al usuario
                    // con la instrucción Escribir, y luego se lee el dato en 
                    // una variable (A para el primero, B para el segundo) con 
                    // la instrucción Leer
                    Escribir "Ingrese el primer numero:"
                    Leer A
                
                    Escribir "Ingrese el segundo numero:"
                    Leer B
                
                    // ahora se calcula la suma y se guarda el resultado en la
                    // variable C mediante la asignación (<-)
                     C = A+B
                
                    // finalmente, se muestra el resultado, precedido de un 
                    // mensaje para avisar al usuario, todo en una sola
                    // instrucción Escribir
                    Escribir "El resultado es: ",C
                FinProceso
            

Veamos algunos ejemplos de algoritmos expresados como pseudocódigo:



A pesar de que no son exactamente iguales, realizan la misma tarea. Recordemos que no existe una sintaxis estándar para el pseudocódigo,por lo tanto, pueden escribirse de formas ligeramente diferentes, de acuerdo a las necesidades de cada grupo de trabajo


Algoritmo Secuencial: La estructura secuencial es aquella en la que una acción (instrucción) sigue otra en secuencia. Las tareas se suceden de tal modo que la salida de una es la entrada de la siguiente y así sucesivamente hasta el fin del proceso.


Algoritmo Iterativo: Los algoritmos iterativos son algoritmos que se caracterizan por ejecutarse mediante ciclos. Estos algoritmos son muy útiles al momento de realizar tareas repetitivas. Casi todos los lenguajes de programación modernos tienen palabras reservadas para la realización de iteraciones.


Algoritmo Selectivo: Estas estructuras se utilizan para TOMAR DECISIONES (por eso también se llaman estructuras de decisión o alternativas). Lo que se hace es EVALUAR una condición, y, a continuación, en función del resultado, se lleva a cabo una opción u otra.


El siguiente ejemplo muestra una lista de opciones (en programación se las suele llamar “MENU”) y permite realizar una u otra tarea según sea la opción elegida. Utilizamos una estructura de la forma “si ... entonces ... sino”. Veamos cómo funciona:


Declaración de variables
                ENTEROS: opción
           fin declaración de variables
           
           inicio
                mostrar por pantalla 'menú de opciones:'
                mostrar por pantalla '1. Diccionario de sinónimos'
                mostrar por pantalla '2. Diccionario de antónimos'
                mostrar por pantalla '3. Buscar palabra'
                mostrar por pantalla '4. Salir'
           
                leer del teclado la variable opción
           
                SI opción = 1 ENTONCES
                     {lo que toque a esta opción}
                SI NO, ENTONCES
                     SI opción = 2 ENTONCES
                          {lo que toque a esta opción}
                     SI NO, ENTONCES
                          SI opción = 3 ENTONCES
                               {lo que toque a esta opción}
                          SI NO, ENTONCES
                               SI opción = 4 ENTONCES
                                     que toque a esta opción}
                               SI NO, ENTONCES
                                     por pantalla 'opción incorrecta'
                               fin del SI
                          fin del SI
                     fin del SI
                fin del SI
           fin
           

Algoritmo Repetición: Es un mecanismo de lazo. Permite repetir varias veces un grupo de pasos, hasta que se satisfaga esta condición. La repetición puede programarse para un cierto número de veces.


El siguiente ejemplo muestra el resultado de la suma de los números del 1 al 100:


Declaración de variables
                ENTEROS: numero, suma
                fin declaración de variables
                
                inicio
                    numero = 1
                    suma = 0
                    
                    REPETIR hasta que numero = 100:
                        suma = suma + numero
                        numero = numero + 1
                    fin del REPETIR
                fin