Teoria de Algoritmos

5/14/2018 Teoria de Algoritmos - slidepdf.com

http://slidepdf.com/reader/full/teoria-de-algoritmos-55a823af9a218 1/23

ALGORITMOS Y ESTRUCTURA DE DATOS.

APUNTE TEORICO

Estructuras fundamentales de datos e introducción a la algoritmia.

Clasificación de los datos.Enteros

Numéricos punto fijoReales

punto flotante

Carácter Alfanuméricos

Simples Cadena

Lógicos

PunteroConstantesDatos Variables

ContinentesCampos

ContenidosEstáticas

Registros ArreglosFicheros secuenciales

EstructuradosFicheros secuenciales

Dinámicas Pila

DensasCola

ListasEncadenadas Simple

O DobleEnlazadas Circulares

Arboles

Estructuras estáticas: son aquellas cuyo tamaño y estructura queda fijado en tiempo de definición ypermanecen inalterables durante la ejecución del proceso en el que fueron declaradas.

Estructuras dinámicas: son aquellas cuyo tamaño u estructura puede variar en tiempo de ejecución ysu única limitación (tamaño máximo) está dado por el tamaño de la memoria que la soporta.

1



• Acción .Es un acontecimiento producido por un actor (ejecutante) que tiene lugar duranteun periodo de tiempo finito y produce un resultado bien definido y previsto.Comienza con dato y termina con un resultado, todo lo que se puede detectar enlos estados intermedios se denomina información.

DATOS ----- INFORMACION ----- RESULTADOSLos resultados son una transformación de los datos.

• Proceso .Es un conjunto de fenómenos organizados en el tiempo y concebido comoactivo. También se lo puede definir como un conjunto de acciones.

Tipos de proceso.1- secuencial: cuando una accion no puede empezar antes de que la accionen

curso esté completamente terminada.2- Paralelo : no existe continuidad. Se pueden ejecutar dos o mas acciones al

mismo tiempo.

• Esquema .Es una descripción o una representación mental reducida a los rasgosesenciales (de un objeto, de un proceso).

Lenguaje natural.

Esquema diagramas (gráficos).

Pseudocódigo.

• Algoritmo .Es una secuencia ordenada de acciones primitivas que pueden ser ejecutadaspor un procesador y que lleve a la solución de un problema dado.

• Maquina .Mecanismo capaz de generar acciones q tienen lugar según un esquemadeterminado.

Tipos de máq.

1- abstractas : destinadas a facilitar el análisis de los problemas. Nos permitellevar a cabo la solucion de algun problema a nivel algoritmico.

2- Real: destinadas a la solución de los problemas, para lo cual se traducen lassoluciones a algun lenguaje de programación. Para estas máq.Consideramos el programa.

Análisis descendente.Estudio de los problemas de alto nivel a los reales, por descomposición sucesiva

en soluciones de nivel de detalle cada vez mas elevado. Parte de las acciones de las

maq. abstractas para llegar a soluciones de maq. reales.

Análisis ascendente.

2



Parte de las acciones de las maq reales y procura construir maq cada vez masabstractas hasta poder realizar una síntesis de alto nivel.

• Programa . Algoritmo destinado a gobernar una maq real. Un lenguaje de programación esun conj de reglas, símbolos y palabras especiales usadas para construir unprograma.

Reglas de formulación de un lenguaje:Sintaxis: reglas formales para la construccion de sentencias válidas en unlenguaje.

Semántica: reglas que dan el significado de una sentencia del lenguaje.

• Resolución de problemas .

Cuatro etapas.

1- formulación o enunciación del problema . Debe ser formulado en forma correcta,precisa, completa y sin ambigüedades.

2- Elección de un método o procedimiento .3- Codificación . Expresar el método o procedimiento elegido de forma tal que pueda

ser comprendido por el procesador que va a utilizarse.4- Ejecución .

• Procesador .Entidad capaz de comprender un enunciado y ejecutar el trabajo indicado por elmismo.

• Ambiente .Conjunto de todos los recursos necesarios para la ejecución de un trabajo, esespecífico del trabajo a ejecutar.Una acción es un evento que modifica el ambiente, desde un estado inicial (Ei),hasta un estado final (Ef). El procesador debe respetar la secuencia de lasacciones.Para un procesador una accion puede ser:

Primitiva: si su enunciado es suficiente, para q pueda ejecutarla sin informaciónadicional.No Primitiva: debe ser descompuesta en acciones primitivas.

• Condición .No es una acción, ya q no modifica el ambiente, es una afirmación lógica q

puede ser cierta o falsa, en el momento de la observación.

• Formalización de algoritmos .las computadoras no pueden ejecutar directamente los algoritmos, es necesarioun lenguaje apropiado que llamaremos lenguaje de programación.

• Formalización del ambiente de un problema .Es el primer paso para l resolución de un problema, consiste en describir, conprecisión y sin ambigüedad los objetos del universo del problema.

1- si queremos citar diferentes objetos, damos una lista de sus nombres, cadaobj. tiene un tipo particular q indica las características comunes a todos losestados posibles del objeto.

