martes, 12 de enero de 2010

UNIDAD 4 RECURSIVIDAD


4.1 Definicion Recursividad
4.2 Procedimientos Recursivos.
4.3 Mecanica Recursión.
4.4 Transformacion Algoritmos Recursivos a Iterativos
4.5 Recursividad en Diseño
4.6 Complejidad Algoritmos Recursivos

4.1 Definición Recursividad
Capacidad que tiene los métodos de invocarse así mismos, esta es una potente herramienta en la informática.
Con esta herramienta muchos algoritmos pueden simplificarse significativamente.


4.2 Procedimientos Recursivos.
La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una funcion desde la misma funcion. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición,

1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * …, incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial.
El siguiente parrafo muestra una función, expresada con palabras, que calcula un factorial.
“Si el número es menor que cero, se rechaza. Si no es un entero, se redondea al siguiente entero. Si el número es cero, su factorial es uno. Si el número es mayor que cero, se multiplica por él factorial del número menor inmediato.”
Para calcular el factorial de cualquier número mayor que cero hay que calcular como mínimo el factorial de otro número. La función que se utiliza es la función en la que se encuentra en estos momentos, esta función debe llamarse a sí misma para el número menor inmediato, para poder ejecutarse en el número actual. Esto es un ejemplo de recursividad.
La recursividad es un concepto importante en informatica. Muchos algoritmos se pueden describir mejor en terminos de recursividad.

Supongamos que P es un procedimiento que contiene una sentencia de Llamada a si mismo o una sentencia de Llamada a un segundo procedimiento que puede eventualmente llamar de vuelta al procedimiento original P. Entonces P se dice que es u procedimiento recursivo. Como el progrma no ha de continuar ejecutandose indefinidamente, un procedimiento recursivo ha de tener las dos siguientes propiedades:
(1) Debe existir un cierto criterio, llamado criterio base, por el que el procedimiento no se llama asi mismo.
(2) Cada vez que el procedimiento se llame a si mismo(directa o inderectamente), debe estar mas cerca del criterio base.
Un procedimiento recursivo con estas dos propiedades se dice que esta bien definido.
Similarmente, una funcion se dice que esta definida recursivamente si la definicion de la funcion se refiere a si misma. De nuevo, para que la definicion no sea circular, debe tener las dos siguientes propiedades:
(1) Debe haber ciertos argumentos, llamados valores base, para los que la funcion no se refiera a si misma.
(2) Cada vez que la funcion se refiera a si misma, el argumento de la funcion debe acercarse mas al valor base.
Una funcion recursiva con estas dos propiedades se dice tambien que esta bien definida.
Tipos.
Podemos distinguir dos tipos de recursividad:
Directa: Cuando un subprograma se llama a si mismo una o mas veces directamente. Indirecta: Cuando se definen una serie de subprogramas usándose unos a otros.
Características.
Un algoritmo recursivo consta de una parte recursiva, otra iterativa o no recursiva y un acondición de terminación. La parte recursiva y la condición de terminación siempre existen. En cambio la parte no recursiva puede coincidir con la condición de terminación. Algo muy importante a tener en cuenta cuando usemos la recursividad es que es necesario asegurarnos que llega un momento en que no hacemos más llamadas recursivas. Si no se cumple esta condición el programa no parará nunca.
Ventajas e inconvenientes. La principal ventaja es la simplicidad de comprensión y su gran potencia, favoreciendo la resolución de problemas de manera natural, sencilla y elegante; y facilidad para comprobar y convencerse de que la solución del problema es correcta. El principal inconveniente es la ineficiencia tanto en tiempo como en memoria, dado que para permitir su uso es necesario transformar el programa recursivo en otro iterativo, que utiliza bucles y pilas para almacenar las variables.


4.3 Mecánica Recursión.

