domingo, 4 de octubre de 2009

UNIDAD 1 ANALISIS DE ALGORITMOS


INSTITUTO TECNOLÓGICO SUPERIOR
DE LA MONTAÑA

INGENIERÍA EN SISTEMAS COMPUTACIONALES

Estructura de Datos

Facilitador: Ing. Francisco Castro Hurtado

Presenta: Armando Clemente García
Temas:
· Resumen Unidad 1
· Desarrollo de un Algoritmo



Tercer Semestre
Tlapa De Comonfort Gro, Octubre 02 - 2009



************************************************************************************






UNIDAD 1 ANÁLISIS DE ALGORITMOS.

1.1 Concepto De Complejidad De Algoritmos.
1.2. Aritmética De La Notación O.
1.3. Complejidad.
1.3.1. Tiempo De Ejecución De Un Algoritmo.
1.3.2. Complejidad En Espacio.
1.4. Selección De Un Algoritmo.

PARTE 1.

1.1 Concepto De Complejidad De Algoritmos.


Algoritmo, el conjunto de pasos para resolver un problema, mientras que complejidad significa la cantidad de recursos que se utilizan para llegar a una meta.
Un algoritmo será mas eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.

La complejidad de un algoritmo es aquella función que da el tiempo de y/o el espacio utilizado por el algoritmo en función del tamaño de la entrada.
Cada algoritmo guarda una estrecha relación con una estructura de datos. Por ello, no siempre es posible utilizar el algoritmo más eficiente, puesto que la elección de las estructuras de datos depende de varias cuestiones, incluida la de qué tipo de datos administramos y la frecuencia con que se realizan diferentes operaciones sobre ellos. Así, deberemos encontrar una situación compromiso entre tiempo y compromiso utilizados. En general, si aumentamos el espacio necesario para almacenar los datos, conseguiremos un mejor rendimiento en el tiempo y viceversa.

La eficiencia de un algoritmo puede ser cuantificada con las siguientes medidas de complejidad:
1. Complejidad Temporal o Tiempo de ejecución. Tiempo de cómputo necesario para ejecutar algún programa.
2. Complejidad Espacial. Memoria que utiliza un programa para su ejecución, La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo. Para calcular la memoria estática de un algoritmo se suma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinámica, el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo.

Este análisis se basa en las Complejidades Temporales, con este fin, para cada problema determinaremos una medida N, que llamaremos tamaño de la entrada o número de datos a procesar por el programa, intentaremos hallar respuestas en función de dicha N.

El concepto exacto que cuantifica N dependerá de la naturaleza del problema, si hablamos de un array se puede ver a N como el rango del array, para una matriz, el número de elementos que la componen; para un grafo, podría ser el número de nodos o arcos que lo arman, no se puede establecer una regla para N, pues cada problema acarrea su propia lógica y complejidad.


Aritmética De La Notación O.




El tiempo de ejecución es proporcional, esto es, multiplica por una constante a alguno de los tiempos de ejecución anteriormente propuestos, además de la suma de algunos términos más pequeños. Así, un algoritmo cuyo tiempo de ejecución sea T = 3N2 + 6N se puede considerar proporcional a N2. En este caso se diría que el algoritmo es del orden de N2, y se escribe O(N2).

Los grafos definidos por matriz de adyacencia ocupan un espacio O(N2), siendo N el número de vértices de éste.
La notación O-grande ignora los factores constantes, es decir, ignora si se hace una mejor o peor implementación del algoritmo, además de ser independiente de los datos de entrada del algoritmo. Es decir, la utilidad de aplicar esta notación a un algoritmo es encontrar un límite superior del tiempo de ejecución.

A veces ocurre que no hay que prestar demasiada atención a esto. Por ejemplo, el tiempo de ejecución del algoritmo Quick Sort es de O(N2). Sin embargo, en la práctica este caso no se da casi nunca y la mayoría de los casos son proporcionales a N•logN. Es por ello que se tiliza esta última expresión para este método de ordenación.
Una definición rigurosa de esta notación es la siguiente:
Una función g(N) pertenece a O(f(N)) si y sólo si existen las constantes c0 y N0 tales que:
g(N) <= c0•f(N) , para todo N >= N0.


1.3. Complejidad.


Un algoritmo es un conjunto finito de reglas que dan una secuencia de operaciones para resolver todos los problemas de un tipo de dato, debe cumplir con condiciones de finitud, definibilidad, entrada, salida y efectividad.

El uso de estructuras pueden hacer trivial el diseño de un algoritmo o un algoritmo muy complejo puede usar estructuras de datos muy simples.


1.3.1. Tiempo De Ejecución De Un Algoritmo.


Período transcurrido entre el inicio y la finalización del algoritmo:

- Tiempo de ejecución constante. Significa que la mayoría de las instrucciones se ejecutan una vez o muy pocas.

