Construccion_de_algoritmos

Adrian Nicolás Malaver Barrera 1

2. Construcción de algoritmos

Una vez explicados los procesos de modelado y especificación de algoritmos, reconocida

su importancia y la manera de formalizar entradas, salidas, pre y poscondiciones,

comenzaremos a trabajar en su construcción.

Pensemos en la siguiente situación: invitamos a un amigo a conocer nuestro nuevo

apartamento pero cuando nos pide la dirección, solo conocemos el número de la torre y

del apartamento, no recordamos la dirección exacta ¿Qué hacemos entonces? ¡Le damos

instrucciones!

Debemos tener en cuenta que estas instrucciones tienen que ser claras y precisas para

que nuestro amigo no se pierda ni se equivoque. Por ejemplo: “Tome la ruta D21 de

Transmilenio que es la más rápida, o cualquier ruta que lo lleve al portal de la 80; luego

sale del portal, cruza el puente peatonal de la calle 80, sigue dos cuadras hacia el

occidente, voltea a la izquierda, sigue tres cuadras y llega a un conjunto cerrado de torres

grises y blancas de 15 pisos. Mi apartamento es el 904 de la torre 8”.

No es difícil… Si tenemos clara la información, ¡Es posible resolver el problema!

Formalmente, a un conjunto ordenado y finito de instrucciones que permiten obtener,

con base en un conjunto de entradas, un conjunto de salidas que representan la solución

al problema, lo llamaremos algoritmo.

Ahora sabemos lo que requerimos para solucionar un problema de forma organizada: sus

entradas y salidas, las precondiciones y pos condiciones definidas para esos datos y un

algoritmo que describa, a partir de instrucciones claras y precisas, paso a paso lo que se

debe hacer para llegar a una solución.

Si queremos definir un algoritmo en un lenguaje que cualquier persona pueda entender

debemos tener en cuenta ciertas reglas. Estas reglas y los elementos que constituyen un

algoritmo los iremos conociendo con el tiempo, a lo largo de este curso. ¡Comencemos!

2.1 Asignación

Un algoritmo se compone de un conjunto de instrucciones que deben ser realizadas

ordenadamente, con el objetivo de dar solución a un problema. La primera forma que

POLITÉCNICO GRANCOLOMBIANO EN ALIANZA CON WHITNEY INTERNATIONAL UNIVERSITY SYSTEM

Adrian Nicolás Malaver Barrera 2

definiremos para una instrucción es la asignación, que se basa en asignar, como su

nombre lo dice, un valor específico a una variable. Este valor puede ser una variable, una

constante, o en general, una expresión. Con la asignación lo que se pretende es

almacenar un resultado en una variable. Cuando definamos asignaciones, lo haremos de la

siguiente manera (Para una definición más formal consulta la lectura 3 de esta semana):

<Variable> ← <Expresión>

Veamos algunos ejemplos de asignaciones:

Tabla 1. Ejemplos de asignaciones

Asignación ¿Qué puede representar?

V ← 15 / 2 El cálculo de una velocidad, basada en valores dados de distancia y tiempo

A ← π*R*R El área de un círculo

P ← 2*π*R La longitud de una circunferencia

V ← π*R*R * h El volumen de un cilindro

Al construir instrucciones en forma de asignaciones debemos tener en cuenta que las

expresiones involucradas estén estructuradas correctamente.

En general, una expresión puede estar mal formada si:

• Contiene errores relacionados con la sintaxis o el orden de los símbolos usados. Por

ejemplo, la expresión 5 + < 4 está mal formada, dado que para realizar cualquiera de

las dos operaciones, se requieren dos operandos.

• Contiene operaciones que no tienen sentido o no respetan las reglas matemáticas

implicadas. Por ejemplo 5 / (8 – 4*2) implica que se haga una división por cero, lo cual

no tiene validez.

• Contiene operaciones que no se pueden aplicar al tipo de dato de los operandos

implicados. Por ejemplo, no es posible evaluar 57 Y 85 ni la expresión V + F * 3.

Podemos entonces, definir las instrucciones de un algoritmo con base en un conjunto de

asignaciones. Veamos un ejemplo:

Se quiere calcular el volumen de agua que puede ser almacenado en 18 vasos cilíndricos,

dados el radio de su base y su altura.

Adrian Nicolás Malaver Barrera 3

Entonces, lo primero que debemos hacer es el proceso de modelado que se basa en la

identificación de entradas y salidas. Podemos decir que requerimos de dos variables de

entrada, que son la base y la altura del vaso y obtendremos una salida que es el valor del

volumen. Luego, identificamos las pre y pos condiciones que hablarían de los valores con

los cuales tendría sentido solucionar el problema. Finalmente, pasamos a definir el

algoritmo que nos permite obtener una solución, que se fundamentaría en el cálculo del

volumen de uno de los vasos y su posterior multiplicación por 18.

Una vez tengamos esta información requerida debemos documentarla mejor. Entre más

claridad tengamos en la definición del problema y del algoritmo, mejores y más precisos

serán los resultados obtenidos.

Un algoritmo bien definido permite que, dado un conjunto de datos de entrada que

cumple las precondiciones, se siguen instrucciones que permiten hallar un conjunto de

salidas que deben cumplir las poscondiciones definidas.

2.2 Estructura formal de un algoritmo

Si juntamos los procesos de modelado, especificación y construcción de algoritmos (con

base en asignaciones como lo hemos visto) podemos definir una forma general para

escribir un algoritmo. Veamos:

Tabla 2. Estructura de un algoritmo

Algoritmo <Nombre del algoritmo> Un nombre que indique lo que pretendemos hacer

con este algoritmo

Entradas Variables de entrada

Pre: {…} Condiciones para las variables de entrada

Inicio Inicio del algoritmo

Paso 1

Paso 2

.

.

.

Paso n

Cada paso o instrucción involucrada en la solución

del problema

Fin Fin del algoritmo

Salidas Variables de salidas

Pos: {…} Condiciones que deberán cumplir las salida

Adrian Nicolás Malaver Barrera 4

Y para el ejemplo visto antes, la definición podría ser la siguiente:

Tabla 3. Ejemplos de algoritmo de acuerdo con la estructura

Algoritmo VolumenDelCilindro

Entradas

radio, altura: Real

Pre: {radio>0 Y altura>0 }

Inicio

...