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.