UNSAAC‎ > ‎Laboratorio III‎ > ‎

desarrollo de laboratorio III

Preguntas de Examén

publicado a la‎(s)‎ 4 jun. 2014 7:37 por Hernan Nina Hanco

Escriba un programa para encontrar el elemento mas frecuente de una lista de elementos. ¿Cúal es la complejidad de tiempo del programa?

Laboratorio 9: Divide y vencerás

publicado a la‎(s)‎ 17 jul. 2012 12:28 por Hernan Nina Hanco

Referencias del algoritmo de multiplicación de un numero grande de N cifras:

Tarea:
  • Implementar la multiplicación con eficiencia
  • Problema de selección (Ejemplo, la mediana)
  • Subsecuencia de suma máxima
  • Par de puntos mas cercanos
  • Fibonacii

Laboratorio 8: Tablas de dispersión

publicado a la‎(s)‎ 29 jun. 2012 10:23 por Hernan Nina Hanco   [ actualizado el 1 ago. 2013 7:13 ]

I) OBJETIVOS
  • Implementar modelos de tablas de dispersión y sus respectivas aplicaciones.
II) MARCO CONCEPTUAL

Hashing o localización
Es una forma de Implementación de tablas hash que dispone de técnicas para realizar inserciones, eliminaciones y búsquedas con coste medio constante.

Funcion hash o de localización
Función que asocia a un elemento y un índice.

Colisión
El empleo de la función de localización introduce una complicación, es posible que a dos elementos distintos les corresponda la misma posición.

Métodos para resolver la colisión
  • Exploración Lineal.- Consiste en buscar secuencialmente en el vector o arreglo hasta que encontremos una posición vacía y pueda agregar el elemento. Sin embargo, cuando el vector o arreglo esta con mas del 70% de su espacio ocupado, las búsquedas se hacen complicadas.
  • Exploración Cuadrática.- Es un método que mejora las deficiencias de la exploración lineal. utiliza la formula F(i)=i*i. Adiciona al valor de hash las funcion F(i).
  • Encadenamiento separado.- Una alternativa a la exploración cuadrática, maneja un arreglo o vector de listas enlazadas. La función Hash indica en que lista se debe almacenar un elemento.
III) PRACTICAS
1) Implementación básica de una tabla hash, con un función hash para números enteros de 16 bits.

namespace AppDispersion { public class TablaHash {
        // Arreglo o vector de elementos enteros private int[] tabla; public TablaHash(int n) { tabla = new int[n];
            // inicializar la tabla
            for (int i=0;i<tabla.Length;i++)
            {
                tabla[i]=0;
            } }
        /* Insertar un elemento al arreglo*/ public void insertar(int elemento) {
            // Determinar el indice del elemento utilizando la función hash int indice = hash(elemento);
            // Asignar elemento a la posición del indice
            // no se controla colisiones - se sobre escriben los elementos.
            tabla[indice] = elemento }
                 /* Implementación de una función hash para enteros de 16 bits */ private int hash(int clave) { return clave % tabla.Length; }
        /* Implementación de una función hash para enteros de 16 bits */ public void MostrarTabla() { for (int i = 0; i < tabla.Length; i++) { Console.Write("Indice: {0} ",i); Console.Write("\t"); Console.Write("Elemento: {0} ", tabla[i]); Console.Write("\n"); } } public bool busqueda(int clave) { return tabla[hash(clave)]!=0; } } }

Programa principal:

namespace AppDispersion
{
    class Program
    {
        static void Main(string[] args)
        {
           
            TablaHash tablaHash = new TablaHash(11);
            tablaHash.insertar(8);
            tablaHash.insertar(7);
            tablaHash.insertar(27);
            tablaHash.insertar(16);
            tablaHash.insertar(17);
            // mostrar la tabla Hash
            tablaHash.MostrarTabla();
            Console.ReadKey();
        }
    }
}

IV) TAREAS
  • Implementar una aplicación donde permita crear una tabla hash de tamaño "n" y poder almacenar, buscar y mostrar los elementos en la tabla.
  • Implementar los métodos de resolución de colisiones lineal, cuadrática y hashing enlazado.
V) Proyecto
  • Descripción: Implementar un Diccionario donde se registre la palabra y su significado. Se debe implementar una función hash para determinar los indices de una Palabra o cadena de caracteres.
  • Fecha de entrega: Martes 06 de Agosto del 2013
  • Numero de personas para el proyecto: 2
  • Recomendación: Evitar la copia de proyectos anteriores o de compañeros.
VI) REFERENCIAS
  • Estructura de datos en Java, Mark Allen Weiss, Addision Wesley - Pearson Educación. Capitulo 19 Tablas de Dispersión.

Laboratorio 7: Árboles B - Publicación pendiente....

publicado a la‎(s)‎ 29 jun. 2012 10:22 por Hernan Nina Hanco   [ actualizado el 29 jun. 2012 16:08 ]

I) OBJETIVOS

II) MARCO CONCEPTUAL
Árbol B
Un árbol B es una clase especial de árbol m-ario balanceado que permite recuperar, eliminar e insertar registros de un archivo con buen rendimiento en el peor caso. Un árbol B de orden m es un árbol de búsqueda m-ario con las siguientes propiedades:
  1. La raíz es una hoja o tiene al menos dos hijos.
  2. Cada nodo, excepto la ráiz y las hojas, tiene entre [m/2] y m hijos.
  3. Cada camino desde la raíz hasta una hoja tiene la misma longitud.

III) PRACTICAS

IV) TAREAS

V) REFERENCIAS

Laboratorio 6: Algoritmo de Ordenación Mergesort

publicado a la‎(s)‎ 13 jun. 2012 17:29 por Hernan Nina Hanco   [ actualizado el 14 jun. 2012 12:48 ]

I) OBJETIVOS
  • Implementar el algoritmo de ordenación Mergesort.

II) MARCO CONCEPTUAL

Mergesort
El algoritmo mergesort consta de tres pasos:
  1. Si el número de elementos a ordenar es 0 ó 1, acabar.
  2. Ordenar recursivamente las dos mitades del arreglo
  3. Mesclar las dos mitades ordenadas en un vector ordenado
 
III) PRÁCTICAS DE LABORATORIO

Implementar el mergesort

/* * Ordenamiento por mergesort. */ static void mergeSort(ref int[] a, ref int[] r, int izq, int der) { if (izq < der) { int centro = (izq + der) / 2; mergeSort(ref a,ref r,izq,centro); mergeSort(ref a, ref r, centro+1, der); mezclar(ref a,ref r,izq,centro+1,der); } } static void mergeSort(ref int[] a) { int[] r = new int[a.Length]; mergeSort(ref a,ref r,0,a.Length-1); } static void mezclar(ref int[] a, ref int[] r, int posIzq, int posDer, int posFin) { int finIzq = posDer - 1; int posAux = posIzq; int numElementos = posFin - posIzq + 1; // Bucle principal while (posIzq<=finIzq && posDer <=posFin) if (a[posIzq] < a[posDer]) r[posAux++] = a[posIzq++]; else r[posAux++] = a[posDer++]; // Copiar el resto de la primera mitad while (posIzq <= finIzq) r[posAux++] = a[posIzq++]; // copiar resto de la segunda mitad while (posDer <= posFin) r[posAux++] = a[posDer++]; // copiar el arreglo temporal al original for (int i = 0; i < numElementos; i++, posFin--) a[posFin] = r[posFin]; }

IV) TAREA:
  1. Evaluación del tiempo de ejecución del mergesort.
  2. Implementar el algoritmo de ordenación de heapsort, y el análisis de complejidad basado en tiempo de ejecución.

V) REFERENCIAS BIBLIOGRÁFICAS
  • Estructura de datos y algoritmos, Alfred V. Aho, John E. Hopcroft, Jefrey D. Ullman.

Laboratorio 5: Algoritmos de ordenación rápida Quicksort

publicado a la‎(s)‎ 6 jun. 2012 18:04 por Hernan Nina Hanco   [ actualizado el 12 jun. 2012 12:47 ]

I) OBJETIVOS
  • Implementar el algoritmo de ordenación mas rápido Quicksort.

II) MARCO CONCEPTUAL


8.3. Clasificación rápida (QuickSort)

