Algoritmos y programas

CAPITULO 3 ALGORITMOS Y PROGRAMAS Este capítulo trata de ser una introducción a la metodología y tecnología de la programación, con el objetivo de proporcionar al lector los procedimientos y técnicas para el desarrollo de programas.

No por obvio, hay que olvidar que los programas se escriben con el ánimo de resolver problemas, con ayuda de las computadoras y que la primera medida a considerar, es el análisis del problema en cuestión y la obtención, en su caso, de un algoritmo adecuado. Por este punto empezaremos nuestra exposición, hasta llegar a los métodos y etapas a seguir para obtener una aplicación informática.

Si bien los conceptos que aquí se introducen son fundamentales para la realización de programas, este capítulo no debe leerse como si se tratara de un manual de programación, sino como una fundamentación de lo que llamamos programación estructurada, mas allá de la sintaxis y de la semántica de un lenguaje de programación concreto.

5030" EQPEGRVQ"FG"CNIQTKVOQ

Sabemos que para que un ordenador pueda llevar adelante una tarea cualquiera, se tiene que contar con un algoritmo que le indique, a través de un programa, que es lo que debe hacer con la mayor precisión posible. Quizás esta afirmación debería ser revisada desde la óptica de la Inteligencia Artificial, pero por el momento la mantendremos como válida dentro del carácter introductorio de este curso. Consecuencia de lo anterior es la importancia del estudio de los algoritmos dentro de las Ciencias de la Computación. Recordemos que un algoritmo es “una sucesión finita de pasos no ambiguos que se pueden ejecutar en un tiempo finito”, cuya razón de ser es la de resolver problemas; por tanto “problema” para nosotros, serán aquellas cuestiones, conceptuales o prácticas , cuya solución es expresable mediante un algoritmo. Afortunadamente, son muchos los problemas cuya solución puede describirse por medio de un algoritmo y ésta es

81

82 FUNDAMENTOS DE INFORMÁTICA Y PROGRAMACIÓN una de las razones subyacentes a la necesidad de que aprendamos a programar y a manejar un ordenador.

Nótese que no es redundante el hecho de exigir que un conjunto finito de pasos o instrucciones acaben en un tiempo finito, pues una sola instrucción del tipo: “hacer acción A1 hasta que se cumpla la condición C1”, acaba dando lugar a un proceso infinito, si no llega a darse nunca la condición C1. El término ‘no ambiguo’ significa que la acción, a desarrollar en cada paso de la secuencia, viene unívocamente determinada, tanto por la instrucción como por los datos disponibles en este momento, de forma que en cada momento se sepa qué acción única, se tiene que llevar a cabo.

5040" NC" TGUQNWEKlP" FG" RTQDNGOCU" [" GN" WUQ" FGN QTFGPCFQT

Antes de entrar en la codificación de la resolución de un problema, hemos de contar con una idea bastante precisa de cómo podemos llegar a esta solución. La experiencia personal de todos nosotros nos dice que la sistematización para la resolución de problemas no es fácil.

Resolución de un problema Análisis del problema Diseño del algoritmo Programación del algoritmo Fig. 3.1. La resolución de un problema en Informática En esta línea, el matemático G. Poyla propuso, a finales de 1940, una metodología general para la resolución de problemas matemáticos, que ha sido adaptada para el caso en que se cuente con un ordenador como recurso. Esta sistemática, de forma muy esquematizada, se puede dividir en tres fases (Ver Figura 3.1):

1. Análisis del problema 2. Diseño del algoritmo 3. Programación del algoritmo

50403" CPiNKUKU"FGN"RTQDNGOC

ALGORITMOS Y PROGRAMAS 83 El objetivo del análisis del problema, es ayudar al programador a llegar a una cierta comprensión de la naturaleza del mismo. Este análisis supone, en particular, la superación de una serie de pasos (Ver Figura 3.2): – –

– Definir el problema con total precisión. Especificar los datos de partida necesarios para la resolución del mismo (especificaciones de entrada). Especificar la información que debe proporcionarse al resolverse (especificaciones de salida).

Análisis del problema Definición del problema Especificaciones Especificaciones de entrada de salida Fig. 3.2. Análisis del problema Ejemplo 1:

