Algoritmos
Los
algoritmos son el fundamento de la programación de computadoras, para que la
computadora pueda ejecutar una tarea es necesario que primero se diseñe el
algoritmo correspondiente, es decir, especificar las operaciones necesarias
para transformar los datos de entrada en datos de salida. Una vez diseñado y
probado el algoritmo, se trasforma en el programa correspondiente. El programa está
compuesto por el algoritmo, la especificación de los datos y las instrucciones
que permiten la comunicación entre los usuarios del programa y la
máquina.
Definición de algoritmo:
Un algoritmo
es un conjunto finito de instrucciones cuyo fin es realizar una tarea; este
conjunto finito de instrucciones debe también ser preciso y determinístico.
Preciso: el algoritmo debe ejecutar la tarea
para el cual fue diseñado.
Determinístico:
significa que el resultado debe
depender estrictamente de los datos suministrados, siempre que el algoritmo se
ejecute con un mismo conjunto de datos de entrada, el resultado debe ser
siempre el mismo.
Son ejemplos
de algoritmos los métodos utilizados en aritmética para sumar,
restar, multiplicar y dividir cantidades; la aplicación de la fórmula
cuadrática para encontrar las raíces de un polinomio de segundo grado En todos
ellos se cumplen las tres características anteriores.
Un algoritmo
eficiente y confiable es el producto de un análisis exhaustivo del
problema, para determinar la mejor alternativa de solución.
Elementos básicos en el diseño de algoritmos
HERRAMIENTAS PARA EL DISEÑO DE
ALGORITMOS
Las dos herramientas más
utilizadas para diseñar algoritmos son el Pseudocódigo y el Diagrama de
flujo.
1. Pseudocódigo
Es un
lenguaje simplificado para describir un algoritmo utilizando una mezcla de
frases en lenguaje común, y palabras claves que indican el inicio y el fin del
algoritmo y las instrucciones específicas a realizar.
Por ejemplo,
el siguiente pseudocódigo corresponde al algoritmo para calcular el área del
rectángulo: el algoritmo calcula el área (a) de un rectángulo cualquiera, si se
le suministra la longitud de de la base (b) y la longitud de la altura (h).
Las palabras
subrayadas se llaman palabras reservadas, se deben utilizar sangrías que
facilitan la lectura del algoritmo Las instrucciones en pseudocódigo
son fáciles de codificar en un lenguaje de programación.
2. Diagrama de flujo
El diagrama
de flujo es la representación gráfica de un algoritmo; para ello se utiliza un
conjunto de símbolos estándares mundialmente utilizados y
desarrollados por organizaciones tales como ANSI (American National
Institute) e ISO (International Standard Organization para la
elaboración de diagramas de flujo;
En el
diagrama cada símbolo representa una acción en concreto; y cada
instrucción del algoritmo se visualiza dentro del símbolo adecuado. Los
símbolos se conectan con flechas para indicar el orden en que se ejecutan las
instrucciones.
Por ejemplo,
el siguiente diagrama de flujo corresponde al algoritmo para calcular el área
del rectángulo.
El ovalo
rotulado con la palabra Inicio indica el comienzo del algoritmo, el
paralelogramo es el símbolo de entrada de datos e indica que se lee el valor de
la base (b) y el valor de la altura (h), el rectángulo es el símbolo de proceso
e indica que se realiza un proceso sobre los datos de entrada para calcular el
área (a) multiplicando la base por la altura, (utilizaremos el * como operador
de multiplicación), el siguiente es el símbolo de salida y representa un
documento e indica que se muestra el valor del área obtenido, en cualquier
dispositivo de salida, finalmente el ovalo rotulado con la palabra Fin indica
que se ha llegado al fin del algoritmo.
Los símbolos
que se utilizaran para dibujar los diagramas de flujo son los
siguientes:
Reglas para
la construcción de diagramas de flujo
1. Todo
diagrama de flujo debe tener un inicio y un fin.
2. Las
líneas de flujo nunca deben cruzarse, para evitarlo deben utilizarse el símbolo
conector.
3. Las
líneas de flujo deben terminar siempre en un símbolo.
4. No
puede llegar más de una línea de flujo a un símbolo.
5. Todos
los símbolos en un diagrama deben estar conectados mediante una línea de flujo;
todo símbolo debe tener una línea de flujo entrando y otra saliendo salvo el
símbolo que indica inicio o fin del diagrama.
6. Como
regla general el flujo del proceso debe mostrarse de izquierda a derecha y de
arriba abajo.
Se
recomienda mantener uniforme el tamaño de los símbolos, por lo que el texto que
se escribe dentro no debe ser muy extenso, recuérdese que el propio símbolo
indica la operación a realizar. La forma en que se capturan los datos de
entrada o se muestran los datos de salida se detallarán al codificar el
algoritmo en el lenguaje de programación. Esto mismo se recomienda para la
representación del algoritmo en pseudocódigo.
DECLARACION DE LOS DATOS
Como ya se
dijo los datos a procesar y los datos resultantes del proceso se almacenan en
la memoria principal de la computadora, también conocida como memoria RAM (Random Access Memory),
y también se destinan localidades de memoria cuando se necesita almacenar
resultados de cálculos intermedios. Para poder localizar los datos en la
memoria se les asignan nombres; que en el ambiente de la programación
se conocen como identificadores de datos. Nombraremos los datos siguiendo las
reglas para definir identificadores especificadas en la mayoría de los
lenguajes de programación:
- Se utilizan secuencias de caracteres formadas por caracteres alfabéticos y los dígitos decimales.
- El primer elemento de la secuencia debe ser un carácter alfabético.
- No se utilizan signos de acentuación
- No se utilizan espacios, si se necesita separador debe utilizarse el carácter de subrayado (_) o guión bajo.
- No se permite el uso de las palabras reservadas o palabras claves
Por ejemplo:
1) Son identificadores
válidos los siguientes:
longitud,
altura, dato1, dato2, Coeficiente_a, numero_menor, EDAD
2) No son
identificadores válidos los siguientes:
ºC , porque
el carácter º no es un carácter permitido
1_dato,
porque comienza con un dígito
número
menor, porque tiene un espacio en blanco como separador
leer,
escribir e inicio, porque son palabras reservadas
INSTRUCCIONES
Un algoritmo
normalmente incluye una gran cantidad de instrucciones, también llamadas
sentencias; inicialmente se presentan las instrucciones de asignación, lectura y escritura;
definiendo cada una de ellas y mostrando su representación en pseudocódigo, su
correspondiente símbolo en el diagrama de flujo y ejemplos.
Instrucción
de asignación
Esta
instrucción asigna valor a un identificador, cuando se ejecuta una instrucción
de asignación se almacena el valor asignado en la localidad de memoria
reservada para el identificador, este identificador también se conoce con el
nombre de variable y se caracteriza porque puede tomar diferentes valores durante
la ejecución del algoritmo.
El formato
de la instrucción de asignación es el siguiente:
Donde
variable es un identificador válido y expresión puede estar formada
por un valor, por un conjunto de valores y operadores o por una función En el
espacio de memoria asignado a la variable se almacena el valor resultante de la
expresión.
Una
asignación tiene tres partes, la variable, el signo de asignación = y la
expresión cuyo valor se asigna a la variable. La variable siempre va a la
izquierda del símbolo =, mientras que la expresión siempre estará a la derecha.
Instrucción Leer
Se define la
instrucción Leer para indicar que se debe enviar información desde un
dispositivo de entrada de datos, como el teclado, hacia la memoria En la
memoria los datos serán ubicados a través de su nombre o identificador
asignado.
El formato
de esta instrucción es el siguiente:
Instrucción Escribir
Se define la
instrucción Escribir para indicar que se va a enviar información desde la
memoria hacia un dispositivo de salida de datos, como la impresora o la
pantalla del monitor.
El formato
de esta instrucción es el siguiente:
Una
constante puede ser un número cualquiera o una secuencia de caracteres, por
ejemplo, el numero 15 o la secuencia "Error". Si la constante es una
secuencia de caracteres se escribirá entre apóstrofos, para indicar que lo que
se escribe es la secuencia. Por ejemplo
Escribir
"Error"
Escribir
3.1416
Generalmente
dentro del símbolo solo se podrán escribir listas cortas, dado que el espacio
es limitado y el tamaño de los símbolos en un diagrama de flujo debe ser
uniforme; para solventar este inconveniente deben utilizarse varios símbolos de
salida. En el caso de fórmulas muy largas, se puede hacer referencia a su número
dentro del símbolo.
METODOLOGIA A SEGUIR EN EL DISEÑO DE
ALGORITMOS
El procedimiento a
seguir para diseñar algoritmos se presenta a continuación:
Entender el
problema
Para
determinar la secuencia de instrucciones que deben constituir el algoritmo, es
importante entender el problema que se pretende resolver, para asegurarse que
entiende el problema el programador debe resolverlo con papel, lápiz grafito y
borrador procurando hacer varios ejercicios de aplicación, generalmente se
encuentran diferentes formas de resolver el problema, por lo que se debe
seleccionar la mejor alternativa de solución.
Declaración
de datos
Una vez
seleccionada la mejor alternativa debe hacerse la declaración de datos, para
ello los datos se clasificarán de la siguiente manera:
Datos de Entrada: Los datos que se suministran
Datos de Salida: los datos o resultados que se
esperan
Datos de trabajo: estos son posiciones de memoria
donde se almacenarán resultados de cálculos intermedios, necesarios para
obtener los datos de salida
Se debe
asignar nombre a los datos de acuerdo a las reglas para formar identificadores.
Al hacer la declaración de los datos también debe especificarse el tipo de dato
que va a almacenarse en la posición de memoria especificada, los tipos de
datos son: numérico, un carácter, una cadena de caracteres o un valor
lógico (verdadero o falso)
Especificar las formulas a utilizar
Las fórmulas
deben escribirse utilizando los nombres asignados a los datos.
Diseño del algoritmo.
Se debe
representar la alternativa de solución seleccionada mediante un algoritmo, el
cual puede desarrollarse utilizando el pseudocódigo o el diagrama de flujo a
preferencia del programador; luego se verifica si el algoritmo cumple con las
características de un algoritmo. Esta verificación se conoce como prueba de
escritorio.
Prueba de
escritorio:
Se debe ejecutar el algoritmo con diferentes datos de entrada para
verificar si se obtienen los datos de salida esperados, en caso contrario se
procede a hacer las modificaciones necesarias al algoritmo. Se recomienda
verificar los resultados obtenidos en los ejercicios realizados en la etapa de
análisis del problema. Los datos de prueba deben escogerse de modo a someter al
algoritmo a todas las posibles situaciones que puedan darse.
El diseño
del algoritmo esta listo si la prueba de escritorio muestra que éste satisface
las características de un algoritmo; si la prueba no es satisfactoria se revisa
el pseudocódigo o el diagrama de flujo y se procede de esta manera hasta
obtener los resultados esperados. La siguientes etapas son la codificación del
algoritmo en el lenguaje de programación seleccionado y su prueba en
la computadora.
A
continuación utilizamos esta metodología en el diseño de un
algoritmo:
Problema 1:
Diseñar un algoritmo para convertir una temperatura dada en grados
Fahrenheit a la correspondiente temperatura en grados Centígrados.
Entender el
problema
El agua se
congela a 0º Centígrados y hierve a 100º Centígrados. El agua se
congela a 32º Fahrenheit y hierve a 212º Fahrenheit. Lo que indica una
diferencia de 180º. Por lo tanto cada grado en la escala Fahrenheit
es igual a 100/180 o 5/9 grados en la escala Celsius.
Para
convertir grados Fahrenheit a grados Celsius se resta 32º a los grados Fahrenheit
y el resultado se multiplica por 5/9
Se
selecciona esta alternativa de solución y se procede con el siguiente paso.
Declaración de los datos
Prueba de escritorio
En el primer
caso 98. 6º Fahrenheit equivalen a 37º Centígrados.
Cualquier
tarea que se pretenda resolver utilizando la computadora debe expresarse como
un algoritmo. Para diseñar algoritmos que sean entendibles y fáciles de
modificar por las personas interesadas, se utiliza un conjunto de estructuras o
construcciones lógicas restringidas, que son la secuencial, la de decisión y la
iterativa. La estructura secuencial se utiliza cuando las
instrucciones del algoritmo deben ejecutase en la secuencia en que se
presentan, de la primera a la última; La estructura de decisión se utiliza
cuando existen situaciones en que se debe escoger entre ejecutar una instrucción
u otra, dependiendo del cumplimiento de una condición y la estructura iterativa
se utiliza cuando es necesario repetir varias veces una instrucción o un
conjunto de instrucciones para que la tarea sea ejecutada.
En la
siguiente sección se estudiarán cada una de estas construcciones lógicas,
también conocidas como estructuras básicas de control lógico
ESTRUCTURA SECUENCIAL
Se trata de
la construcción donde las instrucciones se deben ejecutar una después de la otra,
en el mismo orden en que aparecen en el algoritmo, sin dejar de ejecutar
ninguna de ellas.
Problema 2:
Diseñe un algoritmo para calcular el área de un círculo cualquiera y la
longitud de su circunferencia.
Entender el problema
Ejercicio 1:
Consideremos un círculo de 6 centímetros de radio
Área del
circulo = 3.1416 * 6*6= 113.0976
Longitud de
la circunferencia = 2*3.1415 * 6 = 37.6992
Declaración
de los datos:
Dato de
entrada r: radio del círculo, numérico
Datos de
salida a: área del círculo, numérico
l: Longitud
de la circunferencia, numérico
Prueba de escritorio
ESTRUCTURA DE DECISIÓN
Es una
situación típica en la resolución de problemas, que se tenga que decidir entre
realizar una instrucción u otra dependiendo del cumplimiento de una condición;
por ejemplo: Para calcular c=b/a primero hay que verificar que a sea
diferente de cero, ya que la operación se puede realizar únicamente si a es
diferente de cero Para representar esta situación en el algoritmo se utiliza la
estructura condicional también conocida como estructura de decisión. Esta
estructura se construye de modo a que se ejecuten o se omitan algunas
instrucciones dependiendo del cumplimiento de una condición; el resultado de
evaluar la condición puede tomar un valor lógico verdadero o falso (V ó F).
La condición
puede ser una expresión relacional (por ejemplo a>o) o una expresión lógica
(por ejemplo a>b y b>c), que se construyen utilizando operadores
relacionales (>, <, =, =, =, ?) y operadores lógicos (y, o, negación)
Existen tres
tipos de decisión: decisión simple, la decisión doble y la decisión múltiple
Decisión simple
Una decisión
es simple, cuando sólo se tiene un curso de acción para el caso que el
resultado de evaluar la condición sea verdadero; es decir que si la condición
es verdadera se debe de ejecutar la instrucción o el conjunto de instrucciones
que se indique, y si la condición es falsa se omite la ejecución de dicha
instrucción o conjunto de instrucciones.
El formato
general de esta estructura es la siguiente:
Ejemplo:
Observe el siguiente segmento de pseudocódigo y su diagrama de flujo
Problema 1.
Dado el precio de un artículo y la cantidad de artículos comprados, calcular el
total a pagar, considerando que para compras superiores a 500
lempiras se dará un descuento del 10% y que el comprador debe pagar el 12% por
concepto de impuesto sobre ventas (ISV)
Entender el
problema
Ejercicio 1:
Se compra una docena de camisas a 130 lempiras cada una.
El valor de
la compra es 12 *130=1560, como la compra es superior a 500 lempiras, tiene
derecho al descuento. El 10% es igual a 1560*0.10= 156 lempiras, el valor de la
compra queda en 1560-156=1404 lempiras. El impuesto sobre ventas es igual a
1404*0.12=168.48 y por tanto el total a pagar es igual a 1404+168.48=1572.48
Ejercicio 2:
Suponga que se compran 3 camisetas a 100 lempiras cada una.
El valor de
la compra es 3*100=300 lempiras, como la compra es inferior a 500 lempiras no
se tiene derecho al descuento, el impuesto a pagar es de 36 lempiras y el total
a pagar es 336 lempiras.
Prueba de escritorio
Decisión doble
Una decisión
es doble cuando se tiene un curso de acción para el caso que el resultado de
evaluar la condición sea verdadero y otro para cuando sea falso.
El formato
general de esta estructura es la siguiente:
Ejemplo:
Observe el siguiente segmento de pseudocódigo:
El diagrama
correspondiente al ejemplo anterior es el siguiente:
Entender el
problema
Declaración de los datos:
Datos de entrada x1, y1, x2 y y2 las coordenadas de los dos
puntos, numéricos
Datos de salida m la pendiente, numérica
b el intercepto con el eje , numérico y ó
msg: "Pendiente no definida", secuencia de
caracteres:
Prueba de escritorio
No hay comentarios.:
Publicar un comentario