El primer algoritmo de O(n log n), que se estudia, y tal vez el más eficiente para clasificación interna. La esencia del método consiste en clasificar un arreglo A[1], …,A[N] tomando en el arreglo un valor clave v como elemento pivote, alrededor del cual reorganizar los elementos del arreglo. Es de esperar que el pivote esté cercano al valor medio de la clave del arreglo, de forma que esté precedido por una mitad de las claves y seguido por la otra mitad. Se permutan los elementos del arreglo con el fin de que para algún j, todos los registros con claves menores que v aparezcan en A[1], …,A[j], y todos aquellos con claves v o mayores aparezcan en A[j+1],…,A[N]. Después, se aplica recursivamente la clasificación rápida a A[1], …,A[j] y a A[j+1], …,A[N] para clasificar ambos grupos de elementos. Dado que todas las claves del primer grupo preceden a todas las claves del segundo grupo, todo el arreglo quedará ordenado.


III) PRÁCTICAS DE LABORATORIO

1) Implementar el algoritmo de búsqueda Quicksort

static void AlgoritmoQuickSort(ref int[] arreglo, int i, int j) { int pivote; // el valor del pivote int indice_pivote; // el indice de un elemento de A donde su clave es el pivote int k; // indice al inicio del grupo de elementos >= pivote indice_pivote = encuentra_pivote(arreglo, i, j); Console.WriteLine(indice_pivote); if (indice_pivote != -1) // no hacer nada si todas las claves son iguales { pivote = arreglo[indice_pivote]; k = particion(ref arreglo, i, j,pivote); AlgoritmoQuickSort(ref arreglo, i, k - 1); AlgoritmoQuickSort(ref arreglo, k, j); } } static int encuentra_pivote(int[] arreglo, int i, int j) { int primera_clave; // Valor de la primera clave encontrada int k; // va de izquierda a derecha buscando una clave diferente primera_clave = arreglo[i]; for (k = i + 1; k <= j;k++) // rastrea en busca de una clave distinta if (arreglo[k] > primera_clave) // Selecciona la clave mayor { return k; } else if (arreglo[k] < primera_clave) return i; return -1; // nunca se encuentra dos claves diferentes } static int particion(ref int[] arreglo, int i, int j, int pivote) { int z, d; // cursores z = i; d = j; do { intercambiar(ref arreglo[z],ref arreglo[d]); // ahora se inicia la fase de rastreo while (arreglo[z]<pivote) z++; while (arreglo[d]>=pivote) d--; } while (z<d); return z; }


IV) TAREA:

  1. Evaluación del tiempo de ejecución en el peor, medio y peor caso del algoritmo.
  2. Modificar el algoritmo de la practica para acelerar QuickSoft seleccionando de mejor manera el pivote (elección del pivote en la base a la mediana).
  3. Modificar el algoritmo de la practica para acelerar QuickSoft permitiendo arreglos pequeños y llamando a algoritmos mas simples de ordenación.

V) REFERENCIAS BIBLIOGRÁFICAS
  • Estructura de datos y algoritmos, Alfred V. Aho, John E. Hopcroft, Jefrey D. Ullman.

Laboratorio 3: Algoritmos de ordenación y análisis de complejidad

publicado a la‎(s)‎ 23 may. 2012 19:24 por Hernan Nina Hanco   [ actualizado el 2 may. 2013 7:24 ]

I) OBJETIVOS
  • Implementar algoritmos de ordenación y analizar su complejidad tanto en soluciones iterativas y recursivas.

II) MARCO CONCEPTUAL


Algoritmos de ordenación
La ordenación es muy probable la operación mas importante y mejor estudiada en computación. Principalmente implementaremos algoritmos que realizan la ordenación en la memoria principal, también se puede realizar en el disco duro o en cintas a este tipo de ordenación se conoce como ordenación externa.

Esquemas simples de ordenación o clasificación
Ordenación o clasificación por Burbuja
Uno de los métodos mas simples es la clasificación por burbuja (bubblesort). La idea básica de la clasificación de burbuja es imaginar que los registros a ordenar están almacenados en un arreglo vertical. Los registros con claves menores son “ligeros” y suben. Se recorre varias veces el arreglo de abajo hacia arriba, y al hacer esto, si hay dos elementos adyacentes que no están en orden, esto es, si el “más ligero” está abajo, se invierten. El efecto que produce por esta operación es que el primer recorrido, el registro “más ligero” de todos, es decir, el registro que posee la clave con menor valor, sube hasta la superficie (o parte superior del arreglo). En el segundo recorrido, la segunda clave menor sube hasta la segunda posición, y así sucesivamente.

inicio12345
Pelee
Etna
Krakatoa
Agung
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Santa Elena
Vesubio

Algoritmo

for i=1 to n-1 do
    for j=n to downto i+1 do
        if A[j].clave < A[j-1].clave then
            intercambia(A[j], A[j-1])

Clasificación por Inserción

En el i-ésimo recorrido se “Inserta” el i-ésimo elemento A[i] en el lugar correcto, entre A[1], A[2], … ,A[i-1], los cuales fueron ordenados previamente. Después de hacer esta inserción, se encuentran clasificados los registros colocados en A[1], A[2], … ,A[i].         
inicio23456
-&
Pelee
Etna
Krakatoa
Agung
Vesubio
Santa Elena
-&
Etna
Pelee
Krakatoa
Agung
Vesubio
Santa Elena
-&
Etna
Krakatoa
Pelee
Agung
Vesubio
Santa Elena
-&
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
-&
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
-&
Agung
Etna Krakatoa
Pelee
Santa Elena
Vesubio

Algoritmo
A[0].clave = -
for i=2 to n do
begin
    j=i;
    while A[j]<A[j-1] do
    begin
        intercambia(A[j],A[j-1])
        j=j-1
    end
end

Ordenación y clasificación por selección

En el i-ésimo recorrido se selecciona el registro con la clave mas pequeña, entre A[j],.. ,A[n], y se intercambia con A[i]. Como resultado, después de i pasadas, los i registros menores ocuparán A[1], …, A[i] en el orden clasificado.

inicio12345
Pelee
Etna
Krakatoa
Agung
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Vesubio
Santa Elena
Agung
Etna
Krakatoa
Pelee
Santa Elena
Vesubio

Algoritmo
for i=1 to n-1 do
begin
    {Elegir el menor entre A[i], ..., A[n] e intercambiarlo con A[i] }
    indice_menor = i
    clave_menor = A[i].clave
    for j=i to n do
    begin
        {Comparar la clave con la actual clave menor}
        if (A[j].clave < clave_menor) then
        begin
            clave_menor = A[j].clave
            indice_menor = j;
        end
        intercambia(A[i],A[indice_menor])
    end
end


Complejidad de tiempo de los métodos
Las clasificaciones de burbuja, por inserción y por selección llevan un tiempo O(N2), y llevarán un tiempo &#x1d6c0;(N2) tanto en el peor caso y promedio, en buena parte de las secuencias de entrada de n elementos.

La clasificación por selección es superior a las clasificaciones de burbuja y por inserción.

Limitaciones de los algoritmos simples
la clasificación de shell es una generalización de burbuja de O(N1.5) 

III) PRÁCTICAS DE LABORATORIO
1) Implementar el algoritmo de ordenación Burbuja.

namespace AlgoritmosOrdenacionSimples
{
    class Program
    {
        
        static void Main(string[] args)
        {
            // Un arreglo de elementos 
            int[] arreglo = { 12, 5, 3, 8, 11, 9, 12, 1, 4, 7 };
            // ordenar el arreglo utilizando el método de burbuja
            clasificacionPorBurbuja(ref arreglo);
            // Mostrar el arreglo ordenado
            for (int i = 0; i < arreglo.Length; i++)
            {
                Console.WriteLine("Elemento[{0}]: {1}",i,arreglo[i]);
            }
            Console.ReadKey();
        }
        /*
         * 
         */
        static void clasificacionPorBurbuja(ref int[] arreglo)
        {
            // N recorridos por el arreglo
            for (int i = 0; i < arreglo.Length - 1; i++)
            {
                // Comparar elementos adyacentes para subir
                // elementos de menor valor a la superficie
                for (int j = arreglo.Length-1; j >= i+1; j--)
                {
                    if (arreglo[j] < arreglo[j - 1])
                    {
                        // Permutar o intercambiar elementos del arreglo
                        int temp = arreglo[j];
                        arreglo[j] = arreglo[j - 1];
                        arreglo[j - 1] = temp;
                    }
                }
            }
        }
    }
}

