2.1.1-Manejo de memoria estática

La memoria estática es la que se reserva en el momento de la compilación antes de comenzar a ejecutarse el programa.
Los objetos son credos en ese momento y destruidos al finalizar el programa.
Mantiene la misma localización la memoria durante todo el transcurso de programa.
Los objetos administrados de este modo son:
-variables static
-variables globales
-miembros static de clase
-literales de cualquier tipo
Ejemplo:
En el ejemplo uno se muestra la declaración estática de un arreglo y la declaración de la variable global dentro del for.
En el ejemplo dos se muestra la declaración estática de una función la cual es ejecutada ala enviarle dos parámetro que son literales numéricas.
En resumen el inconveniente de usar estática aunque es más fácil de programar es que la cantidad de memoria se reserva siempre antes de conocer los datos concretos del problema lo que a veces lleva a reservar un máximo de memoria que en la memoria de las veces no se va a necesitar.

1.4- seleccion de un algoritmo
cuando se resuelve un problema y hay la nesesidad de elejir entre varios algoritmos
que nos puedan dar un resultado existen dos objetios que suelen contradesir se para
elejir uno
a)que el algoritmo seafaslde entender , codificar y depurar
b)que el algoritmo use eficientrementelos recursos del computadora y se ejecuten
con mayorr rapides posible

el primer punto se deve elejir cuando se escribe un programa que se vaa utilizar
una o pocas veses ya que el costo del tiempo de programacion no sera tan selevante
ya que solo se ejecutara en pocas ocasiones.
el punto b es masinportante coando se presenta un problema cutya solucion se va
autilizar mucha vese ya que elcostode ejecucion del prigrma nimisara el costo de
escritura.
en conclucion siempre saramas ventajodo del punto de vista economico realisar un
algoritmo complejo siempre y cuando el tiempo de ejecucion del rpogram resulte
significativa mente menor

1.3.2-comlejidasd en el espacio
*complejidad espacia?
esla menoria ue utiliza un programa para su ejecucion lo que inplica que la
eficiencia de memoria de un algoritmo lo indicala cantidad de espacio requerido
par ejecutarloes desir en elpacio en memoria que ocupan todas las variables propias
del algoritmo.
ejemplo
goritmo de busque de arboles
funcioj busuqeda_arbol(problema)
devueleve solucion/fallo
inicializa arbol de busuqeda con estado inicial
ciclo hacer
si no hay candidados para expadir
entonces devolver fallo
en otro caso escoger noda para expandir
si el nodo es el objeto
enonces devolber solucion
en otro caso expandir nodo

=resultados obtenidos=
depth nodes time memory
0 1 1milisecond 100 bytes
2 111 .1 seconds 11 kilobytes
4 11111 11 seconds 1 megabytes
6 10^6 18 miutes 111 megabytes
8 10^8 31 houres 11 gigabytes
10 10^0 128 days 1 terabytes
12 10^12 35 years 111terabytes

notas factor de ramificacion ->10 nodos sucesores p/cada uno como maximo
profundidad del arbol->infinito

1.4seleccion de un algoritmo
?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 fisicsamente calulandola con un reloj o se puede calcular con el codigo contando las intrucciones a ejecutar y multiplicandoli por el tiempo requerido por cada intruccion.

ejemplo:

s1;