Elaborar el análisis para obtener el área y la longitud de una circunferencia. 1.- 2.-

3.- Utilizar las fórmulas del área y la circunferencia en función del radio. Las entradas de datos se reducen al dato correspondiente al radio del círculo. Dada la naturaleza del mismo y el procesamiento al cual lo someteremos, su tipo de dato debe ser un número real. Las salidas serán dos variables también reales: área y circunferencia. La finalización de la fase de análisis del problema nos llevaría al siguiente resultado: Entradas: Salidas:

Variables: Radio del círculo (variable RADIO). Superficie del círculo (variable AREA). Circunferencia del círculo (variable CIRCUNFERENCIA). RADIO, AREA, CIRCUNFERENCIA: tipo real. 50404" FKUGÜQ"FGN"CNIQTKVOQ

Diseñar un algoritmo puede ser una tarea difícil y su aprendizaje no es inmediato, ya que requiere una buena dosis de experiencia y creatividad. Hace ya 100 años, un matemático de la talla de Henri Poincare, que no sólo trabajó en temas

84 FUNDAMENTOS DE INFORMÁTICA Y PROGRAMACIÓN relacionados con la física, el álgebra y el análisis, sino también sobre la filosofía de la ciencia, trató de explicar sus experiencias personales de cómo un problema, a cuya resolución había dedicado mucho tiempo sin éxito, podía aparecer tiempo después resuelto repentinamente en su cabeza, incluso cuando se estaba dedicando a proyectos distintos. Desgraciadamente sus resultados en este empeño, distaron mucho de la brillantez de sus logros como físico y matemático. El periodo que existe entre el análisis de un problema y el diseño de su solución recibe el nombre de periodo de incubación y el proceso mental, que se da durante el mismo sigue siendo un tema de investigación para los psicólogos. Estamos por tanto en el terreno de la inspiración y la madurez mental. Seamos optimistas y pensemos que vamos a tener la capacidad de tener ideas, propias o adquiridas, para desarrollar algoritmos que nos permitan actuar ante los problemas que se nos planteen. Para diseñar algoritmos hay que tener presente los requisitos siguientes: • indicar el orden de realización de cada paso, • estar definido sin ambigüedad y • ser finito

Ejemplo 2:

Averiguar si un número es primo o no, suponiendo que razonamos de la siguiente forma: “Del análisis del hecho de que un número N es primo si sólo puede dividirse por sí mismo y por la unidad, un método que nos puede dar la solución sería dividir sucesivamente el número por 2, 3, 4…, etc. y, según el resultado, podríamos resolver el problema”. Un diseño del mismo sería: 1. 2.

3. 4.

5. 6.

7. 8. 9. 10. Inicio Poner X igual a 2 (X = 2, X, variable que representa a los posibles divisores de N) Dividir N por X (N/X) Si el resultado es entero, entonces N no es primo, y saltar al punto 9 (en caso contrario continuar el proceso en el siguiente punto, 5) Incrementar X en una unidad Si X es menor que N saltar al punto 3 (en caso contrario continuar el proceso en el siguiente punto, 7) Declarar N es primo; Saltar al Fin (punto 10) Declarar N no es primo Fin Como parte del diseño de algoritmo está la selección de uno que sea razonablemente aceptable, entre todos los muchos posibles que resuelven el mismo problema (el ejemplo que acabamos de dar es claramente mejorable, pues si N no era divisible por 2 no tiene mucho sentido volverse a preguntar si lo es por 4).

ALGORITMOS Y PROGRAMAS 85 Durante el diseño es posible y aconsejable, realizar comparaciones entre algoritmos que resuelven el mismo problema. La bondad de un algoritmo puede medirse por dos factores:

– El tiempo que se necesita para ejecutarlo. Para tener una idea aproximada de ello, basta con saber el número de instrucciones de cada tipo necesarias para resolver el problema. – Los recursos que se necesitan para implantarlo.

Así, una vez diseñado un primer algoritmo, conviene realizar una evaluación del mismo, cuestión a veces nada banal y sobre la que volveremos en capítulos posteriores. Si se decide que éste no es eficiente será necesario o bien diseñar uno nuevo o bien optimizar el original. Optimizar un algoritmo consiste en introducir modificaciones en él, tendentes a disminuir el tiempo que necesita para resolver el problema o a reducir los recursos que utiliza. (En el ejemplo 2 el algoritmo se optimiza, si N se declara como primo cuando X supera a N/2).

