¿Qué es un Algoritmo?

Los algoritmos están en la base, y son uno de los conceptos más importantes, de la computación. Un algoritmo es una solución por pasos a un problema de cómputo. Éstos pasos individuales pueden ser repetidos una y otra vez, pero no deben ser ambigüos y, eventualmente, tienen que terminar. Una analogía muy usada para dejar claro qué es un algoritmo, son las recetas de cocina. Éstas incluyen una serie de pasos a realizar en los que el orden es importante y que eventualmente terminan. Por ejemplo, para cocinar huevos con jamón, una receta típica diría:

Paso 1) Pique y fría en mantequilla el jamón hasta que adquiera
        un tono dorado
Paso 2) Agregue uno por uno los huevos y revuelva hasta obtener
        una mezcla homogénea 
Paso 3) Añada una pizca de sal.
Paso 4) Revuelva de vez en cuando hasta que la mezcla esté bien 
        cocida
Paso 5) Sirva con pan tostado.

La tarea es cocinar huevos revueltos, pero ésta ha sido dividida en pasos más pequeños en los cuales el orden es importante. Por ejemplo, vamos a suponer que la cocinera no realiza los pasos en el órden 1) 2) 3) 4) 5), sino en ésta variante: 1), 3), 4), 2), 5). Todos los pasos se ha realizado, pero en éste caso desafortunado, en vez de tener el desayuno servido, tendremos pedazos salados de jamón revueltos con huevos crudos. Éstas instrucciones presentan ambigüedades, por lo cual no se pueden considerar propiamente un algoritmo: hay personas para las que "una pizca de sal" es una cucharada cafetera, y "un tono dorado" puede significar "fría los jamones hasta que se deshidraten tanto que queden crujientes". Desde luego, cualquier cocinera buena evitaría hacer semejantes desastres, pero no debemos confiar mucho en que las cocineras harán un buen desayuno a base de una mala receta, de la misma manera en que no debemos confiar mucho en que el poder ciego de las computadoras va a ejecutar un buen programa a base de un mal algoritmo.
LLevando más lejos incluso la comparación, podemos decir que escribir programas de computación es bastante parecido, al menos conceptualmente, a escribir recetas de cocina. Una receta inicia con una lista de ingredientes y continúa con las instrucciones necesarias para elaborar el platillo. Un programa de cómputo inicia con una declaración de variables que hacen las veces de ingredientes y continúa con instrucciones en las que éstos datos se manipulan para dar un resultado.
Los algoritmos son el grial de la computación. Su importancia se resume en ésta frase, tomada del libro Introducción al diseño y análisis de algoritmos, Un enfoque estratégico, de Lee, Tseng, Chang y Tsai:

"Si usted es rico, y no conoce mucho sobre algoritmos, tal vez no esté preparado para competir con alguien pobre que sepa mucho de algoritmos"

La frase apunta a un hecho bastante común: suele pensarse que para obtener grandes velocidades de cómputo, basta un procesador que realice una gran cantidad de ciclos de instrucción por segundo. Desde luego ésto no es cierto. Se estudian algoritmos para resolver problemas de cómputo de manera eficiente, aún cuando se disponga de los mejores procesadores. Tampoco es cierto que el estudio de los algoritmos haya surgido con la cibernética. Por poner un ejemplo, La Criba de Eratóstenes, un algoritmo para encontrar números primos, fue desarrollado hace 2300 años. Y, finalmente, los algoritmos constituyen la base de la computación no solamente en el software, sino en el hardware. Las operaciones aritméticas llevadas a cabo por la Unidad Aritmética, están basadas en algoritmos, y se ha construído un hardware optimizado cuando se han descubierto algoritmos más eficientes para realizar operaciones aritméticas a nivel de bits.
En las siguientes entradas veremos un par de métodos que los estudiosos de la computación usan para representar algorimos: El Seudocódigo y Los Diagramas de Flujo.
_________________________________________________________________________________________
_________________________________________________________________________________________
Esta entrada forma parte del Curso de C con Programas Explicados Línea por Línea
Índice
Anterior
Siguiente

Las virtudes del programador, según Larry Wall

Larry Wall es el creador del lenguaje de programación Perl y en alguno de sus libros publicó las que para él son tres virtudes básicas del programador. Supongo que estas características son necesarias y útiles no sólo en programación, sino en cualquier actividad. "hibris" es una palabra griega antigua que significa orgullo y confianza excesiva en uno mismo:

1 Pereza - Es la cualidad que te hace realizar un gran esfuerzo para reducir el total del gasto energético. Te hace escribir programas que ahorren trabajo y que otras personas encuentren útil, y documentar lo que escribes para no tener que responder muchas preguntas sobre él. Por lo tanto, la primera gran virtud de un programador. Y también por lo tanto, este libro. Ver también impaciencia e hibris.
2 Impaciencia - La ira que se siente cuando el ordenador se está volviendo perezoso. Esto te hace escribir programas que no solo reaccionan a tus necesidades, sino que se anticipen a ellas. O al menos lo pretendan. Por lo tanto, la segunda virtud de un programador. Ver también pereza e hibris.
3 Hibris - Orgullo excesivo, la suerte de cosas que Zeus te arrebata. También la cualidad que te hace escribir (y mantener) programas de los cuales otras personas no puedan decir cosas malas. Por lo tanto, la tercera virtud de un programador. Ver también pereza e impaciencia.

Unos programas básicos escritos en Perl, explicados paso a paso, se encuentran en Mi Otro Blog

¿Qué es la memoria RAM?

De los dispositivos de almacenamiento de información, la memoria RAM es la más importante para la ejecución de un programa. Una memoria consta de un número (generalmente) muy grande de localidades y un nombre para cada una de ellas. La memoria RAM es la unidad de almacenamiento en la que se guardan los datos y las instrucciones que lleva a cabo la Unidad de Proceso (PU). Sea por ejemplo la operación aritmética

7 + 3 = 10

A la hora de ejecutar el programa, esos datos, los sumandos y la suma, necesitan ser almacenados. Vamos a considerar una memoria RAM en miniatura como la que se presenta en la siguiente figura:

Ésta memoria tiene 12 localidades, cada una de las cuales ha sido etiquetada con un nombre del 0 al 11. En cada una de esas celdas es posible almacenar información. Esta disposición recuerda un conjunto de lockers como los que están disponibles en muchas universidades para guardar útiles. En los espacios de memoria, en vez de tener libros, tenemos tipos de datos. ¿Cuántos bits hay en cada una de las celdas? La gran mayoría de las computadoras tienen unidades independientes de memoria (llamadas espacio de direccionamiento) de 8 bits. Cada grupo de 8 bits recibe el nombre de byte. Las computadoras son direccionables por bytes porque en 8 bits caben todos los caracteres del teclado en código ASCII. Recuerde que los caracteres del código ASCII van del 00 al 255, exactamente los 256 números que se pueden almacenar en 8 bits. Dado que lo menos que tiene que hacer una computadora personal es recibir instrucciones del teclado, ese es el tamaño mínimo direccionable necesario. Una memoria RAM de 2 GB contiene 2000 000 000 de bytes o 16 000 000 000 de bits. Modernamente, para realizar cálculos numéricos, se han creado memorias direccionables por 64 bits.
Nuestra memoria de juguete puede ser direccionable hasta por 4 bits, aunque eso no es importante. Estamos considerando que el número 7 fue almacenado en el espacio 1; el número 3, en el 4. Para acceder a las localidades de memoria, es necesario guardar en el Registro de Dirección de Memoria (MAR) la dirección de la localidad a la cual se va a tener acceso; el resultado de la lectura de dicha localidad se almacena en el Registro de Datos de Memoria (MDR). La PU realiza la operación y guarda el resultado (10) en la dirección de memoria marcada con el número 10. Como puede verse de esta explicación, el tiempo de acceso a los datos almacenados repercute en el tiempo de ejecución del programa. Imaginemos que se tiene que recorrer una por una las direcciones de memoria antes de obtener la necesaria (este tipo de búsqueda es llamada acceso secuencial). En una memoria con miles de millones de espacios de direccionamiento, esto no es eficiente. En lugar de eso, sólo se busca la dirección almacenada en la MAR, este tipo de búsqueda es conocida como acceso aleatorio. De aquí viene el nombre RAM (Random Acces Memory, o memoria de acceso aleatorio).

La RAM tiene estas características:
1) Es volátil. Lo cual significa que la información almacenada estará disponible sólo mientras la computadora está encendida. La vida de las variables de un programa es incluso menor que eso. Duran sólo lo que dura el tiempo de ejecución. Incluso en el lapso de dicha ejecución, una dirección de memoria, identificada con un nombre y tipo de variable, puede cambiar el contenido almacenado, de la misma manera que en el caso de los lockers, con el tiempo cambia el material guardado, aunque la ubicación del locker siga siendo la misma.
2) Es de fácil acceso. Ésto quiere decir que para el procesador es fácil (rápido) extraer y almacenar información en ella, comparado con el acceso y escritura en los dispositivos de almacenamiento como los discos duros.
3) Es imprescindible. No puede echarse a andar una computadora sin memoria RAM.

Cada lenguaje de programación define el tamaño para los tipos de datos enteros y flotantes. Dependiendo del tipo, se reservan una o más localidades de memoria para almacenar datos. Un arreglo es un conjunto contiguo de espacios de direccionamiento. Las variables tipo puntero no guardan números sino direcciones. Una máquina con poca memoria RAM será necesariamente más lenta que otra con mucha; incluso, como en nuestro caso hipotético, podría no poder realizar ciertas operaciones (como sumar números que excedan el almacenamiento de la memoria), sin embargo, ya que, al final de cuentas, lo que hacen es ejecutar programas, si se les da tiempo y memoria, todas las computadoras pueden hacer las mismas cosas.

