Estructura de Datos y Algoritmos
1er. Sem 2003
Tarea 1: Actualizaciones del Máximo
Suponga que tenemos que encontrar el valor máximo entre N números
enteros. El algoritmo común para tal problema es:
int max (int A[], int n)
{/*
Entradas: A: arreglo de números enteros que contiene el máximo
a buscar.
n: número de entradas de A a considerar en la búsqueda del
máximo.
Salida: se retorna el valor máximo entre A[0] .. A[n-1].
Precondición: n>0;
*/
int i, maxActual=A[0];
for ( i=1; i<n; i++)
if ( A[i] > maxActual)
maxActual = A[i];
/* actualización a estudiar*/
return (maxActual);
}
En el proceso de obtención del máximo se desea estudiar cuantas
veces es ejecutada en promedio la asignación destacada en el algoritmo.
Asegúrese el intervalo de confianza para su valor promedio del 95%
sea ± 1%. En otras palabra, su valor promedio µ es tal que el
valor correcto para el promedio, aquel con infinitas iteraciones, está
en el rango µ ± 0.01µ con una probabilidad del 95%.
Trabajo específico: Haga un programa en C que permita generar
dos gráficos: uno indicando el número de iteraciones hasta
lograr el intervalo de confianza indicado versus N, y otro del número
promedio de veces que la asignación tuvo lugar cuando se buscó
el máximo versus N. En este segundo gráfico ponga también
la función ln(x). Varíe N entre 10 y el número de habitantes
de Viña (~300 mil).
Observaciones:
El programa que usted haga debe entregar una tabla de valores. Estos valores
serán graficados por gnuplot.
Para que sus resultados tengan validez estadística, usted deberá
ejecutar la rutina max un "gran" número de veces. ¿Cuántas?
hasta que se cumpla con el intervalo de confianza pedido.
El revisión de su tarea tendrá dos fases. La primera es ejecutar
su programa y obtener las tablas indicadas. La segunda es ejecutar gnuplot
con el archivo de configuración por usted desarrollado para obtener
las gráficas. Muestre el número de iteraciones primero y luego
la del valor promedio y ln(x) en un mismo eje de coordenadas.
¿Qué cosas entregar? Además de lo pedido en el procedimiento de entrega, incorporar su archvio
de configuración para gnuplot.