End.

I started this blog many years ago, and i posted new notes while i studied my engineer degree.

Now, it is time to close.

Best regards.

Twitter network viz march 2011 ipad2 launch

In this video, we present the network evolution around March iPad 2 launch conversation.

Data was collected using twitter real-time API, on March 2nd, 2011, totalling around 50k tweets+retweets

Nested loop optimized with Java Iterators

Few days ago, i saw a piece of a geoprocessing algorithm code. This algorithm get a vector of points, each point with two spatial coordinates: (x,y), and calculate the euclidean distance between of each point with the whole points of the vector. The result is a beatifull matrix of distance between each points.

The problem was the follow: this algorithm use "Iterators" on the vector, as follows:

Iterator i1=layer.iterator();
while(i1.hasNext()){
i1.next();
Iterator i2=layer.iterator();
while(i2.hasNext()){
i2.next();
// calculate Euclidean distance
}
}

but it has a problem in optimization terms, because the distance between point #1 and point #2 is the same that between point #2 and point #1, i.e.,an optimized algorithm only need compute the superior diagonal of the matrix, beacuse the matrix of distances is simetric.

In above sample, with optimized algorithm, we need 3 iterations on the vector and symmetrize the matrix; in the other hand without optimization we need 9 iterations: n^2.

If we assume that the objects in the vector are unique, the best solution in order of do not lose the semantic of Iterators is the use the follows code:

Iterator i1 = l.iterator();
while (i1.hasNext()) {
Integer ii1 = (Integer) i1.next();
Iterator i2 = l.subList(l.indexOf(ii1),l.size()).iterator();
while (i2.hasNext()){
i2.next();
}
}

If we use two index in order to follow the loops, we can use the follows code:

int i=0;
Iterator i1 = l.iterator();
while (i1.hasNext()) {
c=0:
Integer ii1 = (Integer) i1.next();
Iterator i2 = l.subList(i,l.size()).iterator();
while (i2.hasNext()){
i2.next();
long distance = ....
matrix[i][j] = distance;
matrix[j][i] = distance;
c++;
}
i++;
}

In this way we can reduce the computing time in n/2.

Smart pointers. shared_ptr and normal pointer

Shared pointer can make our code more secure. shared_pointer is a kind of pointer that allow to others pointer share his container. And when no pointer points to a container, the garbage collector erase the container thus ensuring the reliable of the program in order to no consume the heap of the process.

If we use the next code, the above behaviour.

The follow code show the common error, creating new pointers and not erase the container.


If we compile and execute this two codes, we obtain the next statistical result:

snGraph. Optimal software to manage scale-free networks

snGraph package provides a flexible and efficient tool for manage graphs representing scale-free network. Can be integrated into others informatic systems. It can be read easily from databases, for example using Hibernate, and build graphs using models. It can serve of bridge between data and software in order to make analisis, for example we can use Ucinet. Also permite design and implement new custom algorithms.

[Link to software and documentation]

Caminar los sueños

La rutina es un papel de lija que desgasta las ilusiones. Demasiadas veces lo cotidiano nos conduce a la monótona repetición de conductas, conversaciones y escaramucillas sin vuelo que transforman las hojas de nuestro calendario en un libro sin texto. Por el contrario, las ilusiones conseguidas son aquellas que quedan impresas para siempre en el libro del mejor recuerdo, esas épocas en las que tomamos conciencia de que el auténtico nivel de vida no lo da ni depende del dinero, sino de la felicidad, ese sentimiento que surge cuando lo soñado y lo vivido transcurren paralelos como los raíles del ferrocarril.

Por eso siempre hay que llevar una doble vida: la despierta y la soñada.

La vida despierta es ese obligado aterrizaje en el suelo duro que nos conduce a través de caminos proyectados por intereses ajenos, cuanto más masivos mas semáforos, radares, velocidades limitadas y direcciones prohibidas.
La vida soñada es la que nos impulsa a salir de lo establecido y nos anima a idear, imaginar,......elevarnos para buscar nuestros propios horizontes.
En una vida completa, soñar y caminar son vasos comunicantes, porque el ave no puede estar siempre volando, pero alzarse le permite divisar, entender, y porque no, ambicionar otros panoramas.