2- Otra característica de los obj. es el valor. En cada instante, todo objeto delambiente tiene un valor, el cual puede cambiar, para algunos obj. después dela ejecución de una acción.

3



• Prueba de un algoritmo .Una manera de comprobar el funcionamiento de un algoritmo es ejecutándolo amano, usando datos representativos y anotando los valores q van tomando losobj. en cada paso, es decir acción por acción, este procedimiento se llamaPRUEBA DE ESCRITORIO.

0 ≤ (datos) ≤ N

Si cumple las características 0 ≤ (resultados) ≤ Mdel algoritmo finitudPrueba

uso de consignas correctas (pseudocód. – sin y sem)

Propiedades de los algoritmos.

Los pasos de un algoritmo deben ser simples y exentos de ambigüedad. Deben ser efectivos, o sea q deben resolver en un número finito de pasos

• Estructura de acciones .

Asignación.Es la acción de transferir un contenido. En toda transferencia existe un emisor y

un receptor.RECEPTOR := EMISOR

Solo una variable puede ser receptor. El emisor puede ser constante, variable oexpresión. El valor q asigna a la variable debe ser del mismo tipo q la variable.

Expresión.Es la reunión de datos (constantes y variables) relacionados mediante

operadores. Pueden ser unimodales o bimodales.

Expresiones aritméticas.+, -, *, /.Bimodales: DIV, MOD.

Precedencia de operadores.Reglas de precedencia.

o Los operadores q tienen mayor precedencia se procesan primero, y después secontinúa de izq a der con los operadores que tienen la misma precedencia.

o Si hay paréntesis en una expresión, primero evaluamos la expresión entreparéntesis, éstos pueden hacer variar las reglas:

1. ** (potencia)2. +, - (operadores de signo, se aplican de izq a der).3. *, /, DIV, MOD (de izq a der).4. +, - (suma y resta, de izq a der).

• Funciones internas .Operadores especiales. Tienen una alta prioridad cuando aparecen en unaexpresión, superior la del operador de potencia.

ABSO Valor absolutoSQRT Raíz cuadradaLN Log natural

LOG Log base 10EXP E a la la pot de xTRUNC X truncadoREDOND Redondeo de x

4



SQR Cuadrado de xSIN SenoCOS CosenoTAN Tangente

• Expresiones lógicas o Booleanas .una expresión booleana puede ser:1. una variable booleana.

2. una expresión seguida de un operador relacional seguida de una expresión.3. una expresión booleana seguida de un operador booleano seguida de una

expresión booleana.

Variable booleana: variable declarada de tipo lógico, puede ser V o F.

Operadores relacionales: mediante la comparación de dos valores, son: =, <>, <,>, ≤, ≥.

Operadores boléanos: son los símbolos especiales “Y” (conjuncion); “O”(disyuncion); y “NO” (negacion), los cuales se definen solo para las expresionesbooleanas.

Los operadores relacionales pueden combinarse con los boléanos.

• Precedencia de todos los operadores .Los operadores relacionales tienen una precedencia menor q todos los demásoperadores.

1. NO.2. *, /, DIV, MOD, Y.3. +, -, O.4. =, <>, <, >, ≤, ≥.

• Acción elemental.es la ejecución de un acontecimiento elemental, aparece en un algoritmo por sunombre, el cual se interpreta como “provocar” el acontecimiento asociado a ese“nombre”.

• Acciones estructuradas .

o Simple . Es la ejecución condicional de una acción. SI condición ENTONCES Acción;FIN SI.

Primero se observa la certeza de la condición, si ésta conduce a una respuestacierta, la acción es ejecutada a continuación de la observación, la cual finaliza laejecución.

o Alternativa . Es la ejecución alternativa de una entre dos acciones.

SI condición ENTONCES Acción1;

SINOAcción2;

FIN SI.

Primero se observa la certeza de la condición, la cual es seguida de la acción1 sila condición es cierta, o de la acción 2 si la condición es falsa.

5



o Selección múltiple . Es la ejecución condicional de una entre varias acciones.

SEGÚN indicador HACERValor1: acción1;…………………Valorn: acciónn;Otros: acción n+1;

FIN SEGÚN.

La ejecución del texto provoca la búsqueda en la lista de los valores de aquélque corresponde al valor observado por el indicador. Se ejecutará una de entre todaslas acciones enumeradas. La acción n+1 se asocia en todos los casos en los cuales elindicador no pertenece al conjunto de todos los n valores explícitamente enumerados.

o Repetitivas . Es la ejecución múltiple de una sola acción.

1. Repetir . (post-test)

REPETIR

Acción;HASTA QUE condicion.

la ejecución de este texto provoca sucesivamente la ejecución de la acción, acontinuación la observación de la condición y ejecuta la acción hasta que lacondición sea falsa. La acción se ejecuta por lo menos una vez.

2. Mientras . (pre-test)

MIENTRAS condición HACER Acción;

FIN MIENTRAS.La acción se ejecuta mientras la condicion sea verdadera. La acción seejecuta como mínimo 0 ≤ (mientras) ≤ N.

3. Manejada por contador .

PARA Vc := Vi HASTA Vf , I HACER Acción;

