Informatica

Programación

Organización de Archivos ( Mapas Conceptuales o mental

Es la técnica utilizada para representar almacenar registros en archivos llamados organización de archivos

Con Técnicas Fundamentales

                   -Secuencia

                   - Secuencial indexado

                   - Relativa o Directo

                   -Multi-llave

- La ordenación física de los registros almacenados

- El conjunto de operaciones necesarias para encontrar registros

Operaciones basicas

Creación

Actualización ( incluye)

Inserción de registros, Modificación, Supresión

Recuperación ( consulta y reportes)

Mantenimiento (Estructuración, Reorganización)

·         Organización de Archivos Secuencial

Definición: Procesamiento de los registros, no importando el orden que se haga, están organizados en forma de lista y se recuperan y procesan uno por uno y se denota con una marca de principio a fin, se usa un tipo de formato fijo, todos los registros tienen el mismo tamaño, en un orden particular se conoce la posición de cada campo secuencial.

-       Se Crea                   -Se Guarda

1

2

3

4

5

Ventajas y desventajas

Se accesa al siguiente registro en forma rápidamente, son sencillos de usar y de aplicar

Se realizan actualizaciones periodicas, por lotesque mezcla el archivo de registro con el registro maestro para producir un nuevo archivo en secuencia correcta de claves

·         Organización de Archivos Secuencial Indexado

Se utiliza este tipo de organización de archivó cuando existe la necesidad tanto de acceso registro con una llave que determina el orden en el cual son acezados los registros  es un campo de registro que sirve para identificarlo y diferenciarlo de otros registros y determinar el orden de acceso

Estructura lógica de archivos secuencial indexado

Se dispone de una tabla, en que aparecen ordenados secuencialmente los numerosa de la clave de archivos, y asociados a cada unos de ellos de la dirección del registro correspondiente

Matricula	Nombre	Apellidos	Dirección
1236563	Ma. Eugenia	Pasten	Ñlfjjfhsd
1232114	Alicia	Mendoza

·         Organización de Archivos Secuencial Directo

Se utiliza la organización relativa cuando existe la necesidad de accesar registro individuales directamente

En un archivo relativo existe una relación predecible

Ventas

Acceso directo

ARCHIVOS SECUENCIALES.

Un campo particular, generalmente el primero de cada registro se conoce como el campo clave. El campo clave identifica unívocamente al registro. así, los valores de la clave para registros diferentes son siempre diferentes.

Los archivos secuenciales son típicamente utilizados en aplicaciones de proceso de lotes Y son óptimos para dichas aplicaciones si se procesan todos los registros. La organización secuencias de archivos es la única que es fácil de usar tanto en disco como en cinta.

Organización de Archivos Secuenciales.

La manera básica de organizar un conjunto de registros, que forman un archivo, es utilizando una organización secuencial. En un archivo organizado secuencialmente, los registros quedan grabados consecutivamente cuando el archivo se usa como entrada.

Un archivo organizado secuencialmente es un conjunto de registros lógicamente relacionados cuya secuencia de acceso está determinada por su ordenamiento. Los registros deben ser grabados consecutivamente cuando el archivo es creado, y deben ser leídos de la misma manera cuando es usado posteriormente como entrada.

Actualización de archivos secuenciales.

Un archivo maestro representa un panorama estático de algún aspecto de una empresa. Sin embargo muchos de los aspectos de dicha organización no son estáticos, sino que continuamente ocurren cambios internos y/o externos que afectan directa o indirectamente a la empresa, como puede ser la contratación de personal, despidos, los ajustes de precios, etc. Para que un archivo pueda reflejar un estado actual lo más confiable posible, nuestro archivo debe ser actualizado.

Ventajas y Desventajas

La ventaja más importante de la técnica de organización secuencial de archivos es la capacidad de acceso al “siguiente” registro rápidamente: Mientras que el patrón de acceso a un archivo secuencial se conforme al ordenamiento de registros en el archivo, los tiempos de acceso serán muy buenos. Sin embargo, si el patrón de acceso al programa no se conforma al patrón de ordenamiento de los registros, entonces la eficiencia del programa puede ser terrible.

Otra ventaja de los archivos de organización secuencial es que son muy sencillos de usar y aplicar.

Almacenamiento De Archivos Secuenciales.

Los archivos secuenciales pueden almacenarse en dispositivos de acceso serial o directo. Con frecuencia los dispositivos de acceso serial son considerablemente menos caros que los dispositivos de acceso directo en un sistema de cómputo, pero de hecho, los dispositivos de almacenamiento de acceso directo en una computadora siempre proporcionan mayor capacidad de almacenamiento y acceso más rápido que los dispositivos de acceso serial.

Declaración De Archivos Secuenciales.

Casi todos los lenguajes proporcionan facilidades para declarar archivos secuenciales a continuación te presentamos un ejemplo en Pascal que bien puede ser aplicado a Delphi.

Program actualiza – maestro (reporte, movimientos, maestro – ent, maestro - salida);

Type registro – maestro = Record

   Número – empleado: 1…9999

   Nombre – empleado: packed array [1..25] of char;

   Departamento: packed array [1..5] of char;

   …

   end;

registro – movimiento = record

   tipo – movimiento: A,D;

   detalle: packed array [1..81] of char;

   end;

var reporte:text;

 movimiento: file of registro – movimiento;

 maestro – ent, maestro-sal: file of registro – maestro;

Creación de un archivo secuencial.

La creación de un archivo secuencial incluye la escritura de registros en una secuencia deseada dentro del medio de almacenamiento. La creación de un archivo secuencial de transacciones incluye la tarea de recolectar datos, convertir los datos a una forma legible para la máquina, editar los datos, convertir los movimientos rechazados y ordenar los datos editados.

Archivos de Reporte.

La creación de un archivo de reporte sigue el siguiente algoritmo:

Recuperación De Información De Archivos Secuenciales.

Método de Heap.

consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento

Arbol binario

Es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno

MÉTODO DE SHELL.

Ordenamiento de disminución incremental.

Nombrado así debido a su inventor Donald Shell.

Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento.

Después de que los primeros K subgrupos han sido ordenados (generalmente utilizando INSERCION DIRECTA), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.

Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado.

Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.

"Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos."

Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.

El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1.

Procedimiento Shell Sort;

const

MAXINC = _____;

incrementos = array[1..MAXINC] of integer;

var

j,p,num,incre,k:integer;

begin

for incre := 1 to MAXINC do begin /* para cada uno de los incrementos */

k := inc[incre]; /* k recibe un tipo de incremento */

for p := k+1 to MAXREG do begin /* inserción directa para el grupo que se encuentra cada K posiciones */

num := reg[p];

j := p-k;

while (j>0) AND (num < reg[j]) begin

reg[j+k] := reg[j];

j := j - k;

end;

reg[j+k] := num;

end

end

end;

MÉTODO BURBUJA.

El bubble sort, también conocido como ordenamiento burbuja, funciona de la siguiente manera: Se recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo va recorriendo de posición en posición hasta ponerlo en su lugar.

Procedimiento Bubble Sort

paso 1: [Inicializa i al final de arreglo] For i <- N down to 1 do

paso 2: [Inicia desde la segunda pos.] For j <- 2 to i do

paso 4: [Si a[j-1] es mayor que el que le sigue] If a[j-1] < a[j] then

paso 5: [Los intercambia] Swap(a, j-1, j).

paso 7: [Fin] End.

Tiempo de ejecución del algoritmo burbuja:

1.    Para el mejor caso (un paso) O(n)

2.    Peor caso n(n-1)/2

3.    Promedio O(n2)

MÉTODO DE SELECCIÓN.

El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo.

Procedimiento Selection Sort

paso 1: [Para cada pos. del arreglo] For i <- 1 to N do

paso 2: [Inicializa la pos. del menor] menor <- i

paso 3: [Recorre todo el arreglo] For j <- i+1 to N do

paso 4: [Si a[j] es menor] If a[j] < a[menor] then

paso 5: [Reasigna el apuntador al menor] min = j

paso 6: [Intercambia los datos de la pos.

min y posición i] Swap(a, min, j).

paso 7: [Fin] End.

Ejemplo:

El arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'].

Se empieza por recorrer el arreglo hasta encontrar el menor elemento. En este caso el menor elemento es la primera 'a'. De manera que no ocurre ningún cambio. Luego se procede a buscar el siguiente elemento y se encuentra la segunda 'a'.

Esta se intercambia con el dato que está en la segunda posición, la 's', quedando el arreglo así después de dos recorridos: a = ['a','a','o','r','t','i','n','g','e','x','s','m','p','l','e'].

El siguiente elemento, el tercero en orden de menor mayor es la primera 'e', la cual se intercambia con lo que está en la tercera posición, o sea, la 'o'. Le sigue la segunda 's', la cual es intercambiada con la 'r'.

El arreglo ahora se ve de la siguiente manera: a = ['a','a','e','e','t','i','n','g','o','x','s','m','p','l','r'].

De esta manera se va buscando el elemento que debe ir en la siguiente posición hasta ordenar todo el arreglo.

El número de comparaciones que realiza este algoritmo es :

Para el primer elemento se comparan n-1 datos, en general para el elemento i-ésimo se hacen n-i comparaciones, por lo tanto, el total de comparaciones es:

la sumatoria para i de 1 a n-1 (n-i) = 1/2 n (n-1).

METODO DE INSERCIÓN.

De cada elemento del arreglo para ser ordenado y lo compara con los que se encuentran en posiciones anteriores a la de él dentro del arreglo. Si resulta que el elemento con el que se está comparando es mayor que el elemento a ordenar, se recorre hacia la siguiente posición superior. Si por el contrario, resulta que el elemento con el que se está comparando es menor que el elemento a ordenar, se detiene el proceso de comparación pues se encontró que el elemento ya está ordenado y se coloca en su posición

Procedimiento Insertion Sort

Este procedimiento recibe el arreglo de datos a ordenar a[] y altera las posiciones de sus elementos hasta dejarlos ordenados de menor a mayor. N representa el número de elementos que contiene a[].

paso 1: [Para cada pos. del arreglo] For i <- 2 to N do

paso 2: [Inicializa v y j] v <- a[i]

j <- i.

paso 3: [Compara v con los anteriores] While a[j-1] > v AND j>1 do

paso 4: [Recorre los datos mayores] Set a[j] <- a[j-1],

paso 5: [Decrementa j] set j <- j-1.

paso 5: [Inserta v en su posición] Set a[j] <- v.

paso 6: [Fin] End.

Ejemplo:

Si el arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'], el algoritmo va a recorrer el arreglo de izquierda a derecha. Primero toma el segundo dato 's' y lo asigna a v y itoma el valor de la posición actual de v.

Luego compara esta 's' con lo que hay en la posición j-1, es decir, con 'a'. Debido a que 's' no es menor que 'a' no sucede nada y avanza i.

Ahora v toma el valor 'o' y lo compara con 's', como es menor recorre a la 's' a la posición de la 'o'; decrementa j, la cual ahora tiene la posición en dónde estaba la 's'; compara a 'o' con a[j-1] , es decir, con 'a'. Como no es menor que la 'a' sale del for y pone la 'o' en la posición a[j]. El resultado hasta este punto es el arreglo siguiente: a = ['a','o','s','r',....]

Así se continúa y el resultado final es el arreglo ordenado :

a = ['a','a','e','e','g','i','l','m','n','o','p','r','s','t','x']

Algoritmos de selección:

Se SELECCIONA o se busca el elemento más pequeño (o más grande) de todo el conjunto de elementos y se coloca en su posición adecuada. Este proceso se repite para el resto de los elementos hasta que todos son analizados.
SELECCION DIRECTA.

Algoritmos de intercambio:

Se toman los elementos de dos en dos, se comparan y se INTERCAMBIAN si no están en el orden adecuado. Este procesose repite hasta que se ha analizado todo el conjunto de elementos y ya no hay intercambios.

BURBUJA

QUICK SORT.

Algoritmos de inserción:

Los elementos que van a ser ordenados son considerados uno a la vez. Cada elemento es INSERTADO en la posición apropiada con respecto al resto de los elementos ya ordenados.

INSERCION DIRECTA

SHELL SORT,

INSERCION BINARIA

HASHING.

ALGORÍTMO

Conjunto de reglas para resolver un problema. Su ejecución requiere unos recursos.

Importancia

Los algoritmos son muy importantes a la hora de programar ya que son los pasos exactos para resolver un problema. Esto quiere decir que es un procedimiento computacional bien definido que requiere de datos de entrada y produce un valor como salida.     

Características

Las características fundamentales que debe cumplir todo algoritmo son:

·         Un algoritmo debe ser preciso e indicar el orden de realización de cada paso.

·         Un algoritmo debe estar definido. Si se sigue un algoritmo dos veces, se debe obtener el mismo resultado cada vez.

·         Un algoritmo debe ser finito. Si se sigue un algoritmo se debe terminar en algún momento; o sea, debe tener un numero finito de pasos.

Eficiencia: Relación entre los recursos consumidos y los productos conseguidos.

Un algoritmo es mejor cuantos menos recursos consuma, su facilidad de programarlo, corto, fácil de entender, robusto, etc.

Tiempo de Ejecución

• 1: la mayor parte de las instrucciones se ejecutan una o muy pocas veces (tiempo constante).
•  (logarítmico): desempeño típico de algoritmos que resuelven un problema de gran tamaño transformándolo en uno más pequeño, dividiéndolo mediante un fracción constante.

ARCHIVOS

Organización de Archivos Secuencial Directo

Se utiliza la organización relativa cuando existe la necesidad de accesar registro individuales directamente

Archivos Directos

Consiste en una colección de registros de longitud fija almacenados uno al lado del otro en un dispositivo de almacenamiento de acceso directo

Archivos de texto: Son aquellos que pueden contener cualquier clase de datos y de tal manera que son “entendibles” por la gente. Los datos en un archivo de texto se almacenan usando el código ASCII, en el cual cada carácter es representado por un simple byte. Debido a que los archivos de texto utilizan el código ASCII, se pueden desplegar o imprimir.

Archivos Binarios: Son aquellos que almacenan los datos numéricos con su representación binaria. Pueden ser archivos que contienen instrucciones en lenguaje máquina listos para ser ejecutados. Por ejemplo, cuando escribimos un programa en un lenguaje en particular (como C++, Pascal, Fortran, etc), tenemos las instrucciones almacenadas en un archivo de texto llamado programa fuente, pero una vez que lo sometemos a un proceso de compilación y ejecución nuestro programa lo trasladamos a un programa ejecutable (en lenguaje máquina),

Archivo Maestro: Es un conjunto de registros relacionados con un aspecto importante de las actividades de una organización. Por ejemplo, una organización de manufactura puede tener un archivo maestro de nómina, de clientes, personal, inventario, etc. Los

archivos maestros son útiles solo mientras se mantengan exactos y actualizados ya que reflejan el estado actual de eventos específicos o indicadores de la empresa y se logra por medio de transacciones.

Archivo de Transacciones: Es un archivo con dos propósitos acumular datos de los eventos al momento que ocurran y actualizar los archivos maestros para reflejar los  resultados de las transacciones actuales.  Los archivos de transacciones son temporales, ya que en algún momento ya no son necesarios y se borran o se destruyen.

Archivos de Reportes: Contiene datos que son formateados para su presentación al usuario. Pueden imprimirse o desplegarse en la pantalla. son archivos temporales

Archivos de Trabajo: Es un archivo temporal. No tiene las características de Entrada/Salida de un archivo de transacciones o de reporte, ni las de largo plazo del archivo maestro. Se utiliza regularmente para pasar datos creados de un programa a otro.

Organización de Archivos Secuencial Indexado

Se utiliza este tipo de organización de archivó cuando existe la necesidad tanto de acceso registro con una llave que determina el orden en el cual son acezados los registros  es un campo de registro que sirve para identificarlo y diferenciarlo de otros registros y determinar el orden de acceso

Estructura lógica de archivos secuencial indexado

Se dispone de una tabla, en que aparecen ordenados secuencialmente los numerosa de la clave de archivos, y asociados a cada unos de ellos de la dirección del registro correspondiente

Matricula	Nombre	Apellidos	Dirección
1236563	Ma. Eugenia	Pasten	Ñlfjjfhsd
1232114	Alicia	Mendoza

Archivos Secuenciales indexados

los registros están organizados en una secuencia basada en un campo.

Características

            -Un índice del archivo para soportar los accesos aleatorios

            provee una capacidad de búsqueda para llegar rapidamente a las proximidades          de un registro deseado

            -Un archivo de desbordamiento

             es similar al archivo de registro usado en un archivo secuencial, pero esta       intregrado de forma que los registros del archivo de desbordamiento se ubican en la dirección de un puntero desde si registro precedente.

             Los registros se almacenan según una secuencia física dada,

            Estructura de un archivo índice es la de un árbol de búsqueda binaria,

             D B G A C E J 1 2 3 Datos no ordenados D 1 B 2 G 3 A 4 C 5 D 6 J 7

               

Ventajas:

-       Permite procesar el archivo secuencialmente por orden lógico y también procesarlo al azar.

-       La organización secuencial indexada es conveniente para archivos con mediana volatilidad, actividad variable y tamaño relativamente estable.

Desventajas:

-       Los índices requieren espacio extra, se necesita una doble búsqueda; una en el índice y otra en el archivo.

-       Los registros deben ser de longitud fija.

-       El archivo debe estar separado por un dispositivo de acceso aleatorio; no se puede utilizar en cintas magnéticas.