Fuente http://mx.geocities.com/developer_webs/temario.htm
Método de la burbuja
Es uno de los métodos más extendidos y más fáciles, pero a la vez es uno de los menoseficaces.
Este método se basa en la ordenación por cambio de elementos, ya que se van comparando de dos en dos los elementos de la tabla. Si nosotros deseamos ordenar dicha tabla de menor a mayor (ascendente) al realizar la comparación entre dos elementos se produce el intercambio en el momento en el que el primer elemento es mayor que el segundo. De esta forma el elemento más grande pasa a estar en el último lugar de la tabla. El elemento sube por la tabla, al igual que una burbuja en un recipiente, de ahí proviene su nombre.
Los pasos a seguir utilizando este método son los siguientes, imaginando que deseamos realizar una ordenación creciente:
1.- Se compara el primer elemento con el segundo. Si están desordenados se intercambian. Luego se mira el segundo con el tercero, intercambiando también si es necesario. Así hasta que llegamos al último elemento. De esta forma tenemos en la última posición de nuestra tabla el elemento más grande.
2.- Repetimos lo mismo que antes pero ahora con todos los elemento, menos el último, que ya está ordenado.
3.- Repetimos el primer paso pero esta vez con otro elemento menos, ya que este también está ordenado. Este método finaliza en el momento en el que se han realizado tantas pasadas como objetos - 1 hay en la lista. Su hace menos 1 pasadas porque el primero de los objetos, como es lógico si pensamos que los demás ya están ordenados, ya está ordenado.
Vamos a ver el código que escribiríamos para utilizar este método:
1-Indice = 1
2-Repetir
3-Mientras Indice2 <> TotalElem - 1 hacer
4-Si Tabla(Indice2) > Tabla(Indice + 1) Entonces
5-Intercambiar Tabla(Indice2), Tabla(Indice2 + 1)
6-Fin Si
7-Indice2 = Indice2 + 1
8-Fin Mientras
9-Hasta que Indice > TotalElem - 1
Vamos a comentar como funcionaría este código:
En la línea 1 iniciamos una variable llamada Indice a 1, ya que vamos a suponer que nuestra tabla empieza a contar en el 1, esta variable es la que nos controlará cuando se acaba nuestra ordenación. La ordenación finalizará cuando el valor de Indice sea mayor que el número total de elementos (aquí representado por TotalElem) menos 1, (Mirar línea 9). Ya que como hemos dicho antes suponemos que en la última pasada, solo existirá un elemento a mirar y por lo tanto ya estará ordenado.
En la línea 2 iniciamos un bucle Repetir... Hasta que que termina en la línea 9. Este bucle terminará en el momento en el que el Indice tenga como valor el total de elementos TotalElem menos 1. Ya que entonces terminará la ordenación.
En la línea 3 iniciamos otro bucle que está situado dentro del primero. Este se repetirá para ir comparando de dos en dos los diferentes elementos de la tabla. Se repetirá mientras Indice2 sea diferente del total de elementos menos 1 (TotalElem - 1). Hacemos que sea TotalElem - 1 porque así nos aseguramos que en ningún momento nos salgamos del índice de la tabla. Este bucle termina en la línea 8.
En la línea 4 miramos si el elemento que ocupa la posición Indice2 de la tabla, es más grande que el siguiente elemento (Indice + 1). Este Si termina en la línea 6, en un principio no sería necesario ya que solo tenemos una instrucción el Si, pero así facilitamos un poco el entendimiento de la estructura.
En la línea 5, utilizamos una nueva instrucción llamada Intercambiar. Esta instrucción lo que nos hace es cambiar los elementos que ocupan dos posiciones determinadas de la tabla. Estos elementos los separaremos entre sí mediante una coma (,). Esta línea se llevará a cabo en el momento que el primer elemento mirado sea más grande que el segundo.
En la línea 7 incrementamos el valor de Indice2, para continuar comparando elementos dentro de la tabla.
Esta sería la estructura básica de la ordenación de elementos de una tabla utilizando el método burbuja. Podemos ver que es un método un poco rudimentario y un poco largo en según que casos.
Imagina que tenemos una tabla de un total de 50 elementos y que desde un principio está ordenada, pero eso nosotros no lo sabemos, por lo que sometemos la tabla a una ordenación. Como te puedes imaginar el programa está empleando un tiempo que nos puede ser útil, para realizar cualquier otro cálculo dentro de la aplicación. Piensa que con una tabla de 50 elementos el programa pasará por el bucle principal 49 veces
Método Shell o Inserción directa
Es una mejora del método de inserción directa, utilizado cuando el array tiene un gran número de elementos. En este método no se compara a cada elemento con el de su izquierda, como en el de inserción, sino con el que está a un cierto número de lugares (llamado salto) a su izquierda. Este salto es constante, y su valor inicial es N/2 (siendo N el número de elementos, y siendo división entera). Se van dando pasadas hasta que en una pasada no se intercambie ningún elemento de sitio. Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1.
Por ejemplo, lo pasos para ordenar el array {40,21,4,9,10,35} mediante el método de Shell serían:
Salto=3:
Primera pasada: {9,21,4,40,10,35} <-- se intercambian el 40 y el 9.
{9,10,4,40,21,35} <-- se intercambian el 21 y el 10.Salto=1:
Primera pasada: {9,4,10,40,21,35} <-- se intercambian el 10 y el 4.
{9,4,10,21,40,35} <-- se intercambian el 40 y el 21.
{9,4,10,21,35,40} <-- se intercambian el 35 y el 40.
Segunda pasada: {4,9,10,21,35,40} <-- se intercambian el 4 y el 9.
Con sólo 6 intercambios se ha ordenado el array, cuando por inserción se necesitaban muchos más.
Método Quicksort
Fuente: http://mx.geocities.com/developer_webs/primer_parcial.htm
Ordenación rápida (quicksort): Este método se basa en la táctica "divide y vencerás"que consiste en ir subdividiendo el array en arrays más pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del array como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el array.
Normalmente se toma como pivote el primer elemento de array, y se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.Por ejemplo, para dividir el array {21,40,4,9,10,35}, los pasos serían:
{21,40,4,9,10,35} <-- se toma como pivote el 21. La búsqueda de izquierda a derecha encuantra el valor 40, mayor que pivote, y la búsqueda de derecha a izquierda encuentra el valor 10, menor que el pivote. Se intercambian:{21,10,4,9,40,35} <-- Si seguimos la búsqueda, la primera encuentra el valor 40, y la segunda el valor 9, pero ya se han cruzado, así que paramos. Para terminar la división, se coloca el pivote en su lugar (en el número encontrado por la segunda búsqueda, el 9, quedando:{9,10,4,21,40,35} <-- Ahora tenemos dividido el array en dos arrays más pequeños: el {9,10,4} y el {40,35}, y se repetiría el mismo proceso. Algoritmo Iniciar I a primero Iniciar J a ultimo seleccionar el elemento pivotecentral ← A ( ( primero + ultimo) /2) repetir 4.a mientras a(I) central hacer
j ←j -1
fin mientras
4.csi I < = J entonces intercambiar a(I), A (J) hasta queI >J
si j > primero,llamar al procedimiento partir, para dividir la sub-lista izquierda(primero. J)
si I <>#includeint funcion(const void *,const void *);void main(){ // Dar valores al array
qsort(array,N,sizeof(array[0]),funcion); // Ordena el array. }int funcion(const void *a,const void *b){ if(*(int *)a<*(int *)b) return(-1); else if(*(int *)a>*(int *)b) return(1); else return(0); }Claramente, es mucho más cómodo usar qsort que implementar toda la función, pero hay que tener mucho cuidado con el manejo de los punteros en la función, sobre todo si se está trabajando con estructuras
Método Radix
Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan. Lo que hacemos es determinar la importancia de los criterios de ordenación y aplicar ordenación estable tantas veces como criterios se tengan, empezando por el criterio menos importante y determinando por el criterio más importante
Fuente: http://iteso.mx/~jpgonzal/ed2a.html
Estructura de datos de montículo
La estructura de montículo consiste en almacenar los registros detal manera que cada llave sea mayor que otras dos llaves en posiciones específicas. A su vez, estas dos llaves deberán de ser mayores que otras dos más y así sucesivamente.
Esta estructura se puede representar en un arreglo en el que colocamos la raíz en la posición 1 y las posiciones de sus hjijos son la 2 y la 3, en el siguiente nivel posiciones 4, 5, 6 y 7, etc. Esta representación es muy práctica porque resulta sencillo viajar de un nodo a su padre o hijo. El padre del nodo en la posición j se encuentra en la posición j/2 (redondeado al entero inferior más cercano si j es non) y susdos hijos en las posiciones 2j y 2j + 1. Un montículo es un árbol binario completo, representado con un arreglo, en el que la llave mayor se encuentra en la primera posición del arreglo.
Para poder construir un montículo es necesario primero desarrollar la operación de inserción como en el siguiente código:
void PQ::upheap (int k)
{
itemType v;
v = a[k]; a[0]= itemMAX;
while (a[k/2] <= v)
{ a[k] = a[k/2]; k = k /2; }
a[kl] = v;
}
void PQ::insert (itemType v)
{ a[++N] = v; upheap (N); }
Para poder realizar las operaciones de reemplazar y remover requerimos de otro procedimiento que nos permita arreglar el montículo de arriba hacia abajo como en el siguiente código:
void PQ::downheap (int k)
{
int j, itemType v;
v = a[k];
while (k <= N/2)
{
j = k + k;
if (j < N && a[j] < a[j + 1]) j++;
if (v >= a[j]) break;
a[k] = a[j]; k = j;
}
a[k] = v;
}
itemType PQ::remove()
{
itemType v = a[1];
a[1] = a[N--];
downheap (1);
return v;
}
itemType PQ::replace (itemType v)
{
a[0] = v;
downheap (0);
return a[0];
}
Fuente http://mx.geocities.com/developer_webs/ejecutables.htm
Búsqueda por Hash
Es un método de búsqueda que aumenta la velocidad de búsqueda, pero que no requiere que los elementos estén ordenados. Consiste en asignar a cada elemento un índice mediante una transformación del elemento. Esta correspondencia se realiza mediante una función de conversión, llamada función hash.
jueves, 6 de noviembre de 2008
Métodos de búsqueda
Fuente : http://html.rincondelvago.com/arreglos.html
a)Búsqueda Secuencial
A este método tambien se le conoce como búsqueda lineal y consiste en empezar al inicio del conjunto de elementos , e ir atravez de ellos hasta encontrar el elemento indicado ó hasta llegar al final de arreglo.
Este es el método de búsqueda más lento, pero si nuestro arreglo se encuentra completamente desordenado es el único que nos podrá ayudar a encontrar el dato que buscamos.
ind <- 1
encontrado <- falso
mientras no encontrado y ind < N haz
si arreglo[ind] = valor_buscado entonces
encontrado <- verdadero
en caso contrario
ind <- ind +1
b)Búsqueda Binaria
Las condiciones que debe cumplir el arreglo para poder usar búsqueda binaria son que el arreglo este ordenado y que se conozca el numero de elementos.
Este método consiste en lo siguiente: comparar el elemento buscado con el elemento situado en la mitad del arreglo, si tenemos suerte y los dos valores coinciden, en ese momento la búsqueda termina. Pero como existe un alto porcentaje de que esto no ocurra, repetiremos los pasos anteriores en la mitad inferior del arreglo si el elemento que buscamos resulto menor que el de la mitad del arreglo, o en la mitad superior si el elemento buscado fue mayor.
La búsqueda termina cuando encontramos el elemento o cuando el tamaño del arreglo a examinar sea cero.
encontrado <- falso
primero <- 1
ultimo <- N
mientras primero <= ultimo y no encontrado haz
mitad <- (primero + ultimo)/2
si arreglo[mitad] = valor_buscado entonces
encntrado <- verdadero
en caso contrario
si arreglo[mitad] > valor_buscado entonces
ultimo <- mitad - 1
en caso contrario
primero <- mitad + 1
c)Búsqueda por Hash
La idea principal de este método consiste en aplicar una función que traduce el valor del elemento buscado en un rango de direcciones relativas. Una desventaja importante de este método es que puede ocasionar colisiones.
funcion hash (valor_buscado)
inicio
hash <- valor_buscado mod numero_primo
fin
inicio <- hash (valor)
il <- inicio
encontrado <- falso
repite
si arreglo[il] = valor entonces
encontrado <- verdadero
en caso contrario
il <- (il +1) mod N
hasta encontrado o il = inicio
Fuente http://html.rincondelvago.com/indexacion.html
INDEXACIÓN
`Una piedra angular de la teoría de estructura de datos es la
distinción entre estructuras fundamentales y “avanzadas”.'
Niklaus Wirth,
`Algoritmos + Estructuras de Datos = Programas'
OBJETIVOS DE ESTE CAPÍTULO:
• Comparar las ED's básicas con sus equivalentes avanzadas
• Estudiar el concepto y propiedades fundamentales de los
árboles AVL
• Estudiar el concepto y propiedades fundamentales de los
árboles B como solución al problema de gran número de claves
• Introducir el concepto de Indexación
ÍNDICE TEMA 2.
2.1 Justificación
2.2 Criterios de equilibrio
Árbol perfectamente equilibrado
Árbol AVL
2.3 Árboles B
Concepto
Inserción
Borrado
Cuentas
2.4 Otras organizaciones de árboles B
B*
B+
2.5. Índice
2.6. Acceso secuencial Indexado
1. INDEXACIÓN.- Justificación
Formas de trabajo sobre Memoria Principal:
Tablas
Listas enlazadas
Árboles binarios de búsqueda
Formas de trabajo sobre Memoria Secundaria:
Ficheros secuenciales
Ficheros de acceso directo
• Objetivo: Acceso directo por clave que reduzca el nº de accesos a realizar.
Algunas definiciones
Árbol de Búsqueda:
Las claves del subárbol izquierdo de un nodo son menores, y las del subárbol derecho, mayores, que la del nodo que se trata.
Árbol Ordenado:
Aquel en que las ramas de cada nodo están ordenadas
Grado:
Número de descendientes directos de un nodo interior
Grado de un Árbol:
Máximo de los grados de todos los nodos del árbol
Árbol Binario:
Árboles ordenados de Grado 2.
2. CRITERIOS DE EQUILIBRIO
Árbol perfectamente equilibrado
`Para cada nodo, `el número de nodos' del subárbol izquierdo y del derecho difieren como mucho en una unidad'
Las claves pueden estar ordenadas o no
Criterio algo `rígido'
Generación de un árbol perfectamente equilibrado:
- Hay que conocer el número de claves del árbol
- El procedimiento ha de ser recursivo
- No es necesario que el árbol esté ordenado
- Si `N' es el número de claves del árbol, se generan dos subárboles, con:
Ni = N div 2 nodos
Nd = N - Ni - 1 nodos
- Altura máxima del árbol <= log (n) + 1
-->[Author:(null)]
Árbol equilibrado
`Para cada nodo, `la longitud' del subárbol izquierdo y del derecho difieren como mucho en una unidad'
Si además el árbol es binario de búsqueda Árboles AVL (Adelson-Velskii y Landis, 1962)
Altura mínima del árbol: log ( N + 1 )
Inserción en árbol equilibrado AVL
Situación de desequilibrio. Factor de equilibrio.
Rotaciones: secuencia de rotaciones de punteros que se intercambian cíclicamente:
Simple derecha, DD
Simple izquierda, II
Doble derecha, ID(*)
Doble izquierda, DI(*)
Estado de equilibrio de cada nodo:
TYPE
tarbol = ^tnodo
tnodo = RECORD
clave: tclave;
izquierdo, derecho: tarbol;
equilibrio: -1..1;
END;
Proceso de Inserción :
Seguir el camino de búsqueda hasta ver que la clave no esta en el árbol.
• Insertar el nuevo nodo, y obtener los nuevos valores de equilibrio.
• Volver por el camino de búsqueda comprobando el factor de equilibrio de cada nodo
Parámetros que se necesitan :
Árbol donde realizar la inserción
• • Clave que se quiere insertar
• • Información de la altura del subárbol (tipo de parámetro ?)
Casos posibles en la realización:
hi < hd ! a!.equilibrio = +1
hi = hd ! a!.equilibrio = 0
hi > hd ! a!.equilibrio = -1
Borrado en árbol equilibrado AVL
Proceso de Borrado:
Búsqueda de la clave.
• • Estudio del equilibrio del árbol.
Parámetros que se necesitan:
Árbol donde realizar la inserción
• • Clave que se quiere borrar.
• • Información de la altura del subárbol.
Casos posibles en la implementación:
Borrado de una hoja sin desequilibrio
• • Borrado de una hoja con desequilibrio
• • Borrado de un nodo interno sin desequilibrio
• • Borrado de un nodo interno con desequilibrio
• Caso 2: DD, II, DI, ID,
Caso 2: DD, II, DI, ID,
Caso 2: DD, II, DI, ID,
3. ÁRBOLES B
“Al buscar una forma de controlar el crecimiento, el árbol perfectamente equilibrado se deshecha inmediatamente debido al gran esfuerzo que requiere la operación de reequilibrado.”
N. Wirth.
Árboles MULTICAMINO: Cada nodo puede tener más de dos ramas.
Realización:
Array de registros
Lista lineal
Utilización:
• Construcción y mantenimiento de árboles de búsqueda a gran escala.
o
División del árbol en subárboles
Páginas
Árboles B
El orden del árbol es n
Todas las páginas, excepto la raíz, tienen entre n y 2n claves
Cada página es una página-hoja (no tiene descendientes), o tiene m+1 descendientes; m ! número de claves de la página
Todas las páginas-hoja se encuentran al mismo nivel
Supóngase la página del árbol:
!
P0 K1 P1 K2 P2 ... Pm-1 Km Pm
! ! ! ! !
¿Qué casos pueden presentarse si una clave `x' no se encuentra en esta página?
Inserción de un elemento en un árbol B
Si la página donde se inserta tiene m > 2n nodos?
Si “ “ “ tiene m = 2n nodos?
Declaración de la estructura de una página:
type pagina = record
m: indice;
p0: ref;
e: array [1 .. nn] of item
end;
const nn = 2 * n;
type ref = !pagina;
indice = 0 .. nn;
item = record
clave: integer;
p: ref;
contador: integer
end;
Conveniencia de una formulación recursiva?
Algoritmo de Búsqueda e Inserción en un árbol B
Buscar ( x: integer; (* Nodo a insertar/buscar *)
a: tArbol; (* Árbol B *)
var cambio: boolean; (* El árbol ha crecido *)
var u: tItem;) (* Elemento que sube de nivel *)
if a = nil
- copiar `x' en `u'
- cambio := true
else
- buscar x en el array
- si está ! operaciones a realizar con la clave
- si no está !
llamada recursiva (x, página siguiente, cambio, u)
if cambio (* se sube un elemento *)
- si m < 2n
- se inserta en esa página
- m := m + 1
- cambio := false
- si m = 2n
- divide página
- copiar en u el elemento en el medio
end
Borrado de un elemento en un árbol B
Casos:
- la clave a borrar está en una hoja
- la clave a borrar no está en una hoja
!
Se sustituye por elementos adyacentes
Número de claves de la página en un árbol B
1.- La información se almacena dentro de la página asociada a las claves
- Estructura para las claves: 2n * tamaño clave
- Estructura para la información: 2n * tamaño info
- Estructura para los descendientes: (2n + 1) * tamaño descendientes
Tamaño de la página "
1 + (2n * Tclave) + (2n * Tinfo) + (2n + 1) * Tdescen =
= (1 + Tdescen) + 2n * (Tclave + Tinfo + Tdescen)
Tpagina - (1 + Tdescen)
n " ___________
Tclave + Tinfo * Tdescen
2.- La información se almacena en un TAD independiente (p.ej. un fichero).
- Estructura para las claves: 2n * tamaño clave
- Estructura para las posiciones: 2n * tamaño posición
- Estructura para los descendientes: (2n + 1) * tamaño descendientes
Tamaño de la página "
1 + (2n * Tclave) + (2n * Tposición) + (2n + 1) * Tdescen =
= (1 + Tdescen) + 2n * (Tclave + Tposición + Tdescen)
Tpagina - (1 + Tdescen)
n " ____________
Tclave + Tposición * Tdescen
Altura de la página de un árbol B
En el peor caso:
- La raíz sólo tiene una clave
- Todas las demás páginas tienen n claves
Nivel 1 1 sola clave-->[Author:(null)] 2 descendientes
Nivel 2 2 pág. con n claves-->[Author:(null)] 2 * (n + 1) descen.
Nivel 3 2 * (n + 1) pág. con n claves-->[Author:(null)] 2 * (n + 1)2 descen.
Nivel 4 2 * (n + 1)2 pág. con n claves 2 * (n + 1)3 descen.
.
.
.
Nivel d 2 * (n + 1)d-2 pág. con n claves 2 * (n + 1)d-1 descen.
Un razonamiento iterativo:
- Una página tiene `n' claves `n + 1' descendientes
- La raíz sólo tiene 1 clave
- Un árbol con `x' claves tiene `x + 1' descendientes en el nivel de las hojas
La altura será aquella que cumpla:
x + 1 " Nº de descendientes al nivel de las hojas = 2 * (n + 1) d - 1
de donde:
d " 1 + log n*1 ((x + 1)/2)
Árboles B*:
Concepto de `Redistribución'
Árboles B*:
Árbol B especial, en el que cada nodo está lleno por lo menos en dos terceras partes (66%). Proporcionan mejor utilización del almacenamiento que los árboles B(6). La situación se genera cuando se produce una inserción al dividir, de dos páginas a tres en lugar de una a dos.
! Cada página tiene un máximo de m descendientes.
! Todas las páginas, excepto la raíz y las hojas, tiene al menos (2m - 1) / 3) descendientes.
! La raíz tiene al menos dos descendientes, al menos que sea `hoja'.
! Todas las páginas-hoja se encuentran al mismo nivel.
! Una página que no sea hoja, con k descendientes, contiene k - 1 claves.
! Una página-hoja contiene al menos [(2m - 1) / 3] claves, y no más de (m - 1)
Árboles B+: El índice del árbol se almacena en un árbol B separado, que permite encontrar la información, que se encuentra en los registros de un fichero secuencial indexado.
5. INDEXACIÓN
Índice Establece un `Orden' en un fichero
Puede ser múltiple
Primera aproximación : tabla de registros
Operaciones básicas de un fichero Indexado :
Creación
Lectura de Índice
Actualización de Índice
Inserción de registros
Eliminación de registros
Modificación de registros
a)Búsqueda Secuencial
A este método tambien se le conoce como búsqueda lineal y consiste en empezar al inicio del conjunto de elementos , e ir atravez de ellos hasta encontrar el elemento indicado ó hasta llegar al final de arreglo.
Este es el método de búsqueda más lento, pero si nuestro arreglo se encuentra completamente desordenado es el único que nos podrá ayudar a encontrar el dato que buscamos.
ind <- 1
encontrado <- falso
mientras no encontrado y ind < N haz
si arreglo[ind] = valor_buscado entonces
encontrado <- verdadero
en caso contrario
ind <- ind +1
b)Búsqueda Binaria
Las condiciones que debe cumplir el arreglo para poder usar búsqueda binaria son que el arreglo este ordenado y que se conozca el numero de elementos.
Este método consiste en lo siguiente: comparar el elemento buscado con el elemento situado en la mitad del arreglo, si tenemos suerte y los dos valores coinciden, en ese momento la búsqueda termina. Pero como existe un alto porcentaje de que esto no ocurra, repetiremos los pasos anteriores en la mitad inferior del arreglo si el elemento que buscamos resulto menor que el de la mitad del arreglo, o en la mitad superior si el elemento buscado fue mayor.
La búsqueda termina cuando encontramos el elemento o cuando el tamaño del arreglo a examinar sea cero.
encontrado <- falso
primero <- 1
ultimo <- N
mientras primero <= ultimo y no encontrado haz
mitad <- (primero + ultimo)/2
si arreglo[mitad] = valor_buscado entonces
encntrado <- verdadero
en caso contrario
si arreglo[mitad] > valor_buscado entonces
ultimo <- mitad - 1
en caso contrario
primero <- mitad + 1
c)Búsqueda por Hash
La idea principal de este método consiste en aplicar una función que traduce el valor del elemento buscado en un rango de direcciones relativas. Una desventaja importante de este método es que puede ocasionar colisiones.
funcion hash (valor_buscado)
inicio
hash <- valor_buscado mod numero_primo
fin
inicio <- hash (valor)
il <- inicio
encontrado <- falso
repite
si arreglo[il] = valor entonces
encontrado <- verdadero
en caso contrario
il <- (il +1) mod N
hasta encontrado o il = inicio
Fuente http://html.rincondelvago.com/indexacion.html
INDEXACIÓN
`Una piedra angular de la teoría de estructura de datos es la
distinción entre estructuras fundamentales y “avanzadas”.'
Niklaus Wirth,
`Algoritmos + Estructuras de Datos = Programas'
OBJETIVOS DE ESTE CAPÍTULO:
• Comparar las ED's básicas con sus equivalentes avanzadas
• Estudiar el concepto y propiedades fundamentales de los
árboles AVL
• Estudiar el concepto y propiedades fundamentales de los
árboles B como solución al problema de gran número de claves
• Introducir el concepto de Indexación
ÍNDICE TEMA 2.
2.1 Justificación
2.2 Criterios de equilibrio
Árbol perfectamente equilibrado
Árbol AVL
2.3 Árboles B
Concepto
Inserción
Borrado
Cuentas
2.4 Otras organizaciones de árboles B
B*
B+
2.5. Índice
2.6. Acceso secuencial Indexado
1. INDEXACIÓN.- Justificación
Formas de trabajo sobre Memoria Principal:
Tablas
Listas enlazadas
Árboles binarios de búsqueda
Formas de trabajo sobre Memoria Secundaria:
Ficheros secuenciales
Ficheros de acceso directo
• Objetivo: Acceso directo por clave que reduzca el nº de accesos a realizar.
Algunas definiciones
Árbol de Búsqueda:
Las claves del subárbol izquierdo de un nodo son menores, y las del subárbol derecho, mayores, que la del nodo que se trata.
Árbol Ordenado:
Aquel en que las ramas de cada nodo están ordenadas
Grado:
Número de descendientes directos de un nodo interior
Grado de un Árbol:
Máximo de los grados de todos los nodos del árbol
Árbol Binario:
Árboles ordenados de Grado 2.
2. CRITERIOS DE EQUILIBRIO
Árbol perfectamente equilibrado
`Para cada nodo, `el número de nodos' del subárbol izquierdo y del derecho difieren como mucho en una unidad'
Las claves pueden estar ordenadas o no
Criterio algo `rígido'
Generación de un árbol perfectamente equilibrado:
- Hay que conocer el número de claves del árbol
- El procedimiento ha de ser recursivo
- No es necesario que el árbol esté ordenado
- Si `N' es el número de claves del árbol, se generan dos subárboles, con:
Ni = N div 2 nodos
Nd = N - Ni - 1 nodos
- Altura máxima del árbol <= log (n) + 1
-->[Author:(null)]
Árbol equilibrado
`Para cada nodo, `la longitud' del subárbol izquierdo y del derecho difieren como mucho en una unidad'
Si además el árbol es binario de búsqueda Árboles AVL (Adelson-Velskii y Landis, 1962)
Altura mínima del árbol: log ( N + 1 )
Inserción en árbol equilibrado AVL
Situación de desequilibrio. Factor de equilibrio.
Rotaciones: secuencia de rotaciones de punteros que se intercambian cíclicamente:
Simple derecha, DD
Simple izquierda, II
Doble derecha, ID(*)
Doble izquierda, DI(*)
Estado de equilibrio de cada nodo:
TYPE
tarbol = ^tnodo
tnodo = RECORD
clave: tclave;
izquierdo, derecho: tarbol;
equilibrio: -1..1;
END;
Proceso de Inserción :
Seguir el camino de búsqueda hasta ver que la clave no esta en el árbol.
• Insertar el nuevo nodo, y obtener los nuevos valores de equilibrio.
• Volver por el camino de búsqueda comprobando el factor de equilibrio de cada nodo
Parámetros que se necesitan :
Árbol donde realizar la inserción
• • Clave que se quiere insertar
• • Información de la altura del subárbol (tipo de parámetro ?)
Casos posibles en la realización:
hi < hd ! a!.equilibrio = +1
hi = hd ! a!.equilibrio = 0
hi > hd ! a!.equilibrio = -1
Borrado en árbol equilibrado AVL
Proceso de Borrado:
Búsqueda de la clave.
• • Estudio del equilibrio del árbol.
Parámetros que se necesitan:
Árbol donde realizar la inserción
• • Clave que se quiere borrar.
• • Información de la altura del subárbol.
Casos posibles en la implementación:
Borrado de una hoja sin desequilibrio
• • Borrado de una hoja con desequilibrio
• • Borrado de un nodo interno sin desequilibrio
• • Borrado de un nodo interno con desequilibrio
• Caso 2: DD, II, DI, ID,
Caso 2: DD, II, DI, ID,
Caso 2: DD, II, DI, ID,
3. ÁRBOLES B
“Al buscar una forma de controlar el crecimiento, el árbol perfectamente equilibrado se deshecha inmediatamente debido al gran esfuerzo que requiere la operación de reequilibrado.”
N. Wirth.
Árboles MULTICAMINO: Cada nodo puede tener más de dos ramas.
Realización:
Array de registros
Lista lineal
Utilización:
• Construcción y mantenimiento de árboles de búsqueda a gran escala.
o
División del árbol en subárboles
Páginas
Árboles B
El orden del árbol es n
Todas las páginas, excepto la raíz, tienen entre n y 2n claves
Cada página es una página-hoja (no tiene descendientes), o tiene m+1 descendientes; m ! número de claves de la página
Todas las páginas-hoja se encuentran al mismo nivel
Supóngase la página del árbol:
!
P0 K1 P1 K2 P2 ... Pm-1 Km Pm
! ! ! ! !
¿Qué casos pueden presentarse si una clave `x' no se encuentra en esta página?
Inserción de un elemento en un árbol B
Si la página donde se inserta tiene m > 2n nodos?
Si “ “ “ tiene m = 2n nodos?
Declaración de la estructura de una página:
type pagina = record
m: indice;
p0: ref;
e: array [1 .. nn] of item
end;
const nn = 2 * n;
type ref = !pagina;
indice = 0 .. nn;
item = record
clave: integer;
p: ref;
contador: integer
end;
Conveniencia de una formulación recursiva?
Algoritmo de Búsqueda e Inserción en un árbol B
Buscar ( x: integer; (* Nodo a insertar/buscar *)
a: tArbol; (* Árbol B *)
var cambio: boolean; (* El árbol ha crecido *)
var u: tItem;) (* Elemento que sube de nivel *)
if a = nil
- copiar `x' en `u'
- cambio := true
else
- buscar x en el array
- si está ! operaciones a realizar con la clave
- si no está !
llamada recursiva (x, página siguiente, cambio, u)
if cambio (* se sube un elemento *)
- si m < 2n
- se inserta en esa página
- m := m + 1
- cambio := false
- si m = 2n
- divide página
- copiar en u el elemento en el medio
end
Borrado de un elemento en un árbol B
Casos:
- la clave a borrar está en una hoja
- la clave a borrar no está en una hoja
!
Se sustituye por elementos adyacentes
Número de claves de la página en un árbol B
1.- La información se almacena dentro de la página asociada a las claves
- Estructura para las claves: 2n * tamaño clave
- Estructura para la información: 2n * tamaño info
- Estructura para los descendientes: (2n + 1) * tamaño descendientes
Tamaño de la página "
1 + (2n * Tclave) + (2n * Tinfo) + (2n + 1) * Tdescen =
= (1 + Tdescen) + 2n * (Tclave + Tinfo + Tdescen)
Tpagina - (1 + Tdescen)
n " ___________
Tclave + Tinfo * Tdescen
2.- La información se almacena en un TAD independiente (p.ej. un fichero).
- Estructura para las claves: 2n * tamaño clave
- Estructura para las posiciones: 2n * tamaño posición
- Estructura para los descendientes: (2n + 1) * tamaño descendientes
Tamaño de la página "
1 + (2n * Tclave) + (2n * Tposición) + (2n + 1) * Tdescen =
= (1 + Tdescen) + 2n * (Tclave + Tposición + Tdescen)
Tpagina - (1 + Tdescen)
n " ____________
Tclave + Tposición * Tdescen
Altura de la página de un árbol B
En el peor caso:
- La raíz sólo tiene una clave
- Todas las demás páginas tienen n claves
Nivel 1 1 sola clave-->[Author:(null)] 2 descendientes
Nivel 2 2 pág. con n claves-->[Author:(null)] 2 * (n + 1) descen.
Nivel 3 2 * (n + 1) pág. con n claves-->[Author:(null)] 2 * (n + 1)2 descen.
Nivel 4 2 * (n + 1)2 pág. con n claves 2 * (n + 1)3 descen.
.
.
.
Nivel d 2 * (n + 1)d-2 pág. con n claves 2 * (n + 1)d-1 descen.
Un razonamiento iterativo:
- Una página tiene `n' claves `n + 1' descendientes
- La raíz sólo tiene 1 clave
- Un árbol con `x' claves tiene `x + 1' descendientes en el nivel de las hojas
La altura será aquella que cumpla:
x + 1 " Nº de descendientes al nivel de las hojas = 2 * (n + 1) d - 1
de donde:
d " 1 + log n*1 ((x + 1)/2)
Árboles B*:
Concepto de `Redistribución'
Árboles B*:
Árbol B especial, en el que cada nodo está lleno por lo menos en dos terceras partes (66%). Proporcionan mejor utilización del almacenamiento que los árboles B(6). La situación se genera cuando se produce una inserción al dividir, de dos páginas a tres en lugar de una a dos.
! Cada página tiene un máximo de m descendientes.
! Todas las páginas, excepto la raíz y las hojas, tiene al menos (2m - 1) / 3) descendientes.
! La raíz tiene al menos dos descendientes, al menos que sea `hoja'.
! Todas las páginas-hoja se encuentran al mismo nivel.
! Una página que no sea hoja, con k descendientes, contiene k - 1 claves.
! Una página-hoja contiene al menos [(2m - 1) / 3] claves, y no más de (m - 1)
Árboles B+: El índice del árbol se almacena en un árbol B separado, que permite encontrar la información, que se encuentra en los registros de un fichero secuencial indexado.
5. INDEXACIÓN
Índice Establece un `Orden' en un fichero
Puede ser múltiple
Primera aproximación : tabla de registros
Operaciones básicas de un fichero Indexado :
Creación
Lectura de Índice
Actualización de Índice
Inserción de registros
Eliminación de registros
Modificación de registros
Definición de metodos de ordenación
Fuente:http://www.ica.luz.ve/juancol/eda/ordenacion/ordenacion.html
Los métodos de ordenación elementales proporcionan:
-Una terminología básica
-Un mecanismo básico que puede extenderse a otros métodos más generales, sofisticados y con mejor desempeño.
Típicamente, los métodos de ordenación elementales tienen peor desempeño que los sofisticados, pero existen muchas aplicaciones en las que es mejor utilizar un método de ordenación elemental. Por ejemplo, cuando el algoritmo se utiliza pocas veces y/o se ordenan pocos elementos.
Como regla general se tiene que los métodos elementales necesitan cerca de pasos para ordenar elementos organizados al azar.
En general, no se recomienda su uso para ordenar:
-Archivos grandes
-Archivos clasificados aleatoriamente.
Por su parte, métodos mas avanzados pueden lograr desempeños de orden , , . Mas aún, se puede demostrar que ningún método de ordenación puede utilizar menos de comparaciones entre claves cuando éstas están organizadas al azar.
Terminología General
En el contexto de los métodos de ordenación, cada elemento de dato tiene su clave, y los métodos de ordenación trabajan ordenando los elementos de dato según sus claves. Por lo regular, los métodos comparan las claves e intercambian los elementos de dato. En lugar de desplazar físicamente los elementos de datos, con frecuencia, sólo se intercambian índices, punteros o referencias. Esto se denomina ordenación indirecta.
Un método de ordenación que trabaja sobre un conjunto de datos que se encuentra en memoria (e.g., un arreglo, una lista) se dice que es un método de ordenación interna. Por el contrario, si el conjunto de datos almacenados en archivos no pueden ser cargado en memoria (por ejemplo, por razones de tamaño) y el método de ordenación opera sobre los archivos, se dice que es de ordenación externa. Evidentemente, en la ordenación interna se accede a los elementos de dato más fácilmente, mientras que en la ordenación externa se accede a los elementos de dato de forma secuencial o al menos en grades bloques.
Los métodos de ordenación se pueden clasificar de acuerdo a sus requerimientos de memoria.
Los métodos in situ son aquellos que requieren ninguna o muy poca memoria extra. En el otro extremo, existen métodos que requieren mucha memoria extra.
Una característica que puede ser importante es la estabilidad del método de ordenación. Un algoritmo de ordenación es estable si elementos de dato con la misma clave conservan su orden relativo luego de su aplicación. Típicamente, los métodos elementales son estables mientras que la mayoría de los algoritmos sofisticados no lo son.
Que es el Intercambio Directo?
Ordenación por intercambio
Fuente: http://www.geocities.com/j_santanah/intercambio.htm
Ordenación por intercambio Directo (burbuja).- La idea básica de este algoritmo consiste en compara pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados.
Ejemplos: Suponga 16, 67, 08, 16, 44, 27, 12, 35
Primera pasada
A[7] > A[8] 12>35 No hay intercambio
A[6] > A[7] 27>12 Si hay intercambio
A[5] > A[6] 44>12 Si hay intercambio
A[4] > A[5] 16>12 Si hay intercambio
A[3] > A[4] 08>12 No hay intercambio
A[2] > A[3] 67>08 Si hay intercambio
A[1] > A[2] 15>08 Si hay intercambio
Luego de la primera pasada
A: 08, 15, 67, 12, 16, 44, 27, 35
Luego de la segunda pasada
A:= 08, 12, 15, 67, 16, 27, 44, 35
3ª. Pasada 08, 12, 15, 16, 67, 27, 35, 44
4ª. Pasada 08, 12, 15, 16, 27, 67, 35, 44
5ª. Pasada 08, 12, 15, 16, 27, 67, 35, 44
6ª. Psada 08, 12, 15, 16, 27, 35, 67, 44
7ª. Pasada 08, 12, 15, 16, 27, 35, 44, 67
BURBUJA1(A,N)
El algoritmo ordena los elementos del arreglo utilizando el método de burbuja, transporta en cada pasada el elemento más pequeño hacia la parte izquierda del arreglo. A es un arreglo de N elementos. {I, J, aux son variables de tipo entero}
1.- Repetir con I desde 2 hasta N
1.1.- Repetir con J desde N hasta I
1.1.1.- Si A[J-1]>A[J] entonces hacer: aux<- a[J-1], a[J-1]<- A[J] A[J]<-aux
1.1.2.- {fin del condicional del paso 1.1.1
1.2.- {in del ciclo del paso
1.12.- {fin del ciclo de paso1
ANALISIS DE EFICIENCIA DEL METODO DE INTERCAMBIO DIRECTO (BURBUJA)
El número de comparaciones en el método de la burbuja es fácilmente contabilizable. En la primera pasada realizamos (n-1) comparaciones, en la segunda pasada (n-2) comparaciones, en la tercera pasada (n-3) comparaciones y así sucesivamente hasta llegar a 2 y 1 comparaciones entre claves, siendo n el número de elementos del arreglo.
Por lo tanto:
C=(n-1)+(n-2)+.......................+2+1= n*(n-1)/2
Que es igual a: C = (n2-n)/2
Respecto al número de movimientos, estos dependen de si el arreglo está ordenado desordenado o en orden inverso.
Los movimientos para cada uno de los casos son:
Mmin = 0
Mmed = 0.75*(n2-n)
Mmax = 1.5*(n2-n)
El tiempo necesario para ejecutar el algoritmo de burbuja es proporcionar a n2, o(n2) donde n es el número de elementos del arreglo.
Los métodos de ordenación elementales proporcionan:
-Una terminología básica
-Un mecanismo básico que puede extenderse a otros métodos más generales, sofisticados y con mejor desempeño.
Típicamente, los métodos de ordenación elementales tienen peor desempeño que los sofisticados, pero existen muchas aplicaciones en las que es mejor utilizar un método de ordenación elemental. Por ejemplo, cuando el algoritmo se utiliza pocas veces y/o se ordenan pocos elementos.
Como regla general se tiene que los métodos elementales necesitan cerca de pasos para ordenar elementos organizados al azar.
En general, no se recomienda su uso para ordenar:
-Archivos grandes
-Archivos clasificados aleatoriamente.
Por su parte, métodos mas avanzados pueden lograr desempeños de orden , , . Mas aún, se puede demostrar que ningún método de ordenación puede utilizar menos de comparaciones entre claves cuando éstas están organizadas al azar.
Terminología General
En el contexto de los métodos de ordenación, cada elemento de dato tiene su clave, y los métodos de ordenación trabajan ordenando los elementos de dato según sus claves. Por lo regular, los métodos comparan las claves e intercambian los elementos de dato. En lugar de desplazar físicamente los elementos de datos, con frecuencia, sólo se intercambian índices, punteros o referencias. Esto se denomina ordenación indirecta.
Un método de ordenación que trabaja sobre un conjunto de datos que se encuentra en memoria (e.g., un arreglo, una lista) se dice que es un método de ordenación interna. Por el contrario, si el conjunto de datos almacenados en archivos no pueden ser cargado en memoria (por ejemplo, por razones de tamaño) y el método de ordenación opera sobre los archivos, se dice que es de ordenación externa. Evidentemente, en la ordenación interna se accede a los elementos de dato más fácilmente, mientras que en la ordenación externa se accede a los elementos de dato de forma secuencial o al menos en grades bloques.
Los métodos de ordenación se pueden clasificar de acuerdo a sus requerimientos de memoria.
Los métodos in situ son aquellos que requieren ninguna o muy poca memoria extra. En el otro extremo, existen métodos que requieren mucha memoria extra.
Una característica que puede ser importante es la estabilidad del método de ordenación. Un algoritmo de ordenación es estable si elementos de dato con la misma clave conservan su orden relativo luego de su aplicación. Típicamente, los métodos elementales son estables mientras que la mayoría de los algoritmos sofisticados no lo son.
Que es el Intercambio Directo?
Ordenación por intercambio
Fuente: http://www.geocities.com/j_santanah/intercambio.htm
Ordenación por intercambio Directo (burbuja).- La idea básica de este algoritmo consiste en compara pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados.
Ejemplos: Suponga 16, 67, 08, 16, 44, 27, 12, 35
Primera pasada
A[7] > A[8] 12>35 No hay intercambio
A[6] > A[7] 27>12 Si hay intercambio
A[5] > A[6] 44>12 Si hay intercambio
A[4] > A[5] 16>12 Si hay intercambio
A[3] > A[4] 08>12 No hay intercambio
A[2] > A[3] 67>08 Si hay intercambio
A[1] > A[2] 15>08 Si hay intercambio
Luego de la primera pasada
A: 08, 15, 67, 12, 16, 44, 27, 35
Luego de la segunda pasada
A:= 08, 12, 15, 67, 16, 27, 44, 35
3ª. Pasada 08, 12, 15, 16, 67, 27, 35, 44
4ª. Pasada 08, 12, 15, 16, 27, 67, 35, 44
5ª. Pasada 08, 12, 15, 16, 27, 67, 35, 44
6ª. Psada 08, 12, 15, 16, 27, 35, 67, 44
7ª. Pasada 08, 12, 15, 16, 27, 35, 44, 67
BURBUJA1(A,N)
El algoritmo ordena los elementos del arreglo utilizando el método de burbuja, transporta en cada pasada el elemento más pequeño hacia la parte izquierda del arreglo. A es un arreglo de N elementos. {I, J, aux son variables de tipo entero}
1.- Repetir con I desde 2 hasta N
1.1.- Repetir con J desde N hasta I
1.1.1.- Si A[J-1]>A[J] entonces hacer: aux<- a[J-1], a[J-1]<- A[J] A[J]<-aux
1.1.2.- {fin del condicional del paso 1.1.1
1.2.- {in del ciclo del paso
1.12.- {fin del ciclo de paso1
ANALISIS DE EFICIENCIA DEL METODO DE INTERCAMBIO DIRECTO (BURBUJA)
El número de comparaciones en el método de la burbuja es fácilmente contabilizable. En la primera pasada realizamos (n-1) comparaciones, en la segunda pasada (n-2) comparaciones, en la tercera pasada (n-3) comparaciones y así sucesivamente hasta llegar a 2 y 1 comparaciones entre claves, siendo n el número de elementos del arreglo.
Por lo tanto:
C=(n-1)+(n-2)+.......................+2+1= n*(n-1)/2
Que es igual a: C = (n2-n)/2
Respecto al número de movimientos, estos dependen de si el arreglo está ordenado desordenado o en orden inverso.
Los movimientos para cada uno de los casos son:
Mmin = 0
Mmed = 0.75*(n2-n)
Mmax = 1.5*(n2-n)
El tiempo necesario para ejecutar el algoritmo de burbuja es proporcionar a n2, o(n2) donde n es el número de elementos del arreglo.
miércoles, 22 de octubre de 2008
Estructura de datos
Estructura: conjunto de parámetros o reglas que nos permiten ordenar datos.
Estructuras de control: permiten tomar decisiones de tipo booleano
(IF- THEN, IF THEN ELSE, SWITCH, CASE)
Estructuras interactivas también llamadas de repetición: (WHILE, DO UNTIL, FOR, DO WHILE)
Punteros variables de tipo flotante que se mueven dentro de un vector (índices)
Tipos de búsqueda:
Búsqueda ascendente búsqueda descendente Búsqueda binaria
Ejercicio1. Declarar matriz de 3 * 3 con números en horizontal y llenarla.
Inicio
int A[1..3] , int x,y; x=columnas y = filas
for x=1 hasta x=3
for y=1 hasta y=3
A [x,y] = A[x,y]+1
imprimir A[x,y],
fin
Ejercicio 2. Multiplicar un vector por 2-Multiplicar una matriz de 3*2*2- Se declaran 2 arreglos
Inicio
int A[1..3] , int x,y; x=columnas y = filas
for x=1 hasta x=3
for y=1 hasta y=3
A [x,y] = A[x,y]+1
imprimir A[x,y] *2,
fin
Ejercicio3. Introducción a métodos de ordenamiento binario, declarar una matriz de 3x3, determinar que registros se encuentran en la posición 2.1
Inicio
int A[1..3] [1..3]
int B[1..3] [1..3]
for x=1 hasta x=3
for y=1 hasta y=3
A [x,y] = A[x,y]+1
imprimir x,y
fin
ARREGLOS:
1.2 Arreglos Unidimensionales
Un arreglo unidimensional es un tipo de datos estructurado que está formado de una colección finita y ordenada de datos del mismo tipo. Es la estructura natural para modelar listas de elementos iguales.
El tipo de acceso a los arreglos unidimensionales es el acceso directo, es decir, podemos acceder a cualquier elemento del arreglo sin tener que consultar a elementos anteriores o posteriores, esto mediante el uso de un índice para cada elemento del arreglo que nos da su posición relativa.
Para implementar arreglos unidimensionales se debe reservar espacio en memoria, y se debe proporcionar la dirección base del arreglo, la cota superior y la inferior.
REPRESENTACION EN MEMORIA
Los arreglos se representan en memoria de la forma siguiente:
x : array[1..5] of integer
Para establecer el rango del arreglo (número total de elementos) que componen el arreglo se utiliza la siguiente formula:
RANGO = Ls - (Li+1)
donde:
ls = Límite superior del arreglo
li = Límite inferior del arreglo
Para calcular la dirección de memoria de un elemento dentro de un arreglo se usa la siguiente formula:
A[i] = base(A) + [(i-li) * w]
donde :
A = Identificador único del arreglo
i = Indice del elemento
li = Límite inferior
w = Número de bytes tipo componente
Si el arreglo en el cual estamos trabajando tiene un índice numerativo utilizaremos las siguientes fórmulas:
RANGO = ord (ls) - (ord (li)+1)
A[i] = base (A) + [ord (i) - ord (li) * w]
1.3 Arreglos Bidimensionales
Este tipo de arreglos al igual que los anteriores es un tipo de dato estructurado, finito ordenado y homogéneo. El acceso a ellos también es en forma directa por medio de un par de índices.
Los arreglos bidimensionales se usan para representar datos que pueden verse como una tabla con filas y columnas. La primera dimensión del arreglo representa las columnas, cada elemento contiene un valor y cada dimensión representa una relación
La representación en memoria se realiza de dos formas : almacenamiento por columnas o por renglones.
Para determinar el número total de elementos en un arreglo bidimensional usaremos las siguientes fórmulas:
RANGO DE RENGLONES (R1) = Ls1 - (Li1+1)
RANGO DE COLUMNAS (R2) = Ls2 - (Li2+1)
No. TOTAL DE COMPONENTES = R1 * R2
REPRESENTACION EN MEMORIA POR COLUMNAS
x : array [1..5,1..7] of integer
Para calcular la dirección de memoria de un elemento se usan la siguiente formula:
A[i,j] = base (A) + [((j - li2) R1 + (i + li1))*w]
REPRESENTACION EN MEMORIA POR RENGLONES
x : array [1..5,1..7] of integer
Para calcular la dirección de memoria de un elemento se usan la siguiente formula:
A[i,j] = base (A) + [((i - li1) R2 + (j + li2))*w]
donde:
i = Indice del renglón a calcular
j = Indice de la columna a calcular
li1 = Límite inferior de renglones
li2 = Límite inferior de columnas
w = Número de bytes tipo componente
1.4 Arreglos Multidimensionales
Este también es un tipo de dato estructurado, que está compuesto por n dimensiones. Para hacer referencia a cada componente del arreglo es necesario utilizar n índices, uno para cada dimensión
Para determinar el número de elementos en este tipo de arreglos se usan las siguientes fórmulas:
RANGO (Ri) = lsi - (lii + 1)
No. TOTAL DE ELEMENTOS = R1 * R2* R3 * ...* Rn
donde:
i = 1 ... n
n = No. total de dimensiones
Para determinar la dirección de memoria se usa la siguiente formula:
LOC A[i1,i2,i3,...,in] = base(A) + [(i1-li1)*R3*R4*Rn + (i2-li2)*R3*R2*... (in - lin)*Rn]*w
1.5 Operaciones Con Arreglos
Las operaciones en arreglos pueden clasificarse de la siguiente forma:
• Lectura
• Escritura
• Asignación
• Actualización
• Ordenación
• Búsqueda
a) LECTURA
Este proceso consiste en leer un dato de un arreglo y asignar un valor a cada uno de sus componentes.
La lectura se realiza de la siguiente manera:
para i desde 1 hasta N haz
x<--arreglo[i]
b) ESCRITURA
Consiste en asignarle un valor a cada elemento del arreglo.
La escritura se realiza de la siguiente manera:
para i desde 1 hasta N haz
arreglo[i]<--x
c) ASIGNACION
No es posible asignar directamente un valor a todo el arreglo, por lo que se realiza de la manera siguiente:
para i desde 1 hasta N haz
arreglo[i]<--algún_valor
d) ACTUALIZACION
Dentro de esta operación se encuentran las operaciones de eliminar, insertar y modificar datos. Para realizar este tipo de operaciones se debe tomar en cuenta si el arreglo está o no ordenado.
Para arreglos ordenados los algoritmos de inserción, borrado y modificación son los siguientes:
1.- Insertar.
Si i< mensaje(arreglo contrario caso En arreglo[i]<--valor i<--i+1 entonces>
2.- Borrar.
Si N>=1 entonces
inicio
i<--1
encontrado<--falso
mientras i<=n y encontrado=falso
inicio
si arreglo[i]=valor_a_borrar entonces
inicio
encontrado<--verdadero
N<--N-1
para k desde i hasta N haz
arreglo[k]<--arreglo[k-1]
fin
en caso contrario
i<--i+1
fin
fin
Si encontrado=falso entonces
mensaje (valor no encontrado)
3.- Modificar.
Si N>=1 entonces
inicio
i<--1
encontrado<--falso
mientras i<=N y encontrado=false haz
inicio
Si arreglo[i]=valor entonces
arreglo[i]<--valor_nuevo
encontrado<--verdadero
En caso contrario
i<--i+1
fin
fin
1.7 Ordenaciones en Arreglos
La importancia de mantener nuestros arreglos ordenados radica en que es mucho más rápido tener acceso a un dato en un arreglo ordenado que en uno desordenado.
Existen muchos algoritmos para la ordenación de elementos en arreglos, enseguida veremos algunos de ellos.
a)Selección Directa
Este método consiste en seleccionar el elemento más pequeño de nuestra lista para colocarlo al inicio y así excluirlo de la lista.
Para ahorrar espacio, siempre que vayamos a colocar un elemento en su posición correcta lo intercambiaremos por aquel que la esté ocupando en ese momento.
El algoritmo de selección directa es el siguiente:
i <- 1
mientras i<= N haz
min <-i
j <- i + 1
mientras j <= N haz
si arreglo[j] < [min] entonces
min <-j
j <- j + 1
intercambia(arreglo[min],arreglo[i])
i <- i +1
b)Ordenación por Burbuja
Es el método de ordenación más utilizado por su fácil comprensión y programación, pero es importante señalar que es el más ineficiente de todos los métodos .
Este método consiste en llevar los elementos menores a la izquierda del arreglo ó los mayores a la derecha del mismo. La idea básica del algoritmo es comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados.
i <- 1
mientras i < N haz
j <- N
mientras j > i haz
si arreglo[j] < arreglo[j-1] entonces
intercambia(arreglo[j],arreglo[j-1])
j < j - 1
i <- i +1
c)Ordenación por Mezcla
Este algoritmo consiste en partir el arreglo por la mitad, ordenar la mitad izquierda, ordenar la mitad derecha y mezclar las dos mitades ordenadas en un array ordenado. Este último paso consiste en ir comparando pares sucesivos de elementos (uno de cada mitad) y poniendo el valor más pequeño en el siguiente hueco.
procedimiento mezclar(dat,izqp,izqu,derp,deru)
inicio
izqa <- izqp
dera <- derp
ind <- izqp
mientras (izqa <= izqu) y (dera <= deru) haz
si arreglo[izqa] < dat[dera] entonces
temporal[ind] <- arreglo[izqa]
izqa <- izqa + 1
en caso contrario
temporal[ind] <- arreglo[dera]
dera <- dera + 1
ind <- ind +1
mientras izqa <= izqu haz
temporal[ind] <- arreglo[izqa]
izqa <- izqa + 1
ind <- ind +1
mientras dera <= deru haz
temporal[ind] <=dat[dera]
dera <- dera + 1
ind <- ind + 1
para ind <- izqp hasta deru haz
arreglo[ind] <- temporal[ind]
fin
1.8 Búsquedas en Arreglos
Una búsqueda es el proceso mediante el cual podemos localizar un elemento con un valor especifico dentro de un conjunto de datos. Terminamos con éxito la búsqueda cuando el elemento es encontrado.
A continuación veremos algunos de los algoritmos de búsqueda que existen.
a)Búsqueda Secuencial
A este método tambien se le conoce como búsqueda lineal y consiste en empezar al inicio del conjunto de elementos , e ir atravez de ellos hasta encontrar el elemento indicado ó hasta llegar al final de arreglo.
Este es el método de búsqueda más lento, pero si nuestro arreglo se encuentra completamente desordenado es el único que nos podrá ayudar a encontrar el dato que buscamos.
ind <- 1
encontrado <- falso
mientras no encontrado y ind < N haz
si arreglo[ind] = valor_buscado entonces
encontrado <- verdadero
en caso contrario
ind <- ind +1
b)Búsqueda Binaria
Las condiciones que debe cumplir el arreglo para poder usar búsqueda binaria son que el arreglo este ordenado y que se conozca el numero de elementos.
Este método consiste en lo siguiente: comparar el elemento buscado con el elemento situado en la mitad del arreglo, si tenemos suerte y los dos valores coinciden, en ese momento la búsqueda termina. Pero como existe un alto porcentaje de que esto no ocurra, repetiremos los pasos anteriores en la mitad inferior del arreglo si el elemento que buscamos resulto menor que el de la mitad del arreglo, o en la mitad superior si el elemento buscado fue mayor.
La búsqueda termina cuando encontramos el elemento o cuando el tamaño del arreglo a examinar sea cero.
encontrado <- falso
primero <- 1
ultimo <- N
mientras primero <= ultimo y no encontrado haz
mitad <- (primero + ultimo)/2
si arreglo[mitad] = valor_buscado entonces
encntrado <- verdadero
en caso contrario
si arreglo[mitad] > valor_buscado entonces
ultimo <- mitad - 1
en caso contrario
primero <- mitad + 1
c)Búsqueda por Hash
La idea principal de este método consiste en aplicar una función que traduce el valor del elemento buscado en un rango de direcciones relativas. Una desventaja importante de este método es que puede ocasionar colisiones.
funcion hash (valor_buscado)
inicio
hash <- valor_buscado mod numero_primo
fin
inicio <- hash (valor)
il <- inicio
encontrado <- falso
repite
si arreglo[il] = valor entonces
encontrado <- verdadero
en caso contrario
il <- (il +1) mod N
hasta encontrado o il = inicio
Estructuras de control: permiten tomar decisiones de tipo booleano
(IF- THEN, IF THEN ELSE, SWITCH, CASE)
Estructuras interactivas también llamadas de repetición: (WHILE, DO UNTIL, FOR, DO WHILE)
Punteros variables de tipo flotante que se mueven dentro de un vector (índices)
Tipos de búsqueda:
Búsqueda ascendente búsqueda descendente Búsqueda binaria
Ejercicio1. Declarar matriz de 3 * 3 con números en horizontal y llenarla.
Inicio
int A[1..3] , int x,y; x=columnas y = filas
for x=1 hasta x=3
for y=1 hasta y=3
A [x,y] = A[x,y]+1
imprimir A[x,y],
fin
Ejercicio 2. Multiplicar un vector por 2-Multiplicar una matriz de 3*2*2- Se declaran 2 arreglos
Inicio
int A[1..3] , int x,y; x=columnas y = filas
for x=1 hasta x=3
for y=1 hasta y=3
A [x,y] = A[x,y]+1
imprimir A[x,y] *2,
fin
Ejercicio3. Introducción a métodos de ordenamiento binario, declarar una matriz de 3x3, determinar que registros se encuentran en la posición 2.1
Inicio
int A[1..3] [1..3]
int B[1..3] [1..3]
for x=1 hasta x=3
for y=1 hasta y=3
A [x,y] = A[x,y]+1
imprimir x,y
fin
ARREGLOS:
1.2 Arreglos Unidimensionales
Un arreglo unidimensional es un tipo de datos estructurado que está formado de una colección finita y ordenada de datos del mismo tipo. Es la estructura natural para modelar listas de elementos iguales.
El tipo de acceso a los arreglos unidimensionales es el acceso directo, es decir, podemos acceder a cualquier elemento del arreglo sin tener que consultar a elementos anteriores o posteriores, esto mediante el uso de un índice para cada elemento del arreglo que nos da su posición relativa.
Para implementar arreglos unidimensionales se debe reservar espacio en memoria, y se debe proporcionar la dirección base del arreglo, la cota superior y la inferior.
REPRESENTACION EN MEMORIA
Los arreglos se representan en memoria de la forma siguiente:
x : array[1..5] of integer
Para establecer el rango del arreglo (número total de elementos) que componen el arreglo se utiliza la siguiente formula:
RANGO = Ls - (Li+1)
donde:
ls = Límite superior del arreglo
li = Límite inferior del arreglo
Para calcular la dirección de memoria de un elemento dentro de un arreglo se usa la siguiente formula:
A[i] = base(A) + [(i-li) * w]
donde :
A = Identificador único del arreglo
i = Indice del elemento
li = Límite inferior
w = Número de bytes tipo componente
Si el arreglo en el cual estamos trabajando tiene un índice numerativo utilizaremos las siguientes fórmulas:
RANGO = ord (ls) - (ord (li)+1)
A[i] = base (A) + [ord (i) - ord (li) * w]
1.3 Arreglos Bidimensionales
Este tipo de arreglos al igual que los anteriores es un tipo de dato estructurado, finito ordenado y homogéneo. El acceso a ellos también es en forma directa por medio de un par de índices.
Los arreglos bidimensionales se usan para representar datos que pueden verse como una tabla con filas y columnas. La primera dimensión del arreglo representa las columnas, cada elemento contiene un valor y cada dimensión representa una relación
La representación en memoria se realiza de dos formas : almacenamiento por columnas o por renglones.
Para determinar el número total de elementos en un arreglo bidimensional usaremos las siguientes fórmulas:
RANGO DE RENGLONES (R1) = Ls1 - (Li1+1)
RANGO DE COLUMNAS (R2) = Ls2 - (Li2+1)
No. TOTAL DE COMPONENTES = R1 * R2
REPRESENTACION EN MEMORIA POR COLUMNAS
x : array [1..5,1..7] of integer
Para calcular la dirección de memoria de un elemento se usan la siguiente formula:
A[i,j] = base (A) + [((j - li2) R1 + (i + li1))*w]
REPRESENTACION EN MEMORIA POR RENGLONES
x : array [1..5,1..7] of integer
Para calcular la dirección de memoria de un elemento se usan la siguiente formula:
A[i,j] = base (A) + [((i - li1) R2 + (j + li2))*w]
donde:
i = Indice del renglón a calcular
j = Indice de la columna a calcular
li1 = Límite inferior de renglones
li2 = Límite inferior de columnas
w = Número de bytes tipo componente
1.4 Arreglos Multidimensionales
Este también es un tipo de dato estructurado, que está compuesto por n dimensiones. Para hacer referencia a cada componente del arreglo es necesario utilizar n índices, uno para cada dimensión
Para determinar el número de elementos en este tipo de arreglos se usan las siguientes fórmulas:
RANGO (Ri) = lsi - (lii + 1)
No. TOTAL DE ELEMENTOS = R1 * R2* R3 * ...* Rn
donde:
i = 1 ... n
n = No. total de dimensiones
Para determinar la dirección de memoria se usa la siguiente formula:
LOC A[i1,i2,i3,...,in] = base(A) + [(i1-li1)*R3*R4*Rn + (i2-li2)*R3*R2*... (in - lin)*Rn]*w
1.5 Operaciones Con Arreglos
Las operaciones en arreglos pueden clasificarse de la siguiente forma:
• Lectura
• Escritura
• Asignación
• Actualización
• Ordenación
• Búsqueda
a) LECTURA
Este proceso consiste en leer un dato de un arreglo y asignar un valor a cada uno de sus componentes.
La lectura se realiza de la siguiente manera:
para i desde 1 hasta N haz
x<--arreglo[i]
b) ESCRITURA
Consiste en asignarle un valor a cada elemento del arreglo.
La escritura se realiza de la siguiente manera:
para i desde 1 hasta N haz
arreglo[i]<--x
c) ASIGNACION
No es posible asignar directamente un valor a todo el arreglo, por lo que se realiza de la manera siguiente:
para i desde 1 hasta N haz
arreglo[i]<--algún_valor
d) ACTUALIZACION
Dentro de esta operación se encuentran las operaciones de eliminar, insertar y modificar datos. Para realizar este tipo de operaciones se debe tomar en cuenta si el arreglo está o no ordenado.
Para arreglos ordenados los algoritmos de inserción, borrado y modificación son los siguientes:
1.- Insertar.
Si i< mensaje(arreglo contrario caso En arreglo[i]<--valor i<--i+1 entonces>
2.- Borrar.
Si N>=1 entonces
inicio
i<--1
encontrado<--falso
mientras i<=n y encontrado=falso
inicio
si arreglo[i]=valor_a_borrar entonces
inicio
encontrado<--verdadero
N<--N-1
para k desde i hasta N haz
arreglo[k]<--arreglo[k-1]
fin
en caso contrario
i<--i+1
fin
fin
Si encontrado=falso entonces
mensaje (valor no encontrado)
3.- Modificar.
Si N>=1 entonces
inicio
i<--1
encontrado<--falso
mientras i<=N y encontrado=false haz
inicio
Si arreglo[i]=valor entonces
arreglo[i]<--valor_nuevo
encontrado<--verdadero
En caso contrario
i<--i+1
fin
fin
1.7 Ordenaciones en Arreglos
La importancia de mantener nuestros arreglos ordenados radica en que es mucho más rápido tener acceso a un dato en un arreglo ordenado que en uno desordenado.
Existen muchos algoritmos para la ordenación de elementos en arreglos, enseguida veremos algunos de ellos.
a)Selección Directa
Este método consiste en seleccionar el elemento más pequeño de nuestra lista para colocarlo al inicio y así excluirlo de la lista.
Para ahorrar espacio, siempre que vayamos a colocar un elemento en su posición correcta lo intercambiaremos por aquel que la esté ocupando en ese momento.
El algoritmo de selección directa es el siguiente:
i <- 1
mientras i<= N haz
min <-i
j <- i + 1
mientras j <= N haz
si arreglo[j] < [min] entonces
min <-j
j <- j + 1
intercambia(arreglo[min],arreglo[i])
i <- i +1
b)Ordenación por Burbuja
Es el método de ordenación más utilizado por su fácil comprensión y programación, pero es importante señalar que es el más ineficiente de todos los métodos .
Este método consiste en llevar los elementos menores a la izquierda del arreglo ó los mayores a la derecha del mismo. La idea básica del algoritmo es comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados.
i <- 1
mientras i < N haz
j <- N
mientras j > i haz
si arreglo[j] < arreglo[j-1] entonces
intercambia(arreglo[j],arreglo[j-1])
j < j - 1
i <- i +1
c)Ordenación por Mezcla
Este algoritmo consiste en partir el arreglo por la mitad, ordenar la mitad izquierda, ordenar la mitad derecha y mezclar las dos mitades ordenadas en un array ordenado. Este último paso consiste en ir comparando pares sucesivos de elementos (uno de cada mitad) y poniendo el valor más pequeño en el siguiente hueco.
procedimiento mezclar(dat,izqp,izqu,derp,deru)
inicio
izqa <- izqp
dera <- derp
ind <- izqp
mientras (izqa <= izqu) y (dera <= deru) haz
si arreglo[izqa] < dat[dera] entonces
temporal[ind] <- arreglo[izqa]
izqa <- izqa + 1
en caso contrario
temporal[ind] <- arreglo[dera]
dera <- dera + 1
ind <- ind +1
mientras izqa <= izqu haz
temporal[ind] <- arreglo[izqa]
izqa <- izqa + 1
ind <- ind +1
mientras dera <= deru haz
temporal[ind] <=dat[dera]
dera <- dera + 1
ind <- ind + 1
para ind <- izqp hasta deru haz
arreglo[ind] <- temporal[ind]
fin
1.8 Búsquedas en Arreglos
Una búsqueda es el proceso mediante el cual podemos localizar un elemento con un valor especifico dentro de un conjunto de datos. Terminamos con éxito la búsqueda cuando el elemento es encontrado.
A continuación veremos algunos de los algoritmos de búsqueda que existen.
a)Búsqueda Secuencial
A este método tambien se le conoce como búsqueda lineal y consiste en empezar al inicio del conjunto de elementos , e ir atravez de ellos hasta encontrar el elemento indicado ó hasta llegar al final de arreglo.
Este es el método de búsqueda más lento, pero si nuestro arreglo se encuentra completamente desordenado es el único que nos podrá ayudar a encontrar el dato que buscamos.
ind <- 1
encontrado <- falso
mientras no encontrado y ind < N haz
si arreglo[ind] = valor_buscado entonces
encontrado <- verdadero
en caso contrario
ind <- ind +1
b)Búsqueda Binaria
Las condiciones que debe cumplir el arreglo para poder usar búsqueda binaria son que el arreglo este ordenado y que se conozca el numero de elementos.
Este método consiste en lo siguiente: comparar el elemento buscado con el elemento situado en la mitad del arreglo, si tenemos suerte y los dos valores coinciden, en ese momento la búsqueda termina. Pero como existe un alto porcentaje de que esto no ocurra, repetiremos los pasos anteriores en la mitad inferior del arreglo si el elemento que buscamos resulto menor que el de la mitad del arreglo, o en la mitad superior si el elemento buscado fue mayor.
La búsqueda termina cuando encontramos el elemento o cuando el tamaño del arreglo a examinar sea cero.
encontrado <- falso
primero <- 1
ultimo <- N
mientras primero <= ultimo y no encontrado haz
mitad <- (primero + ultimo)/2
si arreglo[mitad] = valor_buscado entonces
encntrado <- verdadero
en caso contrario
si arreglo[mitad] > valor_buscado entonces
ultimo <- mitad - 1
en caso contrario
primero <- mitad + 1
c)Búsqueda por Hash
La idea principal de este método consiste en aplicar una función que traduce el valor del elemento buscado en un rango de direcciones relativas. Una desventaja importante de este método es que puede ocasionar colisiones.
funcion hash (valor_buscado)
inicio
hash <- valor_buscado mod numero_primo
fin
inicio <- hash (valor)
il <- inicio
encontrado <- falso
repite
si arreglo[il] = valor entonces
encontrado <- verdadero
en caso contrario
il <- (il +1) mod N
hasta encontrado o il = inicio
miércoles, 1 de octubre de 2008
viernes, 26 de septiembre de 2008
Definicion de Grafos
Teoria de las graficas, Un grafo es un conjunto, no vacío, de objetos llamados vértices(o nodos) y una selección de pares de vértices, llamados aristas(arcs en inglés) que pueden ser orientados o no. Típicamente, un grafo serepresenta mediante una serie de puntos (los vértices) conectados por líneas(las aristas). Un grafo representa un modelo de una realidad empresarial enforma de red. La filosofía de Grafos es la siguiente: "dibujar, modelar,resolver y analizar".
Resumen : Un grafo es la representacion grafica de una seccion o problematica a resolver.
Resumen : Un grafo es la representacion grafica de una seccion o problematica a resolver.
viernes, 19 de septiembre de 2008
Proyecto Unidad1
Nombre del Proyecto: Sistema de Administracion de Discos.
Descripcion del Problema:
- Se requiere realizar un sistema que administre las bibliotecas de Musica con las que contemos.
-Este sistema ademas de almacenar el contenido multimedia, tambien nos facilitará la creacion,busqueda , adicion , actualizacion y eliminacion de nuestros contenidos.
Alcances:
-En nuestro sitema será posible la realizacion de busquedas por diversos criterios.
Ejemplo: Por artista, por album, por genero, etc.
-Tambien será posible la visualizacion de la caratula del album que estemos buscando.
Al mismo tiempo se mostrará la informacion perteneciente a dicho album.
-Si por alguna razon se encuentra mal la informacion de algun album o simplemente se quiere detallar la informacion del mismo, será posible actualizar dicha informacion.
-Tambien será posible aliminar uno o mas registrosde nuestro sistema.
Limitaciones:
-El sistema no podra reproducir los contenidos musicales.
-El sistema tendra un limite de albums a almacenar (300).
-El sistema en faces posteriores podra actualizarse via internet.
Definicion del problema:
-Se desarrollará un sistema en el cual se puedan realizar consultas, altas , bajas y cambios para la administración de una biblioteca de musica.
-Este sistema solo desplegará la informacion referente a los albums, pero no será capaz de reproducir el contenido.
Descripcion del Problema:
- Se requiere realizar un sistema que administre las bibliotecas de Musica con las que contemos.
-Este sistema ademas de almacenar el contenido multimedia, tambien nos facilitará la creacion,busqueda , adicion , actualizacion y eliminacion de nuestros contenidos.
Alcances:
-En nuestro sitema será posible la realizacion de busquedas por diversos criterios.
Ejemplo: Por artista, por album, por genero, etc.
-Tambien será posible la visualizacion de la caratula del album que estemos buscando.
Al mismo tiempo se mostrará la informacion perteneciente a dicho album.
-Si por alguna razon se encuentra mal la informacion de algun album o simplemente se quiere detallar la informacion del mismo, será posible actualizar dicha informacion.
-Tambien será posible aliminar uno o mas registrosde nuestro sistema.
Limitaciones:
-El sistema no podra reproducir los contenidos musicales.
-El sistema tendra un limite de albums a almacenar (300).
-El sistema en faces posteriores podra actualizarse via internet.
Definicion del problema:
-Se desarrollará un sistema en el cual se puedan realizar consultas, altas , bajas y cambios para la administración de una biblioteca de musica.
-Este sistema solo desplegará la informacion referente a los albums, pero no será capaz de reproducir el contenido.
miércoles, 10 de septiembre de 2008
Tarea
Traer por escrito un problema que deceamos resolver con una BD:
Ejemplos:
Sistemas de Inventarios.
Prestamo de libros de una biblioteca.
Ejemplos:
Sistemas de Inventarios.
Prestamo de libros de una biblioteca.
Temario
Objetivo de la asignatura: Que el alumno aplique tecnicas de estructura de datos,que utilizen asinacion dinamica de memoria.
Diseñar problemas de sistemas de Informacion. mediante las tecnicas de ordenamiento.
Resolver problemas de recursividad por medio de grafos.
Temas:
1.- Arboles.
1.1.-Tipo v
1.2.-Tipo AVL
1.3.-Tipo B
Unidad 2 Grafos:
2.1 Terminologia y representaciones.
Unidad 3 Metodos de ordenacion
3.1 Intercambio directo
3.2 Insercion directa.
3.3 Radix
3.4 Monticulo
3.5 Concha
3.6 Mezcla
3.7 Hasthing
Unidad 4
Metodos de busqueda:
4.1 Secuencial
4.2 Binaria
4.3 Secuencial indexado
4.4 Hasthing
Unidad 5
Soluciones avanzadas de operaciones con matrices.
5.1 Multiplicacion de matrices.
5.2 Solucion de sistemas de ecuaciones lineales.
Diseñar problemas de sistemas de Informacion. mediante las tecnicas de ordenamiento.
Resolver problemas de recursividad por medio de grafos.
Temas:
1.- Arboles.
1.1.-Tipo v
1.2.-Tipo AVL
1.3.-Tipo B
Unidad 2 Grafos:
2.1 Terminologia y representaciones.
Unidad 3 Metodos de ordenacion
3.1 Intercambio directo
3.2 Insercion directa.
3.3 Radix
3.4 Monticulo
3.5 Concha
3.6 Mezcla
3.7 Hasthing
Unidad 4
Metodos de busqueda:
4.1 Secuencial
4.2 Binaria
4.3 Secuencial indexado
4.4 Hasthing
Unidad 5
Soluciones avanzadas de operaciones con matrices.
5.1 Multiplicacion de matrices.
5.2 Solucion de sistemas de ecuaciones lineales.
Estructura de datos 2
La forma de evaluacion serà la siguiente:
Tareas 25 %
Practicas 25%
Teoricas 25%
Examen 25%
Nota: Los ejercicios teoricos y practicos no entregados en la clase, solo podrna ser entregados la proxima clase a mas tardar. (via correo electronico o en papel)
Tareas 25 %
Practicas 25%
Teoricas 25%
Examen 25%
Nota: Los ejercicios teoricos y practicos no entregados en la clase, solo podrna ser entregados la proxima clase a mas tardar. (via correo electronico o en papel)
Suscribirse a:
Entradas (Atom)