FIN PARA.

Vc es una variable de tipo numérico llamada variable de control.Vi, Vf e I son variables de tipo numérico, constantes de tipo num oexpresiones aritméticas. Vi recibe el nombre de valor inicial, Vf valor final e Ies el incremento que se expresa cuando es distinto de 1, éste puede ppsitivoo negativo, pero no cero.Si el incremento es positivo: Vi < Vf.Si el incremento es negativo: Vi > Vf .Dentro del para no es correcto modificar el valor de la variable de control.Cuando finaliza el para, Vc queda indefinido.

En el mientras e el repetir la variable condicional debe ser alterada dentro delciclo por instrucción del algoritmo, a diferencia del para que no puede ser alterada dentro del ciclo.

Tratamiento de secuencias.

6



• Noción de secuencia .Un conjunto de objetos está organizado en forma de secuencia, si es posibledefinir las nociones siguientes:

o Primer objeto de la secuencia : un objeto del conjunto, llamado primero se distinguede los demás. El acceso a este elemento, permite el acceso a todos los demáselementos de la fila.

o Relación de sucesión entre los objetos : todos objeto de la secuencia (salvo elelemento final) precede a uno de los demás objetos (su sucesor). Esta relaciónpermite construir el acceso a todos los elementos de la secuencia. Estaenumeración termina con el acceso al elemento final.

o Caracterización del fin de la secuencia : debe estar definido un indicador de fin desecuencia: caracteriza el elemento final, y permite detener la enumeración de lasecuencia por observación de la característica del último elemento.

Acceso secuencial: acceso a los elementos de una secuencia. Se accede por elprimero, y para llegar al elemento i-ésimo se deberá recorrer sucesivamente los i-1elementos que le preceden.

Tratamiento secuencial: es el tratamiento de secuencias.

• La máquina de caracteres .es una procesadora de tiras de carateres. Contiene los siguientes elementos:

Una ventana. Dos botones indicativos: ARRANCAR (ARR: inicio de la cinta)

AVANZAR (AVZ: carácter siguiente)Las dos acciones anteriores permitirán acceder al primer elemento.

• Enumeración de secuencias, búsqueda asociativa .Toda iteración puede ser interpretada como la enumeración de alguna

secuencia. En tal enumeración, se accede a cada uno de los objetos de lasecuencia una vez y solo una, y para cada uno de ellos se aplica un tratamientoúnico.

o Tratamiento en curso : es el correspondiente a cada uno de los objetosdistintos del último de una secuencia.

o Tratamiento final: es el que corresponde al objeto final de la secuencia.

Ciertas enumeraciones son particulares por el hecho de que el tratamiento encurso es vacío y de que no se enumera toda la secuencia: la enumeración sedetiene en el primer elemento de la secuencia que tiene una característica dada,a esto le llamaremos búsqueda asociativa (del primer elemento de la secuencia

que verifica una propiedad dada). La designamos “asociativa” porque lo quecaracteriza al elemento buscado es una propiedad y no el lugar en donde seencuentra.

Esquema 1: el tratamiento final <> altrat en curso.

Enumeración Esquema 2: el tratamiento final = altrat en curso.

SecuenciaInterna: cambia el tratar elemento.

Externa o extraída: comparte prioridad

Búsqueda En condición de fin = búsqueda asociativa

7



(trat cero). Una vez encontrado el elto.no hace falta seguir buscando.

• Esquemas de enumeración de secuencias .Se basan en las siguientes hipótesis:El tratamiento de los elementos de la secuencia.

Tratar elemento: describe el tratamiento en curso.Tratar elemento final: describe el trat del elto final.Inicializar tratamiento: describe el conjunto de las operaciones que debenefectuarse antes de que empiece la enumeración para que el encadenamiento

de los trat (en curso y final) proporcione el resultado esperado.

o Esquema 1 : el trat final es lógicamente distinto del trat en curso.

ACCION esquema 1 ESInicializar tratamiento;Inicializar adquisición;Obtener elto sigte;MIENTRAS elto no final HACER

Tratar elto;Obtener elto sigte;

FIN MIENTRAS;Tratar elto final;

FIN ACCION.

Inicializar trat: puede ser, por ejemplo, poner los contadores y acumuladores acero.Inicializar adquisición: ARRANCAR.Obtener elto sigte: AVANZAR.

o Esquema 2 : el trat final es idéntico al trat en curso. Su principio es agrupar lostrat de todos los eltos, comprendido el último, dentro de la iteración. La condiciónde fin es el encuentro del último elto, pero la observación de esta condición se

realiza después de tratar el elto.

ACCION esquema_2 ESInicializar trat;Inicializar adquisición;REPETIR

Obtener elto sigte;Tratar elto;

HASTA QUE elto finalFIN ACCION.

• Secuencias puras : son aquellas en las que no existe condicion de fin, para éstasusamos el esquema 2.

• Secuencias con marcas (impuras): usamos el esquema 1, en secuencias vacías conmarca no existe tratamiento.

8



• Esquema de búsqueda. Se desea pasar de un elto al sigte hasta que se produzca una de las doscondiciones:

o Se ha encontrado el elto que tiene la propiedad buscada.o Se ha encontrado el elto final antes de haber encontrado el elto deseado,

puede ser que el elto buscado sea el final, si no es así la búsqueda no hatenido éxito.

Para expresar por medio de un esquema tomamos las sigtes convenciones:o ‘ elto hallado ‘: describe el conjunto de operaciones que deben ser

ejecutadas una vez encontrado el elto.

o ‘ tratar ausencia: describe el conjunto de operaciones que debenefectuarse en caso de la búsqueda no tenga éxito.

ACCION búsqueda_asociativa ESInicializar adquisición;Obtener elto sigte;MIENTRAS (elto no hallado) y (elto no final) HACER

Obtener elto sigte;FIN MIENTRAS;SI elto no hallado ENTONCES

Tratar elto hallado;SINO

Tratar ausencia;FIN SI;

FIN ACCION.

• Esquema avanzado de secuencia .

ACCION ejemplo ES

AmbienteVariablesS: secuencia de caracteres;C, ca: carácter;< otras variables >;

Algoritmo ARR (s); AVZ (s,c);< inicializar gral >;MIENTRAS NO FDS (s) HACER SI < cond > ENTONCES

< inicializar parcial >;

REPETIR< trato1 >;AVZ (s,c);

HASTA QUE (<no><cond>) o (FDS (s))<trato 2>;SINO

AVZ (s;c); FIN SIFIN MIENTRAS;< trato final >;CERRAR (s);

FIN ACCION.

Tratamiento de secuencias de registros.

9



• Campo : es una agrupación de datos simples con un objetivo (aportar mayor información), cada campo tiene que recibir un nombre y tendrá su tipo y tamaño propio.

• Campo continente : es un campo formado por contenido. Hay que dar el contenido.

• Campo contenido : requiere que se le de tamaño y tipo. Depende de un campo mayor.

• Registro: es un agrupamiento de campos continentes y contenidos. Estructuracompuesta de un número fijo de componentes llamados campos, donde cada uno deellos viene definidos por su nombre y su tipo (no necesariamente deben ser todos de unmismo tipo). La menor unidad de información de un registro se denomina casmpo.

• Representación de un registro .

o Lineal, gráfica o esquemática: consiste en la continuidad de celdas, donde cadadato tiene su rectángulo. La continuidad determina la relación lógica que existeentre los campos.

o Jerárquica o arbórea : es puramente gráfica, se utiliza en diseños globales yviene por traslado de la representación de los sistemas. Trabaja con nodos deinformación.

Nodos: son rectángulos que representan una entidad física lógica.

o Por nivel o literario : es la representación jerárquica de los datos donde cadanodo o cada elemento ocupa un renglón de escritura y las relaciones dedependencia y subordinación se nota mediante el uso de sangría. Describimos acontinuación el ambiente.

Alumno = registroLegajo 6N; Ape_nbre AN40;Fe_nac fecha;

FIN REGISTRO.

De esta forma vamos a definir un registro en el ambiente.Para poder acceder a las componentes de una variable registro, utilizamos unaexpresión llamada selector de campo. Esta expresión está formada por elnombre de la variable registro y el nombre del campo al cual queremos acceder,separado por un punto.

Esquema general para el tratamiento de registros. ACCION ejemplo ES

AMBIENTETIPOReg = registro

C1: T1;C2: T2;…………Cn: Tn;

Fin registro;VARIABLES

Arch: archivo de reg;Ra: reg;(otras variables);

10



ALGORITMOAbrir (arch); leer (arch,ra);<inicializar variables>;MIENTRAS NO FDA (Arch) HACER

CON Ra HACER<trato>;

FIN CON;Leer (Arch,ra);

FIN MIENTRAS;<Emitir>;Cerrar (Arch);

FIN ACCION.

La estructura de fichero secuencial.

• Fichero .

Es una colección de datos que está almacenado en una memoria externa permanente.Su estructura se caracteriza porque su cardinalidad es infinita, por lo que no hace faltadar la longitud del fichero.Estructura de datos que consta de una secuencia de componentes que son todos delmismo tipo.

ABRIR (F)LEER (F,R)CREAR

o Procesos con ficheros .

genérico

IndividualCorte de control

Procesos

Actualización

Múltiple directaMezcla Apareo

Indirecta

o Individual.Interviene un solo fichero de entrada, pudiendo haber o no uno de salida.

El control de finalización de proceso va a estar dado por el fin de fichero deentrada.

o Múltiple .Por lo menos dos ficheros de entrada, pudiendo existir varios ficheros de

salida. La finalización de proceso se maneja con la técnica de apareo. El apareo

11



de ficheros requiere que aunque los ficheros de entrada tengan estructurasdistintas deben tener en su estructura un elto común, conocido como clave deapareo, la cual debe ser única.

• Mezcla o apareo.Proceso en el cual intervienen por lo menos dos ficheros de entrada, quedeben ser combinados para obtener uno de salida.Puede ser:

o directa : todos los ficheros intervinientes tienen el mismo formato de registro, y elnúmero de registro de mi fichero de salida es la sumatoria de los registros de losficheros de entrada.

