Técnicas de Intercalación

La ordenación de datos por intercalación es un proceso muy frecuente en programación. Esta operación es también un proceso que las personas encuentran comúnmente en sus rutinas diarias. Por ejemplo, cada elemento de la colección de datos de una agenda telefónica tiene un campo nombre, dirección y un número de teléfono. Una colección de datos clasificados se puede almacenar en un archivo, un vector o tabla, una lista enlazada o un árbol. Cuando los datos están almacenados en vectores, tablas (arrays), lista enlazadas o arboles, la ordenación se denomina ordenación interna. Cuando los datos a clasificar se encuentran almacenados en archivos, en soporte de almacenamiento masivo (cintas o discos) el proceso de ordenación se denomina ordenación externa.

Es un proceso utilizado en sistema de actualización, y en casos en que es necesario varias listas ordenadas. También es la única forma que hay para el ordenamiento de archivos, debido a la imposibilidad de almacenarlos en memoria y a limitaciones en el tiempo, por la cantidad de elementos a ordenar.

Es el caso más simple, cuando se intercalan dos listas o archivos. Suponga que se tienen los arreglos ordenados A1 y A2 con elementos n1 y n2 respectivamente. Se desean intercalar en el arreglo A3.

El problema de ordenamiento se puede reducir a uno de intercalación. Si se quiere ordenar una lista muy grande, se puede pensar en subdividir esa lista en sublistas de un elemento, luego intercalar dos sublistas, para obtener sublistas ordenadas de dos elementos, luego de cuatro, etc., hasta obtener la lista ordenada, o tomar sublistas de L elementos, ordenarlas por cualquier algoritmo de ordenamiento y luego intercalarlas.

Existe diferentes tipos de métodos de intercalación, entre ellos se destacarán los siguientes:

Intercalación Simple: 

Se tienen dos archivos ordenados y se obtiene al final un solo archivo ordenado que contiene los elementos de los dos archivos iniciales.

Para utilizar el método se inicia con un vector de n posiciones. Comencemos con el subíndice i en la segunda posición incrementa en 1, el elemento del subíndice del vctor se elimina de la secuencia y se reinserta en el vector en la posición adecuada.

Árboles de cubrimiento de coste mínimo

Definición de árbol de cubrimiento: Sea G= (V, E) un grafo conexo con una función de costos definida sobre las aristas. Un árbol de cubrimiento para G  es un árbol libre que conecta todos los vértices en V. El costo de un árbol de cubrimiento es la suma de los costos de las aristas en el árbol.

Definición árbol de cubrimiento de mínimo costo: Sea G= (V, E) un grafo conexo con una función de costos definida sobre las aristas. Sea A= (V, F) [F  E]  un árbol de cubrimiento para G, A es un árbol de mínimo costo para G si no existe para G otro árbol de cubrimiento cuyo costo sea menor que el costo de A.

Propiedad de los árboles de cubrimiento de mínimo costo: Sea G= (V, E) un grafo conexo con una función de costos definida sobre las aristas. Sea U un subconjunto propio de V [U  V]. Si uv es una arista de menor costo tal que u  U y v  V-U entonces existe un árbol de cubrimiento de mínimo costo que incluye uv como una de sus aristas.

Demostración: Supongamos que no existe para G un árbol de mínimo costo que incluya a uv. Sea  A' un árbol de mínimo costo para G. Como A' es un árbol si añadimos uv a A' entonces introducimos un ciclo en A'. De esto se deduce que existe otra arista u'v' en A' tal que u'  U y v'  V. Si quitamos u'v' de A' entonces eliminamos el ciclo y obtenemos un árbol A cuyo costo no es mayor que el costo de A porque asumimos por hipótesis que costo ( uv ) = costo(u'v'). Ésto entra en contradicción con lo supuesto.

Dos algoritmos para construir árboles de cubrimiento de mínimo costo para grafos no dirigidos, conexos y con costos sobre las aristas.

Algoritmo de Kruskal[1956]