En el suelo reposa lo conocido y cotidiano; en el vuelo despega el sueño y la sana ambición.
La felicidad es caminar los sueños.

Ángela Becerra, ADN, 9 Junio 2010.
abecerra@adn.es

Parallel algorithms. Java threads. Using multiple cores.

Today, computar machines has a multiples cores into his processors. The main problem is that the software engineers do not design the software accord this situation because they ignore this new technology or simply because they doesn´t want design parallel algorithms. This problem imply that the multiple core machines are underused.

I propose a simple problem: Adding an integer array of ten million positions with a due core machine.

1. Only one process
2. Four threads. A piece of vector by thread
3. Two threads. A piece of vector by thread

The results:

Java Readers and Writer. Mutual exclusion.

Think about this situation, you have a buffer and into the bufer has one data. We have several elements in this situation: One Writer, that provide tha data into the buffer, and many Readers, thtat need the data into the buffer; and one restriction, only one persona can read or write into the buffer at the same time.

In order to resolve this problem we can use a Monitor. A monitor is a Class that provide a mutual exclusion in this methods. To write this in Java, we can introduce the keyword synchronized in the method. For ejample, in Buffer.java:




We can see complete execution over Main class



Output:

run:
Reader 0 is waiting to get data (total buffer=0)
Reader 9 is waiting to get data (total buffer=0)
Reader 8 is waiting to get data (total buffer=0)
Reader 7 is waiting to get data (total buffer=0)
Reader 3 is waiting to get data (total buffer=0)
Reader 6 is waiting to get data (total buffer=0)
Reader 2 is waiting to get data (total buffer=0)
Reader 1 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 0 unlock
Reader 0 has read a data (buff=0)
........reader 9 unlock
Reader 9 is waiting to get data (total buffer=0)
Reader 4 is waiting to get data (total buffer=0)
Reader 5 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 8 unlock
Reader 8 has read a data (buff=0)
........reader 7 unlock
Reader 7 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 3 unlock
Reader 3 has read a data (buff=0)
........reader 6 unlock
Reader 6 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 2 unlock
Reader 2 has read a data (buff=0)
........reader 1 unlock
Reader 1 is waiting to get data (total buffer=0)
Reader 28 is waiting to get data (total buffer=0)
Reader 29 is waiting to get data (total buffer=0)
Reader 20 is waiting to get data (total buffer=0)
Reader 11 is waiting to get data (total buffer=0)
Reader 13 is waiting to get data (total buffer=0)
Reader 16 is waiting to get data (total buffer=0)
Reader 27 is waiting to get data (total buffer=0)
Reader 10 is waiting to get data (total buffer=0)
Reader 18 is waiting to get data (total buffer=0)
Reader 24 is waiting to get data (total buffer=0)
Reader 23 is waiting to get data (total buffer=0)
Reader 17 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 9 unlock
Reader 9 has read a data (buff=0)
........reader 4 unlock
Reader 4 is waiting to get data (total buffer=0)
Reader 21 is waiting to get data (total buffer=0)
Reader 22 is waiting to get data (total buffer=0)
Reader 19 is waiting to get data (total buffer=0)
Reader 12 is waiting to get data (total buffer=0)
Reader 25 is waiting to get data (total buffer=0)
Reader 26 is waiting to get data (total buffer=0)
Reader 14 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 5 unlock
Reader 5 has read a data (buff=0)
........reader 7 unlock
Reader 7 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 6 unlock
Reader 6 has read a data (buff=0)
........reader 1 unlock
Reader 1 is waiting to get data (total buffer=0)
Reader 15 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 28 unlock
Reader 28 has read a data (buff=0)
........reader 29 unlock
Reader 29 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 20 unlock
Reader 20 has read a data (buff=0)
........reader 11 unlock
Reader 11 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 13 unlock
Reader 13 has read a data (buff=0)
........reader 16 unlock
Reader 16 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 27 unlock
Reader 27 has read a data (buff=0)
........reader 10 unlock
Reader 10 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 18 unlock
Reader 18 has read a data (buff=0)
........reader 24 unlock
Reader 24 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 23 unlock
Reader 23 has read a data (buff=0)
........reader 17 unlock
Reader 17 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 4 unlock
Reader 4 has read a data (buff=0)
........reader 21 unlock
Reader 21 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 22 unlock
Reader 22 has read a data (buff=0)
........reader 19 unlock
Reader 19 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 12 unlock
Reader 12 has read a data (buff=0)
........reader 25 unlock
Reader 25 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 26 unlock
Reader 26 has read a data (buff=0)
........reader 14 unlock
Reader 14 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 7 unlock
Reader 7 has read a data (buff=0)
........reader 1 unlock
Reader 1 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 15 unlock
Reader 15 has read a data (buff=0)
........reader 29 unlock
Reader 29 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 11 unlock
Reader 11 has read a data (buff=0)
........reader 16 unlock
Reader 16 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 10 unlock
Reader 10 has read a data (buff=0)
........reader 24 unlock
Reader 24 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 17 unlock
Reader 17 has read a data (buff=0)
........reader 21 unlock
Reader 21 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 19 unlock
Reader 19 has read a data (buff=0)
........reader 25 unlock
Reader 25 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 14 unlock
Reader 14 has read a data (buff=0)
........reader 1 unlock
Reader 1 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 29 unlock
Reader 29 has read a data (buff=0)
........reader 16 unlock
Reader 16 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 24 unlock
Reader 24 has read a data (buff=0)
........reader 21 unlock
Reader 21 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 25 unlock
Reader 25 has read a data (buff=0)
........reader 1 unlock
Reader 1 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 16 unlock
Reader 16 has read a data (buff=0)
........reader 21 unlock
Reader 21 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 1 unlock
Reader 1 has read a data (buff=0)
........reader 21 unlock
Reader 21 is waiting to get data (total buffer=0)
The writer is writing data (buffer:1)
........reader 21 unlock
Reader 21 has read a data (buff=0)
The writer is writing data (buffer:1)
The writer is writing data (buffer:2)
The writer is writing data (buffer:3)
The writer is writing data (buffer:4)
The writer is waiting to write data. The buffer is full