La mecánica de la recursividad está basada en una “pila”. Cuando un módulo recursivo se está ejecutando se crea en la memoria de la computadora una pila donde se almacenan los valores de los parámetros y de las variables locales del módulo. Si el módulo es función también se guarda en la pila el valor que adquiere la misma.
Para cada llamada del módulo se almacenan en la pila los nuevos valores de los parámetros y de las variables locales, creándose un nuevo “registro de activación”. De tal forma que, la pila de recursión está formada por registros de activación. Al terminar una llamada al módulo, es decir, cuando se cumple la definición base, se libera (sale) el registro de activación que se encuentra en el tope de la pila. De esta forma es como puede “recordar” qué valores tenían los parámetros y las variables locales en la llamada anterior.
Si observamos el proceso que seguimos para calcular 4! vemos que el valor de n fue cambiando conforme fuimos entrando en recursión y que al salir de recursión necesitábamos recordar el valor que tenía n en la expresión anterior. Esto quiere decir que los valores que fue adquiriendo n fueron entrando a la pila.
No sólo debe recordar los valores que tenían los parámetros y las variables locales al realizarse la correspondiente llamada al módulo sino que también tiene que recordar qué instrucción debe realizar al terminar esa llamada. De tal forma que los registros de activación están compuestos básicamente de:

1. Instrucción a la que debe regresar el control una vez terminada la ejecución actual del módulo.
2. Todos los parámetros y variables locales del módulo.
3. Si el módulo recursivo es una función el valor que adquiere la misma, ya que éste se debe regresar.
Para hacer la representación de la pila de recursión numeramos las instrucciones a las que debe regresar el control una vez terminada la ejecución del módulo recursivo y estos valores son los que ponemos en la pila.

4.4 Transformación Algoritmos Recursivos a Iterativos
El concepto de recursividad va ligado al de repetición. Son recursivos aquellos algoritmos que, estando encapsulados dentro de una función, son llamados desde ella misma una y otra vez, en contraposición a los algoritmos iterativos, que hacen uso de ciclos while, do-while, for, etc.
Algo es recursivo si se define en términos de sí mismo (cuando para definirse hace mención a sí mismo). Para que una definición recursiva sea válida, la referencia a sí misma debe ser relativamente más sencilla que el caso considerado.
Ejemplo: definición de nº natural:
→ el N º 0 es natural
→ El Nº n es natural si n-1 lo es.
En un algoritmo recursivo distinguimos como mínimo 2 partes:
a). Caso trivial, base o de fin de recursión:

Es un caso donde el problema puede resolverse sin tener que hacer uso de una nueva llamada a sí mismo. Evita la continuación indefinida de las partes recursivas.
b). Parte puramente recursiva:
Relaciona el resultado del algoritmo con resultados de casos más simples. Se hacen nuevas llamadas a la función, pero están más próximas al caso base.
4.5 Recursividad en Diseño
Un procedimiento recursivo es aquel que se llama a si mismo, para poder funcionar tiene que tener una condición de salida que de el numero de veces que se va a llamar a si mismo el procedimiento.
La recursividad en diseño se refiere a la manera de cómo representar los procedimientos recursivos al momento de diseñar los programas.
Dependiendo del método que utilicemos para diseñar la representación grafica de la recursividad va a ser diferente sin embargo el procedimiento va a ser similar ya que el fin es el mismo poner una condición que nos diga si llamamos al método o que nos mande terminarlo.
En un diagrama seria algo así:


4.6 Complejidad Algoritmos Recursivos
Un algoritmo recursivo es un algoritmo que se define en términos de sí mismo. Son implementados en forma de subprogramas (funciones, subrutinas, procedimientos, etc) de tal forma que dentro de un subprograma recursivo hay una o más llamadas a él mismo.
FUNCIÓN Factorial(n)
INICIO
SI (n<2) factorial =" 1;" factorial =" n">

Bibliografía

Consulta a libros:

Autores:·

Alfred V. Aho·

John E. Hopcroft·

Jefrey D. Ullman

Libro:

Estructura De Datos Y Algoritmos

Editorial: Addison-Wesley Iberoamericana

Edición: Revisada

REFERENCIAS DE INTERNET

http://arco.esi.uclm.es/~david.villa/pensar_en_C++/products/vol1/ch03s02s09.html

http://www.programacionfacil.com/estructura_de_datos/recursividad

http://www.programacionfacil.com/estructura_datos_csharp/procedimientos_recursivos

