• Categories
• Estructura de datos de matriz
• Algoritmos
• Programación de computadoras
• Ingeniería de software
• Informática

Citation preview

Universidad Central del Ecuador Ingeniería, Ciencias Físicas y Matemáticas

Tema: Algoritmos de búsqueda

Integrantes:      

Jessica Flores Edison Mendoza Byron Macas Jennifer Jurado Mario Quintana Alejandra Guerrero

Investigadora Digitador Digitador Investigadora Programador Coordinadora

0

INDICE Introducción................................................................................................................... 2 Objetivos........................................................................................................................ 3 General:......................................................................................................................... 3 Especificos:.................................................................................................................... 3 Desarrollo:..................................................................................................................... 4 Búsqueda secuencial.....................................................................................................4 Mejoras en la eficiencia de la búsqueda secuencial......................................................4 Ejemplo de búsqueda secuencial:.................................................................................5 Búsqueda secuencial con centinela...............................................................................5 Búsqueda secuencial en C............................................................................................7 Búsqueda secuencial en Visual Basic..........................................................................11 Búsqueda secuencial en JAVA.....................................................................................14 Herramienta de video Mirilliss Action...........................................................................17 Conclusiones:..............................................................................................................18 Recomendaciones:......................................................................................................19 Bibliografía:..................................................................................................................20

1

INTRODUCCIÓN La recuperación de la información es una de las aplicaciones más importantes de las computadoras, está relacionada con las tablas para consultas (lookup). Estas tablas contienen una cantidad de información que se almacena en forma de listas de parejas de datos, por ejemplo un diccionario con una lista de palabras y definiciones, un catálogo con una lista de libros de informática, una lista de estudiantes y sus notas, etc… en todos estos casos es necesario con frecuencia buscar un elemento en una lista.

Uno de los métodos para realizar esta búsqueda tenemos el algoritmo secuencial, su estructura es aquella en la que una acción (instrucción) sigue a otra en secuencia, las tareas se suceden de tal modo que la salida de una es la entrada de la siguiente y así sucesivamente hasta el final de proceso. Así cuando hablamos de búsqueda secuencial nos referimos de la búsqueda en un vector con un contenido indeterminado de un elemento dado de tal manera q nosotros vamos a recorrer el vector hasta que se encuentre dicho valor o bien hasta que se termine el recorrido del vector sin éxito, por esta razón podemos tener dos posibles resultados: o bien el elemento buscado no está en el vector o bien si esta, en este segundo caso deberíamos indicar la posición del vector en el que se encuentra el elemento.

2

OBJETIVOS GENERAL: 1 Conocer sobre los algoritmos de búsqueda para mejorar nuestro desarrollo, mejoramiento en la programación y facilitar la vida del ser humano.

ESPECIFICOS: 1 Demostrar de una manera muy sencilla la búsqueda en secuenciales por vectores numéricos o de otro tipo. 2 Utilizar esta clase de algoritmo de búsqueda secuencial para la solución de problemas. 3 Realizar las presentaciones de Algoritmos de búsqueda en prezi y en power point para una mejor comprensión del tema. 4 Grabar un video del algoritmo de búsqueda secuencial en C para conocer el funcionamiento del programa.

3

DESARROLLO:

Búsqueda secuencial Supongamos una lista de elementos almacenados en un vector (array unidimensional). El método más sencillo de buscar un elemento en un vector es explorar secuencialmente el vector o, dicho en otras palabras, recorrer el vector desde el primer elemento al último.

Si se encuentra el elemento

buscado, visualizar un mensaje similar a ‘Fin de búsqueda’; en caso contrario, visualizar ‘Elemento no existe en la lista’. En otras palabras, la búsqueda secuencial compara cada elemento del vector con el valor deseado, hasta que este encuentra o termina de leer el vector completo. La búsqueda secuencial no requiere ningún registro por parte del vector y, por consiguiente, no necesita estar ordenado. El recorrido del vector se realizara normalmente con estructuras repetitivas. 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 más accesos tenga el registro, más rápidamente avanzara hacia la primera posición. Comparado con el método de movimiento al frente, el método requiere más tiempo de actividad para reorganizar al conjunto de registros. Una ventaja de método de 4

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 número 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.

Ejemplo de búsqueda secuencial:

Se

tiene

un

vector

A

que

( n ) >¿ 1( A [ 1 ] , A [ 2 ] , A [ 3 ] , … , A [ n ] )

contiene

“n”

elementos

numéricos

y se desea buscar un elemento dado t. Si el

elemento t se encuentra, visualizar un mensaje "Elemento encontrado" y otro que diga “Posición:”. Si existe n elementos, se requerirán como media n/2 comparaciones para encontrar un determinado elemento. En el caso más desfavorable se necesitaran n comparaciones.

Búsqueda secuencial con centinela Una manera muy eficaz de realizar una búsqueda secuencial consiste en modificar los algoritmos anteriores utilizando un elemento centinela. Este elemento se agrega al vector final del mismo. El valor del elemento centinela es el del argumento. El propósito de este elemento centinela A (n+1), es significar que la búsqueda siempre tendrá éxito , el elemento A (n+1) sirve como centinela y se asigna el valor de t antes de iniciar búsqueda . en cada 5

paso se evita la comparación de i con N y , por consiguiente , este algoritmo sea preferible a los métodos anteriores ,concretamente el método 4 si el índice alcanza el valor n+1 , supondría que el argumento no pertenece al vector original y en consecuencia la búsqueda no tiene éxito •

Si el vector está ordenado no es necesario recorrerlo completamente.

•

En cuanto el valor buscado es encontrado se puede finalizar el recorrido

y en el momento en que aparece un valor mayor que el buscado también se puede detener la ejecución. •

Al aplicar esto al algoritmo de búsqueda secuencial se obtiene el

algoritmo de búsqueda con centinela.

Síntesis método secuencial centinela •

Como se puede apreciar, la búsqueda secuencial con centinela no

precisa recorrer el vector por completo. •

El caso mejor se produce cuando el elemento a buscar es el primero del

vector o menor que todos los elementos del vector. Entonces la complejidad es O(1). •

El caso peor se da cuando el elemento a buscar es el último del vector o

mayor que todos los elementos del vector. Entonces la complejidad es O(n). •

Por término medio, el algoritmo emplea del orden de n/2 iteraciones, por

lo cual la complejidad del caso medio también sería O(n).

6

Búsqueda secuencial en C //Ingresamos Librerías #include #include //Declaramos variables globales que van a servir en todo el código int numero, vector[200], dimension, i, posiciones[200], aux; //Función para generar los valores de la lista void valores (){ printf("Ingrese el número de elementos de la lista: "); scanf("%d", &dimension); //La dimensión sirve para delimitar cuantos elementos va a tener la lista printf("\n"); for (i=0;i