Java Process and Threads. TCP Java Server.

This post try it to explain how to manage Process, Threads and concurrence.

The main goal is explain how is a thread, and how is a process.
We can explain very well this topics with follow ilustration of Tanenbaum book :


The ilustration show in a) case three process with one thread into each one, in case b) we can see ONE process with three threads into the unique process.
The main diference between Process and Thread is that the thread is more ligth than a Process in order of the Threads works in the details of thw Process`s work and it can share the Thread stack with the others Threads.

A very good example of Process and Threads can be a Server and a Client.The server will be a Process wich accepts requests of a clients. Whe it accept one request, will create a Thread to give service to a client request.
We need three JavaClass: Server.java, Process.java and Cliente.java.

Server class create a s = new ServerSocket(9000); and wait to accept conecctions. When a conecction from a Cliente is coming, the server instance one Process with Procesador proc = new Procesador(cont,s.accept()); proc.start();

In this moment, Server is waiting for a new incoming conecction, and his Thread Process is working with the cliente conecction. The Processador read, operate and request the conecction cliente: b = new BufferedReader( new InputStreamReader ( sc.getInputStream() ) ); , p = new PrintStream ( sc.getOutputStream() );

Now, only need the Cliente operations: it´s simple, only create a socket s = new Socket(host,port); and write the request to a server.
We can see the result.




One iteration between Server and two clients:

One cliente close the conecction, but the oher cliente is coneccted and work in the server.



The client #3 executed two operations in the server and close conecction. Really close the Process Thread.

¿Existe el tiempo?

La idea de que el tiempo es un modo de decir que una cosa sigue a otra como resultado de esta otra, parece que es la clave de la verdadera naturaleza del tiempo.

Leer más: http://recuerdosdepandora.com/filosofia/existe-el-tiempo/#ixzz0je5PbnJ7

Caos que vino del orden el efecto mariposa

Caos que vino del orden: el efecto mariposa

Java Graph Package

This Java Class provide an interface to work with graphs (Direct an Undirect raphs). You can get output format to generate "bmp" graphs with Graphviz.

PROJECT HOME

JAVADOC

Step sample:


1. Import class


2. Code



3. Get results




4. Generate graph with output String Graphviz

El gen egoista

Floyd algorithm

The problem: We have a Graph, no direct and valued, also, we have a vector with N stages. For example, one stage is between nodes 2 and 5, other stage is between nodes 5 and 1 , ect ...
We need the minimun path between first stage and last stage through the middle stages in order.

The solution: We use, Floyd algorithm.

The graph:


The stages :



The output:

I propose new algorithm problem about rated digraphs

The goal: We should get the minimun value way betwen two nodes, with follows constrains:

1. * The total path value is the sum of the edges in the A->B direction plus double value of B->A direction (if exists) .
2. The graph it´s representated by a adjacency matrix .

A graph example :

One possible solution is: 1->2->3->4 with total path value* 10 (1->2 [4] 2->3 [5] 3->4 [10])

Download pascal code
(You need stack estructure [easy to computer engineer ;)])

Against Intellectual Monopoly

Java Random Double in Range Generation

Estos días he estado pensando sobre como generar números aleatorios en Java dentro de un rango, pues bien, aquí esta mi solución y su análisis:



Así, analizando los valores límite, observamos:

max(0.0)+min(1-(0.0)) => min
max(0.5)+min(1-(0.5)) => (max+min)/2
max(1.0)+min(1-(1.0)) => max

De una manera gráfica, observamos como los valores están siempre encerrados dentro de los límites:


Un análisis matemático de ajuste.

Aquí un histograma con 100000 valores generados aleatoriamente, se puede observar como sigue una distribución uniforme.

Con un rango en la escala negativa.

Algorithms

+

MIT - Mathematics

+

EUI UPM Algoritmica

Algorítmica en php - The Knight's Tour

El juego de The Knight's Tour

En un post anterior explicaba el algoritmo minimax (como introducción a la poda alfa-beta). Ahora veremos un poco de algorítmica, mas concretamente el backtracking. Podría decirse (a groso modo) que sería una busqueda minimax o poda alfa-beta pero sin heurística, además, el backtracking nos asegura que siempre encontrará la solución (si la hay) recorriendo así todos los estados posibles.

En wikipedia podemos obtener las reglas y una explicación de su complejidad, excelentes.

Pongo la implementación en PHP como una primera aproximación para la resolución del problema (La implementación la he realizado en php y orientada a objetos para que sea mas facil comprender el proceso de backtracking, evidentemente, no persigo eficiencia).


Backtraking




El software dispone de modo traza para ver los pasos de "vuelta atrás"



Algunos tiempos de ejecución en mi ordenador:

• Tablero 4x4 => 0.19897794723511 seg.
  

• Tablero 5x5 => 39.455229997635 seg.

• Tablero 6x6 => 364.00200605392 seg.

• Tablero 7x7 => 39521.259037971 segundos

• Tablero 8x8 => aún ejecutándose :)

Se observa (sin analizar matemáticamente la complejidad del algoritmo) su complejidad claramente exponencial.

Curva de Bézier

Teoría de códigos

Introducción práctica a la teoría de códigos

Probabilidad

El origen de la probabilidad

The Singularity Is Near

Inteligencia Artificial - MINIMAX - Clisp

Descargar Codigo Fuente / Download Source Code

En el juego de restar cuadrados, dos jugadores juegan por turno restando cuadrados de números de una cantidad inicial, elegida al azar entre 10 y 1000. El siguiente turno partirá de la cantidad resultante de restar el cuadrado elegido a la cantidad, y así sucesivamente.

Por ejemplo, si la cantidad elegida es 17 y juega MAX, éste tendrá cuatro movimientos posibles: restar 4*4, quedando 1, restar 3*3, quedando 8, restar 2*2, quedando 13, o restar 1*1, quedando 16.

MAX y MIN juegan por turno y pierde el que no pueda realizar más movimientos, es decir, cuando la cantidad sea igual a 0.

Ejemplos de partida, partiendo de 13 y jugando MAX:

Partida 1:
MAX juega 2*2, quedan 9
MIN juega 3*3, MAX pierde

Partida 2:
MAX juega 1*1, quedan 12
MIN juega 3*3, quedan 3
MAX juega 1*1, quedan 2
MIN juega 1*1, queda 1
MAX juega 1*1, MIN pierde

--

Las máquinas del futuro, ¿podrán llegar a ser conscientes?

http://www.redcientifica.com/doc/doc200302140312.html

--

Ecole Nationale Supérieure des Télécommunications

Allá voy al curso: "Scientific Research Method : Techniques, Models and Practices" .........


Ver mapa más grande

Who Killed the Software Engineer? (Hint: It Happened in College)

http://itmanagement.earthweb.com/career/article.php/11067_3722876_1

http://picandocodigo.net/index.php/2008/01/22/seguimiento-de-%c2%bfdonde-estan-los-ingenieros-del-manana/

A conversation with Robert Dewar is enough to make you wonder about the future of the American software engineer. Dewar, a professor emeritus of computer science at New York University, believes that U.S. colleges are turning out programmers who are – there’s no nice way to say this – essentially incompetent.

To support his claim, Dewar penned a scathing broadside decrying today’s college-level computer science training. (The article was co-authored by Edmond Schonberg, also a CS professor emeritus at NYU.) Entitled Computer Science Education: Where are the Software Engineers of Tomorrow?, the widely read article has prompted heated discussion throughout the tech industry ............

Sistemas justo a tiempo

Just in Time es un término inglés que significa Justo a tiempo. Es un sistema de organización de la producción para las fábricas, de origen japonés.

Las compañías japonesas que durante los últimos años han adoptado el "método Toyota" o JiT han aumentado su productividad en los últimos 20 años.

Wikipedia

Descargar Sistema Justo a Tiempo
Toyota

Calidad total en Informatica

La calidad se define como total por suponer la plena implicación de todos los miembros de la empresa y de todos los aspectos relacionados con la organización de ésta. Esto incluye la implicación de todos los miembros de la empresa en mejorar la calidad continuamente, por lo que la calidad se intenta obtener en todo lo relacionado a la organización, no exclusivamente en el producto o servicio.

A lo que mercadotecnia se refiere, la calidad está directamente relacionada con la satisfacción del cliente, así es que se dice que a mayor satisfacción del cliente, el producto o servicio prestado adquiere mayor grado de calidad.

Wikipedia

Descargar la Calidad total en Informatica

El Omnipresente Árbol-B

Por DOUGLAS COMER. Departamento de Ciencia Computacional, Universidad de Purdue, West Lafayette, Indiana 47907

Los árboles B han llegado a ser, de hecho, un estándar para la organización
de ficheros. Los ficheros dedicados a usuarios, a sistemas de base de datos, y
a métodos de acceso de propósito general, han sido propuestos e implementados
usando árboles-B.
Palabras clave y Expresiones: Árbol-B, Árbol-B*, Árbol-B+, organización de fichero, índice.
Categorías CR: 3.73 3.74 4.33 4.34

DESCARGAR

Este documento ha sido traducido para la asignatura de Estructuras de Datos II, de la Escuela Universitaria de Informática - UPM

Indexacion Java, Estructura de Datos

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 .

• Gestion de fichero de datos indexado mediante ArbolB
• Codigo Fuente

Parte 2: Mantenimiento de una lista enlazada con nodos en una estructura de datos en disco

• Indexacion con lista enlazada
  
• Codigo Fuente

Anexos :

• Métodos de las Clases InputStream y OutputStream

--

Java sincronizacion concurrente

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.

• La solucion en JAVA se puede descargar aqui

• La solucion en PASCAL-CONCURENT se puede descargar aqui

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

Indexacion Arboles B Bases de Datos PHP

Existen dos tipos de almacenamiento:

1. Memoria Principal (RAM)
   

• Tiempo de acceso bajo
• Capacidad de almacenamiento bajo
• Es volatil
  

1. 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

Casos de desequilibrio, rotaciones





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

Su factor de ocupacion

• MINIMO= 50% , todos los nodos contienen n claves
• MAXIMO= 100%, todos los nodos contienen 2n claves .