http://www.programacionfacil.com/estructura_datos_csharp/procedimientos_recursivos

http://cursos.itam.mx/akuri/2006/Algor%EDtmica/recur1.pdf

http://www.programacionfacil.com/estructura_datos_csharp/recursividad_en_diseno

FECHA DE CONSULTA 05 DE ENERO DEL 2010

UNIDAD 3 ESTRUCTURAS LINEALES ESTÁTICAS Y DINÁMICAS


3.1 Estructura Datos Pilas
3.2 Estructura Datos Colas
3.3 Listas Enlazadas
3.3.1 Lista Enlazada Simples
3.3.2 Lista Enlazada Dobles

3.1 Estructura Datos Pilas
Una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos en uno de los extremos de la lista. Estas operaciones se conocen como "push" y "pop", respectivamente "empujar" y "tirar". Además, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
Estas características implican un comportamiento de lista LIFO (Last In First Out), el último en entrar es el primero en salir.
El ejemplo del que deriva el nombre de la estructura es una pila de platos. Sólo es posible añadir platos en la parte superior de la pila, y sólo pueden tomarse del mismo extremo.
El nodo típico para construir pilas es:

struct nodo {
int dato;
struct nodo *siguiente;
};


Los tipos que definiremos normalmente para manejar pilas serán casi los mismos que para manejar listas, tan sólo cambiaremos algunos nombres:

typedef struct _nodo {
int dato;
struct _nodo *siguiente;}
tipoNodo; typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;

tipoNodo es el tipo para declarar nodos, evidentemente.
· pNodo es el tipo para declarar punteros a un nodo.
· Pila es el tipo para declarar pilas.


3.2 Estructura Datos Colas
Una cola es un tipo especial de lista abierta en la que sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
Este tipo de lista es conocido como lista FIFO (First In First Out), el primero en entrar es el primero en salir.
El ejemplo cotidiano es una cola para comprar, por ejemplo, las entradas del cine. Los nuevos compradores sólo pueden colocarse al final de la cola, y sólo el primero de la cola puede comprar la entrada


3.3 Listas Enlazadas
La lista enlazada que nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener.
En una lista enlazada, cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es null. Por ello los elementos son registros que contienen el dato a almacenar y un enlace al siguiente elemento. Los elementos de una lista, suelen recibir también el nombre de nodos de la lista.
Las operaciones que podemos realizar sobre una lista enlazada son las siguientes:
Recorrido. Esta operación consiste en visitar cada uno de los nodos que forman la lista. Para recorrer todos los nodos de la lista, se comienza con el primero, se toma el valor del campo liga para avanzar al segundo nodo, el campo liga de este nodo nos dará la dirección del tercer nodo, y así sucesivamente.
Inserción. Esta operación consiste en agregar un nuevo nodo a la lista. Para esta operación se pueden considerar tres casos:

Insertar un nodo al inicio.
Insertar un nodo antes o después de cierto nodo.
Insertar un nodo al final.
Borrado. La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos:
Eliminar el primer nodo.
Eliminar el último nodo.
Eliminar un nodo con cierta información.
Eliminar el nodo anterior o posterior al nodo cierta con información.
Búsqueda. Esta operación consiste en visitar cada uno de los nodos, tomando al campo liga como puntero al siguiente nodo a visitar

3.3.2 Listas enlazadas Simples
Una lista de enlace simple es una lista enlazada de nodos, donde cada nodo tiene un único campo de enlace. Una variable de referencia contiene una referencia al primer nodo, cada nodo (excepto el último) enlaza con el nodo siguiente, y el enlace del último nodo contiene null para indicar el final de la lista. Aunque normalmente a la variable de referencia se la suele llamar top, usted puede elegir el nombre que quiera. La siguiente figura presenta una lista de enlace simple de tres nodos, donde top referencia al nodo A, A conecta con B y B conecta con C y C es el nodo final:



Un algoritmo común de las listas de enlace simple es la inserción de nodos. Este algoritmo está implicado de alguna forma porue tiene mucho que ver con cuatro casos: cuando el nodo se debe insertar antes del primer nodo; cuando el nodo se debe insertar después del último nodo; cuando el nodo se debe insertar entre dos nodos; y cuando la lista de enlace simple no existe



