Introduccion Estructuras de Datos

La Estrucutura de datos profundiza en la forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulacion. El temario del curso es el siguiente:

1. Definiciones Basicas.
2. Estructuras líneas.
3. Estructuras recursivas.
4. Estructuras Relacionales.
5. Ordenamiento y busqueda.

Los textos de consulta se exponen a continuacion.

-> Estructuras de Datos & Algoritmos - Addison, Nesley
-> Diseño y Manejo de Estructuras - Villalobos McgrawHill
-> Estructuras de Datos - Cairo, Oswaldo
-> Estructuras de Datos - Becerra

Conceptos Basicos

A continuación se enumeran algunos conceptos básicos sobre la materia.

* Estructura*
Es la manera como se pueden organizar los datos para que puedan ser interpretados de forma lógica y ordenada.

*Dato*
Es la unidad mínima de información, por si misma no tiene significado pero al organizar de forma lógica una cantidad establecida, se logra obtener un significado coherente.

*Algoritmo*
Es un conjunto de pasos finitos ordenados con el cual obtenemos la resolución de un problema especifico.

*Programa*
Es un conjunto de instrucciones que puede interpretar un computador con el fin de realizar un proceso especifico.

*Recursividad*
Propiedad de algunos lenguajes de programación de permitir que un programa solicite su propia ejecución en el curso de su desarrollo.

*Iteratividad*
Las estructuras iterativas son aquellas que nos permiten repetir varias veces un proceso.

*Abstracción*
Consiste en aislar un elemento de su contexto o del resto de los elementos que lo acompañan.

*Clase*
Es una plantilla o un prototipo para crear objetos, por eso se dice que los objetos son instancias de clases.

*Objeto*
Se define como la unidad que en tiempo de ejecución realiza las tareas de un programa.

MAPA CONCEPTUAL


EFICIENCIA




Algoritmo mas efeiciente = menor tiempo de ejecucion.


Tiempos de ejecucion:


Entradas: n1,n2...n logn)
Complejidadx=1 -> 1Cont = cont + 1 -> n+1 ------> 2n + 3 Ta(n)=?; O(n)=?.If x -> n+1



Si Ta1(n) es O(f1(n)) -> Para todo c1n1 > 0 Para cualquier n > = n1 Ta1(n) <= c1*f1(n) n es 0 (f2(n)) => Para todo c1n1 > 0



Para cualquier c2,n2>0
Uso de memoria, datos simples y compuestos.
Mantenimiento a los programas. (reingenieria)Rapidez para hacer cambios, pra leer datos, modificacion. (reingenieria)
TORRES DE HANOI





Las Torres de Hanói es un rompecabezass o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.
Consiste en tres varillas verticales y un número indeterminado de discos que determinarán la complejidad de la solución. No hay dos discos iguales, están colocados de mayor a menor en la primera varilla ascendentemente, y no se puede colocar ningún disco mayor sobre uno menor a él en ningún momento.


El juego consiste en pasar todos los discos a la tercera varilla colocados de mayor a menor ascendentemente.


Las reglas son:


Sólo se puede mover un disco cada vez.
Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.



RESOLUCION


El problema de las Torres de Hanói es curiosísimo porque su solución es muy rápida de calcular, pero el número de pasos para resolverlo crece exponencialmente conforme aumenta el número de discos.
Existen otras versiones del problema con un número diferente de varillas. Aunque se conocen algoritmos eficientes que resuelven el problema con 3 varillas de manera óptima, no se han encontrado aún sus contrapartidas para cualquier número (N igual o superior a 3) de ellas.


Otra manera de resolverlo es basándose en el disco más pequeño, en este caso el de hasta arriba. El movimiento inicial de este es hacia la varilla auxiliar. El disco número dos por regla, se debe mover a la varilla número tres. Luego el disco uno se mueve a la varilla tres para que quede sobre el disco dos. A continuación se mueve el disco que sigue de la varilla uno, en este caso el disco número tres, y se coloca en la varilla dos. Finalmente el disco número uno regresa de la varilla tres a la uno (sin pasar por la dos) y así sucesivamente. Es decir, el truco está en el disco más pequeño.


