Métodos de búsqueda

BÚSQUEDA.

La búsqueda es una operación que tiene por objeto la localización de un elemento dentro de la estructura de datos. A menudo un programador estará trabajando con grandes cantidades de datos almacenados en arreglos y pudiera resultar necesario determinar si un arreglo contiene un valor que coincide con algún valor clave o buscado.Siendo el array de una dimensión o lista una estructura de acceso directo y a su vez de acceso secuencial, encontramos dos técnicas que utilizan estos dos métodos de acceso, para encontrar elementos dentro de un array: búsqueda lineal y búsqueda binaria.

Búsqueda Secuencial: La búsqueda secuencial es la técnica más simple para buscar un elemento en un arreglo. Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados. Si el arreglo está ordenado, se puede utilizar la técnica de alta velocidad de búsqueda binaria, donde se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.

Búsqueda Binaria. La búsqueda binaria es el método más eficiente para encontrar elementos en un arreglo ordenado. El proceso comienza comparando el elemento central del arreglo con el valor buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.

Diferentes Métodos de ordenación

Método de ordenación Burbuja

void bubble(int *start, int *end) //Ordena un conjunto de números enteros de menor a mayor
{ short fin;
do
{ fin=0;
for (int *i=start;i!=*end;i++)
{
if (*i>*(i+1))
{ intercambia(i, i+1);
fin=1;
}
}
} while
(fin!=1);
}


http://seduca.uaemex.mx/SofEdu/Sim/MetOrd/metodos.html

Inserción Directa. (A,N)

La idea central de este algoritmo consiste en insertar un elemento del arreglo en la parte izquierda del mismo, que ya se encuentra ordenado. Este proceso se repite desde el segundo hasta el n-ésimo elemento.
El algoritmo es el siguiente.
1. Repetir con I desde 2 hasta N... Hacer Aux <-- A[I], K <-- I-1... 1.1
Repetir mientras (Aux <> 1).... Hacer A[K+1] <-- A[K] y K <-- K-1...
1.2 {Fin del ciclo del paso 1.1}... 1.3 Si A[K] lt;= Aux, entonces.......... A[K+1] <-- Aux........ sino........ A[K+1] <-- A[K] y A[K] <-- Aux... 1.4 {Fin del condicional del paso 1.3}2. {Fin del ciclo del paso 1}

Ordenamiento Radix

Ordenamiento de distribución por conteoUn problema que se presenta con frecuencia es el siguiente: "Ordenar un archivo con N registros cuyas llaves son enteros comprendidos entre 0 y M-1". SiM no es muy grande, se puede usar el algoritmo de distribución porconteo. La idea básica es contar el número de veces que serepite cada llave diferente y en una segunda pasada utilizar el conteo paraposicionar los registros en el archivo.

Mezcla

Ordenación por mezcla (Merg Sort).
Intercalación de archivos ó mezcla de archivos.Por intercalación de archivos se entiende la unión o fusión de dos o más archivos ordenados de acuerdo con un determinado campo en un solo archivo.

Monticulo

Ordenación por el método de heapsort
El método de ordenación heapsort es también conocido con el nombre "montículo" en el mundo de habla hispana. Su nombre se debe a su autor J. W. Williams quien lo bautió así. Es el más eficiente de los métodos de ordenación que trabajan con árboles.
La idea central de este algoritmo consiste en lo siguiente:
Construir un montículo.
Eliminar la raíza del montículo en forma repetida.
Definición. un montículo se define como "Para todo nodo del árbol se debe cumplir que su valor de cualquiera de sus hijos".
Para representar un montículo en un arreglo lineal:
El nodo k se almacena en la posición k correspondiente del arreglo.
El hijo izquierda del nodo k, se almacena en la posición 2 * k.
El hijo derecho del nodo k, se almacena en la posición 2 * k+1.
Inserción de un elemento en un montículo.
La inserción de un elemento en un motnículo se lleva a cabo de la siguiente manera:
Se inserta el elemento en la primera posición disponible.
Se verifica si su valor es mayor que el de su padre. Si se cumple está condición entonces se efectúa el intercambio. Sino se cumple está condición, entonces, el algoritmo se detiene y el elemento queda ubicado en su posición correcta en el montículo. Cabe aclarar que el paso 2 se aplica de manera recursiva y desde abajo hacia arriba.
Eliminación de un montículo.
El proceso para obtener los elementos ordenados se efectúa eliminando la raíz del montículo en forma repetida. Ahora bien, los pasos necesarios para lograr la eliminación de la raíz del montículo son los siguientes:
Se reemplaza la raíz con el elemento que ocupa la última posición del montículo .
Se verifica si el valor de la raíz es menor que el valor más grande de sus hijos. Si se cumple la condición entonces se efectúa el intercambio. Sino se cumple la condición entonces el algoritmo se detiene y el elemento queda ubicado en su posición correcta en el montículo.
Cabe aclarar que le paso 2 se aplica de manera recursiva y desde arriba hacia abajo.
El algoritmo es el siguiente.
Montículo (A,N).
{El algoritmo ordena los elementos del arreglo utilizando el método del montículo. A es un arreglo de N elementos}.
1. Llamar al algoritmo INSERTAMONTÍCULO con A y N.2. Llamar al algoritmo ELIMINAMONTÍCULO con Ay N.
Insertamontículo (A,N).
{El algoritmo inserta elementos en un montículo representando como arreglo. A es un arreglo de N elementos.}
1. Repetir con I desde 2 hasta N.. Hacer k <-- I y Band <-- Verdadero.. 1.1 Repetir mientras k > 1 y Band = Verdadero...... Hacer Band <-- Falso...... 1.1.1 Si A[k] A[parte entera (k entre 2)] entonces............ Aux <-- A[parte entera (k entre 2)]............ A[parte entera (k entre 2)] <-- A[k]............ Band <>QuickSort (se estima un 70%), es el único que garantiza que aún en el peor caso su tiempo de ejecución es proporcional a: (n * log n), 0 (n * log n).

