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
Ejemplos:
class csimple
{
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]);
}
}
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 dentro del for.
En el ejemplo 2 se muestra declaracion estatica de una funcion la cuela es ejecutada
al enviarle dos parametros que son literales numericas.
En resumen, 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.
sábado, 20 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.
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.
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 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 se debe elegir cuando se escribe un programa que se va utilizar una o pocas veces ya que el costo del tiempo
de programacion no sera tan relevante ya que solo se ejecutara en pocas ecuaciones.
El punto b es mas importante cuando se presenta un problema cuya solución se va a utilizar muchas veces ya que el consto de ejecución de un programa
minimizara al costo de escritura.
En conclusión, siempre sera mas ventajoso del punto de vista económico realizar un algoritmo complejo siempre y cuando
el tiempo de ejecucion del programa resulte significativamente menor.
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 utilizar una o pocas veces ya que el costo del tiempo
de programacion no sera tan relevante ya que solo se ejecutara en pocas ecuaciones.
El punto b es mas importante cuando se presenta un problema cuya solución se va a utilizar muchas veces ya que el consto de ejecución de un programa
minimizara al costo de escritura.
En conclusión, siempre sera mas ventajoso del punto de vista económico realizar un algoritmo complejo siempre y cuando
el tiempo de ejecucion del programa resulte significativamente menor.
1.3.2 - Complejidad en el espacio
Complejidad Espacial:
Es la memoria que utiliza un programa para su ejecucion lo que implica que la eficiencia
en memoria de un algoritmo lo indica la cantidad de espacios requeridos para ejecutarlo es decir
el espacio de memoria que ocupa todas las variables propias del algoritmo.
Ejemplo:
Algoritmo de busqueda en arboles.
funcion busqueda_arbol(problema)
devuelve solucion/fallo
inicializa arbol de busqueda con estado inicial
ciclo hacer
si no hay candidatos para expandir
entonces devolver fallo
en otro caso escoger nodo para expandir
si el nodo es el objetivo
entonces devolver solucion
en otro casi expandir nodo
Resultados Obtenidos
Depth Nodes Time(tiempo) Memory(espacio)
0 1 1 millisecond 100 bytes
2 111 .1 seconds 11 kylobytes
4 11111 11 seconds 1 megabyte
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
Es la memoria que utiliza un programa para su ejecucion lo que implica que la eficiencia
en memoria de un algoritmo lo indica la cantidad de espacios requeridos para ejecutarlo es decir
el espacio de memoria que ocupa todas las variables propias del algoritmo.
Ejemplo:
Algoritmo de busqueda en arboles.
funcion busqueda_arbol(problema)
devuelve solucion/fallo
inicializa arbol de busqueda con estado inicial
ciclo hacer
si no hay candidatos para expandir
entonces devolver fallo
en otro caso escoger nodo para expandir
si el nodo es el objetivo
entonces devolver solucion
en otro casi expandir nodo
Resultados Obtenidos
Depth Nodes Time(tiempo) Memory(espacio)
0 1 1 millisecond 100 bytes
2 111 .1 seconds 11 kylobytes
4 11111 11 seconds 1 megabyte
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
1.3 Complejidad.- Tiempo de ejecucion de un algoritmo
1.3.1 - Tiempo de ejecución de un algoritmo
Como se mide el tiempo de ejecución de un programa en funcion de N (numero de datos)?
Esta función se puede medir físicamente calculando con un reloj o se puede calcular sobre el código contando las instrucciones ejecutadas a ejecutar y multiplicándolo por el tiempo requerido
por cada instrucción.
Ejemplo:
S1;
for(int i=0;i
S2;
entonces: T(n) = t1 + t2 * N
En este ejemplo siendo T1 el tiempo que lleve ejecutar la sentencia de S1 y t2 el tiempo que lleve ejectuar la 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 la sentencia de asignacion ,entrada o salida de datos siempre y cuando no trabajen sobre estructuras cuyo tamaño esta relacionado con N que es el numero de datos.
Como requiere un tiempo constante de ejecucion 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 tomandose en cuenta el orden mas alto
3.- Decision (if):
La condicion puede ser de orden constante o uno, sumando en la peor rama posible ya sea la del then o del else.
4.- Bucles(ciclos):
En los ciclos con contador explicito existen 2 casos: el tamaño N forma parte de los limites del ciclo o no.
Ejemplos:
caso 1: for(int i=0;i
{S1;}
entonces k*0(1)= 0(1) Constante
caso 2: for(int i=0;i
{S1;}
entonces N*O(1) = 0(n) Linear
b) Evolucion de variable de control No lineal (while)
En los ciclos multiplicativos como el while y 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
while (c
{
S1;
c=2*c;
entonces complejidad 0(log n)
logaritmica
Ej.
c=n;
while (c
{
S1;
c=c/2;
}
Complejidad Logaritmica 0(log n)
5.- Llamadas a Procedimientos:
La complejidad de llamar a un procedimiento esta dada por la complejidad del procedimiento en si
es decir, su complejidad depende del tipo de instrucciones o sentencias que existan en el
cuerpo de los procedimientos. En conclusion la complejidad de un procedimiento tiende a
complicarse si se trata de procedimientos recursivos.
Ej. Funcion factorial (no recursividad)
int factorial(int n) //sentencia Entrada (1)
{
int fact = 1; //sentencia asignacion O(1)
for(int i = n; i>0; i--) //ciclo contador explicito O(1)
fact = fact * i; //sentencia de asignacion O(1)
return fact; //sentencia salida O(1)
}
entonces: Complejidad Lineal O(n)
por el ciclo for con numero de interacciones igualan a n.
Programa 9.
Crear clase factorial, recibira n, en el programa principal se pide n.
Factorial (no recursivo)
Ordenes de complejidad
O(1) Constante Ideal
O(n) Lineal Eficiente
O(log n) Logarítmico //
O(nlogn) Casi Lineal //
O(n^k) Polinimica Tratable
O(k^n) Exponencial Intratable
O(n!) Factorial Intratable
Como se mide el tiempo de ejecución de un programa en funcion de N (numero de datos)?
Esta función se puede medir físicamente calculando con un reloj o se puede calcular sobre el código contando las instrucciones ejecutadas a ejecutar y multiplicándolo por el tiempo requerido
por cada instrucción.
Ejemplo:
S1;
for(int i=0;i
S2;
entonces: T(n) = t1 + t2 * N
En este ejemplo siendo T1 el tiempo que lleve ejecutar la sentencia de S1 y t2 el tiempo que lleve ejectuar la 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 la sentencia de asignacion ,entrada o salida de datos siempre y cuando no trabajen sobre estructuras cuyo tamaño esta relacionado con N que es el numero de datos.
Como requiere un tiempo constante de ejecucion 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 tomandose en cuenta el orden mas alto
3.- Decision (if):
La condicion puede ser de orden constante o uno, sumando en la peor rama posible ya sea la del then o del else.
4.- Bucles(ciclos):
En los ciclos con contador explicito existen 2 casos: el tamaño N forma parte de los limites del ciclo o no.
Ejemplos:
caso 1: for(int i=0;i
{S1;}
entonces k*0(1)= 0(1) Constante
caso 2: for(int i=0;i
{S1;}
entonces N*O(1) = 0(n) Linear
b) Evolucion de variable de control No lineal (while)
En los ciclos multiplicativos como el while y 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
while (c
{
S1;
c=2*c;
entonces complejidad 0(log n)
logaritmica
Ej.
c=n;
while (c
{
S1;
c=c/2;
}
Complejidad Logaritmica 0(log n)
La complejidad de llamar a un procedimiento esta dada por la complejidad del procedimiento en si
es decir, su complejidad depende del tipo de instrucciones o sentencias que existan en el
cuerpo de los procedimientos. En conclusion la complejidad de un procedimiento tiende a
complicarse si se trata de procedimientos recursivos.
Ej. Funcion factorial (no recursividad)
{
int fact = 1; //sentencia asignacion O(1)
for(int i = n; i>0; i--) //ciclo contador explicito O(1)
fact = fact * i; //sentencia de asignacion O(1)
return fact; //sentencia salida O(1)
}
por el ciclo for con numero de interacciones igualan a n.
Crear clase factorial, recibira n, en el programa principal se pide n.
Factorial (no recursivo)
O(n) Lineal Eficiente
O(log n) Logarítmico //
O(nlogn) Casi Lineal //
O(n^k) Polinimica Tratable
O(k^n) Exponencial Intratable
O(n!) Factorial Intratable
sábado, 6 de septiembre de 2008
Notacion Omega Grande
Sean 2 funciones f(n) y g(n) de Z+ --> R+. Se dice que f(n) es omega grande de g(n) si existen las constantes positivas c y no tales que f(n) >= cg(n) ara todo n>=n0.
Para cualquier de las 2 funciones f(n) y g(n) definidas anteriormente se tiene que f(n)=Omega grande (g(n)) si y solo si g(n)=O(f(n)).
Da una cota inferior de la forma en que crece el tiempo de ejecucion.
Definicion:
Dada una función
llamamos omega de f al conjunto de todas las funciones de 
en 
acotadas inferiormente por un multiplo real positivo de f para valores de n suficientemente grandes.
Se denota
y sera:
Para cualquier de las 2 funciones f(n) y g(n) definidas anteriormente se tiene que f(n)=Omega grande (g(n)) si y solo si g(n)=O(f(n)).
Da una cota inferior de la forma en que crece el tiempo de ejecucion.
Definicion:
Dada una función
llamamos omega de f al conjunto de todas las funciones de en acotadas inferiormente por un multiplo real positivo de f para valores de n suficientemente grandes.Se denota
y sera:
viernes, 5 de septiembre de 2008
1.2 Aritmetica
Notación asintotica "O" grande
Se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una funcion. La utilidad de aplicar esta anotación a un algoritmo es encontrar el limite superior del tiempo de ejecucion,es decir el peor caso.
Definicion
g(n)1<=|cf(n)|. para todo n>=n
Esto significa que la funcion g(n) pertenece o es valida para f(n) si y solo si existen las constantes c y no tales que para n mayor a
Se cumple esta relación.
El orden de magnitud de la fucion sera el orden del termino de la función mas grande respecto de n.
Ejemplo 1:
Supongase que
cuando 
y 
para 
.
Verifique la funcion utilizando la O.
, 
Se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una funcion. La utilidad de aplicar esta anotación a un algoritmo es encontrar el limite superior del tiempo de ejecucion,es decir el peor caso.
Definicion
g(n)1<=|cf(n)|. para todo n>=n
Esto significa que la funcion g(n) pertenece o es valida para f(n) si y solo si existen las constantes c y no tales que para n mayor a
Se cumple esta relación.
El orden de magnitud de la fucion sera el orden del termino de la función mas grande respecto de n.
Ejemplo 1:
Supongase que
cuando y para .Verifique la funcion utilizando la O.
,
Unidad I.- Analisis de Algoritmos
1.1 Concepto de Complejidad Computacional
Teoría de la Complejidad Computacional
Es la parte de la teoría de la computación que estudia los recursos necesarios durante el calculo para resolver un problema.
Estos recursos son el tiempo y el espacio.
Clases de Complejidad
Los problemas de desicion (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
b) Clase de complejidad NP
c) Clase de complejidad NP-Completo
Clase de complejidad P:
Es el conjunto de los problemas de desicion que pueden ser resueltos en tiempo polinomio por una maquina de Turing, lo que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos.
Clase de complejidad NP:
Es el conjunto de los problemas de desicion que pueden ser resueltos para una maquina de Turing no determinista en tiempo polinomio. Los problemas de esta clase tiene la propiedad de que su solución puede ser verificada.
Clase de complejidad NP-Completo
Es el subconjunto de los problemas de desicion de NP que se destacan por su extrema complejidad en la cueal algunos de ellos en la actualidad no han encontrado una respuesta satisfactoria.
-Diagrama de la relacion entre las clases de complejidad
Teoría de la Complejidad Computacional
Es la parte de la teoría de la computación que estudia los recursos necesarios durante el calculo para resolver un problema.
Estos recursos son el tiempo y el espacio.
Clases de Complejidad
Los problemas de desicion (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
b) Clase de complejidad NP
c) Clase de complejidad NP-Completo
Clase de complejidad P:
Es el conjunto de los problemas de desicion que pueden ser resueltos en tiempo polinomio por una maquina de Turing, lo que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos.
Clase de complejidad NP:
Es el conjunto de los problemas de desicion que pueden ser resueltos para una maquina de Turing no determinista en tiempo polinomio. Los problemas de esta clase tiene la propiedad de que su solución puede ser verificada.
Clase de complejidad NP-Completo
Es el subconjunto de los problemas de desicion de NP que se destacan por su extrema complejidad en la cueal algunos de ellos en la actualidad no han encontrado una respuesta satisfactoria.
-Diagrama de la relacion entre las clases de complejidad
Introduccion
Estructura de Datos
Serie 3W3A
M.C. Luz Elena Cortez Galvan
Temario:
Unidad I.- Análisis de Algoritmos
Unidad II.- Manejo de Memoria
Unidad III.- Estructuras Lineales Estáticas
Unidad IV.- Recursividad
Unidad V.- Estructuras No Lineales Estáticas y Dinámicas (Arboles)
Unidad VI.- Ordenación Interna
Unidad VII.- Ordenación Externa
Unidad VIII.- Métodos de Búsqueda
Evaluación
- 80% Examen
- 15% Programas
- 5% Asistencia/Participación
Bibliografia
*Libre: Cualquier libro de C# con temas de estructuras de datos, algoritmos de ordenamiento y de búsqueda.
Serie 3W3A
M.C. Luz Elena Cortez Galvan
Temario:
Unidad I.- Análisis de Algoritmos
Unidad II.- Manejo de Memoria
Unidad III.- Estructuras Lineales Estáticas
Unidad IV.- Recursividad
Unidad V.- Estructuras No Lineales Estáticas y Dinámicas (Arboles)
Unidad VI.- Ordenación Interna
Unidad VII.- Ordenación Externa
Unidad VIII.- Métodos de Búsqueda
Evaluación
- 80% Examen
- 15% Programas
- 5% Asistencia/Participación
Bibliografia
*Libre: Cualquier libro de C# con temas de estructuras de datos, algoritmos de ordenamiento y de búsqueda.
Suscribirse a:
Comentarios (Atom)
