Universidad Central del Ecuador

Tema: Algoritmos de búsqueda

Integrantes:

Jessica Flores Investigadora Edison Mendoza Digitador Byron Macas Digitador Jennifer Jurado Investigadora Mario Quintana Programador Alejandra Guerrero Coordinadora

INDICE

Introducción.....................................................................................................................2

0

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

INTRODUCCIÓN

1

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

powerpoint para una mejor comprensión del tema.

4. Grabar un video del algoritmo de búsqueda secuencial en C para

conocer el funcionamientodel 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) OrdenamientoUna 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 Aque contiene “n” elementos numéricos

(n )>¿1(A [1 ] , A [2 ] , A [3 ] ,…, A [n ]) 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

paso se evita la comparación de i con N y , por consiguiente , este algoritmo

5

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<stdio.h>#include<conio.h>//Declaramos variables globales que van a servir en todo el códigointnumero, vector[200], dimension, i, posiciones[200], aux;//Función para generar los valores de la listavoid 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 listaprintf("\n");for (i=0;i<dimension;i++) //Usamos este loop para ingresar los valores de cada

elemento del vector{

printf("-Ingrese el elemento %d de la lista: ", i+1);scanf("%d", &vector[i]);

}printf("\n");

}//Función de búsqueda e impresiónvoidbusqueda (){

aux=0;//Inicializamos la variablefor (i=0;i<dimension;i++){ //Usamos este loop para realizar la búsqueda

if (numero==vector[i]){ //Se realiza una comparación de un valor con cada elemento del vector, cuando se encuentra el número se realiza una acción en este caso que imprima la posición del valor.

printf("El número se encuentra en la posición: "); //Imprimimos la posición del vector.

printf("%d\n", i+1);}else{

aux=aux+1; //Este else lo usamos como un acumulador que posteriormente usaremos para realizar una comparación

}}if (dimension==aux){ //Con la variable aux dada un valor podemos hacer una

comparación para realizar una acción en el caso de que no exista el valor buscado en nuestra lista

printf("\nEl número no está en lista.");}

}//Función principal

7

intmain(){//Encabezadoprintf("\tAlgoritmos de Busqueda Secuencial\n\n");printf("La busqueda secuencial se realiza comparando uno por uno\ncada elemento de

una lista.\n\n");printf("Ejemplo\n\n");printf("-Realizar un programa en el cual se verifique la pertenencia de un número\na

una lista e imprimir a su posición en ella.\n\n");//Llamamos a la función valoresvalores();

printf("Ingrese el número a buscar: ");//Ingresamos el número que vamos a buscarscanf("%d", &numero);//Llamamos a la función búsquedabúsqueda();printf("\t\t\n\nGRACIAS\n\n");//Hacemos que el programa se detengasystem("pause");//damos el valor de retorno de la función main para acabarreturn 0;

}

Esta es la primera pantalla que nos aparece al abrir el programa, está esperando que ingresemos la dimensión del vector o “elementos de la lista”

8

Una vez ingresada la dimensión nos va a pedir que ingresemos los valores de cada elemento del vector o lista.

Cuando ingresamos todos los elementos de la lista el programa nos pide que ingresemos el número que deseamos buscar.

9

Después de ingresar el elemento que se desea buscar hay tres posibles casos:

1. Que el número este en lista.

2. Que el número este varias veces en lista.

10

3. Que el número no se encuentre en la lista.

Búsqueda secuencial en Visual Basic

Sub Busqueda()'Algoritmo de busqueda secuencial''Declaramos variables'Dimnumero, vector(200), dimension, i, posiciones(200), aux As Integer'Encabezado'MsgBox ("Algoritmos de Busqueda Secuencial" &vbCrLf& "La busqueda secuencial se realiza comparando uno por uno cada elemento de una lista.")

11

MsgBox ("Ejemplo" &vbCrLf& "-Realizar un programa en el cual se verifique la pertenencia de un número\na una lista e imprimir a su posición en ella.")

'Generamos los valores de la lista'dimension = InputBox("Ingrese el numero de elementos de la lista: ")

i = 0For i = 0 To dimension - 1

vector(i) = InputBox("-Ingrese el elemento de la lista: ")Next i

'Ingresamos el numero que vamos a buscar'numero = InputBox("Ingrese el número a buscar: ")

'Inicializamos la variable'

12

aux = 0'Busqueda e impresión''Usamos este loop para realizar la busqueda'For i = 0 Todimension - 1 'Se realiza una comparación de un valor con cada elemento del vector, cuando se encuentra el número se realiza una acción en este caso que imprima la posición del valor.'If numero = vector(i) Then 'Imprimimos la posición del vector'

MsgBox ("El numero se encuentra en la posición: " & (i + 1))

Else 'Este else lo usamos como un acumulador que posteriormente usaremos para realizar una comparación'

aux = aux + 1 End If Next i'Con la variable aux dada un valor podemos hacer una comparación para realizar una acción en el caso de que no exista el valor buscado en nuestra lista'Ifdimension = auxThen

MsgBox ("El numero no está en lista.")

