Algoritmos y Estructuras de DatosAlgoritmo: Secuencia finita de pasos para resolver un problema. En el caso de nuestro estudio para resolverlo o aplicarlo es necesaria una mquina real, una computadora (que posee particularidades especiales). Para que un algoritmo pueda ejecutarse siempre debemos traducirlo a un lenguaje de programacin, como Basic, Pascal, etc. Para resolver el problema en cuestin, en nuestro estudio no se toman en cuenta ni el lenguaje a utilizar ni la mquina en la que ser ejecutado al algoritmo, en vez de ello se piensa que el algoritmo ser ejecutado en una mquina ideal abstracta y el lenguaje que utilizaremos se denomina pseudocdigo. Accin: Acontecimiento producido por un actor. Tiene lugar durante un perodo de tiempo finito y produce resultados bien definidos y precisos. Clasificacin de Acciones: Pura Asignacin Simples Accin elemental Acciones Accin con nombre Simples Estructuradas Condicionales Cclicas Alternativas Seleccin mltiple Pre-Test (Mientras) Pos-Test (Repetir) Manejadas por contador (Para) Acciones Simples: Asignacin: es la accin que da valor a una expresin, a una variable es la accin de transferir un contenido. El operador de asignacin es: :=. Expresin: Es la reunin de datos (constantes y variables) relacionadas mediante operadores. Acciones Elementales: Es la ejecucin de un acontecimiento elemental. Es una accin que aparece en el algoritmo por su nombre, ejemplo: Leer() o Escribir(). Acciones Estructuradas: Accin con nombre: Es la incorporacin de un nombre al repertorio finito de acciones. Para incorporar el nombre al repertorio es preciso proporcionar al nuevo nombre la especificacin de la accin y el texto que constituye su descripcin. AccinNombrees; Accin1 Accin2 ... Accinn FAccin1

Funcionales Algebraicas

Expresin

Incrementales Contador Acumulador

Condicionales: Simples: Es la ejecucin condicional de una accin. La composicin condicional permite expresar que no es necesario provocar un cierto acontecimiento ms que bajo una determinada condicin. SiCondicinentonces Accin FSi Alternativas: Es la ejecucin alternativa de una entre dos acciones, la composicin alternativa permite expresar que debe provocarse un acontecimiento bajo una determinada condicin u otro bajo la condicin contraria. SiCondicinentonces Accin1 Sino Accin2 FSi Seleccin mltiple: Es la ejecucin condicional de entre varias acciones que se excluyen mutuamente. El conjunto de las condiciones est enteramente definido por el conjunto de los valores que puede tomar un indicador. SegnIndicadorhacer Val1:Accin1 Val2:Accin2 ... ValN:AccinN Otro:AccinOtro FSegun Cclicas: Pre-Test: Esta forma de composicin cclica permite agrupar los procesos en los cuales una accin es ejecutada cero, una o ms veces. La condicin que aparece en el algoritmo indica la observacin que debe hacerse para que contine la iteracin. La accin es ejecutada Mientras la condicin sea verdadera. Es una Estructura Definida e Impura (Impura se refiere a que se descarta un elemento que no cumple con la condicin y por tanto hace salir del ciclo). MientrasCondicinhacer Accin FMientras Pos-Test: La ejecucin de este texto provoca sucesivamente la ejecucin de la accin y, a continuacin la observacin de la condicin y contina as hasta que el resultado de la condicin sea cierto, es decir, se ejecuta la condicin mientras la condicin sea falsa. Es una estructura Indefinida y Pura puesto que todos los elementos son tratados de la misma manera. Repetir Accin HastaqueCondicin Manejada por contador: Se ejecutan las acciones una cantidad preestablecida de veces. Es una estructura Definida y Pura. ParaVc:=VihastaVfhacer Accin FPara

2

