UNIVERSIDAD DEL NORTE

DIVISIÓN DE INGENIERÍA
PROGRAMA DE INGENIERÍA DE SISTEMAS Y COMPUTACIÓN
ALGORITMOS Y COMPLEJIDAD
CÓDIGO:_200129906
NOMBRE: Pedro Otero Serrano
FECHA : ____/____/____/
GRUPO NRC:7543

Práctica No. ____

Resolución de las Prácticas de Computadores, Complejidad e Intratabilidad.

Clasificar los siguientes problemas según su naturaleza.

No  N , N Op. B. U. M. E.D. OC
.
1 n! / n  Z+ N * n Variable O(n)
2 Ordenar una lista de K números N, N Comp. K lista O(n2)
3 MCD(n,m) / (n,m)  Z+ N / Max(n,m Variable
)
4 Search (x) en lista lineal de k nodos de N, N Busqued k Lista
longitud L a
i=k
5 N + k Matriz
SMC=∑ (M ¿ ¿ i ❑ ¿ )¿ ¿
i=1
Con Mi de dimensión [nxn]
No  N , N Op. B. U. M. E.D. OC
.

N= Numérico , N=No Numérico

Op. B. = Operación Básica
U.M. = Unidad de Medida
E.D. = Esctructura de Datos
O.C. = Orden de Complejidad
 1. Diseñar la función de tiempo de corrida (Running Time) del siguiente segmento de
programa, en función del número de datos de entrada, teniendo en cuenta que cada
instrucción (Sti) consume ti unidades de tiempo.

Proc: Genérico1
St1
St2 // Lee el valor de n
Para i=1,n,1 haga
St3
St4
St5
Fin_para
St6
St7
Fin_proc

R/ Sea T (n)el tiempo de demora del algoritmo en función del número de datos de entrada n .

T ( n )=t 1+t 2 +¿

i=n
T ( n )=t 1+t 2 +(t 3 +t 4 +t 5) ∑ ( 1 ) ¿ ¿+ t 6 +t 7
i=1

T ( n )=t 1+t 2 + ( t 3+ t 4 + t 5 )∗n+t 6 +t 7

Si cada t i consume una unidad de tiempo, entonces el tiempo del algoritmo es

T ( n )=3 n+ 4 ≅ O(n)

Escriba el tipo de problema según el orden de complejidad

(P=Polinomial, E = Exponencial ).

2. Construir la función de tiempo de corrida (Running Time) del siguiente segmento de

programa, en función del número de datos de entrada, teniendo en cuenta que cada
instrucción (Sti) consume una unidad de tiempo y la proposición tres se cambia según se
muestra en el texto del algoritmo.

Proc: Genérico2
St1 // Lee el valor de n
St2 // Lee el valor de m
Para i=1,n,1 haga
Para j=1,m,1 haga
St4
St5
Fin_para
Fin_para
St6
St7
Fin_proc

R/, Sea T ( n . m ) el tiempo de corrida de Genérico 2.

T ( n , m )=t 1 +t 2 +¿

T ( n , m )=t 1 +t 2 +¿

T ( n , m )=t 1 +t 2 +¿

T ( n , m )=t 1 +t 2 +¿

T ( n , m )=t 1 +t 2 + ( t 4 +t 5 )∗m∗n+t 6 +t 7

T ( n , m )=1+1+ ( 1+1 )∗m∗n+1+1

T ( n , m )=2∗n∗m+ 4 ≅O(nm)

3. Construir la función de tiempo de corrida (Running Time) del siguiente segmento de

programa, en función del número de datos de entrada, teniendo en cuenta que cada
instrucción (Sti) consume una unidad de tiempo y la proposición tres se cambia según se
muestra en el texto del algoritmo.

Proc: Genérico3
St1 // Lee el valor de n
St2
Para i=1,n,1 haga
Para j=1,i,1 haga
St4
St5
Fin_para
Fin_para
St6
St7
Fin_proc