o Indirecta : dentro de todos los ficheros de entrada hay uno que se considera demayor prioridad y es el que maneja el ciclo de mezcla, los restantes pueden ser de la misma forma del anterior o distintos, y la salida adopta la forma de ficherode mayor prioridad, o una mezcla entre las formas intervinientes.

• Actualización: incorporar, modificar o eliminar información de un fichero mayor (o maestro)y se utilizan como mínimo dos de entrada y uno de salida.

o Ficheros de entrada :

maestro : es el fichero de estructura mayor y es el que va a sufrir actualización. Por su prioridad puede ser:

histórico : contiene información desde el nacimiento de la entidad. Común : es una partición del fichero o normal fichero histórico, puesto que

contiene información de uso cotidiano o habitual.

o Movimientos : estructura menor o igual a la del maestro, y debe contener comomínimo el campo clave de apareo, para poder realizar la actualización.

Altas : incorporación de un nuevo registro al fichero maestro manteniendo launicidad de claves, en general.

Modificación : corresponde a la existencia de un registro del maestro en elcual se desea modificar parte o todos sus campos contenido, exceptuando elcampo clave.

Baja lógica : cosiste en marcar o señalar el registro. Baja física : consiste en eliminar totalmente contenido y clave del fichero

maestro.

o Tipos de actualización :

individual: un archivo de movimiento individual es aquel que contienemovimientos de un solo tipo.

General o combinada : en archivo de movimiento general contiene registrosde los tres tipos de movimiento.

• Corte de control.o Clave compleja : clave formada por varios campos, entre los cuales existe una

relación jerárquica, de inclusión.Es el proceso en el cual se producen paradas momentáneas para emitir totalizadoresparciales o cualquier otra acción del mismo tipo. Existen tantos niveles de corte comocampos tenga la clave compleja. Los cortes se producen por cambio de contenido enlos distintos niveles de la clave compleja.

12



Para realizar un corte de control es necesario que el fichero de entrada esté ordenadode acuerdo a una clave compleja.Por cada nivel de corte de control, existe una variable contador o acumulador, que e laque se emite cuado se efectúa el corte de ese nivel (existen tantos niveles de controlcomo datos tenga el campo clave)Los contadores o acumuladores tienen dos momentos de inicializacion:

Al comienzo del algoritmo (común para todos). En forma individual, cuando se produce el corte correspondiente.

En todo proceso de corte de control, se produce una comparación entre un campoactual y un campo anterior (del mismo tipo), por eso deben coexistir la información delcampo clave actual y la del campo clave anterior, esta última es una variable auxiliar,que debe recibir un contenido de la clave.En el proceso en si, antes de tratar a registro se pregunta si se ha producido un corte.Esto se efectúa mediante un anidamiento de preguntas (SI anidados), desde el nivel decorte mayor, hacia el menor. En caso de una respuesta afirmativa, se produce el cortede nivel correspondiente, lo que obliga a efectuar el proceso de emision de los totalesde los niveles de corte menor, hacia el que produjo el corte.

Listas.Son estructuras flexibles, ya que pueden crecer y reducirse y, los eltos, pueden ser accedidos o

insertados, en cualquier posicion dentro de las mismas, como también eliminados. En una listalos eltos entán linealmente ordenados de acuerdo con su posición dentro de ella. Cada elto estácompuesto por uno o mas campos, el cual puede ser un dato simple o estructurado.

• Listas particularizadas .Son las pilas y colas, que son en realidad una restricción de acceso a una estructura dedatos.

o Pila .Estructura de datos en la cual todas las inserciones y eliminaciones se realizanpor el mismo extremo (extremo superior o tope de la pila). En una pila siempresale el elto que ha sido insertado último, la llamamos LIFO (last in first out). Laspilas se utilizan siempre que se quiere recuperar una secuencia de eltos en el

orden inverso al que fueron obtenidos.

o Cola .Estructura de datos en las cuales las operaciones básicas de añadir y eliminar eltos se realiza en los extremos de la lista. También es una estructura donde elprimero en entrar es el primero en salir, la llamamos estructura FIFO (first in firstout). Se utilizan siempre que se quiere recuperar una secuencia de eltos en elmismo orden que se generó.

• Listas simplemente encadenadas .

13



Es una secuencia de nodos que se encuentra enlazada, cada uno con el sigte,mediante un enlace o puntero. Cada elto de una lista enlazada debe tener dos campos:un campo (info), que contiene el valor de ese elto; y un campo (puntero interno) queindica la posicion del sigte elto. Los eltos de la lista están conectados a través de suscampos enlace o puntero, la marca de fin de la lista es NIL. El puntero externo (PRIM)indica donde comienza la lista. El último elto contiene una dirección que permite saber que el recorrido termina.

• Listas doblemente enlazadas .

Es una lista que posee dos punteros externos, uno apunta al primer nodo (PRIM) y elotro al último (ULT). Su estructura de nodos contiene dos campos de enlace (punteros

internos) donde el predecesor es enlace izq y el sucesor enlace der.

• Listas circulares .

