Estructura De Datos

“INGENIERIA EN SISTEMAS COMPUTACIONALES”

MATERIA: “ESTRUCTURA DE DATOS”

“SINTESIS DE UNIDADES”

PRFESOR(A): ING. JORGE CARRANZA

ALUMNO: JUAN MANUEL RODRIGUEZ MARTINEZ

SEMESTRE: 3 NO. CONTROL: 09320873

UNIDAD I: “ANALISIS DE ALGORITMOS”

Es un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos que no generen dudas a quien deba realizar dicha actividad. Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución.

Hay que hacer énfasis en dos aspectos para que un algoritmo exista:

1. El número de pasos debe ser finito. De esta manera el algoritmo debe terminar en un tiempo finito con la solución del problema.

2. El algoritmo debe ser capaz de determinar la solución del problema.

De este modo, podemos definir algoritmo como un "conjunto de reglas operacionales inherentes a un cómputo". Se trata de un método sistemático, susceptible de ser realizado mecánicamente, para resolver un problema dado.

Características de un algoritmo.

1. Entrada: definir lo que necesita el algoritmo

2. Salida: definir lo que produce.

3. No ambiguo: explícito, siempre sabe qué comando ejecutar.

4. Finito: El algoritmo termina en un número finito de pasos.

5. Correcto: Hace lo que se supone que debe hacer. La solución es correcta

6. Efectividad: Cada instrucción se completa en tiempo finito. Cada instrucción debe ser lo suficientemente básica como para que en principio pueda ser ejecutada por cualquier persona usando papel y lápiz.

7. General: Debe ser lo suficientemente general como para contemplar todos los casos de entrada.

Razones para estudiar los algoritmos.

1. Evitar reinventar la rueda. Para algunos problemas de programación ya existen buenos algoritmos para solucionarlos. Para esos algoritmos ya fueron analizadas sus propiedades.

2. Para ayudar cuando desarrollen sus propios algoritmos. No siempre existe un algoritmo desarrollado para resolver un problema. No existe regla general de creación de algoritmos.

3. Ayudar a entender herramientas que usan algoritmos particulares.

4. Útil conocer técnicas empleadas para resolver problemas de determinados tipos.

Concepto de Eficiencia

Un algoritmo es eficiente cuando logra llegar a sus objetivos planteados utilizando la menor cantidad de recursos posibles, es decir, minimizando el uso memoria, de pasos y de esfuerzo humano.

Un algoritmo es eficaz cuando alcanza el objetivo primordial, el análisis de resolución del problema se lo realiza prioritariamente.

Puede darse el caso de que exista un algoritmo eficaz pero no eficiente, en lo posible debemos de manejar estos dos conceptos conjuntamente.

La eficiencia de un programa tiene dos ingredientes fundamentales: espacio y tiempo.

• La eficiencia en espacio es una medida de la cantidad de memoria requerida por un programa.

• La eficiencia en tiempo se mide en términos de la cantidad de tiempo de ejecución del programa.

Medidas de Eficiencia

La calidad de un algoritmo puede ser avalada utilizando varios criterios:

• Recurso Tiempo:

o Aplicaciones informáticas que trabajan “en tiempo real” requieren que los cálculos se realicen en el menor tiempo posible.

o • Aplicaciones que manejan un gran volumen de información si no se tratan adecuadamente pueden necesitar tiempos impracticables.

• Recurso Memoria:

o • Las máquinas tienen una memoria limitada.

Ejercicio en clase: para medir el tiempo de ejecución de una funcion f(x) = x^2+1/x:

#include <cstdlib>

#include <iostream>

#include <stdio.h>

#include <windows.h>

using namespace std;

double performancecounter_diff(LARGE_INTEGER *a, LARGE_INTEGER *b)

{

LARGE_INTEGER freq;

QueryPerformanceFrequency(&freq);

return (double)(a->QuadPart - b->QuadPart) / (double)freq.QuadPart;

}

long int Suma(long int);

int main(int argc, char *argv[])

{

LARGE_INTEGER t_ini, t_fin;

double secs;

int x;

float fx;

cout<<"introduce el valor de x";

cin>> x;

QueryPerformanceCounter(&t_ini);

fx=(x*x)+(1/x);

cout<<"el resultado de x es:\n\n"<<fx;

long int n = 100000;

cout << "\n\n El resultado es:" << Suma(n) ;

QueryPerformanceCounter(&t_fin);

secs = performancecounter_diff(&t_fin, &t_ini);

printf("\n %.4g milliseconds\n", secs * 1000.0);

system("PAUSE");

return EXIT_SUCCESS;

}