3.2.2.1" Diseño Descendente o Modular

Los problemas complejos se pueden resolver más eficazmente cuando se descomponen en subproblemas que sean más fáciles resolver el original. Este método se denomina divide y vencerás y consiste en convertir un problema complejo en otros más simples que, una vez resueltos, en su conjunto nos solucionen el original. Al procedimiento de descomposición de un problema en subproblemas más simples, (llamados módulos) para, a continuación, seguir dividiendo estos subproblemas en otros más simples, se le denomina diseño descendente. Las ventajas más importantes de este tipo de diseño son: 1)

2)

3) El problema se comprende más fácilmente al dividirse en módulos o partes más simples. Adelantemos que cuando demos el salto a la programación, utilizaremos esta idea constantemente, de forma que hablaremos también de procedimientos, o subprogramas. Las modificaciones en los módulos son más fáciles, pues estamos ante algoritmos más sencillos. La comprobación del problema se puede realizar más fácilmente, al poder localizar los posibles fallos con mayor precisión.

3.2.2.2" Refinamiento por pasos

Durante el diseño, entenderemos por refinamiento por pasos, la metodología por la que en un primer esbozo del algoritmo nos limitamos a señalar

86 FUNDAMENTOS DE INFORMÁTICA Y PROGRAMACIÓN o describir un reducido numero de pasos, que deberán ser expresados con mayor detalle posteriormente. Tras esta primera descripción, éstos se especifican con mayor minuciosidad, de forma más extensa y con más pasos específicos. En cada nivel de refinamiento hay que considerar dos fases: ¿Qué hace el módulo? para a continuación responder a ¿Cómo lo hace?.

Como es natural, dependiendo de la complejidad del problema se necesitarán diferentes y sucesivos niveles de refinamiento antes de que pueda obtenerse un algoritmo con suficiente nivel de detalle. Así en el Ejemplo 1, del cálculo de la longitud y superficie de un círculo, a pesar de presentar un bajo nivel de complejidad, en su diseño, se puede descomponer en subproblemas más simples: 1) leer datos de entrada, 2) calcular superficie y longitud, 3) escribir resultados.

El ejemplo siguiente, nos muestra el diseño de un algoritmo para un problema de carácter no numérico

Ejemplo 3:

Diseñar un algoritmo que responda a la pregunta: ¿Qué debo hacer para ver la película XYZ?. Un primer análisis nos conduce a un esbozo de solución, descomponiéndolo en cuatro módulos sucesivos: 1 2 3 4 ir al cine donde proyectan XYZ comprar una entrada ver la película regresar a casa Estos cuatro pasos se pueden refinar un poco más y así este problema lo podríamos descomponer de la siguiente forma: inicio {algoritmo para ver la película XYZ} consultar la cartelera de cines si proyectan “XYZ” entonces ir al cine correspondiente si_no proyectan “XYZ” declarar el fracaso del objetivo y terminar acudir al cine correspondiente si hay cola entonces ponerse en ella

ALGORITMOS Y PROGRAMAS 87 mientras haya personas delante en la cola hacer avanzar en la cola preguntar si quedan entradas si hay entradas entonces comprar una entrada si_no quedan entradas declarar el fracaso del objetivo, regresar a casa y terminar encontrar el asiento correspondiente mientras proyectan la película hacer ver la película abandonar el cine regresar a casa fin

Algunas de estas acciones son primitivas para nosotros, es decir, no es necesario descomponerlas más, como el abandonar el cine. Sin embargo hay otras acciones que son susceptibles de mayor descomposición. Este es el caso de la acción: “encontrar el asiento correspondiente” si los números de los asientos están impresos en la entrada, esta acción compuesta se resuelve con el siguiente algoritmo:

inicio {algoritmo para encontrar el asiento del espectador} caminar hasta llegar a la primera fila de asientos repetir comparar número de fila con número impreso en billete si no son iguales, entonces pasar a la siguiente fila hasta_que se localice la fila correcta mientras número de asiento no coincida con número de billete hacer avanzar a través de la fila a la siguiente butaca sentarse en la butaca fin De esta forma, podríamos seguir hasta la descomposición de las distintas acciones en instrucciones susceptibles de ser interpretadas, directamente por el ordenador.