- logN. Tiempo de ejecución logarítmico. Se puede considerar como una gran constante. La base del logaritmo (en informática la más común es la base 2) cambia la constante, pero no demasiado. El programa es más lento cuanto más crezca N, pero es inapreciable, pues logN no se duplica hasta que N llegue a N2.

- N. Tiempo de ejecución lineal. Un caso en el que N valga 40, tardará el doble que otro en que N valga 20. Un ejemplo sería un algoritmo que lee N números enteros y devuelve la media aritmética.

- N•logN. El tiempo de ejecución es N•logN. Es común encontrarlo en algoritmos como Quick Sort y otros del estilo divide y vencerás. Si N se duplica, el tiempo de ejecución es ligeramente mayor del doble.

- N2. Tiempo de ejecución cuadrático. Suele ser habitual cuando se tratan pares de elementos de datos, como por ejemplo un bucle anidado doble. Si N se duplica, el tiempo de ejecución aumenta cuatro veces. El peor caso de entrada del algoritmo Quick Sort se ejecuta en este tiempo.

- N3. Tiempo de ejecución cúbico. Como ejemplo se puede dar el de un bucle anidado triple. Si N se duplica, el tiempo de ejecución se multiplica por ocho.

- 2N. Tiempo de ejecución exponencial. No suelen ser muy útiles en la práctica por el elevadísimo tiempo de ejecución. El problema de la mochila resuelto por un algoritmo de fuerza bruta -simple vuelta atrás- es un ejemplo. Si N se duplica, el tiempo de ejecución se eleva al cuadrado.


1.3.2. Complejidad En Espacio.


La cantidad (la medida varía según la máquina) que necesita el algoritmo para su ejecución; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo. Para calcular la memoria estática de un algoritmo se suma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinámica, el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo.






************************************************************************************



EJEMPLO COMPLEJIDAD DE TIEMPO DE EJECUCIÓN DE UN ALGORITMO

El tiempo de ejecución se mide contando el número de pasos de programa.
1. Los comentarios y las instrucciones de declaración no son pasos de programa.
2. Las expresiones y las instrucciones de asignación son un paso de programa.
· Si las expresiones contienen llamadas a funciones al número de pasos se le suma el número de pasos de la función. Si la llamada a la función tiene paso de parámetros por valor hay que tener en cuenta las asignaciones a estos parámetros. Si la función es recursiva deben considerarse también las variables locales, ya que deben ser almacenadas en la pila del sistema.
· Si las expresiones manejan tipos compuestos (por ejemplo vectores) el número de pasos depende del tamaño de los datos.

3. Las instrucciones de iteración.
· La ejecución de la parte de control cuenta como el número de pasos de la expresión que debe ser evaluada.
· El número de pasos necesarios para ejecutar el cuerpo del bucle debe multiplicarse por el número de veces que se ejecuta el bucle.


4. Instrucciones de selección. La ejecución de la parte de control cuenta como el número de pasos de la expresión que debe ser evaluada. Se consideraran las diversas alternativas al contar el número de pasos total del programa.

5. La instrucción de retorno return cuenta como el número de pasos de la expresión que debe ser evaluada.



Ejercicio:

Este Algoritmo realiza la sumatoria de los números enteros comprendidos entre el 1 y el 10, es decir,
1 + 2 + 3 +…. + 10.






Propuesta En Pseudocódigo Propuesta En Diagrama De Flujo




















ALGORITMO PROPUESTO Y DESARROLLADO EN PASCAL

Supongamos un algoritmo que lea las coordenadas de tres puntos y los mueva tres puntos en la coordenada x y escriba el resultado en algún dispositivo de salida:

ALGORITMO lee_tres_vertices
ENTRADA: las coordenadas (x,y) de tres puntos
SALIDA: las coordenadas (x,y) de los tres puntos movidos 3 puntos hacia la derecha.
VARIABLES: i:entera
x,y: real
INICIO
PARA i=1 HASTA 3 CON INCREMENTO +1
ESCRIBE "Abscisa del punto número ", i
LEER x
ESCRIBE "Ordenada del punto número ", i
LEER Y
ESCRIBE "El punto es (" x+3","y")"
FIN_PARA
FIN

El programa equivalente a este algoritmo se muestra a continuación. Como podemos apreciar en un programa en Pascal es importantísimo no olvidar detalles de sintaxis. Por ejemplo cada sentencia termina en punto y coma. De cualquier forma es inmediato apreciar los simples cambios existentes.

program lee_tres_vertices;
var x,y:real;
i:integer;
begin
for i:=1 to 3 do
begin
write ('Abscisa del punto número ',i); readln(x);
write ('Ordenada del punto número ',i); readln(y);
writeln (' El punto es (',x+3,',',y,')');
end;
end;








1 comentario: