Pilas y Colas

Las pilas y colas son estructuras de datos que se generalmente simplifican ciertas operaciones de programación. Estas estructuras pueden implementarse mediante “arrays” o mediante listas enlazadas.

Pilas

Las pilas son estructuras de datos a las cuales se les puede acceder por un solo extremo de la misma. Las operaciones de inserción y extracción se realizan a través del tope, por lo cual no se puede acceder a cualquier elemento de la pila. Tienen dos operaciones básicas: “push” para insertar elementos, y “pop” para extraer elementos. Son conocidas también como estructuras de datos LIFO, que en inglés quiere decir “last in, first out”, o último en entrar, primero en salir. La pila se considera un grupo ordenado de elementos, teniendo en cuenta que el orden de los mismos depende del tiempo que lleven "dentro" de la estructura. Una posible
implementación mediante listas enlazadas sería insertando y extrayendo
siempre por el principio de la lista. Gracias a las pilas es posible el uso de la
recursividad. La variable que llama al mismo procedimiento en el q está, habrá que guardarla así como el resto de variables de la nueva llamada, para a la vuelta de la recursividad ir sacándolas, esto es posible a la implementación de pilas.

Aquí una representación gráfica de cómo es una pila, mostrando como de apila y desapila siempre en el tope.

Y aquí un ejemplo del código escrito en Python:

>>> pila = [6,7,8]
>>> pila.append(9)
>>> pila
[6, 7, 8, 9]
>>> pila.pop()
9
>>> pila.pop()
8
>>> pila[-1]
7

**************************************************************

Colas

Las colas también son llamadas FIFO (First In First Out), que quiere
decir “el primero que entra es el primero que sale”. Tanto el frente como el final de la cola, son los únicos indicados para retirar e insertar elementos, respectivamente. Esto significa que no podemos acceder directamente a cualquier elemento de la cola, sino solo al primero, o sea el que está o se encuentra en el frente, y no se pueden insertar elementos en cualquier posición sino solo por el final, así el elemento insertado queda como último.

Colas simples:
Se inserta por un sitio y se saca por otro, en el caso de la cola simple se
inserta por el final y se saca por el principio. Para realizar este tipo de cola
hay que recordar siempre cual es el siguiente elemento que se va a leer  y cual
es el último elemento que se ha introducido.

Colas circulares:
En las colas circulares se considera que después del último elemento se
accede de nuevo al primero. De esta forma se reutilizan las posiciones
extraídas, el final de la cola es a su  vez el principio, creándose un circuito
cerrado.

Aquí un ejemplo:

Lo que sucedió en esta tabla fue que se insertó un 5, se sacó un 1 y se insertó un 8.

Colas con prioridad:
Las colas con prioridad se implementan mediante listas o arrays
ordenados. No nos interesa en este caso que salgan en el  orden de entrada
sino con una prioridad que le asignemos. Puede darse el caso que existan
varios elementos con la misma prioridad, en este caso saldrá primero aquel
que primero llego (FIFO).

Aquí un ejemplo de cola en Python:

>>> queue = ["Erick", "Juan", "Miguel"]

>>> queue.append("Tomás") # llega Tomás

>>> queue.append("Gerardo") # llega Gerardo

>>> queue.pop(0)

'Erick'

>>> queue.pop(0)

'Juan'

>>> queue

Y aquí una liga donde se muestra una cola de prioridades en código Python:

http://es.w3support.net/index.php?db=so&id=407734

 

Referencias:

• http://www.iuma.ulpgc.es/users/jmiranda/docencia/programacion/Tema4_ne.pdf


• http://html.rincondelvago.com/pilas-y-colas.html


• http://www.juanjoconti.com.ar/2010/07/22/pilas-y-cola-en-python/

Búsqueda Binaria

La búsqueda binaria, también llamada dicotómica,  es de los algoritmos de búsqueda más eficientes que hay. Para poder llevarla a cabo, es necesario que los elementos del vector estén ordenados previamente, ya sea de forma ascendente o descendente.

Estos son los pasos que se llevan a cabo en este tipo de búsqueda:

1. Se divide el vector en dos partes iguales.
2. Si el elemento en el centro del vector es mayor que el del elemento buscado, busca en la primera mitad.
3. Si el elemento en el centro del vector es menor que el elemento buscado, busca en la segunda mitad.
4. Se repiten los pasos hasta llegar al elemento que es buscado. En caso de no encontrarlo, el valor regresado es falso.

Aquí un muy breve video en donde se puede ver gráficamente lo que sucede cuando se ejecuta la búsqueda binaria, en dónde se busca el valor 17 en un vector de 40 valores.

Y aquí una liga para ver el código en C, en donde se aplica de forma recursiva: http://mygnet.net/codigos/c/metodos_de_busqueda/busqueda_binaria_de_forma_recursiva_sobre_un_vector_ordenado_dot_muy_completo.2936

Referencias:

http://www.programacionfacil.com/estructura_datos_csharp:busqueda_binaria

Instalar Ubuntu dentro de Windows

Aquí les escribiré un pequeño tutorial para aquellos que quieren instalar Ubuntu dentro de Windows, para tener la opción de elegir con que sistema operativo quieres trabajar desde que enciendes el computador.
La manera mas sencilla es usando un programa llamado WUBI (Windows Ubuntu Installer)
 
Lo primero que deben hacer es entrar a esta liga: http://www.ubuntu.com/download/ubuntu/windows-installer. Después dar click donde dice Start Download, como se muestra en la imagen.

Después se debe aparecer el ejecutable en la carpeta de descargas:
Abrimos el ejecutable y nos aparecen diferentes opciones como en que disco se va a instalar y el tamaño, el escritorio de Ubuntu que deseamos, y el idioma. El tamaño de instalación de Ubuntu es de 17GB, pero es recomendable seleccionar un poco mas espacio para tus archivos.

Después de poner dos veces la contraseña que deseen, simplemente den click en instalar y el programa se pondrá rápidamente a trabajar. Dependiendo de tu computadora y conexiones es lo que se va a tardar. En mi caso no fueron mas de 3 minutos.

Después que Ubuntu está instalado, se debe reiniciar la computadora. Al arranque (boot) una pantalla negra aparecerá preguntando con qué sistema operativo deseas empezar. Con las flechas y el enter se selecciona Ubuntu, y desde ahí podemos empezar a descubrir sus funcionalidades. Natty Narwal, que es la versión actual, determina en automático si tu computadora puede soportar la interfaz Unity. En caso de que no, se presenta la interfaz clásica parecida a GNOME.
Aquí una liga, en inglés, con 5 cosas que querrás hacer recién instales Ubuntu: http://www.pcworld.com/businesscenter/article/209202/5_things_to_do_first_with_ubuntu.html
Ojalá les sirva este aporte!

Métodos de Ordenamiento

Los algoritmos de ordenamiento nos permite, como su nombre lo dice, ordenar. En
este caso, nos servirán para ordenar vectores o matrices con valores asignados
aleatoriamente.

Para poder ordenar una cantidad determinada de números almacenadas en un vector o
matriz, existen distintos métodos (algoritmos) con distintas características y
complejidad. Existe desde el método mas simple, como el Bubblesort (o Método Burbúja), que son simples iteraciones, hasta el Quicksort (Método Rápido), que al estar optimizado usando recursión, su tiempo de ejecución es menor y es más efectivo.

Existen dos tipos de métodos de ordenamiento, los cuáles son:

- Iterativos: Estos métodos son simples de entender y de programar ya que son iterativos, simples ciclos y sentencias que hacen que el vector pueda ser ordenado.

-Recursivos: Estos métodos son aún mas complejos, requieren de mayor atención y conocimiento para ser entendidos. Son rápidos y efectivos, utilizan generalmente la técnica Divide y vencerás, que consiste en dividir un problema grande en varios pequeños para que sea más fácil resolverlos. Mediante llamadas recursivas a si mismos, es posible que el tiempo de ejecución y de ordenación sea más optimo.

Aquí resumiré y explicaré brevemente algunos de los más importantes métodos de ordenamiento:

• Burbuja: También llamado “bubble sort” es el más sencillo de los métodos, pero muy ineficiente. Lo que hace es que recorre el arreglo intercambiando los valores adyacentes que estén ordenados. Se recorre una y otra ves dicho arreglo hasta que sea imposible realizar cambios. Concretamente lo que hace es que agarra el valor mayor y lo recorre de posición en posición hasta ponerlo en su lugar.

• Complejidad:

1. O(n²)
2. Peor caso n(n-1)/2
• Aquí un pequeño gif explicando el método:

                         

