Universidad Central del Ecuador
Universidad Central del Ecuador
Tema: Algoritmos de bsqueda
Integrantes:Jessica FloresInvestigadoraEdison
MendozaDigitadorByron MacasDigitadorJennifer
JuradoInvestigadoraMario QuintanaProgramadorAlejandra
GuerreroCoordinadora
INDICE
Introduccin2Objetivos3General:3Especificos:3Desarrollo:4Bsqueda
secuencial4Mejoras en la eficiencia de la bsqueda
secuencial4Ejemplo de bsqueda secuencial:5Bsqueda secuencial con
centinela5Bsqueda secuencial en C7Bsqueda secuencial en Visual
Basic11Bsqueda secuencial en JAVA14Herramienta de video Mirilliss
Action17Conclusiones:18Recomendaciones:19Bibliografa:20
INTRODUCCIN
La recuperacin de la informacin es una de las aplicaciones ms
importantes de las computadoras, est relacionada con las tablas
para consultas (lookup). Estas tablas contienen una cantidad de
informacin que se almacena en forma de listas de parejas de datos,
por ejemplo un diccionario con una lista de palabras y
definiciones, un catlogo con una lista de libros de informtica, 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 mtodos para realizar esta bsqueda tenemos el
algoritmo secuencial, su estructura es aquella en la que una accin
(instruccin) 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
bsqueda secuencial nos referimos de la bsqueda 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 razn podemos tener dos posibles resultados: o bien el
elemento buscado no est en el vector o bien si esta, en este
segundo caso deberamos indicar la posicin del vector en el que se
encuentra el elemento.
OBJETIVOSGENERAL:
1. Conocer sobre los algoritmos de bsqueda para mejorar nuestro
desarrollo, mejoramiento en la programacin y facilitar la vida del
ser humano.
ESPECIFICOS:
1. Demostrar de una manera muy sencilla la bsqueda en
secuenciales por vectores numricos o de otro tipo.
1. Utilizar esta clase de algoritmo de bsqueda secuencial para
la solucin de problemas.
1. Realizar las presentaciones de Algoritmos de bsqueda en prezi
y en power point para una mejor comprensin del tema.
1. Grabar un video del algoritmo de bsqueda secuencial en C para
conocer el funcionamiento del programa.
DESARROLLO:Bsqueda secuencial
Supongamos una lista de elementos almacenados en un vector
(array unidimensional). El mtodo ms 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 bsqueda; en caso contrario, visualizar Elemento no
existe en la lista.En otras palabras, la bsqueda secuencial compara
cada elemento del vector con el valor deseado, hasta que este
encuentra o termina de leer el vector completo.La bsqueda
secuencial no requiere ningn 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 bsqueda secuencial 1) Muestreo de acceso Este
mtodo 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 dinmicamente. Con este
mtodo, cada vez que bsqueda de una llave sea exitosa, el registro
correspondiente se mueve a la primera posicin de la lista y se
recorren una posicin hacia abajo los que estaban antes que el.3)
Transposicin Este es otro esquema de reorganizacin dinmica que
consiste en que, cada vez que se lleve a cabo una bsqueda exitosa,
el registro correspondiente se intercambia con el anterior. Con
este procedimiento, entre ms accesos tenga el registro, ms
rpidamente avanzara hacia la primera posicin. Comparado con el
mtodo de movimiento al frente, el mtodo requiere ms tiempo de
actividad para reorganizar al conjunto de registros. Una ventaja de
mtodo de transposicin es que no permite que el requerimiento
aislado de un registro, cambie de posicin todo el conjunto de
registros. De hecho, un registro debe ganar poco a poco su derecho
a alcanzar el inicio de la lista. 4) OrdenamientoUna forma de
reducir el nmero de comparaciones esperadas cuando hay una
significativa frecuencia de bsqueda sin xito es la de ordenar los
registros en base al valor de la llave. Esta tcnica es til cuando
la lista es una lista de excepciones, tales como una lista de
decisiones, en cuyo caso la mayora de las bsquedas no tendrn xito.
Con este mtodo una bsqueda 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 bsqueda secuencial:
Se tiene un vector A que contiene n elementos numricos y se
desea buscar un elemento dado t. Si el elemento t se encuentra,
visualizar un mensaje "Elemento encontrado" y otro que diga
Posicin:.Si existe n elementos, se requerirn como media n/2
comparaciones para encontrar un determinado elemento.En el caso ms
desfavorable se necesitaran n comparaciones.
Bsqueda secuencial con centinela
Una manera muy eficaz de realizar una bsqueda 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
propsito de este elemento centinela A (n+1), es significar que la
bsqueda siempre tendr xito , el elemento A (n+1) sirve como
centinela y se asigna el valor de t antes de iniciar bsqueda . en
cada paso se evita la comparacin de i con N y , por consiguiente ,
este algoritmo sea preferible a los mtodos anteriores
,concretamente el mtodo 4 si el ndice alcanza el valor n+1 ,
supondra que el argumento no pertenece al vector original y en
consecuencia la bsqueda no tiene xitoSi 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 tambin se puede detener la
ejecucin.Al aplicar esto al algoritmo de bsqueda secuencial se
obtiene el algoritmo de bsqueda con centinela.
Sntesis mtodo secuencial centinela
Como se puede apreciar, la bsqueda 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 trmino medio, el algoritmo emplea del orden de n/2
iteraciones, por lo cual la complejidad del caso medio tambin sera
O(n).
Bsqueda secuencial en C
//Ingresamos Libreras#include#include//Declaramos variables
globales que van a servir en todo el cdigoint numero, vector[200],
dimension, i, posiciones[200], aux;//Funcin para generar los
valores de la listavoid valores (){printf("Ingrese el nmero de
elementos de la lista: ");scanf("%d", &dimension); //La
dimensin sirve para delimitar cuantos elementos va a tener la
listaprintf("\n");for (i=0;i