3.3.2 Lista Enlazada Dobles
Una lista doble, ó doblemente ligada es una colección de nodos en la cual cada nodo tiene dos punteros, uno de ellos apuntando a su predecesor (li) y otro a su sucesor(ld). Por medio de estos punteros se podrá avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro puntero.
La estructura de un nodo en una lista doble es la siguiente:
Existen dos tipos de listas doblemente ligadas:
Listas dobles lineales. En este tipo de lista doble, tanto el puntero izquierdo del primer nodo como el derecho del último nodo apuntan a NIL.

Listas dobles circulares. En este tipo de lista doble, el puntero izquierdo del primer nodo apunta al último nodo de la lista, y el puntero derecho del último nodo apunta al primer nodo de la lista.
Debido a que las listas dobles circulares son más eficientes, los algoritmos que en esta sección se traten serán sobre listas dobles circulares.
En la figura siguiente se muestra un ejemplo de una lista doblemente ligada lineal que almacena números:

En la figura siguiente se muestra un ejemplo de una lista doblemente ligada circular que almacena números:


BIBLIOGRAFIA

Consulta a libros:

Autores:

· Alfred V. Aho· John E. Hopcroft· Jefrey D. Ullman

Libro: Estructura De Datos Y Algoritmos

Editorial: Addison-Wesley IberoamericanaEdición: Revisada

Referencias de internet

http://c.conclase.net/edd/index.php

http://www.calcifer.org/documentos/librognome/glib-lists-queues.html

http://sistemas.itlp.edu.mx/tutoriales/estru1/42.htm

fecha de Consulta 05 de enero del 2010

UNIDAD 2 MANEJO DE MEMORIA






  • 2.1 Manejo de Memoria Estática
    2.2 Manejo De Memoria Dinámica


    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.
    En los lenguajes que permiten la existencia de subprogramas, y siempre que todos los objetos de estos subprogramas puedan almacenarse estáticamente se aloja en la memoria estática un registro de activación correspondiente a cada uno de los subprogramas.
    Estos registros de activación contendrán las variables locales, parámetros formales y valor devuelto por la función.


  • Dentro de cada registro de activación las variables locales se organizan secuencialmente. Existe un solo registro de activación para cada procedimiento y por tanto no están permitidas las llamadas recursivas. El proceso que se sigue cuando un procedimiento p llama a otro q es el siguiente:


1. p evalúa los parámetros de llamada, en caso de que se trate de expresiones complejas, usando para ello una zona de memoria temporal para el almacenamiento intermedio. Por ejemplos, sí la llamada a q es q((3*5)+(2*2),7) las operaciones previas a la llamada propiamente dicha en código máquina han de realizarse sobre alguna zona de memoria temporal. (En algún momento debe haber una zona de memoria que contenga el valor intermedio 15, y el valor intermedio 4 para sumarlos a continuación). En caso de utilización de memoria estática ésta zona de temporales puede ser común a todo el programa, ya que su tamaño puede deducirse en tiempo de compilación.
2. q inicializa sus variables y comienza su ejecución.
Dado que las variables están permanentemente en memoria es fácil implementar la propiedad de que conserven o no su contenido para cada nueva llamada




Memoria Dinámica
¿Qué es la memoria dinámica?
Supongamos que nuestro programa debe manipular estructuras de datos de longitud desconocida. Un ejemplo simple podría ser el de un programa que lee las líneas de un archivo y las ordena. Por tanto, deberemos leer un número indeterminado de líneas, y tras leer la última, ordenarlas. Una manera de manejar ese ``número indeterminado'', sería declarar una constante MAX_LINEAS, darle un valor vergonzosamente grande, y declarar un array de tamaño MAX_LINEAS. Esto, obviamente, es muy ineficiente (y feo). Nuestro programa no sólo quedaría limitado por ese valor máximo, sino que además gastaría esa enorme cantidad de memoria para procesar hasta el más pequeño de los ficheros.
La solución consiste en utilizar memoria dinámica. La memoria dinámica es un espacio de almacenamiento que se solicita en tiempo de ejecución. De esa manera, a medida que el proceso va necesitando espacio para más líneas, va solicitando más memoria al sistema operativo para guardarlas. El medio para manejar la memoria que otorga el sistema operativo, es el puntero, puesto que no podemos saber en tiempo de compilación dónde nos dará huecos el sistema operativo (en la memoria de nuestro PC).