Estructura de datos

Estructura: conjunto de parametros o reglas que nos permiten ordenar datos
Estructuras de control: permiten tomar desiciones de tipo booleano
(IF- THEN, IF THEN ELSE, SWITCH, CASE)

Estructuras iteractivas tambien 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

Ejercicio 1. Declarar matriz de 3 * 3 con números en horizontal y llenarla.

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 ;
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

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

Definición Métodos de ordenación

Su finalidad es organizar ciertos datos (normalmente arreglos o archivos) en un orden creciente o decreciente mediante una regla prefijada (numérica, alfabética...); puede ser:

Ordenación interna: Los datos se encuentran en memoria (ya sean arreglos, listas, etc.), y son de acceso aleatorio o directo (se puede acceder a un determinado campo sin pasar por los anteriores).

Ordenación externa: Los datos están en un dispositivo de almacenamiento externo (archivos), y su ordenación es más lenta que la interna.

Los métodos de ordenación interna se aplican principalmente a arreglos unidimensionales. Los principales algoritmos de ordenación interna son:

Selección: Este método consiste en buscar el elemento más pequeño del arreglo y ponerlo en primera posición; luego, entre los restantes, se busca el elemento más pequeño y se coloca en segundo lugar, y así sucesivamente hasta colocar el último elemento.

Burbuja: Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados. Con el arreglo anterior.

Inserción directa: En este método lo que se hace es tener una sublista ordenada de elementos del arreglo e ir insertando el resto en el lugar adecuado para que la sublista no pierda el orden. La sublista ordenada se va haciendo cada vez mayor, de modo que al final la lista entera queda ordenada.

Shell: Es una mejora del método de inserción directa, utilizado cuando el arreglo 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.

Intercalación: no es propiamente un método de ordenación, consiste en la unión de dos arreglos ordenados de modo que la unión esté también ordenada. Para ello, basta con recorrer los arreglos de izquierda a derecha e ir cogiendo el menor de los dos elementos, de forma que sólo aumenta el contador del arreglo del que sale el elemento siguiente para el arreglo-suma.

Mergesort: Una técnica muy poderosa para el diseño de algoritmos es "Dividir para conquistar". Los algoritmos de este tipo se caracterizan por estar diseñados siguiendo estrictamente las siguientes fases:

• Dividir: Se divide el problema en partes más pequeñas.

• Conquistar: Se resuelven recursivamente los problemas más chicos.

• Combinar: Los problemas mas chicos de combinan para resolver el grande.

Ordenación rápida (quicksort): Este método se basa en la táctica "divide y vencerás", que consiste en ir subdividiendo el arreglo en arreglos más pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del arreglo 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 arreglo.

CLASE 5 UNIDAD 2 GRAFOS

UNIDAD 2. GRAFOS

Un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.

Un grafo simple está formado por dos conjuntos:

Un conjunto V de puntos llamados vértices o nodos.

Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados

TIPOS DE GRAFOS

Grafo simple entre dos nodos sólo hay un arco.
Multigrafo cuando tiene más de un arco.
Grafo Dirigido o Dígrafo Si los arcos se pueden recorrer en una en una dirección concreta pero no en la contraria y los arcos son entonces aristas.
Pseudografo si los arcos salen y llegan al mismo punto formando un bucle el grafo resultante.

