Algoritmos

Por definición un algoritmo es la recopilación de los pasos lógicos ordenados para resolver un problema; es decir,un algoritmo enumera todo lo que tenemos que hacer cuando se nos presenta un problema a resolver.

Entonces vamos a plantear un problema; que aunque burdo; no sirve para ejemplificar y explicar lo que son los algoritmos. Ponerse un par de zapatos.

Desde un punto de vista sencillo, el ponerse un zapato no representa gran problema, solo tomas el zapato, te lo pones en un pie y lo anudas. Pero desde un punto de vista como informático debes pensar un poco mas a detalle. Esto implica mucho mas observaciones que solo tomarlo y ponerlo en un pie; es así como podemos plantear este algoritmo.

1. Elegir un par de zapatos.
1. Verificar que tenemos los dos zapatos del par
2. Escoger un par de calcetines acorde al color de los zapatos
3. Ponerse un calcetín en un pie
1. Tomar el calcetín por el extremo abierto
2. Verificar que el calcetín esta derecho; la parte del talo hacia abajo
3. Poner la punta del pie en la boca del calcetín
4. Deslizar el pie dentro
5. Acomodar las arrugas a lo largo del pie
4. Poner el otro calcetín en el otro pie
1. Tomar el calcetín por el extremo abierto
2. Verificar que el calcetín esta derecho; la parte del talo hacia abajo
3. Poner la punta del pie en la boca del calcetín
4. Deslizar el pie dentro
5. Acomodar las arrugas a lo largo del pie
5. Tomar un zapato
1. Verificar de que pie es el zapato
2. Verificar que las agujetas están desanudadas
1. Si están desanudadas soltarlas
3. Colocar el zapato en el pie correspondiente
4. Acomodarlo
5. Ajustar las agujetas
6. Anudar las agujetas
6. Tomar el otro zapato
1. Verificar de que pie es el zapato
2. Verificar que las agujetas están desanudadas
1. Si están desanudadas soltarlas
3. Colocar el zapato en el pie correspondiente
4. Acomodarlo
5. Ajustar las agujetas
6. Anudar las agujetas

Como informático es necesario analizar mas las cosas, solo en las caricaturas podemos ver a Dexter en su laboratorio ordenandole a su computadora a hacer cosas, realizar búsquedas y ver como esta lo hace como por arte de magia, sin pensar en lo que hay detrás. Esto son los algoritmos, cada programa son un conjunto de algoritmos, de hecho, al oprimir el botón de "negrilla" en el editor de texto este no es otra cosa que una rutina o algoritmo que obedece el programa para realizar una función. En google al ingresar un criterio de búsqueda y dar click en "buscar" esto desata otro algoritmo para realizar por el servidor. Es entonces que una computadora sin algoritmos no puede realizar nada, seria lo mas parecido a tener una licuadora descompuesta ya que una pc no puede moler una salsa.

Ahora bien los algoritmos responden a ciertas estructuras ya establecidas (Estructuras condicionales y repetitivas), pues estas nos van a permitir un análisis mas sencillo del problema o hacerlo mas preciso. Como ya mencione nosotros damos por hecho muchas cosas. En el ejemplo anterior solo mencionamos en escoger unos zapatos y unos calcetines; los pusimos en una forma lógica, primero los calcetines y después los zapatos, aunque podemos hacerlo al revés no seria correcto. Pero también podemos afinar mas nuestro algoritmo si incluimos una rutina para hacer que el color de los calcetines y el de los zapatos sea coherente. Hay que recordar que existen reglas de acerca de esto ya que unos zapatos negros con calcetines blancos no se ven bien, o que dentro de el cajón de los calcetines en probable encontrar calcetas deportivas, calcetines con rombos, de colores y que los zapatos deben combinar con el cinturón que utilicemos y el pantalón.

Esto lo detallare mas en la siguiente entrada.

Cálculos sencillos

No he tenido mucho tiempo de escribir estos días. Aquí dejo un código fuente para C++ para realizar unos cálculos sencillos. El objetivo no es hacer en si las operaciones; si no hacer uso de pre-incremento y post-incremento y el módulo resto. Por esto el método utilizado no es el mejor o el más óptimo.

//El programa se escribió con Geany sobre Linux Ubuntu 11.10
//sin tener errores

#include <stdio.h>
#include <math.h>
#include <iostream>  //En linux no existe iostream.h solo se declara como iostream
using namespace std;

int main()
{
    //Se muestra en pantalla a modo de encabezado
    printf("Universidad Nacional Autonoma de México \n");
    printf("Facultad de Contaduría y Admonistración \n");
    printf("Licenciatura en Informática \n");
       
    printf("Se calculará los pares ordenados \"X\", \"Y\" para la siguiente \n");
    printf("ecuación lineal: y=ax+b dado un rango dado\n");
    printf("y los coeficientes de la ecuación \n \n");
   
    float y, a, b, par;
    int x,yy;
   
    printf("Ingrese el valor de \"a\" \n");
    scanf("%f",&a);
    printf("Ingrese el valor de \"b\" \n");
    scanf("%f",&b);
    printf("Cuantos pares ordenados desea calcular? \n");
    scanf("%d",&x);
   
    int i=0;
   
    printf("   Tabla de valores   \n");
    printf("      X      Y    \n");
   
    do{
        y=(a*i)+b;
        yy=y;
        par = (yy % 2);                //modulo resto
        i++;                           //postincremento
        printf("      %d......%.2f",i,y);
        if (par == 0) printf("...Valor positivo \n");
        else printf("...Valor negativo \n");
    }while (i < x);
       
    int n, ii;
   
    printf("\n \n \aCalculo del factorial de un numero dado \n \n");
    printf("Ingrese un valor entero y positivo para calcular su favtorial \n");
    scanf("%d",&n);
   
    i=1;
    ii=1;
   
    do{
        ii*=i;                       //asignación con multiplicación
        ++i;                         //preincremento
    }while (i <= n);
   
    printf("\n \nEl factorial de %d es %d ",n,ii);
   
    return (0);
}