2) Implementar el algoritmo de ordenación por Inserción.

        /*
         * Implementación de la Clasificación por Inserción
         */
        static void clasificacionPorInsercion(ref int[] arreglo)
        {
            // Considerar un valor (A[-1].clave = -∞)
            // cuyo valor de clave sea menor a todos los valores del arreglo
            int min = -9999;
            int j;
            // Realizar n pasadas
            for (int i = 1; i < arreglo.Length; i++)
            {
                // En cada recorrido ubicar el i-ésimo elemento en su posición ordenada
                j = i;
                while (arreglo[j] < arreglo[j - 1])
                {
                    intercambiar(ref arreglo[j], ref arreglo[j - 1]);
                    // Comparar con el valor mínimo
                    // Consideramos esta condición pues en arreglos de
                    // C# no se considera indices menores a 0.
                    if (j<=0)
                    {
                        if (arreglo[j] < min)
                        {
                            intercambiar(ref arreglo[j], ref min);
                        }
                        break; // abandonar la iteración 
                    }
                    j = j - 1;
                }
            }
        }

        /*
         * Método para peermutar los valores de dos variables enteras.
         */
        static void intercambiar(ref int a, ref int b)
        {
            // intercambia(A[j],A[j-1])
            int temp = a;
            a = b;
            b = temp;
        }

3) Implementar el algoritmo de ordenación por Selección.

         /*
         * Método para implementar la Clasificación u ordenación por Selección.
         */

        static void clasificacionPorSeleccion(ref int[] arreglo)
        {
            int indice_menor;
            int clave_menor;
            for (int i = 0; i < arreglo.Length-1; i++)
            {
                // Elegir el menor entre A[i], ..., A[n] e intercambiarlo con A[i]
                indice_menor = i;
                clave_menor = arreglo[i];
                for (int j = i; j < arreglo.Length; j++)
                {
                    // Comparar la clave con la actual clave menor
                    if (arreglo[j] < clave_menor)
                    {
                        clave_menor = arreglo[j];
                        indice_menor = j;
                    }
                }
                intercambiar(ref arreglo[i], ref arreglo[indice_menor]);
            }
        }


IV) TAREA:
  1. Evaluar gráficamente la complejidad de tiempo de los métodos.
  2. Considere dentro de la evaluación, el caso de que los valores del arreglo ya estén ordenados, o en orden inverso.
  3. Implemente el método de clasificación Shellsort.

V) REFERENCIAS BIBLIOGRÁFICAS
  • Estructura de datos y algoritmos, Alfred V. Aho, John E. Hopcroft, Jefrey D. Ullman.

Laboratorio 4: Algoritmos de Búsqueda y complejidad

publicado a la‎(s)‎ 22 may. 2012 12:33 por Hernan Nina Hanco   [ actualizado el 19 may. 2014 8:34 ]

I) OBJETIVOS
  • Implementar algoritmos de búsqueda y analizar su complejidad
II) MARCO CONCEPTUAL
Revisar los temas de Algoritmos de Búsqueda:
  • Búsqueda Secuencial
  • Búsqueda Indexada
    • Indice Binario
    • Arboles B
  • Dispersión
    • Dispersión Cerrada
    • Dispersión Abierta

III) PRÁCTICAS DE LABORATORIO

1) Implementar un algoritmo de Búsqueda Secuencial con cálculo de tiempo de ejecución en nanosegundos.

namespace BusquedaSecuencial
{
   class Program
   {
       static void Main(string[] args)
       {
           // Crear un cronometro
           NanoTemporizador reloj = new NanoTemporizador();
           // crear un arreglo de enteros
           int[] arreglo = {2,4,1,6,3,5,7,10,14,9};
           // buscar el elemento 7
           reloj.Start();
           int idx = busquedaSecuencial(23,arreglo);
           reloj.Stop();
           Console.WriteLine(
             "El elemento 7 esta en la posición: {0}",idx);
           Console.WriteLine(
               "Tiempo en nanosegundos: {0}", reloj.ElapsedNanoseconds);
           Console.ReadKey();
       }
       /*
        * Método para búsqueda secuencial
        * @parameter elemento: es el elemento a búscar
        * @parameter arreglo: es el arreglo que almacena numeros enteros
        * @return: un entero que indique la ubicación del elemento
        */

       static int busquedaSecuencial(int elemento, int[] arreglo)
       {
           int idx = -1; // indica la posición del elemento en el arreglo
           // Recorrido por el arreglo
           for (int i = 0; i <= arreglo.Length - 1; i++)
           {
               // verificar si el i-ésimo elemento es el que búscamos
               if (arreglo[i] == elemento) // Elemento encontrado
               {
                   idx = i;
                   break;
               }
           }
           return idx;
       }
   }
}

