Parte 1: Mantenimiento de una estructura de datos en disco atraves de varios indices-arbol B, en este caso, se gestionan los datos de clientes de un banco .
Parte 2: Mantenimiento de una lista enlazada con nodos en una estructura de datos en disco
Anexos :
--
lunes, 31 de diciembre de 2007
viernes, 28 de diciembre de 2007
Java sincronizacion concurrente
Etiquetas:
concurrente,
java,
semaforos,
semaphore
El problema
En un reino medieval conviven 5 caballeros que deben compartir bajo exclusión mutua un único salón para festejar sus victorias en sus guerras. Para evitar solapar las fiestas de unos caballeros con las de otros el rey ha impuesto la siguiente política:
Cuando un caballero llega a su castillo tras una guerra desea festejarlo. Cada caballero dispone de un vasallo al que avisa para que consiga el salón y lo prepare a su gusto. Después, el caballero debe esperar a que su vasallo haya conseguido el salón y lo haya terminado de preparar, momento en el cual puede comenzar su fiesta. Entonces, el vasallo debe esperar a que el caballero le avise de que ha terminado la fiesta para proceder a limpiar el salón, dejando posteriormente el salón libre.
Output de la solucion :
Caballero 0 guerreando
Caballero 3 guerreando
Caballero 6 guerreando
Caballero 2 guerreando
Caballero 5 guerreando
Caballero 8 guerreando
Caballero 1 guerreando
Vasayo 2 esperando a guerrero
Caballero 4 guerreando
Vasayo 0 esperando a guerrero
Caballero 7 guerreando
Vasayo 3 esperando a guerrero
Vasayo 7 esperando a guerrero
Vasayo 8 esperando a guerrero
Caballero 9 guerreando
Vasayo 4 esperando a guerrero
Vasayo 1 esperando a guerrero
Vasayo 9 esperando a guerrero
Vasayo 6 esperando a guerrero
Vasayo 5 esperando a guerrero
Caballero 2 llamando a vasayo
Vasayo 2 preparando sala
Caballero 2 festejando
Caballero 4 llamando a vasayo
Vasayo 4 esperando para adquirir la sala (esperando 0)
Vasayo 2 esperando terminacion de la fiesta para limpiar
Vasayo 4 preparando sala
Vasayo 2 termino de limpiar la sala
Caballero 0 llamando a vasayo
Vasayo 0 esperando para adquirir la sala (esperando 0)
Caballero 4 festejando
Caballero 5 llamando a vasayo
Vasayo 5 esperando para adquirir la sala (esperando 1)
Vasayo 4 esperando terminacion de la fiesta para limpiar
Vasayo 4 termino de limpiar la sala
Vasayo 0 preparando sala
Caballero 0 festejando
Vasayo 0 esperando terminacion de la fiesta para limpiar
Vasayo 0 termino de limpiar la sala
Vasayo 5 preparando sala
Caballero 5 festejando
Vasayo 5 esperando terminacion de la fiesta para limpiar
Vasayo 5 termino de limpiar la sala
Caballero 8 llamando a vasayo
Vasayo 8 preparando sala
Caballero 8 festejando
Vasayo 8 esperando terminacion de la fiesta para limpiar
Vasayo 8 termino de limpiar la sala
Caballero 7 llamando a vasayo
Vasayo 7 preparando sala
Caballero 7 festejando
Vasayo 7 esperando terminacion de la fiesta para limpiar
Vasayo 7 termino de limpiar la sala
Caballero 6 llamando a vasayo
Vasayo 6 preparando sala
Caballero 6 festejando
Vasayo 6 esperando terminacion de la fiesta para limpiar
Vasayo 6 termino de limpiar la sala
Caballero 3 llamando a vasayo
Vasayo 3 preparando sala
Caballero 9 llamando a vasayo
Vasayo 9 esperando para adquirir la sala (esperando 0)
Vasayo 9 preparando sala
Caballero 3 festejando
Caballero 9 festejando
Vasayo 9 esperando terminacion de la fiesta para limpiar
Vasayo 9 termino de limpiar la sala
Vasayo 3 esperando terminacion de la fiesta para limpiar
Vasayo 3 termino de limpiar la sala
Caballero 1 llamando a vasayo
Vasayo 1 preparando sala
Caballero 1 festejando
Vasayo 1 esperando terminacion de la fiesta para limpiar
Vasayo 1 termino de limpiar la sala
En un reino medieval conviven 5 caballeros que deben compartir bajo exclusión mutua un único salón para festejar sus victorias en sus guerras. Para evitar solapar las fiestas de unos caballeros con las de otros el rey ha impuesto la siguiente política:
Cuando un caballero llega a su castillo tras una guerra desea festejarlo. Cada caballero dispone de un vasallo al que avisa para que consiga el salón y lo prepare a su gusto. Después, el caballero debe esperar a que su vasallo haya conseguido el salón y lo haya terminado de preparar, momento en el cual puede comenzar su fiesta. Entonces, el vasallo debe esperar a que el caballero le avise de que ha terminado la fiesta para proceder a limpiar el salón, dejando posteriormente el salón libre.
Output de la solucion :
Caballero 0 guerreando
Caballero 3 guerreando
Caballero 6 guerreando
Caballero 2 guerreando
Caballero 5 guerreando
Caballero 8 guerreando
Caballero 1 guerreando
Vasayo 2 esperando a guerrero
Caballero 4 guerreando
Vasayo 0 esperando a guerrero
Caballero 7 guerreando
Vasayo 3 esperando a guerrero
Vasayo 7 esperando a guerrero
Vasayo 8 esperando a guerrero
Caballero 9 guerreando
Vasayo 4 esperando a guerrero
Vasayo 1 esperando a guerrero
Vasayo 9 esperando a guerrero
Vasayo 6 esperando a guerrero
Vasayo 5 esperando a guerrero
Caballero 2 llamando a vasayo
Vasayo 2 preparando sala
Caballero 2 festejando
Caballero 4 llamando a vasayo
Vasayo 4 esperando para adquirir la sala (esperando 0)
Vasayo 2 esperando terminacion de la fiesta para limpiar
Vasayo 4 preparando sala
Vasayo 2 termino de limpiar la sala
Caballero 0 llamando a vasayo
Vasayo 0 esperando para adquirir la sala (esperando 0)
Caballero 4 festejando
Caballero 5 llamando a vasayo
Vasayo 5 esperando para adquirir la sala (esperando 1)
Vasayo 4 esperando terminacion de la fiesta para limpiar
Vasayo 4 termino de limpiar la sala
Vasayo 0 preparando sala
Caballero 0 festejando
Vasayo 0 esperando terminacion de la fiesta para limpiar
Vasayo 0 termino de limpiar la sala
Vasayo 5 preparando sala
Caballero 5 festejando
Vasayo 5 esperando terminacion de la fiesta para limpiar
Vasayo 5 termino de limpiar la sala
Caballero 8 llamando a vasayo
Vasayo 8 preparando sala
Caballero 8 festejando
Vasayo 8 esperando terminacion de la fiesta para limpiar
Vasayo 8 termino de limpiar la sala
Caballero 7 llamando a vasayo
Vasayo 7 preparando sala
Caballero 7 festejando
Vasayo 7 esperando terminacion de la fiesta para limpiar
Vasayo 7 termino de limpiar la sala
Caballero 6 llamando a vasayo
Vasayo 6 preparando sala
Caballero 6 festejando
Vasayo 6 esperando terminacion de la fiesta para limpiar
Vasayo 6 termino de limpiar la sala
Caballero 3 llamando a vasayo
Vasayo 3 preparando sala
Caballero 9 llamando a vasayo
Vasayo 9 esperando para adquirir la sala (esperando 0)
Vasayo 9 preparando sala
Caballero 3 festejando
Caballero 9 festejando
Vasayo 9 esperando terminacion de la fiesta para limpiar
Vasayo 9 termino de limpiar la sala
Vasayo 3 esperando terminacion de la fiesta para limpiar
Vasayo 3 termino de limpiar la sala
Caballero 1 llamando a vasayo
Vasayo 1 preparando sala
Caballero 1 festejando
Vasayo 1 esperando terminacion de la fiesta para limpiar
Vasayo 1 termino de limpiar la sala
martes, 13 de noviembre de 2007
Indexacion Arboles B Bases de Datos PHP
Etiquetas:
algoritmo,
arboles,
arboles b,
bases de datos,
binarios,
busqueda,
estructuras de datos,
listas,
recursividad
Existen dos tipos de almacenamiento:
La idea basica, es almacenar los datos en memoria secundaria, pero acceder directamente a ellos a traves de un indice que estara soportado por una estructura de datos, y no de forma secuencial.
El 80% del tiempo se pieder en el movimiento del cabezal. Se lee y se escribe Uble a Uble.
INDICE:
Tipos de indice
El patron o esquema general para el restablecimiento del equilibrio es el siguiente :
ROTACIONES SIMPLES
(I-I)
(D-D)
ROTACIONES DOBLES
(D-I)
(I-D)
A viendo visto todas estas estructuras de datos, pasaremos a estudiar los arboles B, indicando su ventajas mas importantes respecto a las estructuras anteriores.
ARBOLES B
Caracteristicas :
- Memoria Principal (RAM)
- Tiempo de acceso bajo
- Capacidad de almacenamiento bajo
- Es volatil
- Memoria Secundaria (HDD,DVD,..)
- Tiempo de acceso elevado (movimiento del cabezal)
- Capacidad de almacenamiento alto
- No es volatil
La idea basica, es almacenar los datos en memoria secundaria, pero acceder directamente a ellos a traves de un indice que estara soportado por una estructura de datos, y no de forma secuencial.
El 80% del tiempo se pieder en el movimiento del cabezal. Se lee y se escribe Uble a Uble.
INDICE:
- Estructura de acceso que se utiliza para acelerar el acceso a los registros; en respuesta a ciertas condiciones de busqueda.
- Ordenacion virtual del fichero que permite encontrar la informacion mas facilmente
Tipos de indice
- VECTORES
- Ventajas: Acceso a memoria, busquedas binarioas o dicotomicas.
- Inconvenientes: Limitacion de memoria, tamaño del vector (no son dinamicos), inserccion o borrado costosas
- LISTAS ENLAZADAS
- Ventajas: Acceso a memoria, no esta limitada de tamaño, actualizar una lista es menos costosa que un vector
- Inconvenientes: Limitacion de la memoria, la busqueda de los indices es secuencial
- ABB - BST (Arboles Binarios de Busqueda - Binary Search Tree)
- Ventajas: Acceso a memoria, el tamaño no esta limitado, busqeudas binarias
- Inconvenientes: Limitacion de la memoria, pueden degenerar en una lista (sumando asi los inconvenientes anteriores)
- APE (Arboles Perfectamente Equilibrados)
- Ventajas: Acceso a memoria, no tiene limitaciones de tamaño, busquedas binarias, no degeneran el una lista.
- Desventajas: Operaciones de reequilibrio muy costosas, mantenimiento de la informacion de equilibrio constantemente
- AVL
El patron o esquema general para el restablecimiento del equilibrio es el siguiente :
ROTACIONES SIMPLES
(I-I)
(D-D)
ROTACIONES DOBLES
(D-I)
(I-D)
- Ventajas: Acceso a Memoria, el tamaño del arbol no esta limitado, busquedas dicotomicas, actualizar este arbol es menos costoso, no degeneran en una lista, rotaciones menos costosas que el reequiibrio de APE
- Inconvenientes: Limitacion de la memoria, las rotaciones siguen siendo costosas, mantenimiento del factor de reequilibrio
A viendo visto todas estas estructuras de datos, pasaremos a estudiar los arboles B, indicando su ventajas mas importantes respecto a las estructuras anteriores.
ARBOLES B
Caracteristicas :
- Multicamino
- De busqueda (esta rodenado)
- Todas las hojas estan a la misma altura
- Crece hacia arriba, no necesita rotaciones
- MINIMO= 50% , todos los nodos contienen n claves
- MAXIMO= 100%, todos los nodos contienen 2n claves .
lunes, 5 de noviembre de 2007
Algoritmo de compresion HUFFMAN php
Etiquetas:
estadistica,
estructuras de datos
::link1:: Huffman Wikipedia(En)
::link2:: Informacion detallada del algoritmo
La idea que subyace detras del algoritmo es sencilla, primero se crea una tabla con las frecuencias para cada simbolo, se ordena segun su probabilidad, y luego se crea un arbol binario uniendo los nodos desde el primer lugar de a dos, sumergiendo asi los nodos con menos probabilidad de salir en el fondo del arbol, y dejando los nodos con mayor probabilidad en las ramas mas cercanas al nodo central.
Esta compresión sólo será óptima si las probabilidades de todos los símbolos de entrada son potencias enteras de 1/2. Y el peor de todos los casos se presentará cuando alguno de los símbolos posean una probabilidad cercana al 100%.
z(0.0357)u(0.0357)s(0.0357)p(0.0357)m(0.0357)e(0.0357)b(0.0357)
n(0.0714)h(0.0714)
i(0.1071)
c(0.1429)(0.1429)
o(0.2143)
Implementacion en PHP:
Una posible ejecucion del codigo seria:
::link2:: Informacion detallada del algoritmo
La idea que subyace detras del algoritmo es sencilla, primero se crea una tabla con las frecuencias para cada simbolo, se ordena segun su probabilidad, y luego se crea un arbol binario uniendo los nodos desde el primer lugar de a dos, sumergiendo asi los nodos con menos probabilidad de salir en el fondo del arbol, y dejando los nodos con mayor probabilidad en las ramas mas cercanas al nodo central.
Esta compresión sólo será óptima si las probabilidades de todos los símbolos de entrada son potencias enteras de 1/2. Y el peor de todos los casos se presentará cuando alguno de los símbolos posean una probabilidad cercana al 100%.
- Texto a comprimir = "pinocho se comio un bizcocho"
- Grafico de barras de Frecuencias
- Tabla de texto de frecuencias
- Reordenar la tabla en sentido ascendente
z(0.0357)u(0.0357)s(0.0357)p(0.0357)m(0.0357)e(0.0357)b(0.0357)
n(0.0714)h(0.0714)
i(0.1071)
c(0.1429)
o(0.2143)
- Ahora iremos uniendo cada dos elementos (empezando por los que tengan probabilidad mas baja de salir) y crearemos un nodo hijo en el lugar que acupaban estos; asi hasta que quede un lugar, este sera el nodo padre. Observamos que los nodos con menor probabilidad quedaran al final del arbol y los de mayor en las ramas cercanas a la raiz, esto implica que cuanto mas probabilidad de salir tenga un nodo, menor numero de bits le asignara el codigo, y cuanto menos probabilidad, mayor numero de bits; aqui reside la potencia de este algoritmo.
- Para obtener la tabla codificadora de cada elemento, realizaremos una busqueda en preorden por los nodos del arbol, asignando un "1" si bajamos por los hijos izquierdos o un "0" si bajamos por los hijos derechos.
Implementacion en PHP:
Una posible ejecucion del codigo seria:
viernes, 2 de noviembre de 2007
Polinomios interpoladores y el esquema de Shamir
Etiquetas:
calculo,
criptografia,
interpolacion polinomica
domingo, 28 de octubre de 2007
Aboles binarios de busqueda PHP Estructuras de Datos
Etiquetas:
arboles,
binarios,
estructuras de datos,
recursividad
Antes de nada :)
Binary tree (Arboles binarios): In computer science, a binary tree is a tree data structure in which each node has at most two children. Typically the child nodes are called left and right. One common use of binary trees is binary search trees; another is binary heaps.
El codigo fuente para representar cada uno de los nodos es el siguiente
Ahora el codigo que implementa la clase IntBST (Arbol Binario), se muestran las funciones y a continuacion las mismas funciones detalladas
Insert :
Preorder, inorder, postorder :
Binary tree (Arboles binarios): In computer science, a binary tree is a tree data structure in which each node has at most two children. Typically the child nodes are called left and right. One common use of binary trees is binary search trees; another is binary heaps.
El codigo fuente para representar cada uno de los nodos es el siguiente
Ahora el codigo que implementa la clase IntBST (Arbol Binario), se muestran las funciones y a continuacion las mismas funciones detalladas
Insert :
Preorder, inorder, postorder :
miércoles, 10 de enero de 2007
Miller-Rabin primality test
Etiquetas:
aritmetica,
calculo,
codigo,
criptografia,
estadistica,
php,
seguridad
From Wikipedia, the free encyclopedia
The Miller-Rabin primality test or Rabin-Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay-Strassen primality test. Its original version, due to Gary L. Miller, is deterministic, but it relies on the unproven generalized Riemann hypothesis; Michael O. Rabinprobabilistic algorithm.
The Miller-Rabin primality test or Rabin-Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay-Strassen primality test. Its original version, due to Gary L. Miller, is deterministic, but it relies on the unproven generalized Riemann hypothesis; Michael O. Rabinprobabilistic algorithm.
Suscribirse a:
Entradas (Atom)