Juan Garcés

Personal Blog

Introducción a los Algoritmos

enero 7th, 2013




¿Qué es un Algoritmo?

Existen muchas y muy variadas definiciones de lo que es un algoritmo, dependiendo del autor podemos distinguir las siguientes:

  • Conjunto de reglas que permiten obtener un resultado determinado a partir de ciertas reglas definidas.
  • Conjunto de pasos que nos permite obtener un dato.
  • Algoritmo es una secuencia finita de instrucciones, cada una de las cuales tiene un significado preciso y puede ejecutarse con una cantidad finita de esfuerzo en un tiempo finito. Ha de tener las siguientes características: legible, correcto, modular, eficiente, estructurado, no ambiguo y a ser posible se ha de desarrollar en el menor tiempo posible.
  • Un algoritmo es el conjunto de operaciones y procedimientos que deben seguirse para resolver un problema.

A lo anterior debemos agregar que un algoritmo debe cumplir además con las siguientes características:

  • Finitud: el algoritmo debe acabar tras un número finito de pasos. Es más, es casi fundamental que sea en un número razonable de pasos.
  • Definibilidad: el algoritmo debe definirse de forma precisa para cada paso, es decir, hay que evitar toda ambigüedad al definir cada paso. Puesto que el lenguaje humano es impreciso, los algoritmos se expresan mediante un lenguaje formal, ya sea matemático o de programación para un computador.
  • Entrada: el algoritmo tendrá cero o más entradas, es decir, cantidades dadas antes de empezar el algoritmo. Estas cantidades pertenecen además a conjuntos especificados de objetos. Por ejemplo, pueden ser cadenas de caracteres, enteros, naturales, fraccionarios, etc. Se trata siempre de cantidades representativas del mundo real expresadas de tal forma que sean aptas para su interpretación por el computador.
  • Salida: el algoritmo tiene una o más salidas, en relación con las entradas.
  • Efectividad: se entiende por esto que una persona sea capaz de realizar el algoritmo de modo exacto y sin ayuda de una máquina en un lapso de tiempo finito.

Uno de los algoritmos más antiguos conocidos es el algoritmo de Euclides. El término algoritmo proviene del matemático Muhammad ibn Musa al-Khwarizmi, que vivió aproximadamente entre los años 780 y 850 d.C. en la actual nación Iraní. El describió la realización de operaciones elementales en el sistema de numeración decimal. De al-Khwarizmi se obtuvo la derivación algoritmo.

El Lenguaje Informático

    Ya vimos varias definiciones de un algoritmo, pero ahora debemos comprender un nuevo término y que es el de «Lenguaje Informático».

El lenguaje informático es aquel por medio del cual un algoritmo se codifica a un sistema comprensible por el ordenador o computadora. Este tipo de lenguaje es más cercano a la máquina que al ser humano y podemos distinguir distintos tipos dependiendo de la proximidad a la maquina. Se denomina lenguaje de alto nivel aquel que es más cercano a la comprensión humana y lenguaje de bajo nivel a aquellos que son más comprensibles por la máquina.

En concreto, nosotros vamos a estudiar un lenguaje en la frontera de uno de bajo nivel. Este lenguaje es el «C» y es por estar en la frontera que este lenguaje es tan potente y rápido, pues las funciones principales representan las funciones más básicas del ordenador

A menudo los algoritmos requieren una organización bastante compleja de los datos, y es por tanto necesario un estudio previo de las estructuras de datos fundamentales. Dichas estructuras pueden implementarse de diferentes maneras, y es más, existen algoritmos para implementar dichas estructuras. El uso de estructuras de datos adecuadas pueden hacer trivial el diseño de un algoritmo, o un algoritmo muy complejo puede usar estructuras de datos muy simples.

Realización de un Algoritmo

    Para la realización de un algoritmo es necesario realizar una secuencia de pasos para llegar a cumplir con la resolución de un problema dado. Para ello, definiremos los siguientes pasos:

  1. Análisis previo del Problema: Se debe realizar un análisis del funcionamiento del problema antes que se realice cualquier algoritmo. Esto es para poder obtener los requerimientos que deberá satisfacer el algoritmo luego de ser ejecutado.
  2. Definición de Requerimientos: Los problemas a solucionar, esto es, por ejemplo, el sumar dos números, multiplicar dos matrices, ordenar una lista de números, generar un reporte, etc.
  3. Identificación de los Módulos: La identificación de los módulos es tan importante como la identificación correcta de los requerimientos, esto porque la correcta identificación de los módulos simplifica considerablemente la realización de los algoritmos que darán solución a los requerimientos identificados en el paso anterior.

    Por ejemplo, si para lograr cumplir el requerimiento del cálculo de una cuota es necesario multiplicar dos cantidades y luego sumarlas, sería conveniente crear un módulo que permita multiplicar y otro que permita sumar y luego en otro módulo utilizar a estos dos y realizar el cálculo de la cuota. Con esto podemos darnos cuenta que es mucho más simple el realizar los módulos por separado que realizar todas las operaciones amontonadas. Además, el realizar módulos permite que más tarde podamos reutilizarlos en otras operaciones.

    Por otro lado, es importante mencionar que no se deben realizar módulos que sean tan simples que puedan ser reemplazados por una operación sencilla.

  4. Realización de los Algoritmos: A continuación corresponde realizar los algoritmos correspondientes para cada módulo identificado. Dicho algoritmo deberá cumplir con las características que se indicaron para posteriormente implementarse en un lenguaje de programación comprensible por una computadora.
  5. Implementación de los Algoritmos: La implementación de los algoritmos se debe realizar en un lenguaje de programación para que una computadora pueda comprender las instrucciones que el algoritmo modela para así poder ejecutarlas y lograr el resultado esperado.