El algoritmo de Kruskal construye el árbol de mínimo costo haciendo una iteración sobre el conjunto de las aristas del grafo. Se considera primero que el  conjunto de las aristas del árbol a formar está vacío (F= { }).También se considera inicialmente el conjunto de vértices como árboles aislados, componentes conexas por sí mismos del árbol a construir. Entonces en cada paso se halla una arista de mínimo costo que conecte a dos componentes conexas diferentes y se le añade a F, formándose así una nueva componente conexa. Cuando todos los vértices pertenezcan a una misma componente entonces ésta es el árbol de cubrimiento de mínimo costo para el grafo dado.

Su explorador no es compatible con Java. El applet no se puede mostrar.

¿Por qué funciona el algoritmo de Kruskal?

En el algoritmo de Kruskal se considera inicialmente cada vértice como un árbol, una componente conexa por sí mismo. Éstos son además árboles de cubrimiento de mínimo costo para el grafo compuesto solamente por ellos puesto que un vértice es también un grafo. Entonces inicialmente tenemos n (n: número de vértices del grafo inicial) árboles de cubrimiento de mínimo costo, componentes conexas. En cada paso elegimos una arista de menor costo que conecte dos componentes conexas, entonces se forma una nueva componente conexa que es también un árbol de mínimo costo del grafo formado con los vértices de las dos componentes conexas involucradas, puesto que hasta el paso anterior estas componentes eran árboles de mínimo costo y la arista hallada es una de las de menor costo que conecta ambas componentes, no existe otra arista con un costo menor que la elegida que conecte las dos componentes conexas.

Orden del algoritmo de Kruskal 

Nuestra implementación del algoritmo hace uso de una cola con prioridad para ordenar las aristas antes de comenzar a construir el árbol. Las operaciones de crear, insertar las aristas y ordenar la cola con todas las aristas toma O(e log( e ) ) (e: número de aristas) operaciones. En cada iteración se extrae una arista de la cola con prioridad, acción que toma O( log( e ) ) operaciones. Entonces en el peor de los casos, se da cuando la última arista es una arista de menor costo del árbol, el algoritmo tomará un tiempo de orden O(elog(e)) .

Algoritmo de Prim[1957]

Supongamos V= {1, 2,.., n}. El algoritmo de Prim comienza iniciando el conjunto U en cualquier vértice v  V del grafo, tomemos por ejemplo U= {1}. Entonces se construye el árbol de cubrimiento, añadiendo una arista en cada paso, de la manera siguiente:

1. En cada paso buscamos la arista de menor costo (u, v) que conecta U y V-U, entonces se añade al conjunto de aristas F E del árbol, y se añade el vértice v  V-U a U.
2. Se repite el paso 1 hasta que U = V.

El applet no se puede mostrar pues su explorador no es compatible con Java

¿Por qué funciona el algoritmo de Prim?

Este algoritmo es una aplicación directa de la propiedad de los árboles de cubrimiento de mínimo costo: En el primer paso buscamos una arista de menor costo y el árbol formado hasta el momento es de mínimo costo. De manera inductiva notemos que si hasta el paso n-1 tenemos un árbol de mínimo costo con los vértices de U y las aristas halladas, entonces, añadiendo en el paso n la arista de menor costo que conecta U con V-U, seguiremos teniendo un árbol de mínimo costo en U. En el paso n el conjunto de los vértices del árbol obtenido es igual al conjunto de los vértices del grafo (U = V), luego este árbol es de mínimo costo para el grafo en cuestión.

Orden del algoritmo de Prim 

Nuestra implementación del algoritmo hace una iteración sobre cada uno de los vértices en V-U y los añade a U hasta que U = V, por aquí tenemos n operaciones  (n: número de vértices). Por cada una de estas operaciones tenemos que hallar una arista de menor costo (u, v) u pertenece a U y v pertenece a V-U, es decir, una arista que una el árbol que se va formando, con los vértices de U y las aristas halladas, a uno de los vértices restantes (V-U). La búsqueda se puede facilitar si desde el principio vamos archivando las aristas de menor costo que conectan a U con los vértices en V-U y en cada paso vamos rectificando, a medida que se le van añadiendo vértices a U. Como en cada paso tenemos que ir rectificando el archivo, esto nos tomará O(n) operaciones en el mejor de los casos. Por tanto, este algoritmo es de orden O(n²).

 Comparación entre los algoritmos de Prim y Kruskal