for(int i=0;i

s2;

entonces:

t(n)=t1+t2*2

en este ejemplo siento t1 el tiempo que yeve el ejecutar lacentencia s1 y t2 el tiepo que lleve ejecutar la sentencia 2 un numero n de veses dentro del siclo for.

=reglas practicas para calcular la omplejidad de un algoritmo=

1.-sentencia sencilla:se refiere alas sentencia de asigacion mostrada en la asalida de datos simpre yc cunado no trnaaje sobre estructuras cullo tamano esta relacionado con N. como requiere un tiempo constante de ejecucion su complejidad es del orden 1

2.-secuencia de sentencia: su complejidad esta dada por la suma de las complejidades individuales de acuerdo al tipo de sentencias tomandose en cuneta el orden mas alto.

3.-decision (if): la cindicion suele ser de orden constante O(1), sumando en la peor rama posible ya sea d la del then o l a del else

4.-bucles(ciclos): en los cilcos con contaddor explisito existen dos casos el tamana N forme parte de los limites del ciclo o no.ejemplo:

caso 1 for(int i=0;i

{s1;}

entonsesk*O(1)=O(1) constante

caso 2 for(int i=0;i

{s1;}

entonses  N*O(1)=O(1) lineal

no lineal(while)

en los cickos multiplicatios com el whiley el do while el inremento de la variable control no es nineal no que ase incrementar el orden de complejidad como en los ejemplos siguientes.

ejemplo:

c=1;

while(c

{

s1;

c=2*c;

}

entonses complejidad o(log N)

logaritmico

c=N;

while(c>1)

{

S1;

C=C/2;

}

COMPLEJIDAD LOG(log n)

5.-llamdas de procedimientos: la complejidad e llamar a un prosedoimiento esta dada por la cmplejidad del contididdo del proisedimeinto  en si , es desir su complejidad depende del tipo de intrucciones o sentencias que existan en el cuerpo del prodedimiento. en clonclucion la comliejidad dein prosedimineto tiende a complidarse si se trata de prosediminetos recursibos.

===========

=progrma#9=

===========

ej.funcion factorial(no recursiva)

int factorial(int n)//sentencia entrada O(1)

{

int fact=1;//sentencia asinacion O(1)

for(int i=n;i>0;i--)//ciclo contador explicita O(n)

fact=fact*1;//sentencia asignacion O(1)

return fact;//sentencia salida O(1)

}

entonces:complejidad linealO(n)por el ciclo for con numeros de interaccion igual a n.

ordenes de complejidad

O(1)constante           idela

O(n)lineal              eficente

O(log n)logaritmico     eficente

O(n log n)casi lineal   eficente

O(n*)polinomial         tratable

o(K^n)exponencial       intratables

o(n!)factorial          intratables

=NOTACIOJN ASINTOTICA"OMEGA" GRANE=

LA FUNCION OMEGA GRANDE ITILIZA SE UTILIZA PARA EXPLICAR UNA COTA INFERIOR PARA LA VELOSIDAD DEL   DE UNA FUNCION F(N) CUIANDO ESTA EN FUNCION DE N UNA LA DENOTACION T(N) ES OMEGA GRANDE (G(N)) Y SIGNIFICA QUE EXISTE  UAN ACONSTANTE C TAN Y QUE T)N(=>C)(G(N))PARFA UN NUMEO INFINITO PARA VALORES DE N.

EJEMPLO

VERIFICAR LA FUNCION:

PROGRAMA#6

T(N)=N^3+2N^2, C=1  PARA N>=0

N^3+2N^2>=CN^3

(1) (1)^3+2(1)^2>=1(1)^3

1+2>=1 

3>=1

P-7

T(N)=N^2/100>=1/100N^2

PARA N>=0 PaR

Y C=1/100

P-8

T(N)=N PARA N>=1 IMPAR

Y C=1

Temario

Unidad 1.- Análisis de algoritmos.

Unidad 2.-Manejo de memoria.

Unidad 3.-Estructura lineales estáticas y dinámicas (pilas, colas, listas).

Unidad 4.-recursividad.

Unidad 5.-Estructuras no lineales estáticas y dinámicas (árboles).

Unidad 6.-Ordenación interna (burbuja, shell, quicksort, radix).

Unidad 7.-Ordenación externa (intercalación simple, cuadrática marge).

Unidad 8.-Métodos de búsqueda (secuencial, binaria, hash).

 

Unidad 1 Análisis de algoritmos.

1.1  Concepto de 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 conjunto de complejidad comparable que son (llamados clases de complejidad).

 

a) Clase de complejidad P:

El conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinomico de una maquina de turning, lo que corresponde al problema que puede ser resuelto a aun en el peor de sus casos.

 

b) Clases de complejidad NP:

Es el conjunto de los problemas de decisión que pueden ser resueltos por una maquina de turning no determinista en tiempo polinomico la propiedad de que su solución puede ser verificada.

El problema de satisfacción booleana el programa es poco satisfactoria.

 

c) Clase de complejidad NP-completo:

Es le subconjunto de los problemas NP que se destacan por su extrema complejidad en la cual algunos de ellos en la actualidad no han encintrado una solución satisfactoria.

La suma de subconjuntos dado un conjunto S de enteros ¿existe un subconjunto no vació cuyo electos sumen 0?dos grafos son isomorfos.

 

Diagrama de la relación entre las clases de complejidad

Problemas de decisión

 

Presenta à¿las clases p y NP son diferentas o no?

 

1.2aritmetica de la notación 0.

Notación asitotica “O” grande

Se utiliza para hacer referencia a la velocidad de seguimiento de los valores de una función. La habilidad de anotar esta anotación a en algoritmo es encontrar el limite superior del tiempo de ejecución, es decir el peor caso.

=Definición=

1g(n)1<=1c.f(n), para todo n>=n.

Esto significa que la función g(n) pertenece o es valida para f(n) si solo si existen las constantes c no tales que para N>=n. T(n)<=cn el orden de la magnitud de la función será el orden del termino de la función mas grande de n.

Ejemplo 1: T(n)=(n+1)2, n=1 y c+4,n>=1;

 

Programa #3

(n+1)2<=cn2

 

Programa #4

T(n)=3n3+2n2 cuando n=0,c=58para n>=0;

 

Programa #5

T(n)n4+100n2+10n+10 cuando n=0,c=50 para n>=0;

 

Estructura De Datos

Introduccion a la materia