BUSQUEDA HASH

La idea básica de este método consiste en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas.

Hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un registro, archivo, documentó, etc.

Una función de hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales).

ventajas

• žSe pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar.
• žSe logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones.
• No se requiere almacenamiento adicional para los índices.

desventajas

• No pueden usarse registros delongitud variable
• El archivo no esta clasificado
• žNo permite llaves repetidas
• žSolo permite acceso por una sola llave

Un problema potencial encontrado en este proceso, es que tal función no puede ser uno a uno; las direcciones calculadas pueden no ser todas únicas, cuando R(k1 )= R(k2)Pero : K1 diferente de K2 decimos que hay una colisión

costos

• žTiempo de procesamiento requerido para la aplicación de la función hash
• žTiempo de procesamiento y los accesos E/S requeridos para solucionar las colisiones.

funciones hash mas comunes

• žResiduo de la división
• žMedio del cuadrado
• žPliegue

hashing por residuo de la division 

La idea de este método es la de dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para el registro (dirección = llave módulo divisor).

medio del cuadrado

En esta técnica, la llave es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir la dirección relativa.

hashing por pliegue

En esta técnica el valor de la llave es particionada en varias partes, cada una de las cuales(excepto la ultima) tiene el mismo numero de dígitos que tiene la dirección relativa objetivo. Estas particiones son después plegadas una sobre otra y sumadas. El resultado, es la dirección relativa.

operaciones basica

Inserción(llave, valor) búsqueda(llave) que devuelve valor La mayoría de las implementaciones también incluyen borrar(llave). También se pueden ofrecer funciones como iteración en la tabla, crecimiento y vaciado.

insercion

Inserción(llave, valor) búsqueda(llave) que devuelve valor La mayoría de las implementaciones también incluyen borrar(llave). También se pueden ofrecer funciones como iteración en la tabla, crecimiento y vaciado.

busqueda

• žPara recuperar los datos, es necesario únicamente conocer la clave del elemento, a la cual se le aplica la función resumen.
• žEl valor obtenido se mapea al espacio de direcciones de la tabla.
• Si el elemento existente en la posición indicada en el paso anterior tiene la misma clave que la empleada en la búsqueda, entonces es el deseado. Si la clave es distinta, se ha de buscar el elemento según la técnica empleada para resolver el problema de las colisiones al almacenar el elemento.

http://www.youtube.com/watch?v=iBHR2ETg2po&feature=player_embedded

http://www.youtube.com/watch?v=0CIlFpwuj1Q&feature=related

http://www.youtube.com/watch?v=PHzFZMwhtp4&feature=related

http://www.youtube.com/watch?v=BSwmlqHCTMQ

GRAFOS

Cómo se conforma un grafo?
Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

 Qué es un vértice o nodo?

Ø Punto de intersección o unión de varios elementos que confluyen en el mismo lugar

En estructura de datos:

Un nodo es uno de los elementos de una lista enlazada, de un árbolo de un grafo . Cada nodo será una estructura o registro que dispondrá de varios campos , y al menos uno de esos campos será un puntero o referencia a otro nodo, de forma que, conocido un nodo, a partir de esa referencia, será posible en teoría tener acceso a otros nodos de la estructura. Los nodos son herramientas esenciales para la construcción de estructuras de datos dinámicas.

Un Arco o también llamado Arista corresponde a una relación entre dos vértices de un grafo .

Tipos de grafos dígrafo y no dirigido.
Un dígrafo o grafo dirigido es un grafo en el cual las aristas están dirigidas (y se acostumbra llamarles arcos). Es decir, la relación entre dos vértices adyacentes no necesariamente es simétrica ejemplo: si hay un arco que va de A a B (relación que se denota a veces como A→B ) entonces se dice que A domina a B .

Grafo no dirigido es un conjunto de pares no ordenados de elementos.
Un par no ordenado es un conjunto de la forma {a,b} , de manera que {a,b} = {b,a} .

En que consiste el camino en un grafo
Un camino en un grafo es una sucesión finita en la que aparecen alternadamente vértices y aristas de dicho grafo
Tipos de caminos
Camino euleriano: es un camino o circuito que contiene todas las aristas apareciendo cada una de ellas exactamente una vez. Un grafo que admite dicho circuito se denomina grafo euleriano, y sus vértices o tienen grado par o dos de los vértices tienen grado impar.
Camino hamiltoniano: es un camino simple que contiene todos los vértices apareciendo cada uno de ellos exactamente una vez. Un ciclo que a su vez es un camino hamiltoniano se denomina ciclo hamiltoniano, y un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano.

