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
Página siguiente |