lunes, 22 de septiembre de 2008

2.1.2- Manejo de Memoria Dinámica

*Memoria Dinámica:
Las reservas de mamoria dinámica se hacen tiempo de ejecucion despues de leer los datos y de conocer el tamaño eacto del problema a resolver, como consecuancia se adapta mejor a las necesidades de cada caso pero en contrapartida es un poco mas dificil de programar.
Tanto la creación como destruccion de los objetos està en manos del programador a traves de los operadores "new" y "delette", el sitio donde se almacenan los objetos, suelen llamarse heap ò free store, traducido como montículo o memoria libre.
En c# no es necesario considerar la liberaciòn de la memoria dinamica puesto que FrameWork se encarga de liberar todas las referencias que no se esten utilizando y compactar la memoria para mejorar el rendimiento.

En C# todas las clases son tratadas sintacticamente como referencias y no permite elegir como reservar memoria para una instancia en particular, en cambio obliga a que un int sea un tipo valor.

class Program
{
void imprime_binario(int n)
{
if (n>=2)
{

imprime_binario(n/2);

Console.Write("{0}",n%2);

}
else
Console.Write("{0}",n);
}
static void Main (string []args)
{
Console.Write("Alimenta un Número Entero: ");

int numero=Int32.Parse(Console.ReadLine());

Program p=new Program();
Console.Write("\n\tNumero Entero {0} en Código Binario: ", numero); p.imprime_binario(numero);
Console.Write("\n\n\t\tDesea hacer otra Operación S/N: ");

op = char.Parse(Console.ReadLine());

}
while (op == 's' || op == 'S');
}
}

domingo, 21 de septiembre de 2008

Unidad II.- Manejo de Memoria

Toma arreglos y objetos en general, tiene una duracion determinada en el transcurso de un programa y son creados y destruidos, para su uso despues para que la memoria sea liberada, para que la utilicen otros objetos.

En C# existen 3 formas de usar la memoria para almacenar valores son:
a) Memoria Estatica
Es la utilizada por variables globales y las declaradas de tipo static. Estos objetos tienen asignada la misma direccion de memoria desde el comienzo hasta el final del programa.

b) Memoria Automatica
Es la utilizada por argumentos en una funcion y por las variables locales. Cada entrada en la funcion crea estos objetos y son destruidos al salir de ella.

c) Memoria dinamica
Es tambien llamado almacenamiento libre porque en estos casos el programador es el que solicita memoria para crear los objetos y es el responsable de liberar la memoria cuando ya no la necesita para
ser reutilizada.

La reserva y liberacion para variables globales, estaticas, locales y argumentos son realizadas en forma implicita por el programa, la unica que requiere intervencion del programador es la reserva y liberacion de memoria dinamica.

sábado, 20 de septiembre de 2008

2.1.1.- Manejo de Memoria Estática

La memoria estatica es la que se reserva en el momento de la compilacion ates de comenzar a ejecutarse el programa. Los objetos son creados en ese momento y destruidos al finalizar el programa. Mantienen la mismalocalizacion en memoria durante todo el transcurso del programa.
Los objetos administrados de este modo son:
  • Varialbes Estáticas
  • Varialbes Globales
  • Miembros státic de clases
  • Literales de cualquier tipo

Ejemplo1:
class CSimple1 //(PROGRAMA 13)
{
static void Main(string[]args)
{
int []Numeros=new int[]{1,2,3,4,5};
for (int i=0;i<5;i++)
console.Write("{0}",Numeros[i]);
}
}

Ejemplo2:
class CSimple2
{
static int Funcion(int p, int q)
{
return(p+q);
}
static void Main (string[]args)
{
int Resultado=Funcion(7,2);
Console.WriteLine(Resultado);
}
}


En el ejemplo 1 se muestra la declaracion estatica de un arreglo y la declaracion de la variable global de control dentro del for.
En el ejemplo 2 se muestra la declaracion estatica en una funcion la cual es ejecutada al enviarle 2 parametros que son literales numericas.

En resumen el inconveniente de utilizar memoria estatica aunque es mas facil de programar es que la cantidad de memoria se reserva siempre antes de conocer los datos completos del problema lo que aveces lleva a reservar un maximo de memoria que en la mayoria de las veces no se va a necesitar.

lunes, 15 de septiembre de 2008