• Liga para códico en ANSI C: http://www.ajpdsoft.com/modules.php?name=Content&pa=showpage&pid=236
• Ordenamiento por inserción: En este método, también llamado insertion sort, cuando hay n elementos, se toma el elemento n+1 y se compara con los elementos previamente ordenados, deteniéndose al detectar un elemento menor, y es aquí cuando se inserta el elemento k+1 desplazando así a los demás elementos.

• Complejidad:

1. O(n²) 
2. Peor caso: Ω(n)
• Gif explicando el método:

                         

•   Liga para código en ANSI C: http://www.cs.auckland.ac.nz/~jmor159/PLDS210/niemann/s_ins.txt
• Shell sort: . Ordena subgrupos de elementos separados K unidades del arreglo original. El valor K es llamado incremento. Después de que los primeros K subgrupos han sido ordenados), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K. Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado. Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.
• Complejidad:
• O(n^1.25)
• Peor caso: O(n²)
• Aquí un ingenioso video que explica cómo funciona:
  
•   Código en ANSI C: http://www.java2s.com/Code/C/Data-Structure-Algorithm/TheShellSort.htm
• Quick Sort: Este método se basa en la filosofía de “divide y vencerás”. Tiene dos fases, una de particiones y la otra de ordenamiento. En la fase de particiones, listas de dos o mas elementos son divididas en listas mas pequeñas. Todos los objetos menores al valor que fue asignado como pivote se van a una lista, y los que son mayores a otra. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
• Complejidad:

• Promedio: O(n log n),

• Peor caso: O(n²)

• Gif del método:

  
• Código en ANSI C: http://www.daniweb.com/software-development/c/code/216793
• Merge Sort: Es otro ejemplo del principio de “divide y vencerás”. Si el vector tiene mas de dos elementos se lo divide en dos mitades, se invoca recursivamente al algoritmo y luego se hace un merge de las dos mitades ordenadas. Primero se divide en dos sublistas de aproximadamente la mitad del tamaño, se ordena cada lista recursivamente utilizando el ordenamiento por mezcla y al final las dos sublistas en una sola lista ordenada.
• Complejidad:
• O(n log n)
• Peor caso: O(n log n)
• Gif explicativo:

                             

• Código en ANSI C: http://www.rs.io/msort.c/
• Heap sort: Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo, y luego extraer el nodo que queda como nodo raíz del montículo en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento de todos los almacenados en él.
• Complejidad: O(n log n)
• peor caso:
• Gif explicativo:

             

• Código en C: http://www.algorithmist.com/index.php/Heap_sort.c
• Radix Sort: Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan. Se empieza en el dígito más significativo y se avanza por los dígitos menos significativos mientras coinciden los dígitos correspondientes en los dos números. El número con el dígito más grande en la primera posición en la cual los dígitos de los dos números no coinciden es el mayor de los dos (por supuesto sí coinciden todos los dígitos de ambos números, son iguales).
• Complejidad: O(nk)
• Aquí un video con la representación gráfica y con audio de cómo sería la implementación:
  
• Aquí el código en C: http://www.dreamincode.net/code/snippet2030.htm

 

Ya viendo cada uno de éstos métodos es posible comparar la eficiencia de algunos en ésta liga: http://www.sorting-algorithms.com/ en dónde te muestran gráficamente como se comportan con datos arreglados de diferentes maneras.

 

Referencias:

• blog.zerial.org/ficheros/Informe_Ordenamiento.pdf

• http://www.monografias.com/trabajos/algordenam/algordenam.shtml

• http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm

• http://latecladeescape.com/con-nombre-propio/ordenacion-por-el-metodo-de-shell-shellsort.html

• http://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento

• www.cs.toronto.edu/~neto/teaching/238/16/mergesort.html

• http://es.wikipedia.org/wiki/Ordenamiento_por_mont%C3%ADculos

• http://ict.udlap.mx/people/ingrid/Clases/IS211/Radix.html

Ineficiencia de Fibonacci Recursivo

Aquí daré una breve pero acertada explicación de por qué usar la función de Fibonacci en términos recursivos es a la larga bastante ineficiente. Veamos su definición es tales términos:

fib(1)=1
fib(2)=1
fib(n)=fib(n-1)+fib(n-2)     cuando n>2

