La forma en que los algoritmos cambiaron al mundo…

Vi esta imagen de CollegeDegreeSearch.net hace rato y creo que a todos los programadores les puede interesar, así que se los comparto.  ¡Disfruten!


An infographic by the team at College Degree Search

Los errores de Programación

Ante la furor que han causado los memes entre mis alumnos, estuve pensando en la forma de representar algo sencillo por medio de memes.  Una de las primeras cosas que comparto con los que están aprendiendo a programar son los tipos de errores que pueden cometer (para que se cuiden) y es un tema simple que creo que puede ser representado bien con memes porque permite asociar las reacciones que tendría un programador ante cada tipo de error.

Aquí se los comparto. Espero que les sea útil o por lo menos los haga sonreír .

El algoritmo: ¿de qué se trata esta onda?

Seguramente has escuchado hablar de la palabra algoritmo, pero realmente ¿qué es?  O mejor dicho, ¿de qué se trata?  Y una vez que sabes que rollo, ¿cómo lo ejecuta la computadora?  Ante esta incógnita, voy a hablar un poco (o mejor dicho, escribir un poco) acerca de los secretos recónditos de un algoritmo.

La Real Academia de la Lengua (o RAE para los cuates), nos dice que un algoritmo es “Conjunto ordenado y finito de operaciones que permite hallar la solución de un problema”.  Con esto creo que queda muy claro de qué trata el rollo.

Sin embargo, ¿qué chiste tiene escribir aquí lo que dice la RAE?  Voy a adentrarme un poco a las raíces para remontarnos en la historia chirolira acerca del origen de la palabra algoritmo.  Esta palabra viene del apodo de Mohammed Ibn Musa Abu Djefar, mejor conocido como Al-Khwarismi (en español: Aljuarismi), un sabio musulmán que escribió más o menos alrededor del año 830 un libro sobre las matemáticas, concretamente sobre el álgebra.

Como ya se definió antes, un algoritmo consta de los pasos para resolver algún problema, algo así como una receta de cocina: si sigo los pasos, llego a obtener un platillo interesante (y esperemos que sabroso también).

Vamos viendo como se “ejecutaría” un algoritmo de cocina (o sea, una receta).  En primer lugar tenemos una entrada que constaría de los ingredientes necesarios.  En segundo lugar tenemos todo el equipo (hardware) necesario para cocinar (como ollas, cubiertos, platos, etc.), los cuales formarían la unidad de procesamiento.  Aunque no se note, existe una parte en el cerebro del cocinero que controla el proceso, cosa conocida como la unidad de control.  Y al final se tiene el platillo terminado, o sea la salida.  Estos componentes se pueden observar en la siguiente imagen:

 

 Llevando nuestra receta a la computadora, tenemos que tomar en cuenta otro elemento importantísimo y vital: la memoria.  Aquí cambia poquito como se procesa información en comparación a nuestra receta culinaria.

• La entrada consiste en todos los datos que se van a procesar, así como el programa que dice qué se va a hacer con estos datos.
• La memoria almacena la entrada y los resultados de la unidad de procesamiento.
• La unidad de control lee el programa y lo traduce en una serie de operaciones de máquina.
• La unidad de procesamiento realiza todas las operaciones (sumas, multiplicaciones, etc.) sobre la información que recibe de la memoria.
• La salida son los resultados de la unidad de procesamiento, almacenados en la memoria y transmitidos a un dispositivo de salida.

En un diagrama, lo veríamos así:

 

 Los algoritmos se pueden representar básicamente de dos maneras: de manera gráfica y con texto.  Hay 2 o 3 representaciones gráficas donde la más conocida es el diagrama de flujo.  Estos diagramas usan símbolos para representar acciones y son tan conocidos que también son usados fuera del ámbito computacional.  Otro diagrama menos conocido, y que no me gusta para nada, son los diagramas NS o de Nassi-Schneiderman que representa un algoritmo en un bloque cuadrado con varios rectángulos interiores.  En cuanto a representaciones basados en texto, está el pseudocódigo, la cual no es más que todos los pasos escritos uno tras otro.

Escribir los algoritmos es algo fundamental para el buen programador.  Muchos de mis alumnos creen que es una pérdida de tiempo sentarse a pensar una solución, sin embargo es muy importante y te ahorra mucho trabajo, porque el error de programación más difícil de corregir es el lógico, el que surge de un algoritmo que no resuelve el problema.  Los errores de sintáxis, o sea de cosas mal escritas (te falta un punto y coma o un espacio, escribiste mal el nombre de la instrucción, etc.) se corrigen rápido ya que el compilador te indica en qué línea te equivocaste.  Pero ante errores lógicos no hay nada que pueda hacer el compilador.

Aunque vivió muchísimos años antes de los rollos de las computadoras y los algoritmos, Sócrates dijo algo que aplica a los errores lógicos: decía que no hay peor mal que la ignorancia en acción.  Te reto a que no dejes que la ignorancia entre en acción y planifiques tus algoritmos.  No es necesario que tengas que hacer un diagrama de flujo para cada algoritmo que hagas, pero encuentra una herramienta que te sea útil para pensar tu solución.  Por ejemplo, yo trato de diagramar mis sistemas con una mezcla de diagramas de Warnier con código en C.  Eso me funciona, pero tu debes de encontrar tu propia forma de solucionar retos.

