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;