La variable Vc es de tipo numrica y se denomina Variable de control. Vi y Vf son variables de tipo numrica, constantes numricas o expresiones aritmticas. Vi recibe el nombre de Variable inicial, Vf recibe el nombre de Variable final. El ciclo va incrementando la variable de control hasta llegar al final, se hace de uno en uno, a menos que se especifique otro caso. Clasificacin de Datos Simples Numricos Lgicos Punteros Alfanumricos Conjuntos Enteros Reales Carcter Cadena

Punto fijo Punto flotante

Datos Estticos Estructurados Dinmicos Campos Arreglos Registros Ficheros secuenciales Ficheros no secuenciales Densas Listas rboles Enlasadas Pila Cola Simplemente Doblemente Circular Simplemente Doblemente

Secuencia Un conjunto de objetos es una secuencia si se verifican las siguientes condiciones: 1. Primer objeto de secuencia: Un elemento del conjunto llamado primero, se distingue de los dems. Se debe acceder a este elemento para poder acceder a todos los dems. 2. Relacin de sucesin entre los objetos: Todos los elementos de la secuencia (salvo el ltimo) precede a uno de los dems objetos. 3. Caracterizacin de fin de secuencia: Debe estar definido un indicador de fin de secuencia, caracteriza al elemento final y en particular permite detener la enumeracin de la secuencia por observacin de la caracterstica del ltimo elemento. Caractersticas complementarias: Finitud: La longitud de una secuencia puede ser conocida o no, pero todas las secuencias deben ser finitas. Orden: Existe un orden cuando la relacin sucesora es estricta entre el primer elemento y el ltimo. Completitud: Especifica que entre un elemento y su sucesor no hay ausencias. Clasificacin de secuencias: Por su condicin de fin: Puras: El ltimo elemento de la secuencia indica el fin de la misma y debe ser tratado3

como un elemento cualquiera . Se utiliza el ciclo Post-Test. Impuras: Posee una marca de fin, es decir, un objeto extrao al final que no debe ser tratado como el resto de los elementos, se utiliza el ciclo Pre-Test. Por su cantidad de elementos: Definida: Si se conoce a priori la cantidad de elementos que posee. Indefinida: Si no se conoce a priori la cantidad de elementos que posee. Registros Es un agrupamiento de campos continentes y contenidos. Es una estructura compuesta de un nmero fijo de componentes llamados campos, donde cada uno de ellos viene definido con un nombre y un tipo. Se lo llama registro por contener informacin referida a una entidad. Es una estructura esttica, compleja y se almacena en memoria externa. Un campo CONTINENTE es aquel que contiene a otros campos, mientras que un campo CONTENIDO es el que es contenido por otro campo. Clasificacin de los registros: Fija Segn su longitud Variable Por ocurrencia Por enumeracin

Longitud fija: Su tamao est definido en el ambiente y no puede ser alterado. Alu=Registro AyN:AN(30) Leg:N(8) FinRegistro Longitud variable (dinmica): es una estructura compuesta por campos cuyo tamao va a ir variando durante la ejecucin del programa, segn lo regir el planteo del problema. Por ocurrencia: Los registros tiene una longitud mxima y mnima. El tamao vara entre dos valores. Presentan un solo formato y tiene incluido un arreglo dentro del cual se encuentra una parte comn a todos los registros. UTN=Registro Leg:N(8) Cant:0..48 Mat:RegistroocurresegnCant Cod_mat:N(3) Fecha:N(8) FinRegistro FinRegistro

4

