ALGORITMOS 2
DIGITALES II
Ing. Hugo Fdo. Velasco Peña
Universidad Nacional
© 2006
OBJETIVOS

Conocer los principios de evaluación de
costos en algoritmos iterativos y
recursivos.
Ejemplo 1

En algún lugar de la cinta se pueden
encontrar dos o mas letras “a” seguidas.
Copiar una “b” a continuación de la última
“a”
λaaaλ → λaaabλ
Ejemplo 1: Solución 1

 1

a
a
 1
a 1
a 1
a
a 1

b 1

No hay un estado final
Ejemplo 1: Solución 2

 1

 1
b
a
b
a 1
b 1
b 1
?
a
a 1
a

a 1
b 1
Ejemplo 1: Solución 2
Supone que pueden haber caracteres “b”
en la cadena.
 Supone que después de una “a” sola
puede haber una “b”.

Ejemplo 1: Solución 3

 1
b
a
b
a 1
b 1
b 1
b
a

b 1
a 1
b 1
a
a 1
Ejemplo 2

Copiar todas las “a” de la memoria a
continuación de las “b”
λλλλaaaλλλbbbbbλλλλλ→λλλλλλλbbbbbaaaλλλ
Ejemplo 2: Solución
COSTOS

En la maquina de Turing, y en general para
cualquier algoritmo, los costos se pueden medir
de la siguiente forma:
 Costo
de tiempo
 Costo de espacio
COSTO DE TIEMPO

Es la cantidad de transiciones cambios de
estado que realiza la maquina, contando
también aquellas transiciones que parten
de un estado y vuelven al mismo.
Por ejemplo nuestro programa para la
máquina de Turing del ejemplo 1 Para el
caso λaaaaλ insume 5 transiciones y la
cinta queda de la forma λaaaabλ
COSTO DE ESPACIO

Se puede medir como la cantidad de estados
del programa.
Cada estado en la maquina de Turing
representa una cierta memoria por lo que medir
la cantidad de estados es una buena forma de
medir el costo espacial.
Nuestro primer algoritmo para la maquina de
Turing tiene 4 estados.
EFICIENCIA DE UN ALGORITMO

En la maquina de Turing el análisis de la
eficiencia de un algoritmo pasa por
averiguar si no existe un programa que
pueda resolver el mismo problema en
forma mas rápida empleando menos
transiciones o bien utilizando menos
espacio menor cantidad de estados.
EFICIENCIA DE UN ALGORITMO

Desarrolle un algoritmo para cambiar una
bombilla.
OTROS MODELOS
COMPUTACIONALES

La maquina de Turing es un modelo poco
practico ya que al ser demasiado abstracta
programar resulta extremadamente complejo.

Además no es una buena referencia para la
obtención de programas reales ya que un
programa hecho para la maquina de Turing no
tiene relación alguna con un programa realizado
en un lenguaje de propósito general.

Es por esto que destacando la nobleza de la
maquina de Turing pasamos a otros modelos un
tanto mas cercanos a la realidad.
MÁQUINA RAM DE COSTO FIJO

La máquina RAM proviene de Random Access
Memory.

Es una maquina ideal muy similar a una
computadora actual aunque con algunas
simplicaciones.

Los programas de la maquina RAM se
almacenan en memoria (en la maquina de
Turing los programas no se almacenan, por lo
menos no en la cinta) .
MÁQUINA RAM DE COSTO FIJO

Puede suponerse que todos los accesos a memoria
tienen el mismo costo en tiempo y que todas las
instrucciones tienen un costo constante e idéntico
en tiempo.

El set de instrucciones de la máquina RAM está
compuesto por la gran mayoría de las instrucciones
que podemos encontrar en un lenguaje de alto
nivel.

Un programa para la maquina RAM se escribe en
un pseudocodigo especial en el cual vamos a
adoptar algunas convenciones básicas.
Las llaves solo son necesarias si su
ausencia afecta la claridad del código.
 Los pasajes de parámetros a una función
se hacen por valor.
 El acceso a un elemento de un arreglo
cuesta lo mismo que el acceso a una
variable

Algoritmo 1
y←1
A[2] ← 1
if n < 1 then
X←w
else
X←y
end if
while n ≥ 0 do
n ← n -1
end while
ciclo for
for i = 0 to 10 do
A[i] ← 0
end for
Algoritmo 2
a←3
b←a*5
if b == 5 then
a←2
else
a←1
end if

El algoritmo 2 tiene 5 instrucciones de las cuales
se ejecutan unicamente 4. Por lo tanto el costo
del programa en tiempo es de 4*C, siendo C
una constante que indica cuanto tiempo tarda
en ejecutarse una instrucción.

El espacio que necesita el programa es el
espacio ocupado por las variables A y B. Es
decir 2 * Ec, siendo Ec el espacio que ocupa
una variable

La máquina RAM de costo fijo es mucho
más realista que la máquina de Turing ya
que puede verse, claramente, que a partir
de un algoritmo escrito para la máquina
RAM podemos desarrollar un algoritmo
escrito en C, Pascal u otro lenguaje para
una computadora actual.

Este acercamiento a la realidad en el código de
la maquina RAM no se evidencia en cuanto al
costo ya que el modelo planteado en el cual
todas las instrucciones tienen un costo fijo no es
real ya que hay algunas instrucciones que son
claramente mas costosas que otras por ejemplo
una multiplicación insume mas tiempo que una
suma en cualquier computadora
MÁQUINA RAM DE COSTO
VARIABLE

En la máquina RAM de costo variable
cada instrucción Ii tiene asociado un costo
Ci que le es propio y que depende del
costo de implementar dicha instrucción.

Para el Algoritmo 2 en una máquina de costo
variable el costo será
3*C1 + 1*C2+ 1*C3
donde
C1 costo de una asignación
C2 costo de una multiplicación
C3 costo de comparar dos números

El costo del espacio en la máquina RAM
de costo variable es igual al de la máquina
RAM de costo fijo.

Claramente observamos que pese a ganar
claridad en cuanto a la escritura de
programas perdemos precisión y se hace
más complejo el calculo de costos

Potencia1(x,y)
Calcula xy
Require: x > 0
if y == 0 then
return 1
else
result ← x
for i = 0 to y – 1 do
result ← result * x
end for
end if
return result

¿Cuánto cuesta el algoritmo en tiempo?
La comparación del if se ejecuta siempre y
supongamos que y no es cero lo cual va a pasar
la mayoría de las veces. Se ejecuta una
asignación y luego y - 1 veces una
multiplicación.
T = C1 + C2 + (y-1)(C3 + C1)
C1: costo de comparar dos números
C2: costo de realizar una asignación
C3: costo de realizar una multiplicación

Por ejemplo si queremos hacer 28 el
algoritmo calcula
28 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

Pero se podría hacer
A = 2 * 2(22)
B = A * A(24)
C = B * B(28)
con lo cual en lugar de multiplicaciones se
utilizan solamente tres. Por lo tanto podría
haber un algoritmo más eficiente.

Potencia2(x,y)
Calcula xy
Require: x > 0
if y == 0 then
return 1
else
r←1
if y >1 then
r ← Potencia2(x,y/2)
r←r*r
end if
if y mod 2 == 1 then
r←r*x
end if
return result
1
2
3
r1 = 1
7>1
r1 = potencia2(2,3)
r2 = 1
3>1
r2 = potencia2(2,1)
r3 = 1
y=1
y%2=1
r3 = 1 * 2
1
2
3
return 2
r2 = 2 * 2
y%2=1
r2 = 4 * 2
return 8
r=8*8
y%2=1
r = 64 * 2
return 128

Como podemos ver el algoritmo es
recursivo y en nuestro ejemplo para y = 7
realizo 5 multiplicaciones contra las seis
que haríamos en el algoritmo tradicional.

Para valores mas grandes de y la
diferencia entre el primer y el segundo
algoritmo se hace mucho más notoria.
ALGORITMOS ITERATIVOS

Los algoritmos iterativos son aquellos que se
basan en la ejecución de ciclos que pueden ser
de tipo for,while, repeat, etc. La gran mayoría de
los algoritmos tienen alguna parte iterativa y
muchos son puramente iterativos.

Analizar el costo en tiempo de estos algoritmos
implica entender cuantas veces se ejecuta cada
una de las instrucciones del algoritmo y cual es
el costo de cada una de las instrucciones
Ciclos simples
for i = 1 to n do
instrucción
end for

El calculo en costo de
un ciclo simple puede
hacerse utilizando
una sumatoria
n
C
i 1
 n C
Ciclos anidados independientes
for I = 1 to n do
for J = 3 to m do
Instrucción
end for
end for
n
m
n
  C   ( m  2 )C
i 1 j  3
i 1
 n ( m  2 )C
Ciclos anidados dependientes
n
m
n
for i = 1 to n do
  C   ( n  i  1)C
i 1
for j = i to n do i 1 j  i
n
n
n
Instrucción
 n

 C  ( n  i  1)  C   n   i   1 
end for
i 1
i 1
i 1 
 i 1
end for
n * ( n  1)


 C n * n 

2
 n 

 2n 2  n 2  n  2n 
n2  n 
 C
  C

2


 2 
SORT POR BURBUJEO

Uno de los algoritmos
de uso mas común es
el de ordenamiento.

Burbujeo(A,n)
Ordena el vector A
for i  to n  do
for j i  to n do
if Aj Ai then
SwapAiAj
end if
end for
end for

El costo del algoritmo lo vamos a calcular
suponiendo que C1 es el costo de efectuar la
comparacion y que C2 es el costo de efectuar el
SWAP.

Sin embargo el SWAP no se hace siempre sino
que se hace únicamente cuando la comparación
da A[j] > A[i] por ello debemos partir el análisis
en tres casos el peor caso, el mejor caso y el
caso medio.
Peor caso

En el peor caso el algoritmo siempre hace
el Swap. Esto ocurre cuando el vector
viene ordenado en el orden inverso al que
utilizamos

Por ejemplo para n = 8 el peor caso nos
da (C1 + C2)(32-12+1)=21(C1 + C2), un
total de 21 Comparaciones y 21 Swaps
Mejor caso

En el mejor caso el vector ya viene
ordenado por lo que nunca efectúa ningún
swap el costo total es entonces el costo
de las comparaciones que es igual a lo
calculado antes.
Caso medio

En el caso medio el algoritmo efectúa
todas las Comparaciones y solo la mitad
de los Swaps
ORDEN DE UN ALGORITMO

El análisis de los algoritmos realizado es muy
preciso pero resulta incomodo para entender
que tan eficiente es un algoritmo o para poder
compararlo contra otro algoritmo.

Habitualmente no interesa cuanto tarda
exactamente un algoritmo sino que nos interesa
saber cual es la tasa de crecimiento del
algoritmo en función de los datos de entrada.
ORDEN DE UN ALGORITMO

DEFINICIÓN
Tasa de crecimiento del tiempo que
insume el algoritmo en función de la
cantidad o tamaño de los datos de entrada
COTAS DE COMPLEJIDAD.
MEDIDAS ASINTÓTICAS.
NOTACIÓN “O”

Para el estudio de algoritmos existe una
notación muy practica y utilizada universalmente
en este tipo de problemas conocida como la
gran “O” (Big-Oh notation) que define el orden
de un algoritmo.

Esta notación sirve para clasificar el crecimiento
de las funciones
O(g(n))

Sea una función f(n) decimos que f(n) pertenece
a la familia de funciones O(g(n)) si existe una
constante C1 y un numero n0 tales que
0 ≤ f(n) ≤ C1 * g(n) para n ≥ n0

Es decir que a partir de un cierto n la función f(n)
queda por debajo de la función g(n) multiplicada
por una constante

Sirve para acotar el peor caso de un algoritmo
Ω(g(n))

Sea una función f(n) decimos que f(n) pertenece
a la familia de funciones Ω (g(n)) si existe una
constante C1 y un numero n0 tales que
C1 * g(n) ≤ f(n) para n ≥ n0

Es decir que a partir de un cierto n la función f(n)
siempre es mayor que la función g(n)
multiplicada por una constante.

Sirve para acotar el mejor caso de un algoritmo.
Θ(g(n))

Sea una función f(n) decimos que f(n) pertenece
a la familia de funciones Θ(g(n)) si existen
constantes C1 y C2 y un número n0 tales que
C1 * g(n) ≤ f(n) ≤ C2 * g(n) para n ≥ n0

Es decir que a partir de un cierto n la función f(n)
queda atrapada entre C1 g(n) y C2 g(n)
Θ
O
Ω

Como un abuso de notación usaremos
f(n) = Ω(g(n))
f(n) = o(g(n))
f(n) = θ(g(n))
donde el signo igual debe leerse como
pertenece

O(f(n)) + O(g(n)) = O(f(n)) sii f(n) crece
más rápido que g(n)
Por ejemplo n2 + n = O(n2)

Aplicando esta notación a los algoritmos
estudiados podemos ver que el mejor caso del
burbujeo es Ω(n2). El peor caso es O(n2) por lo
tanto el algoritmo de burbujeo es Θ(n2). Es decir
que es un algoritmo de orden cuadrático.

El sort por inserción en cambio en el mejor caso
es Ω(n) y en el peor caso es O(n2). En el caso
medio el algoritmo es O(n2). Por lo que también
tenemos un algoritmo de orden cuadrático pero
que en el mejor de los casos es lineal.
Algunas funciones típicas ordenadas por
orden de crecimiento
√n < log n < n < n log(n) < nc < xn < n! < nn















1. Para cualquier función f se tiene que f Є O(f).
2. f Є O(g) O(f) ⊂ O(g).
3. O(f) = O(g) ⇔ f ∈O(g) y g ∈O(f).
4. Si f ∈O(g) y g ∈O(h) ⇒ f ∈O(h).
5. Si f ∈O(g) y f ∈O(h) ⇒ f ∈O(min(g,h)).
6. Regla de la suma: Si f1 ∈O(g) y f2 ∈O(h) ⇒ f1 + f2 ∈O(max(g,h)).
7. Regla del producto: Si f1 ∈O(g) y f2 ∈O(h) ⇒ f1·f2 ∈O(g·h).
8. Si existe
gn
lim f n
n→∞
= k, dependiendo de los valores que tome k obtenemos:
a) Si k ≠0 y k < ∞ entonces O(f) = O(g).
b) Si k = 0 entonces f ∈O(g), es decir, O(f) ⊂ O(g), pero sin embargo se
verifica que g ∉O(f).
Descargar

ALGORITMOS DIGITALES II - Universidad Nacional de …