Busqueda Secuencial o Lineal

METODOS DE BUSQUEDA

•La recuperación de información es una de las aplicaciones más importantes de las computadoras. La búsqueda de información está relacionada con las tablas para consultas. Estas tablas contienen una cantidad de información que se almacenan en forma de listas de parejas de datos. Por ejemplo un catálogo con una lista de libros de matemáticas, en donde es necesario buscar con frecuencia elementos en una lista. Existen diferentes tipos de búsqueda, pero en este informe describiremos sólo la de tipo Secuencial y Binaria.

BUSQUEDA SECUENCIAL

•Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector, es decir; recorrer el vector desde el primer elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a “Fin de Búsqueda” o “Elemento encontrado” y otro que diga “posición=” en caso contrario, visualizar un mensaje similar a “Elemento no existe en la Lista”.

•Este tipo de búsqueda compara cada elemento del vector con el valor a encontrar hasta que este se consiga o se termine de leer el vector completo

EJEMPLO

•Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista. 

Mejoras en la eficiencia de la búsqueda secuencial

•1)Muestreo de acceso     Este método consiste en observar que tan frecuentemente se solicita cada registro y ordenarlos de acuerdo a las probabilidades de acceso detectadas. 

•

•2)Movimiento hacia el frente     Este esquema consiste en que la lista de registros se reorganicen dinámicamente. Con este método, cada vez que búsqueda de una llave sea exitosa, el registro correspondiente se mueve a la primera posición de la lista y se recorren una posición hacia abajo los que estaban antes que el.

•3)Transposición     Este es otro esquema de reorganización dinámica que consiste en que, cada vez que se lleve a cabo una búsqueda exitosa, el registro correspondiente se intercambia con el anterior. Con este procedimiento, entre mas accesos tenga el registro, mas rápidamente avanzara hacia la primera posición. Comparado con el método de movimiento al frente, el método requiere mas tiempo de actividad para reorganizar al conjunto de registros . Una ventaja de método de transposición es que no permite que el requerimiento aislado de un registro, cambie de posición todo el conjunto de registros. De hecho, un registro debe ganar poco a poco su derecho a alcanzar el inicio de la lista.

•

• 4)Ordenamiento     Una forma de reducir el numero de comparaciones esperadas cuando hay una significativa frecuencia de búsqueda sin éxito es la de ordenar los registros en base al valor de la llave. Esta técnica es útil cuando la lista es una lista de excepciones, tales como una lista de decisiones, en cuyo caso la mayoría de las búsquedas no tendrán éxito. Con este método una búsqueda sin éxito termina cuando se encuentra el primer valor de la llave mayor que el buscado, en lugar de la final de la lista.

BIBLIOGRAFIA

http://sistemas.itlp.edu.mx/tutoriales/estructdatos2/tema5_1.htm

GRAFOS

Grafo

un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representarrelaciones binarias entre elementos de un conjunto.

En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }.

Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que . Para simplificar, notaremos la arista (a,b) como ab.

En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.

Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad.

Aristas dirigidas y no dirigidas

En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus direcciones únicas. El conjunto de aristas será ahora un subconjunto de todos los posibles pares ordenados de vértices, con (a, b) ≠ (b, a). Los grafos que contienen aristas dirigidas se denominan grafos orientados, como el siguiente:

Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido).

En el grafo anterior se ha utilizado una arista que tiene sus dos extremos idénticos: es un lazo (o bucle), y aparece también una arista bidireccional, y corresponde a dos aristas orientadas.

Aquí V = { a, b, c, d, e }, y A = { (a, c), (d, a), (d, e), (a, e), (b, e), (c, a), (c, c), (d, b) }.

Se considera la característica de "grado" (positivo o negativo) de un vértice v (y se indica como (v)), como la cantidad de aristas que llegan o salen de él; para el caso de grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas incidentes a este vértice. Por ejemplo, el grado positivo (salidas) de d es 3, mientras que el grado negativo (llegadas) de d es 0.

Según la terminología seguida en algunos problemas clásicos de Investigación Operativa (p.ej.: el Problema del flujo máximo), a un vértice del que sólo salen aristas se le denomina fuente (en el ejemplo anterior, el vértice d); tiene grado negativo 0. Por el contrario, a aquellos en los que sólo entran aristas se les denomina pozo o sumidero (en el caso anterior, el vértice e); tiene grado positivo 0. A continuación se presentan las implementaciones en maude de grafos no dirigidos y de grafos dirigidos.En los dos casos, las especificaciones incluyen, además de las operaciones generadoras, otras operaciones auxiliares