Por enumeracin: Se tienen varios formatos de registros. En el archivo se definen varios registros de longitud fija. Es la aglutinacin de varios registros. MOVC=Registro MOVB=Registro MOVA=Registro Clave=Registro Clave=Registro Clave=Registro CodE: CodE: CodE: NroR: NroR: NroR: Freg Freg Freg CodMov:'C' CodMov:'B' CodMov:'A' RestoC:Comun RestoR:Remi RestoC:Comun FReg FReg RestoR:Remi FReg BAJA=Registro Clave=Registro CodE: NroR: Freg CodMov:('D','E') RestoC:Comun FReg ArchMov:ArchivodeMOVA,MOVB,MOVC,BAJA. Archivos Es un conjunto de registros o una coleccin de datos que estn almacenados en memoria externa permanentemente. La estructura del archivo se caracteriza por su cardinalidad finita. Por esta razn no hace falta dar la longitud del archivo. Consta de una secuencia de componentes del mismo tipo. Clasificacin: Archivo Organizacin Secuencial Relativa Directa Indexada Secuencial Al azar Acceso Directo Mixto

Organizacin: Es como van a ser almacenados los datos. La organizacin es permanente, ya que una vez definida no puede cambiarse. La forma de almacenamiento nace y muere con el archivo. Secuencial: Implica continuidad fsica entre los registros que es inamovible. Los registros son almacenados en el mismo orden en que se ingresan. Para poder acceder a un registro en particular debe accederse a todos los anteriores. Si un archivo esta abierto para la escritura, no puede usarse para la lectura. Directa: Usa los espacios libres en memoria. Hace un uso dinmico de la memoria. Relativa: Se debe definir su tamao. La ventaja es que se debe predecir el espacio. Los registros se graban ordenados por clave. Pueden ser accedidos directamente o secuencialmente, es muy seguro por ser inviolable. Indexada: Tiene dos reas; una de datos y otra de ndices. En la ubicacin de los5

registros se crea una clave de ndice, que es una tabla donde se anotan los lugares libres y la ubicacin de los registros. Poseen la libertad de crecer.

Acceso: Es la forma en la que se van a leer (recuperar) los registros. Secuencial: Para acceder a un determinado registro debo pasar por sus antecesores. Directo: Solo es posible para la asignacin de tipo directa. Al azar o puntual: Debe tener un ndice, por lo tanto se puede acceder directamente a un registro particular mediante su clave. Dinmica o mixta: Primero se accede al azar y luego de forma secuencial (no al revs), para esto se debe conocer la clave del primer elemento que se busca y a partir de ah recorrer secuencialmente. Procesos con archivos

Simples * Generacin o Carga * Corte de Control * Listado de Padrones * Estadsticos

Complejos * Falso Complejo * Actualizacin * Mezcla o Apareo * Heterognea * Homognea

Procesos Simples: Interviene un slo archivo de entrada, pudiendo haber o no uno de salida. Carga o Generacin: Es el proceso que se encarga de la creacin y la carga de los archivos. Consistencia: leer un dato desde un archivo y verificar que cumpla las caractersticas de salida. Congruencia: Comparar los datos de un mismo registro y verificar que se cumple. Listado o Padrn: Siempre hay un archivo de entrada y la salida siempre es impresa. Los controles se realizan con contadores. El archivo debe estar ordenado. Corte de Control: Se producen paradas momentneas para emitir totalizadores parciales u otras acciones del mismo tipo. Se produce por cambio de contenido en los distintos niveles de clave compleja (Existen tantos niveles de corte como campos tenga la clave). Objetivo: Obtener valores cuantificados. Los registros estn ordenados por clave compleja. Estadsticos: Son los nicos procesos que no piden ningn requisito de entrada. Busca emitir tablas de valores, la emisin es pequea, pero se tienen fuertes procesos de clculo. Busca emitir tablas de valores, es una proceso largo que no recorre todo el archivo, su herramienta es el arreglo, no existe requisito para el archivo de entrada y muestra los resultados al final del proceso. Procesos Complejos: Existen por lo menos dos archivos de entrada, pudiendo existir varios de salida. La finalizacin del proceso se maneja con la teora de apareo. Falso Complejo: De varios archivos de entrada, solo uno es importante, por lo que se verifica un proceso simple, los dems archivos se utilizan como auxiliares. Mezcla o Apareo: Intervienen por lo menos dos ficheros de entrada que deben ser combinados para obtener uno de salida, los archivos de entrada deben estar ordenados por clave de apareo. Homognea: Todos los archivos que intervienen poseen el mismo formato de registro y el nmero de de registros del archivo de salida es la sumatoria de todos los registros de entrada. Heterognea: Los archivos de entrada tienen formatos diferentes y se debe definir el6