EndIfMsgBox ("GRACIAS")

End Sub

13

Búsqueda secuencial en JAVA

//Algoritmosdebusquedasecuencial//Java esunlenguajeorientado a objetosporloquetenemosquecrearunoparausarlasdiferentesclases//Importamosunaclasequenossirveparaingresardatosportecladosimportjava.util.Scanner;

publicclassAlgoritmos_de_busqueda_secuencial {publicstaticvoid main (String[] arg){

//Declaramoslosatributos, queen C o en Vbsellaman variablesintnumero, dimension, i, aux;

//Declaramosvectoresint[] vector = newint[200];

//Creamosunobjetoparausarlaclase "Scanner" y todossusmetodosScanner scan = newScanner(System.in);

//EncabezadoSystem.out.println("\tAlgoritmos de Busqueda Secuencial\n");System.out.println("La busqueda secuencial se realiza comparando

uno por uno\ncada elemento de una lista.\n\n");System.out.println("Ejemplo\n\n");System.out.println("-Realizar un programa en el cual se

verifique la pertenencia de un número\na una lista e imprimir a su posición en ella.\n\n");

System.out.println("Ingrese el numero de elementos de la lista: ");

//Ladimensiónsirveparadelimitarcuantoselementosva a tenerlalistadimension= scan.nextInt();

//Usamosesteloopparaingresarlosvaloresdecadaelementodel vectorfor (i=0 ; i<dimension ; i+=1){

System.out.println("-Ingrese el elemento "+(i+1)+" de la lista: ");

vector[i]=scan.nextInt();}

14

//Ingresamos el numeroquevamos a buscarSystem.out.println("Ingrese el número a buscar: ");numero=scan.nextInt();

//Inicializamosla variableaux=0;

//Usamosestelooppararealizarlabusquedafor (i=0;i<dimension;i+=1){

//Serealizaunacomparacióndeun valor concadaelementodel vector, cuandoseencuentra el número se

//realiza una accion en este caso que imprima la posicion del valor.

if (numero==vector[i]){

//Imprimimos la posición del vector.System.out.println("El numero se escuentra en la

posicion: "+(i+1));}

15

else{

//Este else lo usamos como un acumulador que posteriormente usaremos para realizar una comparación

aux+=+1;}

}

//Con la variable aux dada un valor podemos hacer una comparación para realizar una acción en el caso de que no exista el valor buscado en nuestra lista

if (dimension==aux){System.out.println("\nElnumero no esta en lista.");

}

System.out.print("\t\t\n\nGRACIAS\n\n");}}

16

Herramienta de video MirillissAction

La herramienta que será utilizada para realizar el video es MirillisAction.

Se escogió esta herramienta ya que encontramos varios videos en YouTube

que recomendaban utilizarla puesto que puede grabar juegos y todo lo que se

ve en el Escritorio, así como sacar capturas JPG. Luego, los vídeos se pueden

comprimir y subir a Facebook o YouTube con un clic.

Ventajas:

o Fácil instalación

o Graba vídeo, audio y saca capturas

o Códec propio de alto rendimiento

o Exportación a Facebook, YouTube, etc.

o Benchmarking de rendimiento (FPS)

o Modo de grabación Perfect Video Match

o Aceleración de vídeo vía GPU

Desventaja:

o La versión de prueba añade una marca de agua

Esta herramienta posee solo una desventaja por ser versión de prueba, por lo

demás es muy recomendada.

17

Conclusiones:

1. Este método de búsqueda es muy lento. Si los valores del vector no son

únicos, para encontrar todos los valores con un valor particular, se requiere

buscar en todo el arreglo para encontrar todas las coincidencias.

2. Si el elemento buscado con frecuencia no está al principio del arreglo, la

cantidad promedio de comparaciones aumenta notablemente dado que se

requerirá más tiempo para encontrar el elemento.

3. Definitivamente, la búsqueda secuencial es el método menos eficiente

porque se basa en comparar el valor que se desea buscar con cada uno de los

valores del arreglo.

4. La búsqueda secuencial es de gran utilidad cuando se tienen datos no

ordenados

5. Esta búsqueda es sencilla de implementar e intuitiva ya que consiste en

buscar de manera secuencial un elemento, es decir preguntar si el elemento

buscado es igual al primero, segundo, tercero y así sucesivamente hasta

encontrar el deseado.

18

Recomendaciones:

1. Es el mejor método de búsqueda para registros desordenados y revisa nodo

(posición) por nodo(posición) sin brincar ninguno ( es muy seguro).

2. No es recomendable usar este método cuando se tiene una gran cantidad de

datos.

3. Se recomienda que 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. Esto para que se tenga una mejor apariencia del

programa realizado.

19

Bibliografía:

1. Joyanes, L. (2008). Fundamentos de programación, Algoritmos, estructura

de datos y objetos. España: McGraw – Hill.

2. Deitel, P. y Deitel H. (2012). Como programar en Java.

3. Joyanes Aguilar, L. (2010). Programación en C, C++, Java y UML. México:

McGraw – Hill.

20