Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Algoritmos y programas




Enviado por pedro obregon



Partes: 1, 2

    Monografias.com

    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

    Monografias.com

    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

    Monografias.com

    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

    Monografias.com

    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).

    Monografias.com

    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

    Monografias.com

    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

    Monografias.com

    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)

    Monografias.com

    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,

    Monografias.com

    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”

    Monografias.com

    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.

    Monografias.com

    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

    Monografias.com

    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

    Partes: 1, 2

    Página siguiente 

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter