La memoria estática se reserva en el momento de compilación antes de comenzar a ejecutar su programa los objetos son creados en ese momento y destruidos al finalizar el programa.
Mantiene la misma localización de memoria durante todo el transcurso del programa.
los objetos administrados de este modo son.
-Variables static.
-Variables globales.
-Miembros static de clases
-Literales de cualquier tipo
El inconveniente de usar memoria estatica aunque es mas facil de programar
es que la cantidad de memoria se reserva siempre antes que conocer los datos dentro
del problema lo que a veces llega a reservar un maximo de memoria que en la mayoria de las veces no se va a necesitar.
Monday, September 22, 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.
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.
Monday, September 15, 2008
Unidad I -Seleccion de un Algoritmo-
1.4 Seleccion de un Algoritmo
Cuando se resuelve un problema y hay la necesidad de elegir entre varios algoritmos que nos puedan dar un resultado existen dos 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 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 ejecutara 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 desde el punto de vista económico realizar un algoritmo complejo siempre y cuando el tiempo de ejecución del programa resulte significativamente menor.
Cuando se resuelve un problema y hay la necesidad de elegir entre varios algoritmos que nos puedan dar un resultado existen dos 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 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 ejecutara 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 desde el punto de vista económico realizar un algoritmo complejo siempre y cuando el tiempo de ejecución del programa resulte significativamente menor.
Unidad I- Complejidad
1.3 Complejidad
1.3.1 Tiempo de ejecución de un algoritmo
Como se mide el tiempo de ejecución de un programa en función de N numero de datos?
Esta función se puede medir físicamente calculándola con un reloj o se puede calcular sobre el código contando las instrucciones a ejecutar y multiplicándolo por el tiempo requerido por cada instrucción.
En este ejemplo siendo t1 el tiempo que lleva ejecutar la sentencia s1 y t2 el tiempo que lleva ejecutar la sentencia s2 un numero n de veces dentro del ciclo for.
Reglas practicas para calcular la complejidad de un algoritmo
1. Sentencia sencilla: Se refiere a las sentencias de asignación entrada salida de datos , siempre y cuando no trabajen sobre estructuras cuyo tamaño esta relacionado con N. Como requieren tiempo constante de ejecución su complejidad es del orden constante (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 tomandose en cuenta el orden mas alto.
3. Decisión (if): La condición suele ser de orden constante O(1) , sumando en la peor rama posible ya sea la del then o del else.
4. Bucles (ciclos): En los ciclos con contador explicito existen dos casos que el tamaño N forme parte de los limites del ciclo o no.
b) 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:
ejemplo 1:
c=1;
while (c1)
{
S1;
C=c/2;
}
Entonces 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.
Ejemplo: función factorial (no recursiva)
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 asignación O(1)
Return fact; //sentencia salida O(1)
}
Entonces: Complejidad Lineal O(n) por el ciclo for con numero de interacciones iguales a n.
Ordenes de complejidad
O(1) Constante Ideal
O(n) Lineal Eficiente
O(log n) Logarítmico Eficiente
O(n log n) Casi Lineal Eficiente
O(n^k) Polinomial Tratable
O(K^n) Exponencial Intratables
O(n!) Factorial Intratables
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.
Ejemplo: Algoritmo de búsqueda en arboles.
Función busqueda_arboles(problema)
Devuelve solución/fallo
Inicio búsqueda de árbol con estado inicial
Ciclo hacer
Si no hay cantidades para expandir
Entonces devolver fallo
En otro caso escoger nodo para expandir.
Si el nodo es el objetivo
Entonces devolver solución
En otro caso expandir nodo
Resultados obtenidos
Depth Nodes Time Memory
0 1 1 millisecond 100 bytes
2 111 .1 seconds 11 kilobytes
4 11,111 11 seconds 1 megabytes
6 10^6 18 minutes 111 megabytes
8 10^8 31 hours 11 gigabytes
10 10^10 128 days 1 terabyte
12 10^12 35 years 111 terabytes
Notas:
Factor de ramificación 10 nodos sucesores p/cada uno como máximo
Profundidad del árbol infinita
1.3.1 Tiempo de ejecución de un algoritmo
Como se mide el tiempo de ejecución de un programa en función de N numero de datos?
Esta función se puede medir físicamente calculándola con un reloj o se puede calcular sobre el código contando las instrucciones a ejecutar y multiplicándolo por el tiempo requerido por cada instrucción.
En este ejemplo siendo t1 el tiempo que lleva ejecutar la sentencia s1 y t2 el tiempo que lleva ejecutar la sentencia s2 un numero n de veces dentro del ciclo for.
1. Sentencia sencilla: Se refiere a las sentencias de asignación entrada salida de datos , siempre y cuando no trabajen sobre estructuras cuyo tamaño esta relacionado con N. Como requieren tiempo constante de ejecución su complejidad es del orden constante (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 tomandose en cuenta el orden mas alto.
3. Decisión (if): La condición suele ser de orden constante O(1) , sumando en la peor rama posible ya sea la del then o del else.
4. Bucles (ciclos): En los ciclos con contador explicito existen dos casos que el tamaño N forme parte de los limites del ciclo o no.
b) 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:
ejemplo 1:
c=1;
while (c1)
{
S1;
C=c/2;
}
Entonces 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.
Ejemplo: función factorial (no recursiva)
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 asignación O(1)
Return fact; //sentencia salida O(1)
}
Entonces: Complejidad Lineal O(n) por el ciclo for con numero de interacciones iguales a n.
Ordenes de complejidad
O(1) Constante Ideal
O(n) Lineal Eficiente
O(log n) Logarítmico Eficiente
O(n log n) Casi Lineal Eficiente
O(n^k) Polinomial Tratable
O(K^n) Exponencial Intratables
O(n!) Factorial Intratables
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.
Ejemplo: Algoritmo de búsqueda en arboles.
Función busqueda_arboles(problema)
Devuelve solución/fallo
Inicio búsqueda de árbol con estado inicial
Ciclo hacer
Si no hay cantidades para expandir
Entonces devolver fallo
En otro caso escoger nodo para expandir.
Si el nodo es el objetivo
Entonces devolver solución
En otro caso expandir nodo
Depth Nodes Time Memory
0 1 1 millisecond 100 bytes
2 111 .1 seconds 11 kilobytes
4 11,111 11 seconds 1 megabytes
6 10^6 18 minutes 111 megabytes
8 10^8 31 hours 11 gigabytes
10 10^10 128 days 1 terabyte
12 10^12 35 years 111 terabytes
Notas:
Factor de ramificación 10 nodos sucesores p/cada uno como máximo
Profundidad del árbol infinita
Unidad I Notaciones Aritmeticas
Unidad 1
1.2 Aritmetica de la notacion “O”
Notación asintótica “O” grande:
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 limite superior del tiempo de ejecución, es decir el peor caso.
para todo 
Esto significa que la función
pertenece o es valida para 
si solo si existen las constantes C y no tales que para 
Nota: El orden de magnitud de la función será el orden del término de la función mas grande respecto de n.
Notación Omega grande:
Se dice que f(n) es omega grande de g(n) si existen las constantes positivas C y no tales que f(n)>=g(n) para todo
Para cualesquiera de las dos funciones f(n) y g(n) definidas anteriormente se tiene que
f(n) = Omega grande( g(n) ) si y sólo si g(n) = O( f(n) ).
F(n)=O si y solo si g(n)=O(f(n))
La función 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. Y se usa la notación T(n) es omega grande(g(n)) y significa que existe una constante c tal que t(n)>=c(g(n)) para un numero infinito de valores n.
1.2 Aritmetica de la notacion “O”
Notación asintótica “O” grande:
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 limite superior del tiempo de ejecución, es decir el peor caso.
Esto significa que la función
Nota: El orden de magnitud de la función será el orden del término de la función mas grande respecto de n.
Notación Omega grande:
Se dice que f(n) es omega grande de g(n) si existen las constantes positivas C y no tales que f(n)>=g(n) para todo
Para cualesquiera de las dos funciones f(n) y g(n) definidas anteriormente se tiene que
f(n) = Omega grande( g(n) ) si y sólo si g(n) = O( f(n) ).
F(n)=O si y solo si g(n)=O(f(n))
La función 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. Y se usa la notación T(n) es omega grande(g(n)) y significa que existe una constante c tal que t(n)>=c(g(n)) para un numero infinito de valores n.
Sunday, August 31, 2008
Unidad I- Analisis de Algoritmos- 08/29/08
1.1 Concepto de la complejidad de algoritmos
*Teoría de la complejidad computacional
Es la parte de la teoría de la computación que estudia los recursos necesarios durante el cálculo para resolver un problema.
Estos recursos son: el tiempo y el espacio.
*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 decisión que pueden ser resueltos en tiempo polinomico por una maquina de TURING lo que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos.
b) Clase de complejidad NP. Es el conjunto de los problemas de decisión 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 es verificable. (problema del agente viajero)
c) Clase de Complejidad NP-completo. Subconjunto de los problemas NP destacado por su complejidad, en la cual algunos de ellos en la actualidad no han encontrado una solución satisfactoria (La suma de subconjutnos dado un conjunto S de enteros ¿existe un subconjunto novacio cuyos elementos sumen 0?|| ¿Dos grafos son isomorfos si se pueden transformar uno en el otro simplemente renombrando sus vértices?)
*Diagrama de relación entre las clases de complejidad
Problemas de decisión
Pregunta:¿Las clases P y NP son diferentes o no?
El Clay Mathematics Institute ofrece 1 millon de dlls a quien sea capaz de responder satisfactoriamente a esa pregunta.
Subscribe to:
Posts (Atom)