Es una lista en la que el puntero sigte al último elto apunta hacia el primer elto. esta listase caracteriza por no existir el puntero nulo, no existe primer ni último elto (pero se debeelegir arbitrariamente un puntero externo a un nodo de la lista). Esta lista permite que seacceda a un nodo desde cualquier otro.

• Implementación de las listas lineales .Extisten dos formas de almacenar las listas lineales en memoria.

o Almacenamiento secuencial.La forma mas simple y natural de almacenar una lista lineal en la memoria es ubicar los eltos de la misma, que son lógicamente adyacentes, en posiciones físicamenteadyacentes. Insertar un elto, en el medio de una lista almacenada de esta forma,requiere el recorrido de un lugar, de los eltos que le siguen, con el fin de ubicarlo y,eliminar cualquier elto excepto el último, requiere del corrimiento de los mismos, conel fin de evitar los espacios vacíos.

o Almacenamiento encadenado .Este es un esquema más flexible, cada elto tiene un indicador que apunta al próximoelto de la lista. No es necesario que los eltos que son lógicamente adyacentes,

14



ocupen posiciones contiguas de memoria. Este tipo de almacenamiento permiteaprovechar mejor la memoria. En este caso los componentes de la lista sonvariables dinámicas.

o Variable dinámica .Es una variable simple o una estructura de datos creada en tiempo de ejecución yaccedida mediante un puntero (indicador).

o Puntero .Es una variable simple (estática) que se utiliza para guardar la dirección de memoriade una variable dinámica.

La ventaja de poder crear variables en tiempo de ejecución es que no necesitamoscrear nada más que lo que realmente necesitamos.El tipo puntero es un tipo simple, pero no es un tipo estándar, por lo quenecesitamos declararlo en cada programa:

P : puntero a tipo;Donde tipo en un tipo de dato (por ej un reg). P apuntaa un espacio en la memoriadonde le quepa ese tipo. Las variables a las que apuntará P se crearándinámicamente.

Ejemplo:Tipo

P = puntero a persona;Persona = registro

DNI: ;Nombre: ;

Fin registro;

o Creación de una variable dinámica .Se genera por medio de un procedimiento estándar, que llamaremos NUEVO (P),

donde P es una variable puntero, este procedimiento busca un lugar libre dememoria y lo reserve para almacenar un elto de la lista.Para acceder a las variables recientemente creadas que no tienen nombre, sino queson referenciadas mediante una variable puntero, una de las sigtes expresiones:

P^, *PLas cuales representan el valor almacenado hacia adonde apunta P, o, el lugar apuntado por P.

Arreglos.

Es una estructura de datos en la que se almacena una colección de datos del mismo tipo.Se caracteriza por:

o Almacenar los eltos del arreglo en posiciones de memoria continua.o Tener un único nombre de variable que representa a todos los eltos y éstos se

diferencian por un índice.o Acceso directo a los eltos individuales del arreglo.

Se clasifican en:o Unidimensionales (vectores o listas).o Multidireccionales (tablas o matrices).

• Vectores .Tipo de dato estructurado de eltos finitos, tamaño fijo y eltos homogéneos.

Declaración: Var Nombre_arreglo: Arreglo [tipo de índice] de tipo;

o Uso del índice de un arreglo .

15



Cada referencia a un arreglo incluye el nombre y el índice encerrado con corchetes: elíndice determina que elto se procesa.

o Operaciones con arreglos .Los vectores no pueden leer/escribir con una sola operación, esto se hace elto a elto y parapoder realizarlo se debe visualizar los componentes del arreglo, a través de estructurasrepetitivas.

ConstanteN = 100;Variable

Notas : arreglo [1..N] de enteros;

Lectura/escritura de un vector:

Para i := 1 a N hacer Leer/escribir (notas [i] );

Fin para.

• Arreglos multidireccionales .

• Arreglos bidireccionales .Son arreglos de dos índices, pueden ser ordinales o de tipo subrango, se los conoce con elnombre de tabla o matriz.Los tipos de índices no necesitan ser subrango del mismo tipo.

Declaración de arreglos bidireccionales:Se crean con la declaracion de variables.Se debe indicar:

1. nombre del arreglo.2. tipo del arreglo.

3. el rango permitido (el primero y el último de los valores posicionados).Ident : arreglo [índice1,índice2] de tipo de elto;

• manipulación de tablas .los más usuales son los recorridos por filas y los por columnas.

Por filas.

Para FILA := 1 a N hacer Para COLUMNA := 1 a N hacer

Leer ( A [FILA,COLUMNA] );F para;

F para;

Por columnas.

Para COLUMNA := 1 a N hacer Para FILA := 1 a N hacer

Leer ( A [FILA,COLUMNA] );

F para;F para;

Diferencias y semejanzas entre las estructuras de datos: Arreglos, Archivos y Listas.

16



ARCHIVOS ARREGLOS LISTAS

• se almacenan en memoriaexterna.

• Son de acceso secuencial ypara acceder al último deboacceder a todos los anteriores.

• Los indexados poseen acceso

secuencial y directo acualquier elto.

