3  Algoritmos y la resolución de problemas

En esta sección se hará una revisión del proceso a seguir para la resolución de problemas mediante el uso de un computador, incluyendo el concepto de algoritmo.

En esta revisión se hace mención a las características, medios de expresión, elementos básicos y estructura general de los algoritmos.

Preparación de clase

En sus propias palabras, explique lo que le transmitió y lo que le enseño cada parte de lo que leyó en el texto, incluya su discusión, reflexiones y conclusiones al respecto; exponga lo que no entendió e intente encontrar por su cuenta respuestas a las preguntas que le surgieron, para poder compartirlas en clase.

3.1 Fases en la resolución de problemas

Las personas aprenden lenguajes de programación para usar un computador en la resolución de problemas. Varias fases pueden ser identificadas en el proceso de resolución de problemas mediante el uso de un computador.

Figura 3.1: Fases en la elaboración de un programa de computador que resuelva un problema dado.
%%{init: {'theme':'neutral'}}%%
flowchart TB
    Problem["Problema"] --> Analisis["Análisis del problema"]
    subgraph 1ra parte
      Analisis -->
      Dise["Diseño del algoritmo"] -->
      VerifD["Verificación del diseño (pruebas de escritorio)"] --> 
      AprobD{{"¿Diseño pasa todas las pruebas?"}} -- No --> Dise
    end
    subgraph 2da parte
      Codif["Codificación del algoritmo"] -->
      Ejec["Ejecución del programa (pruebas de ejecución)"] -->
      AprobP{{"¿Programa pasa todas las pruebas?"}} -- No --> Codif
    end
    AprobD -- Si --> Codif
    AprobP -- Si --> ListoP["El programa resuelve el problema"] -->
    Mejor{{"¿Se puede mejorar (hacer que sea más eficiente)?"}}
  • Análisis. El primer paso para encontrar la solución a un problema es el análisis del mismo. Se debe examinar cuidadosamente el problema a fin de obtener una idea clara sobre lo que solicita y determinar lo que se necesita para conseguirlo. El problema se analiza teniendo en presente la especificación de los requisitos dados por la persona que requiere el programa (el usuario).
  • Diseño. Una vez analizado el problema, se diseña una solución que conducirá a un algoritmo que resuelva el problema. Se plantean, la forma en que se reciben los datos de entrada, el proceso por el cual se produce el resultado y la forma en que se muestra la salida. Una vez que se ha terminado de escribir un algoritmo es necesario comprobar que realiza la tarea para la cual fue diseñado y produce el resultado correcto y esperado.
  • Codificación (implementación). El algoritmo diseñado se escribe en la sintaxis del lenguaje de programación seleccionado, obteniendo así el programa fuente.
  • Ejecución, verificación y depuración. El programa se ejecuta, se comprueba rigurosamente y se eliminan todos los errores que puedan aparecer (eliminar bugs). Asumiendo una competente codificación, entre mejor se haga todo en las fases de análisis y diseño menos tiempo se gastará buscando, identificando y solucionando errores. Cuando se ejecuta un programa pueden producirse tres tipos de errores: de traducción, de ejecución y lógicos.
  • Documentación. Documentos que soportan todo lo realizado con respecto al programa. Incluye diseño, codificación, manuales, normas, etc. Se recomienda ir documentando cada cosa que se hace, en vez de esperar hasta el final y tener que documentar todo de principio a fin. Existe documentación interna, incluida dentro del código fuente mediante comentarios, y documentación externa. La documentación es vital para que los usuarios puedan usar el programa y para que los programadores entiendan y modifiquen el código fuente.
  • Mantenimiento. El programa se actualiza y modifica cada vez que sea necesario, de modo que se cumplan todas las necesidades adicionales de los usuarios.

3.2 Algoritmos

3.2.1 Características

  • Carácter finito. Un algoritmo siempre debe terminar después de un número finito de pasos.
  • Precisión. Cada paso de un algoritmo debe estar precisamente definido; las operaciones a llevar a cabo deben ser especificadas de manera rigurosa y no ambigua para cada caso.
  • Entrada. Un algoritmo tiene cero o más entradas: cantidades que le son dadas antes de que el algoritmo comience, o dinámicamente mientras el algoritmo corre. Estas entradas son tomadas de conjuntos específicos de objetos.
  • Salida. Un algoritmo tiene una o más salidas: cantidades que tienen una relación específica con las entradas.
  • Eficacia. También se espera que un algoritmo sea eficaz, en el sentido de que todas las operaciones a realizar en un algoritmo deben ser suficientemente básicas como para que en principio puedan ser hechas de manera exacta y en un tiempo finito por un hombre usando lápiz y papel.

Los problemas complejos se pueden resolver de manera más eficaz cuando se dividen en subproblemas que sean más fáciles de solucionar que el inicial (diseño descendente).

3.2.2 Medios de expresión

  • Máquina de Turing: Es un modelo matemático diseñado por Alan Turing que formaliza el concepto de algoritmo, es una descripción que se puede considerar de abstracción de bajo nivel.
  • Pseudocódigo: Es la descripción, de tal forma que se asemeja a un lenguaje de programación pero con algunas convenciones del lenguaje natural.
  • Diagrama de Flujo: Los diagramas de flujo son descripciones gráficas de algoritmos, usando símbolos conectados con flechas para indicar la estructura del algoritmo.
  • Descripción de Alto Nivel: Se establece el problema, se selecciona el modelo matemático y se explica el algoritmo de manera verbal.

3.2.3 Elementos básicos

3.2.3.1 Comentarios

Los comentarios sirven para documentar el algoritmo y en ellos se escriben anotaciones generalmente sobre su funcionamiento. En pseudocódigo, cuando se coloque un comentario de una sola línea se escribirá precedido de //. Si el comentario es multilínea, lo pondremos entre {}.

3.2.3.2 Palabras reservadas

Las palabras reservadas o palabras clave (Keywords) son palabras que tienen un significado especial, como: inicio y fin, que marcan el principio y fin del algoritmo.

3.2.3.3 Identificadores

Identificadores son los nombres que se dan a las constantes simbólicas, variables, funciones, procedimientos, u otros objetos que manipula el algoritmo. La regla para construir un identificador establece que:

  • Debe resultar significativo, sugiriendo lo que representa.
  • No podrá coincidir con palabras reservadas, propias del lenguaje algorítmico. Como se verá más adelante, la representación de algoritmos mediante pseudocódigo va a requerir la utilización de palabras reservadas.
  • Se recomienda un máximo de 50 caracteres.
  • Comenzará siempre por un carácter alfabético y los siguientes podrán ser letras, dígitos o el símbolo de subrayado.
  • Podrá ser utilizado indistintamente escrito en mayúsculas o en minúsculas

3.2.3.4 Datos

Dato es la expresión general que describe los objetos con los cuales opera el algoritmo. El tipo de un dato determina su forma de almacenamiento en memoria y las operaciones que van a poder ser efectuadas con él. En principio hay que tener en cuenta que, prácticamente en cualquier lenguaje y por tanto en cualquier algoritmo, se podrán usar datos de los siguientes tipos:

  • entero. Subconjunto finito de los números enteros, cuyo rango o tamaño dependerá del lenguaje en el que posteriormente codifiquemos el algoritmo y de la computadora utilizada.
  • real. Subconjunto de los números reales limitado no sólo en cuanto al tamaño, sino también en cuanto a la precisión.
  • lógico. Conjunto formado por los valores verdad y falso.
  • carácter. Conjunto finito y ordenado de los caracteres que la computadora reconoce.
  • cadena. Los datos (objetos) de este tipo contendrán una serie finita de caracteres, que podrán ser directamente traídos o enviados a/desde la consola.

En los algoritmos para indicar que un dato es de uno de estos tipos se declarará utilizando directamente el identificador o nombre del tipo.

Los datos pueden venir expresados como constantes, variables, expresiones o funciones.

Las constantes son datos cuyo valor no cambia durante todo el desarrollo del algoritmo.

Una variable es un objeto cuyo valor puede cambiar durante el desarrollo del algoritmo. Se identifica por su nombre y por su tipo, que podrá ser cualquiera, y es el que determina el conjunto de valores que podrá tomar la variable. En los algoritmos se deben declarar las variables que se van a usar, especificando su tipo.

Una expresión es una combinación de operadores y operandos. Los operandos podrán ser constantes, variables u otras expresiones y los operadores de cadena, aritméticos, relacionales o lógicos. Las expresiones se clasifican, según el resultado que producen, en:

  • Numéricas. Los operandos que intervienen en ellas son numéricos, el resultado es también de tipo numérico y se construyen mediante los operadores aritméticos. Se pueden considerar análogas a las fórmulas matemáticas. Debido a que son los que se encuentran en la mayor parte de los lenguajes de programación, los algoritmos utilizarán los siguientes operadores aritméticos: inverso aditivo (–), suma (+), resta (–), multiplicación (*), división real (/), residuo/módulo de la división entera (mod) y cociente de la división entera (div). Tenga en cuenta que la división real siempre dará un resultado real y que los operadores mod y div sólo operan con enteros y el resultado es entero.
  • Alfanuméricas. Los operandos son de tipo alfanumérico y producen resultados también de dicho tipo. Se construyen mediante el operador de concatenación, representado por el operador ampersand (&) o con el mismo símbolo utilizado en las expresiones aritméticas para la suma.
  • Booleanas. Su resultado podrá ser verdad o falso. Se construyen mediante los operadores relacionales y lógicos. Los operadores de relación son: igual (=), distinto (<>), menor que (<), mayor que (>), mayor o igual (>=), menor o igual (<=). Actúan sobre operandos del mismo tipo y siempre devuelven un resultado de tipo lógico. Los operadores lógicos básicos son: negación lógica (no), multiplicación lógica (y), suma lógica (o). Actúan sobre operandos de tipo lógico y devuelven resultados del mismo tipo, determinados por las tablas de verdad correspondientes a cada uno de ellos.

En los lenguajes de programación existen ciertas funciones predefinidas o internas que aceptan unos argumentos y producen un valor denominado resultado.

3.2.3.5 La operación de asignación

Esta operación se utiliza para dar valor a una variable en el interior de un algoritmo y permite almacenar en una variable el resultado de evaluar una expresión, perdiéndose cualquier otro valor previo que la variable pudiera tener.

Se supone que se efectúan conversiones automáticas de tipo cuando el tipo del valor a asignar a una variable es compatible con el de la variable y de tamaño menor. En estos casos se considera que el valor se convierte automáticamente al tipo de la variable. También se interpreta que se efectúa este tipo de conversiones cuando aparecen expresiones en las que intervienen operandos de diferentes tipos.

3.2.4 Estructura general y partes

El pseudocódigo es la herramienta más adecuada para la representación de algoritmos. El algoritmo en pseudocódigo debe tener una estructura muy clara y similar a un programa, de modo que se facilite al máximo su posterior codificación. Interesa por tanto conocer las secciones en las que se divide un programa, que habitualmente son:

  • La cabecera.
  • El cuerpo del programa:
    • Bloque de declaraciones.
    • Bloque de instrucciones.

La cabecera contiene el nombre del programa.

El cuerpo del programa contiene a su vez otras dos partes: el bloque de declaraciones y el bloque de instrucciones.

En el bloque de declaraciones se definen o declaran las constantes con nombre, los tipos de datos definidos por el usuario y también las variables. Suele ser conveniente seguir este orden. La declaración de tipos suele realizarse en base a los tipos estándar o a otros definidos previamente, aunque también hay que considerar el método directo de enumeración de los valores constituyentes.

El bloque de instrucciones contiene las acciones a ejecutar para la obtención de los resultados. Las instrucciones o acciones básicas a colocar en este bloque se podrían clasificar del siguiente modo:

  • De inicio/fin. La primera instrucción de este bloque será siempre la de inicio y la última la de fin.
  • De asignación. Esta instrucción se utiliza para dar valor a una variable en el interior de un programa.
  • De lectura. Toma uno o varios valores desde un dispositivo de entrada y los almacena en memoria en las variables que aparecen listadas en la propia instrucción.
  • De escritura. Envía datos a un dispositivo de salida.

La representación de un algoritmo mediante pseudocódigo se muestra a continuación. Esta representación es muy similar a la que se empleará en la escritura al programar.

Algoritmo: nombre_del_algoritmo
//comentario_1
const
  nombre_de_constante_1 <- valor_1
  …
var
  tipo_de_dato_1: nombre_de_var_1, nombre_de_var_2, …
  …
inicio
  acción_1
  acción_2
  …
  //Algunas acciones podrían ser de escritura:
  escribir(expresión_cadena)
  //Algunas acciones podrían ser de lectura:
  leer(variable)
  //Algunas acciones podrían ser de asignación:
  nombre_de_variable <- expresión
  …
fin

La representación de un algoritmo mediante un diagrama de flujo utiliza unos símbolos estándar. Los principales símbolos son:


Ejemplo 3.1 Diseñar en diagrama de flujo y pseudocódigo un algoritmo que calcule e imprima el área de un triangulo a partir de la base y la altura dadas por el usuario.

En pseudocódigo:

Algoritmo: Área de un triángulo
//El usuario ingresa dos números reales asociados a la altura y la
//base de un triángulo y el algoritmo devuelve el valor asociado
//al área del triángulo
var
  real: base, altura, area
inicio
  escribir(“Ingrese la altura”)
  leer(altura)
  escribir(“Ingrese la base”)
  leer(base)
  area <- base * altura / 2
  escribir(“El área del triángulo es:”)
  escribir(area)
fin

En diagrama de flujo:

digraph area_triang {
  ini [label="Inicio", shape="ellipse", color=lightsalmon, style=filled]; 
  pedir_val [label="\"Ingrese los valores para \nla base y la altura\"", shape="parallelogram", color=lightgreen, style=filled];
  leer_val [label="base, altura", shape="parallelogram", color=lightblue, style=filled];
  calc [label="area = base * altura / 2", shape="box", color=yellow, style=filled];
  escr_area [label="\"El área del triángulo es\", area", shape="parallelogram", color=lightgreen, style=filled];
  fin [label="Fin", shape="ellipse", color=lightsalmon, style=filled]; 
  ini -> pedir_val -> leer_val -> calc -> escr_area -> fin;
}
area_triang ini Inicio pedir_val “Ingrese los valores para la base y la altura” ini->pedir_val leer_val base, altura pedir_val->leer_val calc area = base * altura / 2 leer_val->calc escr_area “El área del triángulo es”, area calc->escr_area fin Fin escr_area->fin 
flowchart TB
  ini([Inicio]) -->
  pedir_val[/"#quot;Ingrese los valores para la base y la altura#quot;"\] -->
  leer_val[\"base, altura"/] -->
  calc(area = base * altura / 2) -->
  escr_area[/"#quot;El área del triángulo es#quot;", area\] -->
  fin([Fin])
  style ini fill:lightsalmon
  style fin fill:lightsalmon
  style pedir_val fill:lightgreen
  style escr_area fill:lightgreen
  style leer_val fill:lightblue
  style calc fill:yellow
flowchart TB
  ini([Inicio]) -->
  pedir_val[/"#quot;Ingrese los valores para la base y la altura#quot;"\] -->
  leer_val[\"base, altura"/] -->
  calc(area = base * altura / 2) -->
  escr_area[/"#quot;El área del triángulo es#quot;", area\] -->
  fin([Fin])
  style ini fill:lightsalmon
  style fin fill:lightsalmon
  style pedir_val fill:lightgreen
  style escr_area fill:lightgreen
  style leer_val fill:lightblue
  style calc fill:yellow