LABORATORIO DE ESTRUCTURAS DE DATOS

PRÁCTICA Nº 1: 1 sesión

(del 5 de Marzo al 9 de Marzo de 2000)

Análisis de costes algorítmicos
0. Objetivo

En esta práctica intentaremos obtener el coste temporal de diferentes algoritmos de búsqueda vistos en clase.

Para ello realizaremos un programa que implementará en C++ los diferentes algoritmos como subprogramas que se aplicaran a diferentes vectores, devolviendo en cada caso el número de asignaciones y comparaciones realizados por el subprograma.

1. Introducción

Una tarea habitual en informática es la búsqueda de un valor en un conjunto de valores y para ello se han desarrollado diferentes algoritmos.

El algoritmo más normal para buscar en un conjunto de valores es la búsqueda secuencial.

Si suponemos que buscamos 'x' (entero) en un conjunto de valores (enteros) guardados en un vector 'v' de 'n' elementos tendríamos la siguiente función de búsqueda:

Algoritmo Buscar_1

Entradas

v: vector, n:entero, x:entero

Salidas

enc: booleano

Variables auxiliares

i: entero

Inicio

enc <- falso

i <- 0

Mientras ( x < n ) Hacer

Si v[i] = x Entonces

enc <- verdadero

Fin_si

i <- i + 1

Fin_mientras

Devolver (enc)

Fin

Ya se comentó en teoría que la función se podía modificar cortando la búsqueda en cuanto se encuentre el elemento

Algoritmo Buscar_2

Entradas

v: vector, n:entero, x:entero

Salidas

enc: booleano

Variables auxiliares

i: entero

Inicio

i <- 0

Mientras ( x < n ) && ( v[i] != x ) Hacer

i <- i + 1

Fin_mientras

Si (x == n) Entonces

enc <- falso

Sino

enc <- verdadero

Fin_si

Devolver (enc)

Fin

Y, finalmente, que la función mejoraba si añadíamos la presencia de un centinela

Algoritmo Buscar_3

Entradas

v: vector, n:entero, x:entero

Salidas

enc: booleano

Variables auxiliares

i: entero

Inicio

v[n] <- x

i <- 0

Mientras (v[i] != x) Hacer

i <- i + 1

Fin_mientras

Si (x == n) Entonces

enc <- falso

Sino

enc <- verdadero

Fin_si

Devolver (enc)

Fin

En el caso en que tengamos el vector ordenado podemos aprovechar este hecho para determinar si tenemos que seguir buscando o no.

Algoritmo Buscar_4

Entradas

v: vector, n:entero, x:entero

Salidas

enc: booleano

Variables auxiliares

i: entero

Inicio

v[n] <- x

i <- 0

Mientras (v[i] < x) Hacer

i <- i + 1

Fin_mientras

Si (v[i] == x) && (i != n) Entonces

enc <- verdadero

Sino

enc <- falso

Fin_si

Devolver (enc)

Fin

Además también podemos aplicar una nueva técnica de búsqueda: La búsqueda dicotómica.

Algoritmo Buscar_1

Entradas

v: vector, n:entero, x:entero

Salidas

enc: booleano

Variables auxiliares

i: entero; bajo, alto, medio: entero

Inicio

bajo <- 0

alto <- n-1

medio <- (bajo + alto) / 2

Mientras (v[medio] != x) && (bajo < alto) Hacer

Si (x < v[medio]) Entonces

alto <- medio - 1

Sino

bajo <- medio + 1

Fin_si

medio <- (bajo + alto) / 2

Fin_mientras

Si (v[medio] == x) Entonces

enc <- TRUE

Sino

enc <- FALSE

Fin_si

Devolver (enc)

Fin
2. Realización de la práctica

En la practica implementaremos las diferentes funciones de búsqueda añadiendo en la realización de las mismas, dos contadores para determinar el número de asignaciones y el número de comparaciones que se realizan en la llamada a la función.

Por ejemplo, la primera función de búsqueda quedaría como sigue:

Algoritmo Buscar_1

Entradas

v: vector, n:entero, x:entero

por referencia n_a, n_c: entero

Salidas

enc: booleano

Variables auxiliares

i: entero

Inicio

n_c <- 0

n_a <- 2

enc <- falso

i <- 0

Mientras ( x < n ) Hacer

n_c <- n_c + 2

Si v[i] = x Entonces

n_a <- n_a + 1

enc <- verdadero

Fin_si

n_a <- n_a + 1

i <- i + 1

Fin_mientras

n_c <- n_c + 1

Devolver (enc)

Fin_funcion

El programa principal presentara las siguientes posibilidades:

a. Introducir un valor de 'n' (numero de elementos donde buscar en el vector) siempre menor que TAM-1

b. Generar un vector aleatorio con valores entre '0' y 'n'

c. Generar un vector ordenado (por ejemplo con los valores 0, 1, 2, ..., n-1)

d. Buscar en el vector con la funcion 1, el primer elemento del vector

e. Buscar en el vector con la funcion 2, el primer elemento del vector

f. Buscar en el vector con la funcion 3, el primer elemento del vector

g. Buscar en el vector, si esta ordenado, con la funcion 4, el primer elemento del vector

h. Buscar en el vector, si esta ordenado, con la funcion 5, el elemento que esta en el punto medio del vector

i. Buscar en el vector con la funcion 1, un elemento x con valor n+1

j. Buscar en el vector con la funcion 2, un elemento x con valor n+1

k. Buscar en el vector con la funcion 3, un elemento x con valor n+1

l. Buscar en el vector, si esta ordenado, con la funcion 4, un elemento x con valor n+1

m. Buscar en el vector, si esta ordenado, con la funcion 5, un elemento x con valor n+1

n. Buscar en el vector con la funcion 1, un elemento x aleatorio que se encuentre en el vector

o. Buscar en el vector con la funcion 2, un elemento x aleatorio que se encuentre en el vector

p. Buscar en el vector con la funcion 3, un elemento x aleatorio que se encuentre en el vector

q. Buscar en el vector, si esta ordenado, con la funcion 4, un elemento x aleatorio que se encuentre en el vector

r. Buscar en el vector, si esta ordenado, con la funcion 5, un elemento x aleatorio que se encuentre en el vector

Una vez realizado el programa habría que rellenar la tabla adjunta:

Vector aleatorio

Vector ordenado

mejor

medio

peor

mejor

medio

peor

n_a

n_c

n_a

n_c

n_a

n_c

n_a

n_c

n_a

n_c

n_a

n_c

Buscar_1

Buscar_2

Buscar_3

Buscar_4

Buscar_5

Para los siguientes valores de n: 100, 300, 600, 1000, 2000, 3000 (definir la constante TAM como 3001).

Para el cálculo del valor medio repetir las pruebas 10 veces y calcular la media de los valores obtenidos.

3. Requisitos

Recordar que para poder acceder a la sesión de prácticas correspondiente es necesario entregar un pequeño esquema de lo que se va a realizar en la práctica. Si no se presenta el resumen ANTES de acceder al laboratorio, no se permitirá la entrada a la sesión de prácticas.

4. Entrega de prÁcticas

Por e-mail a la dirección del profesor encargado del grupo o en disquette al iniciar la siguiente sesión de prácticas, pero siempre ANTES de empezar la siguiente sesión de prácticas.

Cualquier práctica entregada fuera de plazo no será admitida para su corrección.