long int Suma(long int n){

long int S = 0;

for (long int i = 0; i<n; i++)

S +=i;

return S;

}

Introducción:

En esta práctica se medirá el tiempo de ejecución de una función. Se irá aumentando el valor de los datos.

Procesador: core 2 quad

Velocidad: 2.40Ghz x 4

Memoria RAM: 2gb

Disco duro: 200Gb

Sistema operativo: windows 7

Datos de la corrida:

Corrida no. 100 1000 2000 3000 10000 20000 30000

1 0.0008533 0.0008533 0.01749 0.02603 0.08704 0.1707 0.2598

2 0.0008533 0.0008533 0.02048 0.02603 0.08619 0.1737 0.2603

3 0.0008533 0.00896 0.01792 0.02517 0.09045 0.2637 0.2603

4 0.00128 0.00896 0.01792 0.02645 0.09003 0.1732 0.2586

5 0.00128 0.000853 0.01792 0.02603 0.08619 0.1698 0.2603

promedio: 0.00102398 0.00409592 0.018346 0.025942 0.08798 0.19022 0.25986

Conclusión: el tiempo de ejecución va a depender del valor de los datos. Y viendo los resultados de los demás compañeros he notado que varía mucho según las características de su equipo.

CONCLUSIÓN DE LA UNIDAD:

En esta unidad vimos que es un algoritmo, sus características generales, la importancia del estudio; ya que con el estudio de algoritmos podemos determinar cuál es la mejor manera para solucionar un problema utilizando la menor cantidad de recursos, la eficiencia de un algoritmo se basa en la cantidad de tiempo de tiempo de ejecución y la cantidad de memoria que lleguen a ocupar para llegar a una solución esperada. Ya existen algoritmos eficientes para la solución de algunos problemas por eso es necesario el estudio de los dichos ya que de esa manera nos evitamos el esfuerzo de realizar un algoritmo ya existente.

BIBLIOGRAFIA:

• http://es.wikipedia.org/wiki/Algoritmo

• programación en c++ 2da edición. Algoritmos, estructura de datos y objetos Luis Joyanes Aguilar.

• Manual de análisis y diseño de algoritmos. © 2003 de Instituto Nacional de Capacitación. Todos los derechos reservados. Copiapó, Chile.

UNIDAD II. “MANEJO DE MEMORIA”.

Memoria Estática

La forma más fácil de almacenar el contenido de una variable en memoria en tiempo de ejecución es en memoria estática o permanente a lo largo de toda la ejecución del programa.

No todos los objetos (variables) pueden ser almacenados estáticamente.

Para que un objeto pueda ser almacenado en memoria estática su tamaño (número de bytes necesarios para su almacenamiento) ha de ser conocido en tiempo de compilación, como consecuencia de esta condición no podrán almacenarse en memoria estática:

• Los objetos correspondientes a procedimientos o funciones recursivas, ya que en tiempo de compilación no se sabe el número de variables que serán necesarias.

• Las estructuras dinámicas de datos tales como listas, árboles, etc. ya que el número de elementos que las forman no es conocido hasta que el programa se ejecuta.

Las técnicas de asignación de memoria estática son sencillas.

A partir de una posición señalada por un puntero de referencia se aloja el objeto X, y se avanza el puntero tantos bytes como sean necesarios para almacenar el objeto X.

La asignación de memoria puede hacerse en tiempo de compilación y los objetos están vigentes desde que comienza la ejecución del programa hasta que termina.

Memoria dinámica.

La memoria dinámica es un espacio de almacenamiento que se puede solicitar en tiempo de ejecución. Además de solicitar espacios de almacenamiento, también podemos liberarlos (en tiempo de ejecución) cuando dejemos de necesitarlos.

Para realizar esta administración de la memoria dinámica, C++ cuenta con dos operadores new y delete. Antes de utilizarlos, debemos incluir el encabezado <new>.

El operador new reserva memoria dinámica de cualquier tipo, esto es:

• tipos primitivos (int, double, etc)

• tipos definidos por el usuario (clases o estructuras).

Programa, con una sencilla clase Punto, y la declaración

...