¡Hasta la próxima!

Insertando orden: ordenamiento inserción

Hace tiempo había escrito de la manera en que se pueden ordenar datos usando el algoritmo conocido como burbuja (puedes ver ese artículo aquí).  Aunque ese algoritmo es el más fácil de entender, también es el meno eficiente.  ¿Por qué digo que es ineficiente?  Es que la eficiencia de un algoritmo de ordenamiento se mide en base al número de comparaciones (o sea, ifs) y el número de asignaciones que tiene que hacer: entre más hace, más se tarda.

Realmente no hay un algoritmo de ordenamiento que sea ideal para todo tipo de arreglos porque unos funcionan mejor para arreglos que están totalmente desordenados (como lo es el QuickSort) o arreglos que están a medio ordenar.  El algoritmo que voy a cubrir aquí es fácil de entender y de implementar.  Además es muy eficiente para ordenar listas que casi están ordenadas.  El algoritmo es el de ordenamiento por inserción.

Para explicar como funciona, tengo varias imágenes que indican el proceso.  Supongamos que tenemos un arreglo de 10 elementos desordenados como el que se ve aquí:


Lo que vamos a hacer es comparar el segundo elemento con el primero.  Si es menor, los intercambio y si no, lo dejo como está y avanzo al siguiente elemento.  En este caso 10 es mayor a 3 así que no hago nada.  Esto se puede ver en esta figura:


Ahora va el tercer elemento.  Lo comparo con el segundo y veo que es menor asi que los intercambio.  Luego lo comparo con el primero y también es menor así que los intercambio.  Como ya es el primer elemento, ahi le paro (es el menor de todos los que he revisado hasta ahorita).  Este proceso lo pueden ver en estas figuras:


Ahora vamos con el cuarto elemento (el 8) y lo comparo con el tercero (10).  Como es menor los intercambio y lo comparo con el segundo (3).  Como no es menor, ahi se queda.  Estas son las imágenes:

Ahora hago lo mismo con el quinto elemento (15) el cual no se mueve por ser mayor que el cuarto (10) como se ve aquí:


Lo mismo con el sexto (5):


Ahora con el séptimo:


Y ahora el octavo:


Ahora el noveno.  Fíjate que como el 5 está repetido en la posición 3, no lo sustituye y se queda en la posición 4 como se ve en estas imágenes:


Y ahora con el último elemento:


Y al final queda el arreglo listo:

Para otra explicación, encontré este video que lo explica bastante bien.  Este es:

Dije que era de fácil implementación, así que vamos a ver como funciona.  Este sería el código en C:


Después de verlo, decidí que se podía optimizar reduciendo el número de asignaciones y quedó así:


Cuando lo ejecutas, se ve así:


Bien, ahora veamos en Visual Basic 6.  Al correrlo, se vería así:


El código sería este.  Fíjate que en el ciclo while tuve que poner un If para comparar el valor del arreglo porque me marcaba error al comparar el elemento del arreglo si j era menor a 0.  Sé que son más comparaciones y disminuye la velocidad de ordenamiento (aunque si lo corres en un CoreDuo o el Quad no notas la diferencia).


Al igual que con el ejemplo de ordenamiento burbuja, implementar el algoritmo en VB 2005 es más engorroso porque no se pueden hacer arreglos de controles (en el ejemplo de VB6, todas las cajas de texto eran un arreglo llamado txtNum), así que hice una subrutina que copia lo que hay en las cajas de texto al arreglo y otro que pasa lo que tiene el arreglo a las cajas de texto.  Fuera de eso, es casi idéntico al código de VB6.  Así se ve cuando se ejecuta:


Y este es el código:


Espero que todo haya quedado claro.  Si te quedaron dudas, déjame un comentario.

¡Saludos!

DFD: Ejecución de diagramas de flujo

Me acabo de topar con un programa buenísimo para enseñar principios de programación. Como saben, los diagramas de flujo nos sirven para plasmar nuestras ideas acerca de cómo resolver algún problema, en este caso, la solución de un programa que necesito implementar en mi computadora (para una explicación más detallada acerca de los diagramas de flujo, puedes checar este artículo en Wikipedia).

DFD es un programita que te permite dibujar diagramas de flujo y una vez que los terminas, te permite ejecutarlos. Lo puedes descargar aquí) y esta es un manual que describe como funciona y toda la onda (si no aparece allí, lo puedes descargar aquí).

Si estás trabajando con algoritmos y quieres ver si funciona tu idea antes de perder el tiempo intentando codificar una idea que no sirve, creo que DFD te puede ayudar mucho. ¡Hasta la próxima!

Ordenando datos... un ejemplo

Aquí les dejo un proyecto muy sencillo que hicimos en una clase. Se trata de ejemplificar la diferencia de usar arreglos y variables al intentar ordenar datos. Por lo tanto, este ejemplo ordena 4 números usando variables y luego ordena 10 números usando arreglos y ordenamiento burbuja.

Aquí se los dejo. ¡Hasta la próxima!

Ordenando el caos con burbujas...

Cuando estamos trabajando con mucha información, es imposible encontrar lo que ando buscando si no está ordenado. Imagínate tu directorio telefónico si no estuviera ordenado alfabéticamente probablemente jamás lo usarías. Esto sucede con los sistemas informáticos también: no basta guardar todos los datos, hace falta mantenerlos en orden o poder ordenarlos.

Ahorita voy a explicar una manera de ordenar datos. Es el algoritmo menos eficiente, pero el más fácil de entender. Este algoritmo es el de Burbuja (o bubble sort) y lo voy a ilustrar usando arreglos. Una vez que entiendas como funciona con arreglos, no tendrás problemas en implementarlo con diferentes tipos de estructuras, clases, registros, etc. Voy a hacer el código usando Visual Basic 6.0 (que va a ser igual que el 2005) y en C. Con esto creo que no tienen problema en transportar el código a cualquier lenguaje de programación.

El algoritmo funciona de la siguiente manera: primero compara el primer elemento contra los demás (obviamente se va comparando uno por uno, elemento por elemento). Si se encuentra un elemento menor, intercambia el contenido (es decir, asigna a este elemento el valor menor y el valor que tenía lo deja en el elemento donde estaba el valor más pequeño). Una vez terminado de comparar el primer elemento contra todos los demás (se supone que el elemento menor está en la primera posición), hago lo mismo con el siguiente elemento: lo comparo con todos los que siguen y dejo el menor valor (de los que quedan) , y así sucesivamente voy comparando todos los elementos contra todos. Al final del día, debería tener un arreglo ordenado.

Por si te hice bolas, sé que una imagen vale mil palabras y como no pienso escribir mil palabras, mejor hice unos dibujitos para aclarar la situación. Espero que se entienda. Después de la imagen, hacemos el algoritmo en C y Visual Basic. Ahí va la manera en que ordeno el primer elemento...


Ok. Allí está el primer elemento. Ahora voy con el segundo elemento...


Ahora voy con el tercero...


Así me voy ordenando todos, pero para completar el ejercicio, ahí va la manera en que se ordena el cuarto elemento:


Y el quinto...

Y el sexto...

El séptimo y octavo...

Ya no tiene comparar el octavo con el noveno porque se supone que si todos los número están ordenados hasta el octavo elemento, el último debe ser el mayor a todos. El arreglo final, ordenadito y toda la cosa, es así:



¡Listo! Queda un arreglo ordenadito y toda la cosa. Este algoritmo es muy sencillo de entender, sin embargo, es muy ineficiente. La eficiencia de un algoritmo tiene que ver directamente con el número de comparaciones que tiene que hacer y este algoritmo es muy ineficiente porque hace muchísimas.

Ahora, ya entendido el concepto y la manera en que funciona este algoritmo, vamos a mostrar cómo se vería ya en código. Como el lenguaje C es muy simple, primero lo voy a resolver en este lenguaje. Aquí pongo el código y abajo de esta imagen explico que onda.


Le puse comentarios al código con la esperanza que se entienda mejor. De este código, lo interesante, lo que hace el trabajo, son los dos ciclos anidados. El ciclo de "i" se encarga de dejarnos visitar todos los elementos del arreglo y el ciclo "j" nos permite comparar todos los elementos que son mayores de i (o sea, los que faltan por comparar). Si el elemento en la posición j es menor al que está en la posición i, los intercambio (para esto uso una variable k que auxilia en la cambiadera).

Simplemente como comentario cultural, el código en C lo hice usando el compilador Microsoft Visual C++ 6.0, pero como usé el C estándar (ANSI C) debería funcionar con cualquier compilador (bueno, algunos comentarios están en "formato" C++, los que comienzan con dos diagonales invertidas, pero no creo que tengas broncas).

Al ejecutarlo se ve así:


Transportar esta idea a Visual Basic 6.0 es sencillo (y es aún más fácil usar el código de Visual Basic 6 en el 2005). Hice una pequeña aplicación, sencillita, que tiene 10 cajas de texto y dos botones. Un botón ordena los valores de las cajas de texto y el otro finaliza la ejecución del programa. El interfaz se ve así:


El código del programa es ésta:


En éste código, txtNumero es un arreglo de los TextBoxes que están en la pantalla. ¿Algún problema? Recuerda que si te quedaste con dudas, me puedes dejar un comentario e intentaré responderte en cuanto pueda.

Ahora voy a hacer esta misma aplicación en Visual Basic 2005. Es casi igual que en la versión 6, pero de todos modos les muestro la interfaz y luego el código. El gran problema que me trauma de la versión 2005 es que no es posible tener arreglos de controles. Bueno, sí se puede pero es un gran relajo al que prefiero no entrarle. Para saltarme esta bronca, antes de ordenar, copio los valores de las cajas de texto (txtNumero1 a txtNumero10) a un arreglo.


Y aquí les dejo el código de la ventana es ésta:


Por ahorita, esto es todo. Si tienes dudas, déjame un comentario. ¡Hasta la próxima!