Los algoritmos de Prim y Kruskal toman un tiempo de orden O(n²) y O(elog(e)) respectivamente (n, e: número de vértices y aristas del grafo, respectivamente). Por ésto si el grafo es denso, tiene muchas aristas con respecto a la cantidad de vértices   (e ≈ n² ó e > n²), es aconsejable utilizar el algoritmo de Prim, de lo contrario, cuando la cantidad de aristas sea  pequeña con respecto a los vértices (e <= n²), es mejor aplicar el algoritmo de Kruskal.

Dsipositivos de almacenamiento magneticos

Disco magnético
Las Unidades de Disco Magnético son un periférico de almacenamiento que utilizan un disco magnético como soporte físico de la información. Estas unidades nos permiten leer la información que esta ya grabada en el disco (de entrada) y escribir información en el disco (de salida). Los discos magnéticos son el principal medio de almacenamiento que utilizan los ordenadores, brindando un acceso directo a los datos en forma aleatoria. El disco puede dividirse en:

* Caras: En un disco es posible leer y escribir información en sus dos caras (la primera cara es la numero 0 y la segunda el 1). Los discos duros pueden tener múltiples platos, cada uno de ellos con dos caras, numeradas 0, 1, 2, 3, etc.

* Pistas: Las caras de un disco se divide según círculos concéntricos. La pista de mayor radio en cada cara es la 0. Así tenemos la pista 0 cara 0, y la de la otra cara pista 0 cara 1.

* Cilindros: Las pistas de igual radio de un disco reciben el nombre colectivo de cilindro. Si usted coloca uno encima de otro obtiene un cuerpo que semeja la forma de una lata sin tapa ni fondo - un cilindro. En un disco flexible un cilindro contiene únicamente 2 pistas.

* Sectores: Se llama sector de un disco, una parte en forma de cuña del mismo. Cada sector está numerado. Todas las pistas de un disco se dividen en un mismo número de sectores, todos de igual área. El número de sectores por pistas varía con el tamaño de disco. Ej: en un disquete de 5 1/4" hay 40 pistas con 9 sectores cada una. En un disquete de 3 1/2" hay 80 pistas con 9 sectores cada una.

A los discos magnéticos se los puede clasificar en:

• Discos Rígidos o Duros.
• Discos Flexibles o Disquete o Floppy Disk

a) Discos Magnéticos rígidos

Por dentro, los discos rígidos son un conjunto de platos separados uno de otro por una distancia que permita la existencia de una cabeza lectora - grabadora por superficie, por simplicidad, las cabezas se mueven al mismo tiempo.

b) Disquetes

Los discos flexibles están hechos de material plástico de Mylar, recubierto de una capa de oxido magnético, poseen un agujero central que les sirve para encajar en el mecanismo de rotación, y un pequeño agujero de control es sus proximidades, que sirve como índice para referenciar el comienzo de cada pista.

Cinta magnética

Este medio (la cinta magnética) sirve para el tipo de organización de archivo secuencial ya que cada registro se graba a continuación de otro. Para acceder a cualquiera de ellos es necesario recorrer los anteriores. La organización física de cada sector grabado se hace en función de un agrupamiento lógico de registros, separados por un trozo de cinta sin grabar (GAP). Este espacio es necesario para producir la aceleración de la cinta desde cero hasta la velocidad óptima de lectura y luego disminuirla a cero cuando esta se efectuó.

Cada Cinta tiene al inicio y al final algunos metros sin utilizar, con marcas especiales que indican el comienzo (BOT, Begining Of Tape) y al final (EOT, End Of Tape).

La grabación se efectúa en 7 o 9 pistas, con una determinada densidad (bytes por pulgada) y la unidad encargada de su lectura y grabación tiene un principio de funcionamiento similar al de los grabadores comunes.

La misma cinta magnética puede ser reutilizada para almacenar nueva información, sin más que escribir encima de la información anteriormente grabada. El costo por unidad de información es muy bajo.