formato del archivo de salida, pudiendo ser diferente al formato de la entrada. De todos los archivos de entrada hay uno de mayor importancia y es el que maneja el ciclo de mezcla. La salida adopta la forma del de mayor prioridad o una mezcla de los mismos Tcnicas de apareo: Incluyente (o): Todos los archivos de entrada son tratados en el mismo ciclo. Excluyente (y): Se tratan los archivos comunes en el ciclo y los no comunes fuera de el. Actualizacin: Significa incorporar, modificar o eliminar informacin de un archivo mayor (maestro) y se utilizan como mnimo dos de entrada y uno de salida. Este proceso se da en los archivos Maestros y Movimientos, en ste ltimo pueden venir todas o algunas de las siguientes informaciones: Altas: Incorporar nuevos registros. Bajas: Pueden ser fsicas (borra el registro fsicamente) o lgicas (se marca el registro como inactivo, desactivado, etc.) Modificacin: Modifica los registros existentes. Segn la cantidad de movimientos se clasifican en: Unitaria: Un movimiento por cada registro del maestro. Por Lotes: Varios movimientos por cada registro del maestro. Segn su organizacin el archivo puede ser: Secuencial: El archivo maestro es secuencial. Indexada: El archivo maestro es indexado. Actualizacin Secuencial El archivo maestro es secuencial. Es un proceso diferido, pues se prolonga en el tiempo, es un proceso lento, si hay una baja en el sistema (corte del suministro elctrico, etc.) no se pierden los archivos, la actualizacin no se lleva a cabo en el mismo maestro (batch). #Mae Maestro Movimientos #Mov = #A + #B + #M

Actualizacin Secuencial

Maestro Actualizado #Mae_Act = #Mae + #Ac[-Bfc]

Alta Baja Modif

7

Poseen acceso secuencial y para acceder al ltimo debo acceder a todos los anteriores. Son estructuras estticas (no se pueden ampliar) Los registros se almacenan secuencialmente con adyacencia fsica Para insertar un registro hay que crear un nuevo archivo. Proceso diferido: no modifico el archivo en el momento en que ocurren los movimientos. Proceso Batch (juntar) todos los movimientos en un archivo. Resguardos automticos (Back-Up) Actualizacin Indexada

El archivo base tiene organizacin directa, es un proceso in-situ, es decir, la actualizacin se realiza sobre el mismo maestro de entrada. Si las actualizaciones se realizan en el mismo momento en que ocurren (Si por ejemplo se realizan en un terminal) el proceso se llama interactivo. El proceso finaliza cuando termina el archivo de movimientos, o en el caso interactivo, cuando el usuario lo desee. El archivo base es muy vulnerable y puede ser violado. Index Maestro Movimientos

Back-Up Iguales

Actualizacin Indexada

Movimientos para el control

Secuencial Maestro Actualizado Solo para control

Posee acceso secuencial y directo a cualquier elemento del archivo. Son estructuras dinmicas que pueden crecer o reducirse. Los registros son almacenados con adyacencia lgica y nocin de adyacencia fsica. Proceso in-situ Se procesa sobre el mismo maestro indexado en el momento en que se realizan los hechos. Proceso interactivo o dinmico: No existe un archivo de movimientos, la actualizacin es de manera interactiva. Resguardos provocados.8

