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) ;

...