NOTACION o GRANDE

Definicion:
Se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una funcion, es decir su utilidad radica en encontrar un limite superior de tiempo de ejecucion de un algoritmo en el peor de los casos.

 

La definicion de esta notacion es la siguiente.-

g(n) O(F(n)) si y solo si existen las constantes C y n tales que g(n) <= C * F(n).

 

para todo C>=n se tiene que T(n)<=Cn el orden de la magnitud de una funcion es el orden del termino de la funcion mas grande en terminos de n.

Nota: el orden de magnitud de una función es el orden del termino de la función mas grande respecto de n.

 

caracterisitcas:

• El análisis de algoritmos estima el consumo de recursos de un algoritmo.
•  Esto nos permite comparar los costos relativos de dos o más algoritmos para resolver el mismo problema.
• El análisis de algoritmos también les da una herramienta a los diseñadores de algoritmos para estimar si una solución propuesta es probable que satisfaga las restricciones de recursos de un problema.
• El concepto de razón de crecimiento, es la razón a la cual el costo de un algoritmo crece conforme el tamaño de la entrada crece.
• Usualmente se mide el tiempo de ejecución de un algoritmo, y el almacenamiento primario y secundario que consume.
• Consideración principal para estimar el desempeño de un algoritmo, es el número de operaciones básicas requeridas por el algoritmo para procesar una entrada de cierto tamaño.

ALGORITMOS

Un algooritmo es un procedimiento esquematico que comprende un conjunto de pasos secuenciales ordenados, para realizar una actividad especifica

Un Algoritmo es..
Preciso: cada instruccion tiene que ser clara y determinada a una accion
Definidido: por que debe obtenerse los resultados determinados con las instrucciones de entrada
Finito: por que su diseño debe tener un numero limitado en cuanto a los pasos
Ordenado: por que tienen una secuencia de pasos
Efectividad: El tiempo y esfuerzo por cada paso realizado debe ser preciso, no usando nada más ni nada menos que aquello que se requiera para y en su ejecución.

CODIGO DE ARBOL EN JAVA

class NodoBinario{
 int dato;
 NodoBinario Hizq, Hder;
 //Constructores
 NodoBinario (int Elem){
  dato = Elem;
  NodoBinario Hizq, Hder = null;
 }
 //Insercion de un elemento
 public void InsertaBinario (int Elem){
  if(Elem < dato){
   if (Hizq == null)
    Hizq = new NodoBinario(Elem);
   else
    Hizq.InsertaBinario(Elem);
  }
  else{
   if (Elem > dato){
    if (Hder == null)
     Hder = new NodoBinario (Elem);
    else
     Hder.InsertaBinario(Elem);
   }
  }
 }
}
//Definicion de la clase Arbol
class Arbol{
 Cola Cola = new Cola();
 NodoBinario Padre;
 NodoBinario Raiz;
 //Constructor
 public Arbol(){
  Raiz = null;
 }
 //Insercion de un elemento en el arbol
 public void InsertaNodo(int Elem){
  if(Raiz == null)
   Raiz = new NodoBinario (Elem);
  else
   Raiz.InsertaBinario (Elem);
 }
 //Preorden Recursivo del arbol
 public void Preorden (NodoBinario Nodo){
  if(Nodo == null)
   return;
  else{
   System.out.print (Nodo.dato + " ");
   Preorden (Nodo.Hizq);
   Preorden (Nodo.Hder);
  }
 }
 //PostOrden recursivo del arbol
 public void PostOrden (NodoBinario Nodo){
  if(Nodo == null)
   return;
  else{
   PostOrden (Nodo.Hizq);
   PostOrden (Nodo.Hder);
   System.out.print (Nodo.dato + " ");
  }
 }
 //Inorden Recursivo del arbol
 public void Inorden (NodoBinario Nodo){
  if(Nodo == null)
   return;
  else{
   Inorden (Nodo.Hizq);
   System.out.print(Nodo.dato + " ");
   Inorden (Nodo.Hder);
  }
 }
 //Busca un elemento en el arbol
 void Busqueda (int Elem, NodoBinario A){
  if((A == null) | (A.dato == Elem)){
   System.out.print(A.dato + " ");
   return;
  }
  else{
   if(Elem>A.dato)
    Busqueda (Elem, A.Hder);
   else
    Busqueda ( Elem, A.Hizq);
  }
 }
 //Altura del arbol
 public int Altura (NodoBinario Nodo){
  int Altder = (Nodo.Hder == null? 0:1 + Altura (Nodo.Hder));
  int Altizq = (Nodo.Hizq == null? 0:1 + Altura (Nodo.Hizq));
  return Math.max(Altder,Altizq);
 }
 //Recorrido en anchura del arbol
 public void Anchura (NodoBinario Nodo){
  Cola cola= new Cola();
  NodoBinario T = null;
  System.out.print ("El recorrido en Anchura es: ");
  if(Nodo != null){
   cola.InsertaFinal (Nodo);
   while(!(cola.VaciaLista ())){
    T = cola.PrimerNodo.datos;
    cola.EliminaInicio();
    System.out.print(T.dato + " ");
    if (T.Hizq != null)
     cola.InsertaFinal (T.Hizq);
    if (T.Hder != null)
     cola.InsertaFinal (T.Hder);
   }
  }
  System.out.println();
 }
}
//Definición de la Clase NodoLista
class NodosListaA{
   NodoBinario datos;
    NodosListaA siguiente;
     //Construtor  Crea un nodo del tipo Object
 NodosListaA (NodoBinario  valor){
  datos =valor;
     siguiente = null;  //siguiente con valor de nulo
  }
 // Constructor Crea un nodo del Tipo Object y al siguiente nodo de la lista
 NodosListaA (NodoBinario valor, NodosListaA signodo){
  datos = valor;
     siguiente = signodo; //siguiente se refiere al siguiente nodo
 }
}
//Definición de la Clase Lista
class Cola{
 NodosListaA PrimerNodo;
 NodosListaA UltimoNodo;
 String Nombre;
 //Constructor construye una lista vacia con un nombre de List
 public Cola(){
  this ("Lista");
 }
 //Constructor
  public Cola (String s){
  Nombre = s;
     PrimerNodo = UltimoNodo =null;
 }
 //Retorna True si Lista Vacía
 public boolean VaciaLista() {
  return PrimerNodo == null;
 }
 //Inserta un Elemento al Frente de la Lista
 public void InsertaInicio (NodoBinario ElemInser){
  if(VaciaLista())
      PrimerNodo = UltimoNodo = new NodosListaA (ElemInser);
     else
      PrimerNodo = new NodosListaA (ElemInser, PrimerNodo);
 }
 //Inserta al Final de la Lista
 public void InsertaFinal(NodoBinario ElemInser){
  if(VaciaLista())
         PrimerNodo = UltimoNodo = new NodosListaA (ElemInser);
     else
         UltimoNodo=UltimoNodo.siguiente =new NodosListaA (ElemInser);
 }
 //Eliminar al Inicio
 public void EliminaInicio(){
  if(VaciaLista())
      System.out.println ("No hay elementos");
   // Restablecer  las referencias de PrimerNodo y UltimoNodo
   if(PrimerNodo.equals (UltimoNodo))
      PrimerNodo = UltimoNodo = null;
     else
      PrimerNodo = PrimerNodo.siguiente;
 }
 //Elimina al final
 public void EliminaFinal (){
     if(VaciaLista())
       System.out.println ("No hay elementos");
  // Restablecer  las referencias de PrimerNodo y UltimoNodo
  if (PrimerNodo.equals (UltimoNodo))
      PrimerNodo = UltimoNodo = null;
     else{
      NodosListaA Actual =PrimerNodo;
   while (Actual.siguiente != UltimoNodo)
    Actual = Actual.siguiente;
   UltimoNodo =Actual;
   Actual.siguiente = null;
     }
 }
}

class ArbolBinarioA{
 public static void main (String[]args){
  Arbol A = new Arbol();
  A.InsertaNodo (10);
  A.InsertaNodo (7);
  A.InsertaNodo (8);
  A.InsertaNodo (6);
  A.InsertaNodo (12);
  A.InsertaNodo (11);
  A.InsertaNodo (5);
  A.InsertaNodo (4);
  A.InsertaNodo (3);
  A.InsertaNodo (2);
  System.out.print("El recorrido en Preorden es: ");
  A.Preorden (A.Raiz);
  System.out.println();
  System.out.print("El recorrido en Inorden es: ");
  A.Inorden (A.Raiz);
  System.out.println();
  System.out.print("El recorrido en Postorden es: ");
  A.PostOrden (A.Raiz);
  System.out.println();
  System.out.println("La altura del arbol es: " + A.Altura (A.Raiz));
  A.Anchura (A.Raiz);
 }
}