1.4- Selección de un Algoritmo

Cuando se resuelve un problema y hay la necesidad de elegir entre varios algoritmos que nos puedan dar un resultado existen 2 objetivos que suelen contradecirse para elegir uno:
a) Que el algoritmo sea fácil de entender, codificar y depurar.

b) Que el algoritmo use eficientemente los recursos de la computadora y se ejecute con la mayor rapidez posible.

El primer punto (a) se debe elegir cuando se escribe un programa que se va a utilizar una o pocas veces ya que el costo del tiempo de programación no será tan relevante ya que solo se utilizara en pocas ocasiones.
El punto b es más importante cuando se presenta un problema cuya solución se va a utilizar muchas veces ya que el costo de ejecución del programa minimizara al costo de escritura.

En conclusión: Siempre será más ventajoso del punto de vista económico realizar un algoritmo complejo siempre y cuando el tiempo de ejecución del programa resulte significativamente menor.

1.3.2.- Complejidad en el Espacio

Complejidad espacial.- Es la memoria que utiliza un programa para su ejecución. Lo que implica que la eficiencia en memoria de un algoritmo lo indica la cantidad de espacio requerido para ejecutarlo es decir, el espacio en memoria que ocupan todas las variables propias del algoritmo.
Ej. Algoritmo de búsqueda en árboles.

Función búsqueda_arboles(problema)
devuelve solución/fallo
inicializa árbol de búsqueda con estado inicial
ciclo hacer
si no hay cantidades para expandir
entonces devolver “fallo”
en otro caso escoge r nodo para expandir
si el nodo es el objetivo
entonces devolver solución
en otro caso expandir nodo

=Resultados Obtenidos=


NOTAS: factor de ramificación --> 10 nodos sucesores p/cada uno como máximo profundidad del árbol

1.4.- Selección de un Algoritmo
Tarea: Como seleccionar un buen Algoritmo?

1.3 Complejidad

1.3.1 Tiempo de Ejecucion de un Algoritmo.
Como se mide el tiempo de ejecucion de un programa en funcion de N (numero de datos)?
Esta funcion se puede medir fisicamente calculandolo con un reloj o se puede calcular sobre el codigo, contando las instrucciones a ejecutar y multiplicandolo por el tiempo requerido por cada instruccion.

Ejemplo:
Sentencia 1

. Sentencia 2
. entonces
. . T(N)=t1+t2*N
En este ejemplo, siendo t1 el tiempo que lleve ejecutar la sentencia S1 y t2 el tiempo que lleve ejecutar la sentencia S2 un numero de n veces dentro del ciclo "for".

=Reglas Prácticas para calcular la complejidad de un algoritmo=
1.- Sentencia Sencilla: Se refiere a las sentencias de asignación, entrada o salida de datos siempre y cuando no trabajen sobre estructuras cuyo tamaño está relacionado con N(número de datos). Como requiere un tiempo constante de ejecución su complejidad es el orden O(1)
2.-Secuencia de Sentencias: Su complejidad esta dada por la suma de las complejidades individuales de acuerdo al tipo de sentencias que se trate tomándose en cuenta el orden mas alto.
3.-Sentencia de Decisión (if): La condición suele ser de orden constante, osea O(1), sumando en la peor rama posible ya sea la del THEN o la de ELSE.
4.-Bucles (Ciclos): en los ciclos con contador explicito existen 2 casos y el tamaño N forme parte de los límites del ciclo o no.
4a) Contador Explicito
Caso 1 For (int i=0;
;i++)
{S1;}
Entonces K*O(1)=O(1) Constante
Caso 2 For (int i=0;;i++)
{S1;}
Entonces N*O(1)=O(n) Lineal

4b) Evolución de Variable de Control No Lineal (WHILE): En los ciclos multiplicativos como el WHILE y el DO WHILE el incremento o decremento de la variable de control no es lineal lo que hace incrementar el orden de complejidad como en los ejemplos siguientes:
Ej. c=1;//Incremento
While (c1)
{
S1;
c=c/a
}
Complejidad Logarítmica O(log n)