1- Mediante recursividad:


Este problema se suele plantear a menudo en ámbitos de programación, especialmente para explicar la recursividad.


Si numeramos los discos desde 1 hasta n, y llamamos X a la primera pila de discos (origen), Z a la tercera (destino) e Y a la intermedia (auxiliar) y a la función le llamaríamos hanoi (origen, auxiliar, destino), como parámetros, la función recibiría las pilas de discos.
El algoritmo de la función sería el siguiente:



Si origen == {0}: mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino); terminar.
Si no: hanoi({0...n-1},destino, auxiliar) //mover todas las fichas menos la más grande (n) a la varilla auxiliar
mover disco n a destino //mover la ficha grande hasta la varilla final
hanoi (auxiliar, origen, destino) //mover todas las fichas restantes, {0...n-1}, encima de la ficha grande (n)
terminar



2- Mediante Iteratividad:


Otra manera de resolver el problema, sin utilizar la recursividad, se basa en el hecho de que para obtener la solución más corta, es necesario mover el disco más pequeño en todos los pasos impares, mientras que en los pasos pares sólo existe un movimiento posible que no lo incluye. El problema se reduce a decidir en cada paso impar a cuál de las dos pilas posibles se desplazará el disco pequeño:


El algoritmo en cuestión depende del número de discos del problema.
Si inicialmente se tiene un número impar de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila destino, y en cada paso impar se le mueve a la siguiente pila a su izquierda (o a la pila destino, si está en la pila origen).


La secuencia será DESTINO, AUXILIAR, ORIGEN, DESTINO, AUXILIAR, ORIGEN, etc.
Si se tiene inicialmente un número par de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila auxiliar, y en cada paso impar se le mueve a la siguiente pila a su derecha (o a la pila origen, si está en la pila destino).
La secuencia será AUXILIAR, DESTINO, ORIGEN, AUXILIAR, DESTINO, ORIGEN, etc.

****_ ALGORITMO EN JAV@_****
import java.util.Stack;
class Hanoy {
// Las 3 pilas de discos
private Stack columnas[];
// Constructor, toma el nº de fichas total
public Hanoy(int fichas) {
columnas = new Stack[3];
// Inicializamos las columnas vacias
columnas[0] = new Stack();
columnas[1] = new Stack();
columnas[2] = new Stack();
// Colocamos en la primera las fichas, de mayor a menor
for (int i=fichas;i>0;i--) columnas[0].push(i);
}
// Muestra el estado actual
public void Mostrar() {
for (int i=0;i<3;i++)>
System.out.print("Col. "+i+": ");
for(int n : columnas[i]) System.out.print("["+n+"]");
System.out.println("");
}
}
// Mueve de la columna origen a la columna destino 1 disco
public void Mover(int origen, int destino) {
// Mostramos en pantalla lo que hacemos
Mostrar();
System.out.println("Movemos desde ("+origen+") hasta ("+destino+")"); System.out.println("");
// Y luego, lo hacemos, claro
columnas[destino].push(columnas[origen].pop());
}
// Mueve de la columna origen a la columna destino varios discos
public void MoverN(int origen, int destino, int cuantas) {
// Si solo es uno, se mueve sin más
if (cuantas <= 1) Mover(origen,destino);
else {
// Si son varios, entonces:
// - Primero movemos N-1 a la columna ni origen ni destino
MoverN(origen,3 - (origen+destino),cuantas-1);
// - Movemos la N, es decir, la grande
Mover(origen,destino);
// - Movemos las N-1 del primer paso, a la col. destino
MoverN(3 - (origen+destino),destino,cuantas-1);
}
}
// Programa principal
public static void main(String args[]) {
// Creamos una partida de 5 discos
Hanoy h = new Hanoy(5);
// Y la resolvemos (movemos de col.0 a col.2 los 5 discos
h.MoverN(0,2,5);
// Mostramos resultado, resuelto
h.Mostrar();
}
}