Kernighan_Ritchie_2.10 (Convertir un texto a minúsculas)

___________________________________________________________________________________
2.10 Reescriba la función lower, que convierte letras mayúsculas en minúsculas, con una expresión condicional en vez de un if-else.
___________________________________________________________________________________
SOLUCIÓN: La modificación es directa. El programa está escrito de tal manera que se puede recibir como entrada un archivo de texto y convertirlo a minúsculas. La razón por la que éste programa sólo funciona con el código ASCII, es porque la línea principal de la función lower es la siguiente:

x = (c >= 'A' && c <= 'Z')? c + 'a' - 'A': c;

básicamente hace uso del hecho que en ASCII, las letras mayúsculas aparecen antes que las minúsculas, y la distancia entre una mayúscula y su correspondiente minúscula es de 32 posiciones. Así, el valor de A es 65, y el de a es 97; el de S es 83, y el de s 115. Por tal motivo, en la instrucción de asignación, primero se verifica que el carácter sea mayúscula, si lo es, entonces se cambia a el correspondiente valor más 32 ( escrito como c + 'a' -'A'), de lo contrario, se deja igual.

#include <stdio.h>

int lower(int s);


////////////////////////////////////////////////
// MAIN
////////////////////////////////////////////////

int main()
{ /*Abre main*/
int z, l;

printf("\nPor favor, introduzca un texto. ");
printf("Se imprimira en minusculas.\n");

while( (z = getchar()) != EOF)
{ /* Abre while */  
l = lower(z);
putchar(l);
}/*Cierra while */

return 0;
} /*Cierra main*/

/*//////////////////////////////////////////////
// LOWER
//////////////////////////////////////////////*/

int lower(int c)
{  /*Abre lower*/
int x;

x = (c >= 'A' && c <= 'Z')? c + 'a' - 'A': c;

return x;
}  /*Cierra lower*/

La ejecución con éste texto como entrada

ERASE UN HOMBRE A UNA NARIZ PEGADO,
ERASE UNA NARIZ SUPERLATIVA
UNASE UNA NARIZ ZAYON Y ESCRIBA,
ERASE UN PEJE ESPADA MUY BARBADO.

produce:

Por favor, introduzca un texto. Se imprimira en minusculas.

erase un hombre a una nariz pegado,
erase una nariz superlativa
unase una nariz zayon y escriba,
erase un peje espada muy barbado.

Kernighan_Ritchie_2.5 (Primera posición de la coincidencia de dos cadenas)

___________________________________________________________________________________
2.5 Escriba la función any(s1,s2), que regresa la primera posición de la cadena s1 en donde se encuentre cualquier carácter de la cadena s2, o -1 si s1 no contiene caracteres de s2. (La función de biblioteca estándar strpbrk hace el mismo trabajo pero regresa un apuntador a la posición encontrada).
___________________________________________________________________________________
Solución: El código siguiente presenta la solución del problema. Se ha puesto un par de cadenas, las cuales se pueden cambiar. Lo importante es la función any. La ejecución del programa, tal como está, produce -1 como salida, ya que la cadena "xxz" no tiene ningún elemento en común con "La felicidad esta en lugares mas o menos lejanos".

#include<stdio.h>
enum {TAMANO1 = 100, TAMANO2 = 50};

int any(char s1[], int n, char s2[], int m);
void Imprimir( char cadena[]);

/*//////////////////////////////////
// MAIN
//////////////////////////////////*/

int main()
{ /* Abre main */
int y;

char cadena1[TAMANO1] = "La felicidad esta en lugares mas o menos lejanos";
char cadena2[TAMANO2] = "xxz";
/*La cadena1 */
Imprimir(cadena1);
printf("\n");
/*La cadena 2*/
Imprimir(cadena2);
printf("\n");

y = any(cadena1, TAMANO1, cadena2, TAMANO2);

if (TAMANO1 != y)
printf("\n%d\n", y);
else 
printf("-1\n");
return;
} /* Cierra main*/

/*//////////////////////////////////
// ANY
//////////////////////////////////*/

int any(char s1[], int n, char s2[], int m)

{ /* Abre any*/
int i, j, x = TAMANO1; 

for (i = 0; s2[i] !=  '\0'; i++)   
for (j = 0; s1[j] !=  '\0'; j++)
{ /*Abre for*/
if (s1[j] == s2[i])
{ /* Abre if */
x = (j < x)?  j:x;
break; /*Salimos del for anidado*/
} /* Cierra if*/
} /* Cierra for*/

return x;
} /* Cierra any*/