Leonhard Euler fué quien ideó los grafos como una manera muy potente y elegante de resolver el problema de los puentes de Königsberg

Las reglas estáticas (que sirven para dibujar un solo grafo y no una sucesión de ellos de forma dinámica) se dividen en :

Ejemplos: http://www.infovis.net/printMag.php?num=137&lang=1

Reglas básicas: se refieren a aspectos elementales como el solapamiento entre aristas vertices o ambos.

Reglas semánticas: son reglas de posicionamiento de vértices y de dibujo de arcos o aristas (enrutado) derivadas del significado de vértices y aristas. Por ejemplo dibujar el tamaño de un vértice o el grosor de una arista en función de su importancia. Suelen venir dadas por el usuario o son deducidas de la información de sus etiquetas asociadas.

Reglas estructurales: son reglas de posicionamiento y enrutado relacionadas sólo con las propiedades de la teoría de grafos. Por ejemplo colocar los vértices de mayor orden en el centro del dibujo o minimizar la longitud total de aristas, minimizar el numero de cruces entre vértices, etc.

PROYECTO UNIDAD 1

SISTEMA DE ADMINISTRACIÓN DE DISCOS

DESCRIPCIÓN DEL PROBLEMA

Un sistema que permita a los empleados de una tienda identificar de una forma rápida y confiable el nombre de algún álbum, el artista, las canciones que contiene, asi como la ubicación y existencia de los discos que se venden ahí, a través de consultas por alguna parte de la letra de la cancìón, nombre de la canción, nombre del álbum, artista, genero, etc.

ALCANCES

El sistema debe permitir que el cliente pueda visualizar el disco que està buscando de forma gráfica, es decir se debe mostrar en pantalla la portada del CD con una la relaciòn de sus canciones y el precio.
Al empleado le debe mostrar si el disco se encuentra en existencia y la ubicación física del mismo.

LIMITACIONES

La búsqueda del álbum a traves de una parte de la canción, no es posible debido a que el agregar la letra de todas las canciones tomaria mas tiempo del estimado además de que ocuparia muchos recursos del sistema que retrasarian el tiempo de respuesta.

DEFINICIÓN DEL PROBLEMA

Se realiazarà un sistema que permita a los empleados de la tienda consultar y visualizar de forma gráfica el disco que le solicite un cliente, su existencia y ubicación. Las consultas solo se pueden hacer por nombre de la canción, nombre del álbum, artista o género.

Pràctica 1

Indices Densos e Indices Escasos (Esparcidos)

Indices densos: aquellos que poseen un número de elementos igual al de registros en el archivo de datos


Ejemplo de Índice Denso

Se tiene un archivo con información de ciudades y valores de operaciones realizadas. Se pide crear un archivo de índices que permita el rápido acceso a los datos.

Indices esparcidos: aquellos que son más reducidos que su respectivo archivo de datos

Ejemplo de índice Esparcido

TAREA MIERCOLES 10 SEPTIEMBRE

Traer por escrito un problema que deseo resolver con una base de datos:
Ejemplo
Sistemas de inventarios
Sistemas de libros de una biblioteca

TEMARIO

Objetivo de la asignatura que el alumno aplique tecnicas de estructura de datos, que utilizen asignaciòn dinamica de memoria.
Diseñar problemas de sistemas de informacion mediante las tecnicas de ordenamiento.
Resolver problemas de recursividad por medio de grafos.

TEMAS Y SUBTEMAS

1. ARBOLES
1.1 Tipo V
1.2 Tipo AVL
1.3 Tipo B

2. GRAFOS
2.1 Terminologia y representaciones

3. METODOS DE ORDENACION
3.1 Intercambio directo
3.2 Inserciòn directa
3.3 Radix
3.4 -Monticulo
3.5 Concha
3.6 Mezcla
3.7 Hashing

4. METODOS DE BUSQUEDA
4.1 sECUENCIAL
4.2 Binaria
4.3 Secuencial indexado
4.4 Hashing

5. SOLUCIONES AVANZADAS DE OPERACIONES CON MATRICES
5.1 Multiplicacion de matrices
5.2 solucion de sistemas de ecuaciones lineales

FORMA DE EVALUACION

25 % EJERCICIOS TEORICOS
25% EJERCICIOS PRACTICOS
25% EXAMEN
25% TAREAS


LOS EJERCICIOS TEORICOS Y PRACTICOS NO ENTREGADOS EN LA CLASE, SOLO PODRÀN SER ENTREGADOS LA PRÒXIMA CLASE A MAS TARDAR (ESCRITO O POR CORREO ELECTRONICO)