Ahora pongamos como ejemplo que queremos sacar Fibonacci 6, o sea n=6. Primero debemos tener en cuenta que como n=6 no es un caso base, se vuelve a invocar recursivamente dos veces, primer con n=5 y luego con n=4. Éstos números a su ves necesitan dos llamadas mas, y cada una de estas harán otras dos llamadas, y así sucesivamente hasta llegar a los números base que no necesitan una llamada, y cortan la cadena de llamadas recursivas.

Aquí se representan las llamadas gráficamente, en donde el resultado es una estructura de árbol binario, en donde la profundidad depende del n inicial. 

Podemos ver en la gráfica que cada círculo representa un valor de n para la invocación de una función, empezando con n=6. Para calcular fib(6), es necesario calcular fib(5) y fib(4), y para calcular fib(4) es necesario calcular fib(3) y fib(2), y así sucesivamente, hasta llegar a fib(1) y fib(2), que son los casos base y donde la recursividad se corta. No parece mucho, pero imaginen si queremos encontrar fib(25), tendríamos que dibujar 150000 nodos!

Otra cosa importante a notar es que por la propia implementación recursiva de la función algunos valores se calculan más veces de lo necesario, por ejemplo fib(4) se calcula dos veces y fib(3) se calcula tres veces, cuando sólo se ocupan calcular una ves. Calcular un valor grande como fib(50) tardaría bastante tiempo en realizarse, tanto que cerraríamos el programa en desesperación! Es por esto que se concluye que para sacar números Fibonacci de una manera eficiente es mejor hacerlo de una manera iterativa, que tomaría exponencialmente menos tiempo que de manera recursiva. 

Referencias:

http://latecladeescape.com/basico/entender-la-recursividad.html

Recursividad

Un algoritmo se llama recursivo cuando se usa una parte del mismo como solución al problema. El resto es generalmente la solución trivial, o sea aquella cuya solución será siempre conocida, es fácil de calcular o es parte de la definición del problema a resolver. Ésta solución sirve como referencia y permite que el algoritmo tenga una cantidad finita de pasos. Por lo general estos algoritmos se implementan junto a una estructura de datos, la cual es la pila, en la cual se almacenan los resultados parciales de cada recursión.

Para mostrarles un ejemplo de algoritmo recursivo hice este programa que muestra una sucesión de números Fibonacci. Primero veamos la definición:

Los números de Fibonacci se definen como:

F_N = F_N-1 + F_N-2 para N > 2

F₀ = F₁ = 1

que definen la secuencia:

1,1,2,3,5,8,13,21,34,55,89,144, .....

Aquí un programa que hice en C:

#include <stdio.h>

int main(void)
{
    int   num_anterior=0;
    int   num_actual=1;
    int   num_siguiente;
    int cont;
    int x;
   
    printf("Cuantos numeros Fibonacci deseas calcular?\n");
    scanf("%d", &x);
    cont=1;
    system("cls");
    printf("%d\n", num_anterior);
    while (cont<x) {
       
        printf("%d\n", num_actual);
        num_siguiente = num_actual + num_anterior;

        num_anterior = num_actual;
        num_actual = num_siguiente;
        cont++;
    }
    printf("Fin de la sucesion");
    getch();
    return (0);
}

Aquí se aplica la recursividad para calcular el valor siguiente (num_siguiente), pues tiene que recurrir a los valores de num_actual y num_anterior que se sacaron anteriormente para sumarlos. Luego reemplaza num_anterior por num_actual, y num_actual se vuelve el valor anterior de num_siguiente.

Bibliografía

• http://es.wikiversity.org/wiki/Curso_de_Estructuras_de_Datos_y_Algoritmos_/_Algoritmos_recursivos
• www.cs.buap.mx/~titab/files/recursion1.doc

Escala Logarítmica

Aquí una definición: La escala logarítmica es una escala de medida, que se utiliza para representar más cómodamente cantidades físicas en forma de porcentajes ( y no en valor absoluto, como en la escala lineal). Es una escala donde las longitudes son proporcionales a los logaritmos de las magnitudes.

Aquí un ejemplo con las gráfica que hice hace dos entradas, en la cual evalué valores de “y” con diferentes ecuaciones. Aquí la original:

Y la siguiente es después de haber aplicado en Excel la opción de mostrar en escala logarítmica:

Podemos notar las diferencias en los ejes, que por definición no pueden tener 0. La línea que se elevaba mas en la primera gráfica ahora es totalmente recta, al igual que la línea anterior, y se pueden notar todos los valores separados con buena distancia, al contrario de la primera gráfica.