2) Implementar un algoritmo en Búsqueda Binaria con análisis del tiempo de ejecución en nanosegundos.

namespace BusquedaBinaria
{
    class Program
    {     
        static void Main(string[] args)
        {
            // Crear un cronometro
            NanoTemporizador reloj = new NanoTemporizador();
            // crear un arreglo de enteros ordenado
            int[] arreglo = { 1,2,3,6,8,9,12,14,16,45,90};
            // buscar el elemento 9
            reloj.Start();
            int idx = busquedaBinaria(9,arreglo,0,arreglo.Length);
            reloj.Stop();
            Console.WriteLine("El elemento 9 esta en la posición: {0}", idx);
            Console.WriteLine(
                "Tiempo en nanosegundos: {0}", reloj.ElapsedNanoseconds);
            Console.ReadKey();
        }

        /*
         * Método para búsqueda binaria 
         * @parameter elemento: es el elemento a búscar
         * @parameter arreglo: es el arreglo que almacena numeros enteros
         * @parameter l: Límite inferior
         * @parameter u: Límite superior
         * @return: un entero que indique la ubicación del elemento
         */
            
        static int busquedaBinaria(int elemento, int[] arreglo, int l, int u)
        {
            int medio;
            if (l > u)
                return -1;
            medio = (l + u) / 2;

            if (arreglo[medio] < elemento)
                return busquedaBinaria(elemento, arreglo, medio + 1, u);
            else
                if (arreglo[medio] > elemento)
                    return busquedaBinaria(elemento, arreglo, l, medio - 1);
                else
                    return medio;        
                }

    }
}



IV) TAREA:

1) Modificar el programa de la práctica para obtener datos desde un archivo de datos en modo texto, para luego realizar una búsqueda secuencial.
2) Modificar el programa de la práctica para obtener datos desde un archivo de datos en modo texto, para luego realizar una búsqueda binaria.
3) Mostrar la complejidad de algoritmos en su forma gráfica para búsqueda secuencial y binaria. realice una comparación de gráficos. Considere los tiempos en el mejor, medio y peor caso para cada algoritmo.

V) REFERENCIAS BIBLIOGRAFICAS

Laboratorio 2. Prueba empírica de la Complejidad de Algoritmos

publicado a la‎(s)‎ 24 abr. 2012 16:38 por Hernan Nina Hanco   [ actualizado el 16 may. 2012 8:04 ]

I) OBJETIVOS
  • Experimentar la prueba empírica de la complejidad de algoritmos.
II) MARCO CONCEPTUAL
Revisar los temas de Complejidad de algoritmos y orden de la complejidad de algoritmos

III) PRÁCTICAS DE LABORATORIO
1) Cálculo del tiempo transcurrido en milisegundos de la ejecución de un algoritmo.


   class Program
   {
       static void Main(string[] args)
       {
           // Obtener el tiempo inicial
           DateTime t1 = DateTime.Now;
           // Ejecutar el algoritmo para un valor n = 100
           int suma = sumaN(100);
           Console.WriteLine("Valor de la Suma: {0}",suma);
           // Obtener el tiempo final de la ejecución
           DateTime t2 = DateTime.Now;
           //Determinar el tiempo en milisegundos
           long tiempo = ((t2.Hour + t2.Minute + t2.Second) * 1000

+ t2.Millisecond) -

               ((t1.Hour + t1.Minute + t1.Second) * 1000 + t1.Millisecond);
           // Mostrar el tiempo
           Console.WriteLine("El tiempo transcurrido es: {0}",tiempo);
           Console.ReadKey();
       }

       static int sumaN(int n)
       {
           int s = 0;
           for (int i = 1; i <= n; i++)
           {
               s = s + i;
           }
           return s;
       }
   }



2) Cálculo del tiempo transcurrido en milisegundos utilizando la clase Stopwatch.


  
 static void Main(string[] args)
       {
           // Obtener el tiempo inicial
           Stopwatch reloj = new Stopwatch();
           reloj.Start();
           // Ejecutar el algoritmo para un valor n = 100
           int suma = sumaN(100000);
           Console.WriteLine("Valor de la Suma: {0}", suma);
           // Obtener el tiempo final de la ejecución
           reloj.Stop();
           //Determinar el tiempo en milisegundos
           long tiempo = reloj.ElapsedMilliseconds;
           // Mostrar el tiempo
           Console.WriteLine("El tiempo transcurrido es: {0}", tiempo);
           Console.ReadKey();
       }


IV) TAREA:
1) Aplicando los programas de la practica determine gráficamente la complejidad de un algoritmo, lineal, cuadratico, cubico, exponencial.
2) Aplicando los programas de la práctica determine gráficamente la complejidad de un algoritmo de Potencia, Factorial y Fibonaci. Considere los casos de soluciones iterativa y recursivas.
3) Implemente un programa para medir el tiempo de ejecución en nanosegundos.

V) REFERENCIAS BIBLIOGRAFICAS

Laboratorio 1: Gestión de Archivos

publicado a la‎(s)‎ 24 abr. 2012 8:56 por Hernan Nina Hanco   [ actualizado el 22 may. 2012 14:13 ]

I) OBJETIVOS
  • Conocer el almacenamiento de datos de forma persistente utilizando librerias de gestión de archivos en un lenguaje de programación.
II) MARCO CONCEPTUAL

Streams

Los streams son la forma en la que se realizan operaciones de lectura/escritura desde/hacia medios de almacenamiento como pueden ser un disco o la propia memoria. Todas las clases que representan a streams heredan de la clase Stream (System.io.Stream).

Clase Stream ( sus subclases) ofrecen un punto de vista sobre las distintas fuentes de datos, repositorios, etc… y aislan a los programadores de los detalles específicos del sistema operativo y los dispositivos.

  • Los streams nos permiten realizar los siguientes tipos de operaciones:

    • Realizar lecturas de los streams: Extraer datos del stream.

    • Realizar escrituras en los streams: Escribir datos en el stream.

    • Realizar posicionamientos en los streams: Dependiendo del tipo de almacenamiento, permitiran modificar la posición sobre el stream

Algunas de las operaciones básicas de la implementación del stream son:

  • Read – CanRead

  • Write – CanWrite

  • Seek, SetLength – CanSeek, Position, Length


El espacio de nombres System.io contiene:

  • BufferedStream: Emplea un buffer para las lecturas y escrituras mejorando el rendimiento. No permite herencias.

  • MemoryStream: Crea streams utilizando la memoria como almacenamiento, no usa ni disco ni red.

  • FileStream: Lectura y escritura en ficheros. Aunque trabaja en modo síncrono, provee de un constructor para abrir ficheros en modo asíncrono.


Readers y Writers

Las clases que se derivan de System.IO.Stream realizan la operaciones de entrada/salida basada en bytes. Los Readers y los Writers pueden tomar otros tipos de datos y leerlos o escribirlos en streams o cadenas.

Clases:

  • BinaryReader y BinaryWriter: Leen y escriben tipos primitivos en un stream

  • TextReader y TextWriter: Diseñadas para la entrada/salida de caracteres

  • StreamReader y StreamWriter: Se derivan de TextReader y TextWriter. Pensadas para la lectura y escritura en un stream.

  • StringReader y StringWriter: Se derivan de TextReader y TextWriter. Leen los caracteres de un string y escriben en un StringBuilder.


Entrada y salida basica a ficheros: Clase FileStream

Utilizada para leer y escribir en ficheros. Su constructor posee tres parámetros (además del

nombre):

  • FileMode: Open, Append, Create

  • FileAccess: Read, Write, ReadWrite

  • FileShare: Enumeración con constantes útiles para controlar el tipo de acceso que tendrán otros FileStream al archivo. Esta enumeración es útil cuando más de dos procesos acceden al mismo archivo simultaneamente:

    • Read → Permite a los otros procesos leer

    • Write → Permite a los otros procesos escribir

    • None → Rechaza las peticiones de apertura por otros procesos

    • ReadWrite → Permite a los otros procesos leer y escribir


Crear un nuevo FileStream

FileStream fs = new FileStream (nombre_archivo, FileMode.Open, FileAccess.Read, FileShare.Read)


El Método Seek para ficheros de acceso aleatorio:

  • Los objetos FileStream soportan acceso aleatorio a los ficheros mediante el método Seek.

  • El método Seek permite mover la posición actual de lectura/escritura dentro del fichero.

  • El cambio de posición se realiza mediante un offset o desplazamiento basado en el número de byte.

  • El offset es relativo a un punto de referencia dado. Este punto de referencia viene por la enumeración SeekOrigin.

  • SeekOrigin posee tres miembros:

    • Begin: Hace referencia a la posición inicial del fichero

    • Current: Hace referencia a la posición actual del fichero

    • End: Hace referencia a la posición final del fichero


III) Practicas de laboratorio

Practica 1: Acceso de lectura y escritura de un archivo

La siguiente aplicación muestra la forma de crear un archivo de tipo binario y poder escribir datos como su contendo y luego hacer la lectura del contenido, para ello se utiliza librerias de gestión de Archivos de la plataforma .Net Framework en el lenguaje de programación C#



   class Program
   {
       private const string NOMBRE_ARCHIVO = "prueba.txt";
       static void Main(string[] args)
       {
           // Creamos el archivo de datos
           if (File.Exists(NOMBRE_ARCHIVO)){
               Console.WriteLine(

"El Archivo {0} ya existe", NOMBRE_ARCHIVO);

               return;
           }

           FileStream fs = new

FileStream(NOMBRE_ARCHIVO,FileMode.CreateNew);

           // Se crea el Writer para escribir los datos
           BinaryWriter bw = new BinaryWriter(fs);
           // Escribir los datos
           for (int i = 0; i <= 10; i++)
           {
               Console.WriteLine("Escribiendo {0}",i);
               bw.Write(i);
           }
           // cerramos el stream de escritura y el archivo
           bw.Close();
           fs.Close();
           
           // volvemos a abrir el archivo
           fs = new FileStream(NOMBRE_ARCHIVO,FileMode.Open,

FileAccess.Read);

           // Creamos el Stream de lectura
           BinaryReader br = new BinaryReader(fs);
           // Recorremos los datos del archivo
           for (int i = 0; i <= 10; i++)
           {
               Console.WriteLine("Leyendo {0}",

br.ReadInt32());

           }
           // Cerramos el stream y el archivo
           br.Close();
           fs.Close();
       }
   }




Practica 2: Ejercicio de estructura de directorios y archivos

La estructura de directorios y archivos es una aplicación de la estructura de datos árbol. Los sistemas de archivos de los Sistemas Operativos manejan este tipo de estructuras. En el código siguiente se muestra un método para mostrar el contenido de un directorio, se considera solo archivos pudiendo también listar los subdirectorios. Se utiliza las Clases de información DirectoryInfo, FileInfo.


      public static void MostrarContenidoDirectorio()
      {


          // Información de un determinado directorio
          DirectoryInfo di = new DirectoryInfo("c:/");
          // Arreglo de archivos que se encontraban en el

// directorio

          FileInfo[] diar1 = di.GetFiles();
          // Mostrar todos los archivos encontrados
          foreach (FileInfo f in diar1)
          {
              Console.WriteLine(f.Name + "\n");
          }
      }


Practica 3: Leer un archivo de texto

using System.IO;

class LecturaArchivo
{
    private const string ARCHIVO = "lineas.txt";
    static void main(string[] args)
    {
        string linea;
        if (!File.Exists(ARCHIVO))
        { 
            Console.WriteLine("El archivo {0} no existe", ARCHIVO);
            return;
        }
        // StreamReader derivado de TextReader para leer un archivo
        StreamReader sr = File.OpenText(ARCHIVO);
        // leer linea a línea un archivo hasta que no exista líneas
while ((linea = sr.ReadLine()) != null)
        {
            Console.WriteLine(linea);
        }
        Console.WriteLine("Fin de archivo");
        sr.close();
    }
}



IV) Trabajo para casa:

Ejercicio propuesto 1:
  • Programar dos pequeños programas que permitan leer y escribir registros en dos Archivos.
    • Campos de registro_1:
      • <nombre><apellido1><apellido2><teléfono>
    • Campos de registro_1:
      • <dd/mm/aaaa><Título_cita><hh:mm>
  • Sugerencia: Crear métodos que realicen la escritura de registros de manera atómica. Ej: escribirPersona, leerPersona, etc.
  • Sugerencia: Crear clases que representen los objetos denotados por los registros e incluir en éstas la responsabilidad de la escritura/lectura de los registros.
Ejercicio propuesto 2:

Escriba una aplicación para mostrar el contenido de un directorio considerando los archivos y subdirectorios del mismo, también mostrar el contenido de los subdirectorios. Puedes considerar como modelo de la aplicación el comando tree de Windows.


V) Referencias bibliograficas

1-10 of 10