50405" RTQITCOCEKlP"FGN"CNIQTKVOQ

Una vez que el algoritmo está diseñado y representado, se debe pasar a la fase de resolución práctica del problema con el ordenador. Esta fase se descompone a su vez en las siguientes subfases: (Ver Figura 3.3)

88 FUNDAMENTOS DE INFORMÁTICA Y PROGRAMACIÓN

1. Codificación del algoritmo en un programa. 2. Ejecución del programa. 3. Comprobación del programa.

Programación del algoritmo Codificación en un programa Ejecución del programa Comprobación del programa Fig. 3.3Programación del algoritmo

La fase de conversión de un algoritmo en instrucciones de un lenguaje de programación, como sabemos, se denomina codificación. El código deberá estar escrito de acuerdo con la sintaxis del lenguaje de programación ya que solamente las instrucciones sintácticamente correctas pueden ser interpretadas por el computador.

Nótese que durante el proceso de programación, se debe separar el diseño del algoritmo de su posterior implementación en un lenguaje de programación específico. Por ello distinguimos entre el concepto más general de programación y el más particular de codificación, que depende del lenguaje de programación utilizado. Al llegar a este punto, se supone que el lector conoce al menos uno de estos lenguajes y éste es el momento en el que tiene que mostrar sus habilidades para efectuar una codificación lo más correcta y eficiente posible.

Tras la codificación del programa, éste deberá ejecutarse en un computador. El resultado de esta primera ejecución es incierto, ya que existe una alta posibilidad de que aparezcan errores, bien en la codificación bien en el propio algoritmo. Por tanto, el paso siguiente consiste en comprobar el correcto funcionamiento del programa y en asegurarse, en la medida de lo posible, de la validez de los resultados proporcionados por la máquina.

5050" TGRTGUGPVCEKlP"FG"CNIQTKVOQU

Un algoritmo es algo puramente conceptual que necesita una forma de representación, bien para comunicarlo a otra persona bien para ayudar a convertirlo en un programa. De hecho, la codificación en un lenguaje de programación, es una representación muy utilizada de un algoritmo, sin embargo tiene el inconveniente de que no todas las personas conocen el lenguaje que se haya elegido. Por ello,

ALGORITMOS Y PROGRAMAS 89 existen diferentes métodos que permiten que se pueda independizar el algoritmo de su correspondiente codificación. Veamos dos de ellos:

50503" RUGWFQEQFKIQ

El pseudocódigo es un lenguaje de especificación de algoritmos (no de programación) basado en un sistema notacional, con estructuras sintácticas y semánticas, similares a los lenguajes procedurales, aunque menos formales que las de éstos, por lo que no puede ser ejecutado directamente por un computador. El pseudocódigo utiliza para representar las sucesivas acciones, palabras reservadas – similares a sus homónimas en los lenguajes de programación-, tales como start, end, stop, if-then-else, while-do, repeat-until, (inicio, fin, parar, si-entonces- sino, mientras-hacer, repetir-hasta), etc. A lo largo de este capítulo, a medida que vayamos describiendo las estructuras de control utilizadas en los programas, iremos haciendo una lista de las instrucciones más usuales del pseudocódigo. La ventajas del uso del pseudocódigo residen en:

– Su uso en la planificación de un programa; permitiendo que el programador se pueda concentrar en la lógica y en las estructuras de control y no tenga que preocuparse, por ahora de detalles acerca de las reglas sintácticas y semánticas de un lenguaje específico. Consiguientemente es más fácil de modificar, en el caso de que se descubran errores o anomalías en la lógica del algoritmo.

– Aunque el pseudocódigo es independiente del lenguaje de alto nivel que vaya a utilizarse, un algoritmo expresado en pseudocódigo puede ser traducido más fácilmente a muchos de ellos.

Ejemplo 4:

Supongamos que tenemos un algoritmo para averiguar si un número es par, que puede ser descrito narrativamente de la siguiente forma: “Si restando consecutivamente doses del número se obtiene el numero 2, es par, si se obtiene otro valor (el 1), entonces es impar”. Este algoritmo escrito en pseudocódigo sería:

leer N mientras N > 2 hacer N ? N -2 si N = 2 entonces escribe “es par” sino escribe “es impar”

90 FUNDAMENTOS DE INFORMÁTICA Y PROGRAMACIÓN fin

Nótese que en este ejemplo y en otros anteriores hemos utilizado dos estructuras que son muy usadas en programación: mientras-hacer y si-entonces- si_no; y que la escritura del pseudocódigo usa normalmente la indentación (sangría en el margen izquierdo) de diferentes líneas para ayudar a delimitar visualmente cada una de las estructuras utilizadas.

50504" QTICPKITCOCU

Para ganar claridad expositiva se han desarrollado una serie de símbolos gráficos que permiten representar los algoritmos y que son universalmente reconocidos. Veamos algunos ejemplos: Fig. 3.4. Símbolos usados para confeccionar organigramas Los organigramas o diagramas de flujo son herramientas gráficas utilizadas tanto para representar algoritmos, como en la ayuda en el diseño de programas. Están compuestos por una serie de símbolos, unidos con flechas, donde cada símbolo representa una acción distinta y las flechas el orden de realización de las acciones. Cada símbolo, por tanto, tendrá al menos una flecha que conduzca a él y una flecha que parta de él, exceptuando el comienzo y final del algoritmo. En la Figura 3.4, se muestran los símbolos utilizados habitualmente en la confección de organigramas, cuyo significado completaremos más adelante.

La Figura 3.5. representa, en forma de organigrama, el algoritmo del Ejemplo 4 que ha sido expresado en pseudocódigo en la sección anterior.

ALGORITMOS Y PROGRAMAS 91 Fig. 3.5. Organigrama del Ejemplo 4 5060" GUVTWEVWTCU"FG"EQPVTQN

En el Capítulo 1, vimos los elementos básicos constitutivos de un programa:

– palabras reservadas (inicio, si-entonces, etc.) – identificadores (nombres de variables, procedimientos, etc.) – caracteres especiales (coma, punto y coma, apóstrofo, etc.) – constantes – variables – expresiones – instrucciones

Sin embargo como hemos visto al diseñar algoritmos para escribir un programa, además de estos elementos básicos, hemos de conocer determinadas estructuras, cuyo objetivo es controlar su ejecución y sin cuya comprensión es imposible programar.

Llamaremos estructuras de control a las acciones que tienen por objeto marcar el orden de realización de los distintos pasos de un programa ó algoritmo. Cada estructura tiene un punto de entrada y uno de salida, lo que facilita la depuración de posibles errores. Estas son de tres tipos:

• estructuras secuenciales

92 FUNDAMENTOS DE INFORMÁTICA Y PROGRAMACIÓN • estructuras selectivas • estructuras repetitivas

y vamos a estudiarlas con un cierto detalle. El uso de las estructuras de control es una de las características de la programación estructurada que constituye la principal orientación de este texto, aunque otros lenguajes procedurales no estructurados también utilizan estas estructuras.

50603" GUVTWEVWTCU"UGEWGPEKCNGU

Son aquéllas en las que una acción (instrucción) sigue a otra de acuerdo con su orden de escritura. Las tareas se suceden de tal modo que tras la salida (final) de una se efectúa la entrada (principio) en la siguiente y así sucesivamente hasta el fin del proceso. Su organigrama obedece al esquema de la Figura 3.6: Fig. 3.6. Esquema de una estructura secuencial Las estructuras secuenciales se codifican de forma directa en cualquier lenguaje de programación, pues como sabemos el orden de ejecución de todo programa es precisamente, salvo orden en sentido contrario, de arriba abajo. A pesar de su simplicidad, ya sabemos, que algunos problemas se pueden resolver con la sola utilización de esta estructura, como por ejemplo el cálculo del volumen del cilindro visto en el Capítulo 1, y codificado en los cuatro lenguajes de programación.

50604" GUVTWEVWTCU"UGNGEVKXCU

Como hemos tenido ocasión de comprobar, la especificación formal de algoritmos tiene utilidad real, cuando éstos requieren una descripción más complicada que una simple secuencia de instrucciones. Uno de estos casos se