5.- Llamadas a Procedimientos: La complejidad de llamar a un procedimiento esta dada por la complejidad del contenido del procedimiento en si, es decir, su complejidad depende del tipo de instrucciones o sentencias que existan en el cuerpo del procedimiento. En conclusión la complejidad de un procedimiento tiende a complicarse si se trata de procedimientos recursivos.
NOTA: Procedimiento Recursivo: el que se manda llamar a si mismo un a y otra ves.
Ej. Función Factorial (no recursiva) Programa 9
Int factorial (int n) //sentencia entrada O(1)
{
Int fact=1; //sentencia asignación O(1)
For (int i=n;i>0;i--) //ciclo contador explicito O(n)
Fact=fact*I; //sentencia asignacion O(1)
Return fact; //sentencia salida O(1)
}
Entonces: Complejidad Lineal O(n) por el ciclo for con numero de iteraciones igual a n

ORDENES DE COMPLEJIDAD
O(1) Constante Ideal
O(n) Lineal Eficiente
O(log n) Logaritmico Eficiente
O(n log n) Casi Lineal Eficiente
O(n^k) Polinomial Tratable
O(k^n) Exponencial Intratables
O(n!) Factorial Intratables

domingo, 14 de septiembre de 2008

Notación Asintótica "Omega" Grande

Fórmula.-
Una funcion g(n) pertenece a O{f(n)} si y solo si existen las variables tales que g(n)<=f(n)
*La funció Omega Grande se utiliza para especificar una cota inferior para la velocidad de crecimiento de una función f(n) cuando esta en función de n se usa la notación que se lee: T(n) es omega "símbolo" (g(n)) y significa que existe una constante c tal que t(n)>=c(g(n)) para un número infinito de valores de n.

Ejemplo 1: Programa 6
Verificar la función
Ejemplo 2: Programa 7
Verificar la función
Ejemplo 3: Programa 8
Verificar la función

1.1 Concepto de Complejidad de Algorítmos

TEORIA DE LA COMPLEJIDAD COMPUTACIONAL.- Es la parte de la teoría de la omputación que estudia los recursos necesarios durante el cálculo para resolver un problema.

=Clases de Complejidad=
Los problemas de decisión (aquellos donde la respuesta posible es "si" o "no") se clasifican en conjuntos de complejidad comparable que son llamados clases de complejidad.

a)Clase de complejidad P: Es el conjunto de los problemas de decision que pueden ser resultos en timepo polinomico por una maquina de turing, lo que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos.
Ejemplos:
*Camino Optimo de un cartero
*Saber si un numero entero es primo. Programa 1
*Decidir si una grace pertenece a un conjunto dado de fraces.

a)Clase de complejidad NP:
Es el conjunto de los problemas de decision que pueden ser resueltos por una maquina de Turing no determinista en tiempo polinomico. Los problemas de esta clase tienen la propiedad de que su solución puede ser cerificada
Ejemplos:
*El problema del Agente Viajero. Programa 2
*El problema de Satisfactibliidad Boolenana.
a)Clase de complejidad NP: Es el subconjunto de los problemas de decision NP que se destacan por su complejidad en la cual algunos de ellos en la actualidad no han encontrado una solucion satisfactoria.
Ejemplos:
*La suma de subconjuntos dado un "S" de enteros, Existe un conjunto no vacío cuyos elementos sumen 0?
*2 grafos son isomorfos si se puede transformar uno en el otro simplemente renombrando sus vértices?

=Diagrama de la Relación entre las clases de Complejidad=
Problemas de Decisión:

Pregunta: Las clases P y NP son diferentes o No?

El Clay Matematics Institute ofrece $1,000,000 de dlls a quien sea capaz de responder satisfactoriamente a esta pregunta.

1.2 Arítmetica de la notación O

Notación Asintótica O:
Se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una función.
la utilidad de aplicar esta notación a un algoritmo es encontrar el límite superior del tiempo de ejecucion, es decir el peor caso.

Definición: lg(n)|<=|c.f(n)1 para todo n>=n
Esto significa que la función g(n) pertenece o es válida para f(n) si y solo si existen las constantes c y n=0, tales que para n>=, T(n)>=cn. El órden de magnitud de la función sera el órden de términos de la función mas grande respecto de n. Supóngase que:
ejemplo 1:

Realizar operación en un programa ejecutable (consola o visual):
Programa 3:
Programa 4:
Programa 5:
TAREA:
Notación Asintótica Omega Grande:
-Función?
-Fórmula?
-Ejemplos?