R/. Sea T ( n ) el tiempo de corrida de Genérico 3.

T ( n )=t 1+t 2 +¿

T ( n )=t 1+t 2 +¿
T ( n )=t 1+t 2 +¿

T ( n )=t 1+t 2 +¿

i=n
n (n+1)
∑ i= 2
i=1

T ( n )=t 1+t 2 +¿

T ( n )=2+n2 +n+ 2

T ( n )=n2 +n+ 4 ≅O( n2)

 4. Diseñar la función de tiempo del siguiente segmento de algoritmo, que busca el elemento x
en una vector L[1..n] elementos, suponiendo que elemento x se encuentra en el arreglo.

Search(L,n,x)
i←1
Mq(x < > L(i) and in) haga
i←i+1
Fin_Mq
Si (x=L(i)) entonces
Devolver i
Si_no
Devolver 0
Fin_si
Fin_Search

Nota: El algoritmo no es determinístico sino probabilístico. Luego, se debe calcular el

comportamiento promedio (p)

Sea T qp (n) , el tiempo promedio de demora del algoritmo en función del número de datos de
entrada n y una probabilidad q.

Se definen dos instancias de comportamiento del algoritmo que son:

Ii = Caso en el que x está la i_ésima posición, o sea x  L

In+1= Caso en el cual el cual x  L

El tiempo de demora de las dos instancias es:

t(Ii) = i , para 1 ≤ i ≤ n , o x  L

t(In+1) = n , o cuando x  L

Sea q la probabilidad de que x  L, entonces

p(Ii) = q/n , si x  L
p(In+1) = 1-q , si x  L , Luego..

T qp ( n )= p ( I i )∗t (I i) + p ( I n+1 )∗t ( I n+1)

i=n
q
T qp ( n )=∑ ( )∗i + ( 1−q )∗n
i=1 n

i=n
q q
T ( n )=( ) ∑ i + ( 1−q )∗n
p
n i=1

q
q
T ( n )=
( n)
∗n∗( n+1 )
+ ( 1−q )∗n
p
2

q n+1
Si la llave x se encuentra en el arreglo L entonces q=1. Luego T p ( n )=
2
 5. Dado el siguiente texto algorítmico, diseñar la función de tiempo T(¿?) del algoritmo en
función del número de datos de entrada considerando que la instrucción Si consume una
unidad de tiempo, y calcular el tiempo cuando el valor de n = 100 .

Proc __________ ( A,n ) // A es un arreglo de n elemento

Para j = n hasta 2 con incrementos de -1 haga
Corrimiento (A,j)
fin_para_j
Fin_pro;

Proc Corrimiento (A,j )

Para i = 1 hasta j-1 haga
Si A(i) < A(i+1) entonces // O(1)
temp  A(i)
A(i)  A(i+1)
A(i+1)  temp
fin_si
fin_para_i
fin_proc_corrimiento;

Sea T(n) el tiempo de demora del procedimiento.

j=n
T ( n )=∑ t c , donde t c es el tiempo del procedimiento corrimiento
j=2

i= j−1
t c= ∑ 1= j−1
i=1

j=n
T ( n )=∑ j−1 , cambiando de variable si j=k +1 k= j−1
j=2

k=n−1
T ( n )= ∑ k , cuando j=2 k=1 ; y cuando j=n k=n−1
k=1

Recordando que:
i=n
n∗( n+1)
∑ i= 2
i=1

( n−1 )∗(n−1+1) n∗(n−1) n 2 n

T ( n )= = = −
2 2 2 2

Luego T ( n ) O(n2 )
 6. Si el tiempo de ejecución de un programa en función del número de datos de entrada es
igual a T ( n )=100∗n . Resolver las siguientes preguntas: i) Si se dispone de un tiempo de 1
hora qué tamaño de problema se puede resolver. ii) Suponga que el tiempo se dispone es de
1000 Seg, qué tamaño de problema se puede resolver?.

R/. i) Al disponer un tiempo de 1 hora, entonces:

T ( n )=100∗n=3600 , luego el tamaño de problema está dado por:

3600
n= =36
100

ii) Como se dispone de un tiempo igual a 1000 segundos, entonces:

T ( n )=100∗n=1000 , luego el tamaño de problema que se puede resolver es:

1000
T ( n )= =10
100

7. Diseñar la función de tiempo T(¿?) y concluya el orden de complejidad de la siguiente

función:
Potencia(n)
i0 // i, n son definidos como enteros
Mq (n%2 = 0) haga //% Es la función módulo dos.
nn/2
ii+1
Fin_Mq
Retorne i
Fin
R/.

 Si n es impar  el número no es potencia de dos. No cuenta su número de potencias

T(n)=1+1=2.Luego T(n) ≅ O(k) , siendo k una constante.
 Si n es par entonces es potencia de dos ( 23 = 8 ) . Sea m el número de potencias de dos o sea

2m =n m=log 2 ( n ) , Luego T ( n )=2+ log 2 ( n ) ≅ log 2 ( n )

 8. Demostrar la regla de la multiplicación de funciones asintóticas: T1(n) * T2(n) es O(f(n)
* g(n))

R/. Dadas las constantes c1, c2, c3 , n1 y n2,

Si n  n1, entonces T1(n)  c1*f(n), y si n  n2 , entonces T2(n)  c2*g(n). Sea n0 = máx (n1, n2).

Si n  n0, T1(n) * T2(n)  c1*f(n)* c2*g(n)  c3* (f(n)*g(n)), siendo c3  0 y c3 = c1 * c2.

Luego, aplicando la regla de la constante:

T1(n) * T2(n)  O(f(n)*g(n)); por lo tanto: T1(n)*T2(n) es O(f(n) * g(n)).

b) Demostrar matemáticamente la regla de la constante de funciones asintóticas

R/ c* f(n) es 0* (f(n))
 9. Diligenciar la siguiente tabla identificando la clase de complejidad asociada a cada problema ..


P=Polinomial Alg. Det y O(P(n)) Proc: Sea T(n) el tiempo de de
Lea n
Para i=1,n,1
Para j=1,n,1 haga T ( n )=O (1 )+O ( n 2) +O( n)
A(i,j)0
Fin_para Luego T ( n ) ≅ O( n2)
Fin_para
Para i=1,n,1 haga
A(i,i)1
Fin_para
Fin_proc
E=Exponencia Alg con T(n) es Fib(n) Es un algoritmo tipo
l determinístico Si (n=1)o(n=0) entonces
Num_Fibn Luego T ≅ 1,6 n
O(a n ¿ a> 1 Si_no
Num_FinFib(n-2)+Fib(n-1)
Fin_si
Fin_función_Fib
NP Alg. No determinístico Search(L,n,x) Es un Alg
(Probabilístico) i←1
y Mq(x < > L(i) and in) haga q n+1
Luego T p ( n )=
O(P(n)) i←i+1 2
Fin_Mq
Si (x=L(i)) entonces
Devolver i
Si_no
Devolver 0
Fin_si
Fin_Search

T=Tratables Sol, eficiente en tiempo Asignador de llaves de longitud L Luego T Hash =O()
y espacio no repetidas en una función de
Hash
I=Intratables Sol. impráctica Función Exposec(a,n)
En tiempo y espacio // Para números (a) > de 1´ billón
ra
Para i=1,n-1,1 haga
ra*r
Fin_para
Devolver r
Fin_Exposec
NP_C No se han encontrado VP(n) N=19
NP_H Alg., polinomiales para Dado un entero positivo n decidir N=81
su solución pero no se si n es o no primo
han demostrado que no
existen
U=Undecible No existen algoritmos Traductor de lenguajes y dialectos
para solucionarlos multilingües escrito y hablado
100%
10. Colocar una imagen del GSI, en el cual se muestre completamente: Código, Nombre del
alumno, fecha, y los resultados paso a paso generados por el GSI.

ES