Arreglos Es una estructura de datos fijos, ay que una vez que se ha definido su tamao no puede crecer ni reducirse, tiene continuidad fsica, se almacena en memoria interna, posee accesos directo y secuencial a todos sus elementos. Pueden ser recorridos en forma inversa, es una estructura homognea, tiene un nico nombre para todo el grupo. Cada elemento se identifica por un ndice, el cual permite el acceso directo. La definicin de la cantidad de componentes est dada por la longitud. La cantidad de ndices indica la dimensin; puede ser unidimensional, bidimensional, o multidimensional. La repeticin de la estructura se establece por medio de un intervalo. Es una herramienta auxiliar, los vectores no se pueden leer y escribir con una sola operacin, la lectura y escritura se hace elemento a elemento y para visualizar los elementos del arreglo es preciso utilizar estructuras repetitivas.Carga o inicializacin Lgico Ilgico Parcial Lineal Bsqueda Binaria Mtodos directos Ordenamiento Mtodos avanzados Pura Con centinela Desordenado Ordenado Insercin Seleccin Intercambio

Total Recorrido Procesos con arreglos

Proceso de carga o inicializacin: La Carga consiste en colocar contenidos en el arreglo capturados desde el exterior. La inicializacin consiste en hacer un recorrido total del arreglo y asignarle un valor inicial, generalmente el 0. Recorrido: Si el recorrido es Total, se recorren todos los elementos del arreglo, se utiliza una estructura iterativa del tipo Para. ste recorrido a su vez puede ser Lgico o Ilgico, el primero es cuando se recorre de a un elemento y desde el primero al ltimo, de menor a mayor. El segundo es cuando se contradice esto, es decir, se recorre desde el mayor ndice al menor de ellos. Cuando el recorrido es Parcial solo se accede a algunos elementos, no a todos. Bsqueda: Consiste en producir un recorrido sobre el arreglo a fin de detectar un contenido particular. Existen dos posibles estados finales: el xito o el fracaso. Ordenamiento: Consiste en recorrer el arreglo para ordenar sus elementos con algn criterio, por ejemplo de menor a mayor. La declaracin de un arreglo en el ambiente se realiza de la forma siguiente: Ambiente Array:Arreglo[1..30]deentero /*Siqueremosunamatrizde5x5porejemlo:*/ Matrix:Arreglo[1..5,1..5]deentero

9

Mtodos de Bsqueda Bsqueda Lineal: La bsqueda lineal se subdivide en Pura o Simple y en bsqueda Con centinela, sta ltima a su vez sufre una pequea modificacin de su implementacin para arreglos ordenados y no ordenados. Pura o Simple: Consiste en recorrer el arreglo desde la primer posicin hasta la ltima, comparando cada elemento con el valor buscado. Al finalizar la bsqueda se deber informar donde se encontr el elemento en caso de que la bsqueda haya tenido xito, en caso contrario se deber informar la no existencia del mismo. Se aplica indistintamente para arreglos ordenados como para no ordenados. La bsqueda no finaliza al encontrar la primer ocurrencia, sino que apunta a la multitud de xitos. A continuacin se mostrar el algoritmo de esta bsqueda, se observar que: Los xitos se trabajan dentro del ciclo y los fracasos fuera de l y el nmero de comparaciones realizadas como mnimo ser igual a la cantidad de elementos que posea el arreglo. Encontrado=Falso Leer(x) Parai:=1hastanhacer SiA[i]=xentonces Tratar_Encontrado Fsi FPara SiEncontrado=Falsoentonces Tratar_Fracaso FSi Con Centinela: El recorrido NO es total, la bsqueda finaliza cuando encuentra la primer ocurrencia o al primer valor mayor que el elemento buscado (en arreglos ordenados). El ciclo debe ser manejado por una condicin. El nmero de comparaciones como mnimo ser el nmero de elementos que haya antes de encontrar el elemento0 buscado. Para su implementacin en arreglos desordenados se debe colocar el smbolo de distinto en el mientras, en los arreglos ordenados se debe colocar el smbolo de mayor > o menor