Diseño de algoritmos

Hoy voy a escribir de forma breve lo que es el diseño de algoritmos. Ya mas adelante extenderé cada parte del tema pues este tema da para mucho mas que una entrada de blog

Conceptos básicos

En principio describiremos de forma general las técnicas para resolver algoritmos, estas no son otra cosa que estrategias utilizadas en la resolución de problemas que, originalmente fueron planteadas por matemáticos para su propio campo, y como estos mismos investigadores fueron los pioneros de la computación junto con físicos, aplicaron los mimos criterios para resolver los algoritmos. Cabe mencionar que en su principio la computación fue enfocada a la resolución de problemas matemáticos orientados a asuntos bélicos como la balística y que después se implementó el uso de las máquinas a cuestiones financieras; mismas que convergían en la solución de números.

Estas técnicas fueron nombradas de acuerdo al procedimiento que seguían, y las principlaes son:

• Algoritmos voraces
• Divide y vencerás
• Programación dinámica
• Vuelta atrás
• Ramificación y poda

Niveles de abstracción para la construcción de algoritmos.

La construcción de algoritmos necesita de tres niveles de abstracción; es decir; son tres los pasos necesarios para su construcción. Estos son:

1. Análisis
2. Diseño
3. Implementación

Análisis

Consiste en la recopilación de toda la información necesaria para el algoritmo, variables que lo rodean, el proceso que le demos a estas, y la salida que queremos encontrar.

Es aquí donde los procesos pueden identificarse como operaciones que se aplican a las variables del problema. Y se perfila el resultado deseado.

Diseño

Para esta etapa ya se tiene identificados y delimitado el problema, se conoce las variables involucradas y se sabe el los valores de salida deseados; no resueltas sino más bien que debemos esperar de estas; con lo cual se comienza a perfilar la solución mediante el planteamiento de la hipótesis, se modela el algoritmo mediante la aplicación de estructuras definidas para los algoritmos y se comienza hacer pruebas de su uso mediante las “pruebas de escritorio”

Implementación

En este paso ya se comienza la programación en un lenguaje adecuado al algoritmo basados en la solución que se tiene modelada.

Estructuras básicas de un algoritmo

En la implementación de algoritmos se puede observar la presencia de comportamientos clásicos y que están definidos a través de modelos previamente definidos.

Las estructuras típicas que podemos definir son:

• Ciclos
• Contadores
• Acumuladores
• Condicionales
• Interruptores

Ciclos

Estas estructuras hacen que el algoritmo se repita de forma iterativa en función de una condición cumplida en un momento determinado.

Existen dos tipos de ciclos. Los que se ejecutan “mientras que” y los que se ejecutan “hasta que”

Mientras que:

Este realiza la verificación de la condición antes de ejecutar una instrucción, así es que, si se cumple la condición puede realizar su función de otro modo salta a otro paso. Al terminar el proceso vuelve hacer la verificación.

Hasta que

Este ciclo realiza su propio proceso y después hace la verificación de la condición para que este se ejecute y esta le dice si debe volver a realizar el proceso o seguir con el algoritmo.

Ambas iteraciones tienen en común que se debe cumplir cierta condición para realizar su proceso.

Contadores

Esta estructura también realiza iteraciones de las instrucciones por un momento conocido. Esta estructura sufre incrementos o decrementos del valor asignado a ella y se ejecutará mientras no se cumpla su condición.

Acumuladores

Estos guardan valores crecientes o decrecientes a lo largo de la ejecución del algoritmo. Esto debido a que los primeros y últimos valores así como los intermedios son relevantes para la solución o forman parte de ella.

Condicionales

Esta estructura tiene como fin que se realice o no cierta parte del código de acuerdo a una condición definida. Esto lo hace si se cumple una condición se ejecuta una parte del código si no se ejecuta otra.

Interruptores

Estas estructuras disparan un código o parte de uno si se cumple una condición o evento sin hacer incrementos o decrementos, solo si se cumple o sucede una condición.

Estrategias de diseño de algoritmos

Toda modelación de un algoritmo debe caer o se debe diseñar por una de estas estrategias para la resolución de un problema.

Algoritmos voraces

Estos se utilizan para la solución de problemas de optimización, son sencillos de programar y pueden encontrar una solución en un tiempo corto.

Divide y vencerás

Toma el problema y lo divide en partes más pequeñas y por ende más sencillas del mismo. La solución la encuentra haciendo una sumatoria do todas estas partes pequeñas.

Programación dinámica

Defina sub-problemas superpuestos y sub-estructuras optimas, buscan soluciones óptimas del problema en su conjunto.

Vuelta atrás

Toma un valor del conjunto de posibles soluciones posibles al problema y lo evalúa para ver si es la solución deseada. Si se comprueba que este valor no es el mejor regresa al punto donde tomo la variable para evaluarla y elige el valor siguiente, Esto lo realizará hasta que encuentra un valor satisfactorio.

Ramificación y poda

Su estrategia es muy similar a vuelta atrás, solo que se diferencia en que puede ejecutar un conjunto de posibles soluciones a la vez y no hacer esto de una en una. De este proceso puede discriminar a un conjunto de posibles soluciones y descartar (poda) los valores que no satisfacen al algoritmo. Realiza una segunda evaluación de los valores restantes y descarta los menos óptimos. El proceso se ejecuta hasta que se obtiene un valor que resuelva el problema y se pueda determinar a alguno como el más óptimo.