En el último paso ya podemos hablar de una aplicación o programa de computadora, que estará compuesto por una serie de instrucciones que ordenadas una tras otra logran representar los algoritmos diseñados y dar así solución a los requerimientos identificados.

Representación de un Algoritmo

    La principal forma de representación de un algoritmo es la utilización de los denominados «Diagramas de Flujo».

    Los diagramas de flujo, como su nombre lo indica, son gráficas que representan la dirección que sigue la información que contiene un algoritmo; los datos se encierran en diferentes figuras, estas se llaman figuras lógicas. Existen siete figuras lógicas utilizadas en el diagrama de flujo: Inicio, Lectura/Escritura, Flujo, Proceso, Decisión, Ciclo y Fin.



Ejemplo:

    Aquí podemos apreciar cómo se relacionan los elementos anteriores entre sí:


    Esta es una de las tantas formas de representación de un algoritmo. También podemos representarlo en forma de líneas de texto estructurado u otra.

 

Concluyendo

El algoritmo es de carácter general y puede aplicarse a cualquier operación matemática o a cualquier problema.

La formulación de algoritmos fue uno de los más grandes adelantos dentro de la ciencia matemática ya que a partir de ellos se pudieron resolver infinidad de problemas.

Los algoritmos, para llegar a ser tales deben reunir ciertas características. Una de ellas es que los pasos que deben seguirse deben estar estrictamente descritos, cada acción debe ser precisa, y debe ser general, es decir, que pueda ser aplicable a todos los elementos de una misma clase.

    La representación gráfica de un algoritmo permite un mayor entendimiento de éste y da una mayor claridad al momento de realizar un seguimiento de éste.

    La implementación es el fin último del algoritmo y mediante esta implementación puede ser puesto en práctica en una computadora.

Algoritmos y Programas

    El computador debe estar al servicio de resolver problemas. Éste es una máquina que no funciona sin un grupo de instrucciones que le indiquen qué hacer.

    Para comunicarnos o darle instrucciones a un computador debemos aprender un lenguaje común para ambos (Lenguaje de Programación). Este lenguaje de programación debe contener un grupo de símbolos que la máquina comprende y que ayuda a la ejecución de las instrucciones que queremos.

    A medida que pasa el tiempo, los lenguajes de programación han ido evolucionando para parecerse más a nuestro idioma.

    En la actualidad existen en el mercado una serie de lenguajes de programación, unos más evolucionados que otros, entre los cuales podemos mencionar: Pascal, C, Java, Visual Basic, Power Builder, etc. Para este curso utilizaremos el lenguaje C como lenguaje de trabajo.

    Como vimos en la parte introductoria, para poder construir un programa de computadora debemos diseñar previamente un algoritmo que lo modele.

    Todo algoritmo puede ser construido por medio de tres estructuras:

  1. Decisión
  2. Ciclo
  3. Proceso

Ejercicio

    Veamos ahora un ejemplo de diseño e implementación de un algoritmo. Consideremos el problema de resolver una serie como la de a continuación:


    Veamos ahora como construir un algoritmo que calcule el valor de S para valores dados de x e y.

Paso 1: Realizar el análisis previo. Se debe determinar el valor de la variable S a partir de los valores x e y ingresados. Estos valores deben ser leídos y procesados de acuerdo a la serie presentada para obtener el valor de ésta.

Paso 2: Requerimientos. El requerimiento principal es el determinar el valor de S y mostrarlo por pantalla.

Paso 3: Módulos a diseñar. El problema es sencillo y puede ser resuelto por medio de dos módulos, uno que realice la función exponencial y otro que desarrolle la serie haciendo la llamada respectiva al módulo anterior.

Paso 4: Realización de los Algoritmos. Al realizar los algoritmos debemos tener presentes las características que debe tener un algoritmo para poder llegar a una correcta implementación de éstos. Para ello utilizaremos los símbolos descritos y con ellos lograremos el algoritmo que a continuación se presenta.

 

Algoritmos Solución:


     Podemos apreciar cómo nuestro algoritmo A requiere del algoritmo B para poder realizar la operación exponencial que hemos separado en otro módulo que más tarde podremos reutilizar en algún otro algoritmo que necesitemos realizar.

Ahora sólo nos queda el último paso, la implementación de los algoritmos anteriores en un lenguaje de programación, que cómo dijimos anteriormente será el lenguaje C.

Paso 5:



Finalmente, veamos cómo se ve todo el código anterior escrito en lenguaje C completo.

    La sentencia del comienzo «#include <stdio.h>» nos permite utilizar las funciones comunes que incluye el lenguaje C como son scanf que permite leer un valor desde el teclado y la printf que permite mostrar por pantalla el valor de una variable.

Comments

One Coment

RSS

Juan Garcés

Personal Blog