/*///////////////////////////////////
// IMPRIMIR
///////////////////////////////////*/

void Imprimir(char cadena[])

{ /*  Abre Imprimir */
int i = 0; 
for (i = 0; cadena[i] != '\0'; i++)
putchar(cadena[i]); 

return;
} /* Abre Imprimir */

La ejecución de éste programa es la siguiente:

Cadena 1:
La felicidad esta en lugares mas o menos lejanos
Cadena 2:
xxz
-1

__________________________________________________________________________________________
Esta entrada es parte de los problemas resueltos del libro El Lenguaje de Programación C de B. Kernighan y D. Ritchie
Entrada anterior
Entrada siguiente
__________________________________________________________________________________________

Kernighan_Ritchie_2.4 (Suprimir las coincidencias de dos cadenas)

___________________________________________________________________________________
2.4 Escriba una versión alterna de squeeze(s1,s2) que borre cada carácter de s1 que coincida con cualquier carácter de la cadena s2.
___________________________________________________________________________________
Solución:
La función squeeze a la que hace referencia el enunciado aparece en el texto y es la siguiente:

void squeeze(char s[], int c)
{
int i, j;

for(i = j = 0; s[i] != '\0'; i++)
   if (s[i] != c)
      s[j++] = s[i];

s[j] = '\0';
}

Esta función comprime la cadena s1 por medio de eliminar la variable c. La variable i recorre el arreglo que contiene s1 y la variable j recorre el mismo arreglo siempre que la variable leída no coincida con c. Al final, para indicar que la cadena ha terminado, se escribe explícitamente el carácter de terminación de cadena '\0'.
A continuación presento mi versión de ésta problema tal como lo pide el libro. He puesto un par de cadenas, la primera que dice: "La felicidad esta en lugares mas o menos lejanos, como Londres" y la segunda: "Hola". Lo que hace el programa, y concretamente la función squeeze, es recibir las dos cadenas (supone que la primera es mayor que la segunda) y recorrer todo el primer arreglo (el mayor) desde el elemento 0 hasta el último en busca de coincidencias. Al mismo tiempo va sustituyendo las variables encontradas en el mismo arreglo, sólo si no coinciden con alguna de las entradas de la segunda cadena. Para esto, se recorren también todos los elementos del segundo arreglo hasta encontrar el elemento terminal '\0'.

/*************************************************************************
*                                                                        *
* Este programa tiene como datos un par de cadenas: cadena y cadena2     *
* Suprime todas las coincidencias de cadena2 en cadena e imprime cadena  *
*                                                                        *
**************************************************************************/
#include<stdio.h>
#define TAMANO 100

void squeeze( char s[], char t[],  int c);
void Imprime(char cl[], int n);

/*//////////////////////////////////////
// MAIN
//////////////////////////////////////*/ 

int main()
{  /* Abre main */

char cadena[TAMANO] = "La felicidad esta en lugares mas o menos lejanos," " como Londres";
char cadena2[TAMANO] = "Hola";
/*Las cadenas se pueden concatenar en tiempo de complilacion*/

/*cadena antes de llamar a la funcion squeeze*/
printf("\nCadena 1: \n");
Imprime(cadena, TAMANO);
printf("\nCadena 2:\n");
Imprime(cadena2, TAMANO);

printf("\n");

squeeze (cadena, cadena2, TAMANO);
 
/* Cadena despues de llamar a la funcion squeeze */ 
Imprime(cadena, TAMANO);

printf("\n");

return 0; 
}  /* Cierra main */

/*/////////////////////////////////////
// SQUEEZE
/////////////////////////////////////*/

void squeeze( char s[], char f[], int c)
{  /* Abre squeeze */
int i, j, k;

for (k = 0; k < c; k++) 
{ /*Abre for*/
for (i = j = 0; s[i] != '\0'; i++)
if ( s[i] != f[k]) 
s[j++] = s[i];

s[j] = '\0';
} /*Cierra for*/
}  /* Cierra squeeze*/

/*//////////////////////////////////////
//  IMPRIME
//////////////////////////////////////*/

void Imprime(char cl[], int n)
{  /* Abre Imprime */
for (n = 0; cl[n] != '\0'; n++ )
putchar(cl[n]);

}  /* Cierra Imprime */

La ejecución de éste programa produce la salida:

Cadena 1: 
La felicidad esta en lugares mas o menos lejanos, como Londres
Cadena 2:
Hola
L feicidd est en ugres ms  mens ejns, cm Lndres

que es, efectivamente, la cadena original sin los elementos de la segunda.

__________________________________________________________________________________________
Esta entrada es parte de los problemas resueltos del libro El Lenguaje de Programación C de B. Kernighan y D. Ritchie
Entrada Anterior
Entrada Siguiente
__________________________________________________________________________________________