• Los secuenciales sonestructuras estáticas, una vezcreadas no se pueden ampliar.

• Los indexados son estructurasdinámicas que pueden crecer o reducirse.

• Los sec se almacenansecuencialmente en memoriacon adyacencia física.

• Los index se almacenan conadyacencia lógica y no física.

• Se almacenan en memoriainterna.

• Acceso directo y secuencial.Pueden ser recorridos enforma inversa.

• Estructuras estáticas, una vez

creados no pueden crecer nireducirse.

• Se almacenan en formaadyacente en memoria, unotras otro.

• Se puede realizar búsquedabinaria, si se encuentraordenado.

• Se almacenan en memoriainterna.

• Acceso secuencial uno trasotro, solo pueden ser recorridas en forma inversa lasdoblemente enlazadas.

• El último elto de una lista sedistingue por apuntar a unpuntero nulo (NIL).

• Estan enlazadas mediante unpuntero interno que cada nodoo elto posee. Cada punteroposee la dir del sigte elto.

• Estructura dinámica quepuede crecer o reducirsemientras la memoria losoporte.

•

Se almacenan en memoriautilizando cualquier parte quesoporte su registro.

• La operación de insertar unnodo es sencilla.

• Los nodos no tienenadyacencia física.

• Ordenación .

Consiste en disponer de un conj (de estructura) de datos en algún determinado orden conrespecto a uno de los campos de eltos del conj.

o Ordenación interna : cuando están en un arreglo.o Ordenación externa : cuando están en un archivo.

Una lista se dice que está ordenada por clave k, si la lista está en orden ascendente odescendente con respecto a esta clave.Dos criterios a tener en cuenta, para ver cual algoritmo es el mejor:

o Tiempo menor de ejecución en computadora .o Menor número de instrucciones .

Directa

17



Insercion Binaria

Simples,

Directos o Selección directa

Eltales. Directo o burbuja

Intercambio Directo con test de comprob.

Método de la sacudida

Métodos de ordenación

Indirectos, Inserción (con incrementos decrecientes)

Avanzados o Selección (orden según árbol o método de

Logarítmicos la criba o del montículo, heapsort)

Intercambio (orden por partes met. Ráp)

(quick sort)

• Ordenamiento por burbuja .Se basa en el principio de comparar e intercambiar pares de eltos adyacentes hasta que todosestén ordenados.Se lo conoce generalmente como burbuja, porque si se mira el arreglo, como si estuviera enposicion vertical, en vez de horizontal, los eltos se consideran burbujas en un depósito de agua.En cada pasada, una burbuja asciende hasta el nivel de peso que le corresponde.El método de intercambio es el más lento de los tres métodos básicos de ordenación (incluidolas mejoras del método de intercambio).

Acción Intercambio_directo es Ambiente

Cons

N= 500Var A: arreglo [1..n] de enteros,Aux: enteroI, J: índice;

AlgoritmoPara i:= 1 hasta n-1 hacer

Para j:= 1 hasta n-i hacer Si a[j] > a[j +1] entonces

Aux: = a [j]; A [j]: = a[j +1]; A [j+1]:=aux

F si:F para;F para;

F acción.

18



• Ordenamiento por selección directa .Este método se basa en los siguientes principios.o Encontrar el elemento con clave mínima.o Intercambiarlo con el primero. A continuación estas operaciones se repiten con los elementos n-1, n-2, etc. restantes, hastaque quede un único elemento, el mayor. Considera a todos los elementos de la secuenciaorigen para encontrar el elemento con clave mínima y depositarlo como elemento siguiente de

la secuencia destino. Es más rápido que el de insercion directa. Pero en el caso de que elarreglo este ordenado o casi ordenado puede resultar mas rápido el de insercion.La hipótesis utilizada es: tengo un arreglo ordenado hasta la posicion (i-1), busco el menor desde la posicion i hasta la última, lo insertamos en la posicion a[i] y luego incremento i.

A: arreglo [1..n] de enteros,Aux: enteroI, J: índice;

AlgoritmoPara i:= 1 hasta n-1 hacer

Min:=iPara j:= i+1 hasta n hacer Si a[j] < a[min] entonces

Min:= jF si

F paraAux:=a [min]A [min]:= a[i]A[i]:= aux

F paraF acción

• Ordenación por insercion .

Los elementos están divididos conceptualmente en una secuencia origen ai…an, unasecuencia destino a1…ai-1. En cada caso; empezando con i=2, e incrementando i de uno enuno, se toma el elemento (x) de la secuencia origen y se lo transfiere a la secuencia destinoensartandolo en el sitio adecuado. Conviene alternar comparaciones y movimientos,comparando x con el elemento inmediato precedente aj, como consecuencia se inserta x o semueve aj a su derecha y se continua con el inmediato por la izquierda, según el mismoproceso. Obsevamos que en este proceso de caída existen dos condiciones distintas determinación:

o Se encuentra un elemento aj con clave menor que la de x.o Se alcanza el extremo izquierdo de la secuencia destino.

Este caso típico con dos condiciones de terminación, permite usar la técnica del centinela. Estose hace usando a0= x como centinela.