Memoria Dinámica.
La memoria dinámica sirve para que los programas se adapten siempre al tamaño del problema que tienen que resolver, sin desperdiciar recursos de memoria. Esto se traduce asimismo en una mayor eficiencia en la ejecución de los programas. 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.
Sobre el tratamiento de memoria, GLib dispone de una serie de instrucciones que sustituyen a las ya conocidas por todos malloc, free, etc. y, siguiendo con el modo de llamar a las funciones en GLib, las funciones que sustituyen a las ya mencionadas son g_malloc y g_free.
Reserva de memoria.



La función g_malloc posibilita la reserva de una zona de memoria, con un número de bytes que le pasemos como parámetro. Además, también existe una función similar llamada g_malloc0 que, no sólo reserva una zona de memoria, sino que, además, llena esa zona de memoria con ceros, lo cual nos puede beneficiar si se necesita un zona de memoria totalmente limpia.
gpointer g_malloc (gulong numero_de_bytes );
gpointer g_malloc0 (gulong numero_de_bytes );
Existe otro conjunto de funciones que nos permiten reservar memoria de una forma parecida a cómo se hace en los lenguajes orientados a objetos.




Liberación de memoria.
Cuando se hace una reserva de memoria con g_malloc y, en un momento dado, el uso de esa memoria no tiene sentido, es el momento de liberar esa memoria. Y el sustituto de free es g_free que, básicamente, funciona igual que la anteriormente mencionada.
void g_free (gpointer memoria_reservada );



Realojamiento de memoria



En determinadas ocasiones, sobre todo cuando se utilizan estructuras de datos dinámicas, es necesario ajustar el tamaño de una zona de memoria (ya sea para hacerla más grande o más pequeña). Para eso, GLib ofrece la función g_realloc, que recibe un puntero a memoria que apunta a una región que es la que será acomodada al nuevo tamaño y devuelve el puntero a la nueva zona de memoria. El anterior puntero es liberado y no se debería utilizar más:
gpointer g_realloc (gpointer memoria_reservada , gulong numero_de_bytes );



Asignación dinámica
El proceso de compactación del punto anterior es una instancia particular del problema de asignación de memoria dinámica, el cual es el cómo satisfacer una necesidad de tamaño n con una lista de huecos libres. Existen muchas soluciones para el problema. El conjunto de huecos es analizado para determinar cuál hueco es el más indicado para asignarse. Las estrategias más comunes para asignar algún hueco de la tabla son:



Primer ajuste: Consiste en asignar el primer hueco con capacidad suficiente. La búsqueda puede iniciar ya sea al inicio o al final del conjunto de huecos o en donde terminó la última búsqueda. La búsqueda termina al encontrar un hueco lo suficientemente grande.



Mejor ajuste: Busca asignar el espacio más pequeño de los espacios con capacidad suficiente. La búsqueda se debe de realizar en toda la tabla, a menos que la tabla esté ordenada por tamaño. Esta estrategia produce el menor desperdicio de memoria posible.



Peor ajuste: Asigna el hueco más grande. Una vez más, se debe de buscar en toda la tabla de huecos a menos que esté organizada por tamaño. Esta estrategia produce los huecos de sobra



más grandes, los cuales pudieran ser de más uso si llegan procesos de tamaño mediano que quepan en ellos.
Se ha demostrado mediante simulacros que tanto el primer y el mejor ajuste son mejores que el peor ajuste en cuanto a minimizar tanto el tiempo del almacenamiento. Ni el primer o el mejor ajuste es claramente el mejor en términos de uso de espacio, pero por lo general el primer ajuste es más rápido.



Bibliografía




Pagina de Internet
· ProgramacionFacil
· http://www.programacionfacil.com/estructura_de_datos/manejo_de_memoria
· Fecha de Consulta: lunes 04 del 2010



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;