DOCENCIA UNIVERSITARIA > Laboratorio III >
desarrollo de laboratorio III
Preguntas de Examén
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
Referencias del algoritmo de multiplicación de un numero grande de N cifras: Tarea:
|
| Archivos adjuntos:
divide y venceras.pdf
Laboratorio 8: Tablas de dispersión
I) OBJETIVOS
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
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
V) Proyecto
VI) REFERENCIAS
|
Laboratorio 7: Árboles B - Publicación pendiente....
I) OBJETIVOS Á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:
III) PRACTICAS IV) TAREAS V) REFERENCIAS |
Laboratorio 6: Algoritmo de Ordenación Mergesort
I) OBJETIVOS
Mergesort El algoritmo mergesort consta de tres pasos:
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:
V) REFERENCIAS BIBLIOGRÁFICAS
|
Laboratorio 5: Algoritmos de ordenación rápida Quicksort
I) OBJETIVOS
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:
V) REFERENCIAS BIBLIOGRÁFICAS
|
Laboratorio 3: Algoritmos de ordenación y análisis de complejidad
I) OBJETIVOS
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.
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].
Algoritmo A[0].clave = -∞begin j=i; while A[j]<A[j-1] do begin intercambia(A[j],A[j-1]) j=j-1 endendEn 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.
Algoritmo for i=1 to n-1 dobegin {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]) endendComplejidad 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 𝛀(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:
V) REFERENCIAS BIBLIOGRÁFICAS
|
Laboratorio 4: Algoritmos de Búsqueda y complejidad
I) OBJETIVOS
Revisar los temas de Algoritmos de Búsqueda:
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
I) OBJETIVOS
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
((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
I) OBJETIVOS
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.
Algunas de las operaciones básicas de la implementación del stream son:
El espacio de nombres System.io contiene:
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:
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):
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:
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(
return; } FileStream fs = new
// 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,
// 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}",
} // Cerramos el stream y el archivo br.Close(); fs.Close(); } }Practica 2: Ejercicio de estructura de directorios y archivosLa 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
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:
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