Acción Inserción-directa esAmbiente

Const n=500Var A: arreglo [0..n] de enteros Aux,x entero;I,j; índice;

AlgoritmoPara i:=2 hasta n hacer

X:=a[i]A[0]:=x; j:=i-1Mientras (x<a[j]) hacer

A[j+1]:=a[j];J:=j-1;

Fin mientras

19



A[j+1]:=x;Fin para;

Fin acción.

• Ordenación de un arreglo de registroSe realiza de igual manera que los arreglos simples.

• Búsqueda .Es la búsqueda en un conjunto de datos de un elemento específico y de la recuperación de unelemento asociado al mismo.o Métodos de búsqueda

Lineal. Lineal con centinela. Dicotómica o binaria.

o Búsqueda lineal.Consiste en recorrer todo el vector, comparando cada elemento, con el valor buscado. Alfinalizar el algoritmo deberá informar la posicion donde se encontró el elemento en caso de

que la búsqueda haya tenido éxito o la no existencia del mismo. Ventaja: se aplica a arreglos ordenados y desordenados, es útil parabúsquedas múltiples.

Desventajas: recorre todo el vector aunque el elemento se haya encontradoen el primer lugar.

Número de comparaciones como máximo: tantas como elementos haya en elarreglo.

Leer(x)Pos=0Para i:=1 a n hacer

Si a[i]=x entoncesPos:=i

FsiFparaSi pos>0 entonces

Emitir (‘Esta en Posición:’, pos)Sino

Emitir (‘No se encuentra)Fsi

• Búsqueda lineal con centinela .Similar al anterior pero con la mejora de que en momento que se localiza el elto, se finaliza elbucle de búsqueda.

o Ventajas: se aplica tanto a arreglos ordenados o desordenados.Cuando encuentra el elto no sigue buscando.

o Desventajas: es muy lenta cuando el número de eltos del arreglo es grande, no admitebúsquedas múltiples.

….Leer (x);I:= 1;

Mientras ( i < n ) y ( a[i] <> x ) hacer I:= i+1;

Fin mientras;Si a[i] = x entonces

20



Emitir (‘está’);SinoEmitir (‘no está);

F si;

• Búsqueda binaria .Consiste en comparar el elto central con el valor buscado. Si este no es igual, se reduce elintervalo de búsqueda a la mitad derecha o izquierda. Según que el valor sea mayor que el elto

central o menor respectivamente. El algoritmo termina cuando se encuentra el elto o biencuando se anula el intervalo de búsqueda.o Ventajas: es muy rápido cuando el arreglo está ordenado.o Desventaja: no se puede aplicar para arreglo desordenados.

….Leer (x);Li := 1; Ls:= n;Me:=(Li + Ls);Mientras (Li < Ls) y (a[me] <> x) hacer

Si a[me] < x entoncesLi := me +1;

SinoLs := me – 1;

F si;Me := (Li + Ls) div 2;

F mientras;Si a[me] = x entonces

Emitir (‘encontrado’);Sino

Emitir (‘elemento inexistente’);F si.

La búsqueda lineal es más rápida cuando el número de eltos del arreglo es pequeño. Ladiferencia con la binaria se nota cuando crece el número de eltos del arreglo.

• Búsqueda en un arreglo de registro. Se realiza a través de un campo clave.

• Recursividad .Es la propiedad por la cual un subprograma puede llamarse a si mismo para realizar una tarea.Un objeto es recursivo, si forma parte de si mismo o se define en funcion de si mismo. Larecursividad reside en la posibilidad de definir un número infinito de objetos mediante unenunciado finito. De igual forma un número infinito de operaciones de cálculo puede describirsemediante un programa recursivo finito.

o Características .♦ una llamada a si mismo.♦ Una condición de fin.

o Pro y contra de la recursividad .

• No utilizar recursividad a menos que tenga un medio para terminar la llamadarecursiva.

• No utilizar recursividad cuando hay limitaciones en la memoria.• No utilizar recursividad cuando no hay una ventaja clara.• Es conveniente generalmente cuando el problema o los datos que deben

manipularse están definidos en forma recursiva.

o Tipos .

• Directa : un subprograma se llama a si mismo una o más veces.• Indirecta : un subprograma A llama a otro B y este a su vez llama a A.

21



LA RECURSIVIDAD PUEDE APLICARSE EN FUCIONES Y PROCEDIMIENTOS

FUNCIONES:

FUNCION factorial (n:entero): entero(n>=0 y definida)

Si n = 0 entonces

Factorial:= 1;SinoFactorial:= n * factorial; (n-1)

F si;

PROCEDIMIENTOS.

PROCEDIMIENTO inverso (n:entero)(n>=0)

Escribir (n mod 10);Si n>= 10 entonces

Inverso (n div 10)F si;

• Arboles .Son estructuras que permiten representar datos que tienen enlaces jerárquicos entre ellos.

Terminología.• Raíz: elto superior.• Nodo Terminal: un nodo que no tiene subárboles.• Nodo interior: 1 o 2 subárboles.

• Bosque: los nodos de cada nivel están ordenados.

22



23

Documents

Teoria de Algoritmos